【tyvj】刷题记录(1001~1099)(64/99)

1001:排序完按照题意做即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 int a[10001],k,n;
 7 int main(){
 8     scanf("%d%d",&n,&k);
 9     for (int i=1; i<=n; i++) scanf("%d",&a[i]);
10     sort(a+1,a+n+1);
11     int m=a[n-k+1]-a[k];
12     if (m<2&&m>=0) printf("NO");
13     else if (m>0){
14         if (m==2) printf("YES
");
15         else{
16             for (int i=2; i<=floor(sqrt(m)); i++)
17                 if (m%i==0){
18                     printf("NO
");
19                     printf("%d",m);
20                     return 0;
21                 }
22             printf("YES
");
23         }
24         printf("%d",m);
25         return 0;
26     }else printf("NO
%d",m);
27     return 0;
28 }
1001

1002：模拟，按题意完成即可。

 1 #include<cstdio> 
 2 #include<iostream> 
 3 #include<string> 
 4 using namespace std; 
 5 int qm,bj,lw,hv,ma,n,sum; 
 6 bool gb,wt; 
 7 string bb,cc; 
 8 int main(){ 
 9     cin>>n; 
10     for (int i=1; i<=n; i++){ 
11         hv=0; 
12         //cout<<i<<":"; 
13         cin>>bb; 
14         scanf("%d%d",&qm,&bj); 
15         getchar(); 
16         gb=getchar()=='Y'?1:0; 
17         getchar(); 
18         wt=getchar()=='Y'?1:0; 
19         scanf("%d",&lw); 
20         if (qm>80&&lw) hv+=8000; 
21         if (qm>85&&bj>80) hv+=4000; 
22         if (qm>90) hv+=2000; 
23         if (qm>85&&wt) hv+=1000; 
24         if (bj>80&&gb) hv+=850; 
25         if (hv>ma) { 
26             ma=hv; 
27             cc=bb; 
28         } 
29         sum+=hv; 
30         //cout<<hv<<":"<<i; 
31     } 
32     cout<<cc<<endl<<ma<<endl<<sum; 
33 }
1002

1003：模拟即可。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
int main(){
    int m,t,u,f,d,s=0,t1=0;
    char a[100001];
    scanf("%d %d %d %d %d",&m,&t,&u,&f,&d);
    for(int i=0;i<t;i++)
    scanf("%s",&a[i]);
    for(int i=0;i<t;i++){
            if(a[i]=='u'||a[i]=='d') s=s+u+d;
            else s=s+f*2;
            if(s>m) break;
            t1++;
            }
    cout<<t1<<endl;
    return 0;
}
1003

1004：用了奇技淫巧。。。正解应该是记忆化搜索，我的做法是排序后贪心一波。

 1 #include<cstdio> 
 2 #include<iostream> 
 3 #include<algorithm> 
 4 using namespace std; 
 5 struct fff{ 
 6     int x,y,n; 
 7 }a[10001]; 
 8 int f[101][101],b[101][101],n,m,ans; 
 9 int pd(const fff &a,const fff &b){ 
10     return a.n<b.n; 
11 } 
12 int main(){ 
13     cin>>n>>m; 
14     for (int i=1; i<=n; i++) 
15         for (int j=1; j<=m; j++){ 
16             scanf("%d",&b[i][j]); 
17             a[i*m-m+j].x=i;a[i*m-m+j].y=j;a[i*m-m+j].n=b[i][j]; 
18             f[i][j]=1; 
19         } 
20     sort(a+1,a+n*m+1,pd); 
21     for (int i=1; i<=n*m; i++){ 
22         int x=a[i].x,y=a[i].y; 
23         f[x+1][y]=((b[x+1][y]>a[i].n)&&(f[x+1][y]<f[x][y]+1))?f[x][y]+1:f[x+1][y]; 
24         f[x-1][y]=((b[x-1][y]>a[i].n)&&(f[x-1][y]<f[x][y]+1))?f[x][y]+1:f[x-1][y]; 
25         f[x][y+1]=((b[x][y+1]>a[i].n)&&(f[x][y+1]<f[x][y]+1))?f[x][y]+1:f[x][y+1]; 
26         f[x][y-1]=((b[x][y-1]>a[i].n)&&(f[x][y-1]<f[x][y]+1))?f[x][y]+1:f[x][y-1]; 
27     } 
28     for (int i=1; i<=n; i++) 
29         for (int j=1; j<=m; j++) 
30             ans=max(ans,f[i][j]); 
31     cout<<ans; 
32 }
1004

1005：裸01背包。。。。

 1 #include<cstdio> 
 2 #include<iostream> 
 3 using namespace std; 
 4 int f[1001],p[101],a[101],n,v; 
 5 int main(){ 
 6     cin>>v>>n; 
 7     for (int i=1; i<=n; i++) scanf("%d%d",&a[i],&p[i]); 
 8     for (int i=1; i<=n; i++) 
 9         for (int j=v; j>=a[i]; j--) 
10             f[j]=max(f[j],p[i]+f[j-a[i]]); 
11     cout<<f[v]; 
12 }
1005

1006：模拟。

#include<cstdio>
#include<iostream>
#define k(x,y) y*(a[x]-48)
using namespace std;
int main(){
    char a[14];
    gets(a);
    if ((k(0,1)+k(2,2)+k(3,3)+k(4,4)+k(6,5)+k(7,6)+k(8,7)+k(9,8)+k(10,9))%11==(a[12]=='X'?10:a[12]-48)) cout<<"Right";
        else{
            cout<<a[0]<<a[1]<<a[2]<<a[3]<<a[4]<<a[5]<<a[6]<<a[7]<<a[8]<<a[9]<<a[10]<<a[11];
            if ((k(0,1)+k(2,2)+k(3,3)+k(4,4)+k(6,5)+k(7,6)+k(8,7)+k(9,8)+k(10,9))%11==10) cout<<"X";
                else cout<<(k(0,1)+k(2,2)+k(3,3)+k(4,4)+k(6,5)+k(7,6)+k(8,7)+k(9,8)+k(10,9))%11;
        }
}
1006

1007：各种排序。。。然后就行了

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 int m,n,k,l,d,x,xx,yy,y;
 6 struct fff{
 7     int k,no;
 8 }anh[1001],anl[1001];
 9 int fuck(const fff &a,const fff &b){
10     return a.k>b.k;
11 }
12 int fuck233(const fff &a,const fff &b){
13     return a.no<b.no;
14 }
15 int main(){
16     cin>>m>>n>>k>>l>>d;
17     for (int i=1; i<n; i++) anl[i].no=i;
18     for (int i=1; i<m; i++) anh[i].no=i;
19     for (int i=1; i<=d; i++){
20         scanf("%d%d%d%d",&x,&y,&xx,&yy);
21         if (x==xx) anl[min(y,yy)].k++;
22         else if (y==yy) anh[min(x,xx)].k++;
23     }
24     sort(anl+1,anl+n+1,fuck);
25     sort(anh+1,anh+1+m,fuck);
26     sort(anl+1,anl+l+1,fuck233);
27     sort(anh+1,anh+k+1,fuck233);
28     for (int i=1; i<k; i++) printf ("%d ",anh[i].no);
29     cout<<anh[k].no<<endl;
30     for (int i=1; i<l; i++) printf ("%d ",anl[i].no);
31     cout<<anl[l].no;
32 }
1007

1008：又是模拟。。。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int f[31][31],m,n;
 5 int main(){
 6     scanf("%d%d",&n,&m);
 7     f[0][1]=1;
 8     for (int i=1; i<=m; i++)
 9         for (int j=1; j<=n; j++){
10             f[i][j]=f[i-1][j==1?n:j-1]+f[i-1][j==n?1:j+1];
11         }
12     cout<<f[m][1];
13 }
1008

1009：略过略过~

1010：模拟即可。。。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 char a[100];
 7 int f[27],ma,mi=0x7f;
 8 int main(){
 9     gets(a);
10     for (int i=0; i<strlen(a); i++)
11         f[a[i]-95]++;
12     for (int i=1; i<=26; i++){
13         ma=max(ma,f[i]);
14         mi=min(mi,f[i]==0?0x7f:f[i]);
15     }
16     ma-=mi;
17     if (ma<2){
18         cout<<"No Answer
0";
19         return 0;
20     }
21     else{
22         if (ma!=2) for (int i=2; i<=floor(sqrt(ma)); i++) if (ma%i==0){
23             cout<<"No Answer
0";
24             return 0;
25         }
26         cout<<"Lucky Word
"<<ma;
27     }
28 }
1010

1011：题意就是从(1,1)->(m,n)找两条最大权值不相交路线。f[i,j]就是找到了第i个人，第一条路线在第j行，第二条路线在第k行的最优值。DP一下就行了。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 using namespace std;
17 int f[101][51][51],a[51][51],n,m;
18 inline int in(){
19     int x=0,f=1;
20     char ch=getchar();
21     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
22     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
23     return x*f;
24 }
25 int main(){
26     n=in(),m=in();
27     For(i,1,n)
28         For(j,1,m)
29             a[i][j]=in();
30     For(i,1,n+m)
31         For(j,1,min(n,i))
32             For(k,1,min(n,i))
33             if (j!=k||i==n+m)
34                 f[i][j][k]=max(f[i-1][j-1][k-1],max(max(f[i-1][j][k],f[i][j][k]),max(f[i-1][j-1][k],f[i-1][j][k-1])))+a[j][i-j+1]+a[k][i-k+1];
35     printf("%d
",f[n+m][n][n]);
36 }
1011

1012：按题意枚举之后判断就行了。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 using namespace std;
19 int n,a[10]={6,2,5,5,4,5,6,3,7,6};
20 inline int in(){
21     int x=0,f=1;
22     char ch=getchar();
23     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
24     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
25     return x*f;
26 }
27 inline int get(int x){
28     if (!x) return 6;
29     int cnt=0;
30     while(x){
31         cnt+=a[x%10];
32         x/=10;
33     }
34     return cnt;
35 }
36 int main(){
37     n=in();
38     n-=4;
39     int ans=0;
40     For(i,0,800)
41         For(j,i,800)
42             if (get(i)+get(j)+get(i+j)==n)
43                 if (i!=j) ans+=2;
44                 else ans++;
45     printf("%d",ans);
46 }
1012

1013:二维费用的01背包。我们用f[i][j]表示剩余i金j金币时能跑到zxy妹子的最多个数，记录此时的最小时间消耗为g[i][j](你泡妹子还那么急真是不懂得享受┑(￣Д ￣)┍)状态转移方程略。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 using namespace std;
19 struct zxy{
20     int rp,c,t;
21 }a[101];
22 int f[101][101],g[101][101],n,rp,m,ans,mi;
23 inline int in(){
24     int x=0,f=1;
25     char ch=getchar();
26     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
27     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
28     return x*f;
29 }
30 int main(){
31     n=in();
32     For(i,1,n)
33         a[i].c=in(),a[i].rp=in(),a[i].t=in();
34     m=in(),rp=in();
35     mem(g,127/3); g[0][0]=0;
36     For(i,1,n)
37         Ford(j,m,a[i].c)
38             Ford(k,rp,a[i].rp)
39                 if (f[j-a[i].c][k-a[i].rp]+1>f[j][k]||(f[j-a[i].c][k-a[i].rp]+1==f[j][k]&&g[j][k]>g[j-a[i].c][k-a[i].rp]+a[i].t)){
40                     f[j][k]=f[j-a[i].c][k-a[i].rp]+1;
41                     g[j][k]=g[j-a[i].c][k-a[i].rp]+a[i].t;
42                     if (f[j][k]>ans||(f[j][k]==ans&&g[j][k]<mi)){
43                         ans=f[j][k];
44                         mi=g[j][k];
45                     }
46                 }
47     printf("%d",mi);
48 }
1013

1014:区间DP，枚举区间内要拿走的牌按题意完成即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 using namespace std;
19 int n,a[101],f[101][101];
20 inline int in(){
21     int x=0,f=1;
22     char ch=getchar();
23     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
24     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
25     return x*f;
26 }
27 inline int dp(int l,int r){
28     if (f[l][r]!=f[0][0]) return f[l][r];
29     if (l+1==r) return 0;
30     For(i,l+1,r-1)
31         f[l][r]=min(f[l][r],dp(l,i)+dp(i,r)+a[l]*a[i]*a[r]);
32     return f[l][r];
33 }
34 int main(){
35     n=in();
36     For(i,1,n) a[i]=in();
37     mem(f,127/3);
38     dp(1,n);
39     printf("%d",f[1][n]);
40 }
1014

1015：非常水的DP。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 int a[111],n,f[11];
 6 int main(){
 7     memset(a,127/3,sizeof(a));
 8     for (int i=1; i<=10; i++)
 9         scanf("%d",&f[i]);
10     cin>>n;
11     a[10]=0;
12     for (int i=11; i<=n+10; i++)
13         for (int j=1; j<=10; j++)
14             a[i]=min(a[i],a[i-j]+f[j]);
15     cout<<a[n+10];
16 }
1015

1016：裸01背包+1

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int f[20001],a[31],n,v;
 5 int main(){
 6     cin>>v>>n;
 7     for (int i=1; i<=n; i++) scanf("%d",&a[i]);
 8     for (int i=1; i<=n; i++)
 9         for (int j=v; j>=a[i]; j--)
10             f[j]=max(f[j],a[i]+f[j-a[i]]);
11     cout<<v-f[v];
12 }
1016

1017：并查集之后统计没有用的合并次数即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 using namespace std;
19 int fa[101],n,m,ans;
20 inline int in(){
21     int x=0,f=1;
22     char ch=getchar();
23     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
24     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
25     return x*f;
26 }
27 inline int find(int x){
28     fa[x]=fa[x]==x?x:find(fa[x]);
29     return fa[x];
30 }
31 int main(){
32     n=in(); m=in();
33     For(i,1,m) fa[i]=i;
34     For(i,1,n){
35         int x=in(),y=in();
36         if (find(x)==find(y)) ans++;
37         else fa[find(x)]=find(y);
38     }
39     printf("%d",ans);
40 }
1017

1018:20！用LL就可以存了。。。。然后按题意模拟一下即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 using namespace std;
19 int n,k,mo=1,a[30];
20 ll ans=1;
21 inline int in(){
22     int x=0,f=1;
23     char ch=getchar();
24     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
25     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
26     return x*f;
27 }
28 int main(){
29     n=in();k=in();
30     bool p=0;
31     For(i,1,k) mo*=10;
32     For(i,1,n) 
33         ans*=i;
34     while(ans%10==0) ans/=10;
35     int cnt=0;
36     while(ans){
37         a[++cnt]=ans%10;
38         ans/=10;
39     }
40     Ford(i,min(cnt,k),1) printf("%d",a[i]);
41 }
1018

1019：通过进行数学推导，我们容易发现，对于b[i] 中大于a[i]的数，用它们任意进行相减的和是一定的，反之亦然，于是我们只需要将b数组与a数组按大小一一匹配即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 using namespace std;
19 int a[10001],b[10001],n,ans;
20 inline int in(){
21     int x=0,f=1;
22     char ch=getchar();
23     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
24     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
25     return x*f;
26 }
27 int main(){
28     n=in();
29     For(i,1,n) a[i]=in();
30     For(i,1,n) b[i]=in();
31     sort(a+1,a+n+1);
32     sort(b+1,b+n+1,greater<int>());
33     For(i,1,n)
34         ans+=abs(b[i]-a[i]);
35     printf("%d",ans);
36 }
1019

1020：筛法筛质数，然后对于每个a[i]暴力枚举注意及时剪枝就行了。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 using namespace std;
19 bool f[20001];
20 int pr[20001],ma,maxx,n,x,cnt;
21 inline int in(){
22     int x=0,f=1;
23     char ch=getchar();
24     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
25     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
26     return x*f;
27 }
28 void init(){
29     f[1]=1;
30     For(i,2,20000)
31         if (!f[i])
32             For(j,2,20000/i)
33                 f[i*j]=1;
34     For(i,2,20000)
35         if (!f[i])
36             pr[++cnt]=i;
37     return;
38 }
39 int main(){
40     init();
41     n=in();
42     For(i,1,n){
43         x=in();
44         Ford(i,cnt,1)
45             if (pr[i]<maxx) break;
46             else if (x%pr[i]==0){
47                 ma=x;
48                 maxx=pr[i];
49             }
50     }
51     printf("%d",ma);
52 }
1020

1021:模拟即可。。。。

1021

1022：进制转换你不会吗？（从低位向上除，判断是否是奇数即可）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 using namespace std;
19 ll x;
20 bool ans[33];
21 inline ll in(){
22     ll x=0,f=1;
23     char ch=getchar();
24     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
25     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
26     return x*f;
27 }
28 int main(){
29     x=in();
30     ll p=1;
31     int i=0;
32     for(p=1; i<=32; p*=(-2),i++)
33         if ((x/p)&1){
34             ans[i]=1;
35             x-=p;
36         }
37     while(!ans[i]&&i) i--;
38     Ford(j,i,0)
39         printf("%d",(ans[j]?1:0));
40 }
1022

1023:简单DP，用f[i][j]表示第i分钟时疲倦值为j的最大距离，则f[i][j]=f[i-1][j-1]+d[i](1<=j<=m),f[i][0]=max(f[i-1][0],f[i-j][j])(1<=j<=i&&j<=m)

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 using namespace std;
19 int d[2001],n,m,f[2001][501];
20 inline int in(){
21     int x=0,f=1;
22     char ch=getchar();
23     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
24     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
25     return x*f;
26 }
27 int main(){
28     n=in(),m=in();
29     For(i,1,n) d[i]=in();
30     For(i,1,n){
31         f[i][0]=f[i-1][0];
32         For(j,1,min(i,m)) f[i][0]=max(f[i][0],f[i-j][j]);
33         For(j,1,m) f[i][j]=f[i-1][j-1]+d[i];
34     }
35     printf("%d",f[n][0]);    
36 }
1023

1024:最长不下降子序列还是很简单的吧。。。注意一下输入的处理就行了。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 using namespace std;
19 int dy[26],a[255],f[255],cnt,ans[255];
20 char zxy[255];
21 inline int in(){
22     int x=0,f=1;
23     char ch=getchar();
24     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
25     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
26     return x*f;
27 }
28 int doit(int n){
29     mem(f,0);
30     f[1]=0;
31     int ans=0;
32     For(i,2,n)
33         For(j,1,i-1)
34             if (a[i]>=a[j]){
35                 f[i]=max(f[i],f[j]+1);
36                 ans=max(f[i],ans);
37             }
38     return ans;    
39 }
40 int main(){
41     scanf("%s",zxy);
42     For(i,0,strlen(zxy)-1)
43         dy[zxy[i]-'a']=i;
44     while(scanf("%s",zxy+1)!=EOF){
45         cnt=0;
46         For(i,0,strlen(zxy)-1)
47             a[++cnt]=dy[zxy[i]-'a'];
48         printf("%d",doit(cnt));
49     }
50 }
1024

1025：判断奇偶性你不会吗？

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 char a[255],b;
 6 int n;
 7 int main(){
 8     cin>>n;
 9     getchar();
10     for (int i=1; i<=n; i++){
11         gets(a);
12         b=a[strlen(a)-1];
13         if (b%2==0) cout<<"even
";
14         else cout<<"odd
";
15     }
16 }
1025

1026:数据范围这么小，打暴力不就好了。。。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 using namespace std;
19 bool f[241][241];
20 int n,m,I,ans;
21 inline int in(){
22     int x=0,f=1;
23     char ch=getchar();
24     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
25     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
26     return x*f;
27 }
28 int main(){
29     n=in(),m=in(),I=in();
30     int x,xx,y,yy;
31     For(i,1,I){
32         x=in(),y=in(),xx=in(),yy=in();
33         For(i,x,xx)
34             For(j,y,yy)
35                 f[i][j]=1;
36     }
37     For(i,1,n)
38         For(j,1,m)
39             if (f[i][j]) ans++;
40     printf("%d",ans);
41 }
1026

1027：按照题意搜索即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 using namespace std;
19 int a[45][45],dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},n,m;
20 inline int in(){
21     int x=0,f=1;
22     char ch=getchar();
23     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
24     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
25     return x*f;
26 }
27 int bfs(){
28     int x=1,y=1;
29     int ans=a[1][1];
30     a[1][1]=0;
31     while(x!=n||y!=m){
32         int ma=0,nx,ny;
33         For(i,0,3)    
34             if (a[x+dx[i]][y+dy[i]]>ma){
35                 ma=a[x+dx[i]][y+dy[i]];
36                 nx=x+dx[i],ny=y+dy[i];
37             }
38         ans+=ma;
39         x=nx,y=ny;
40         a[x][y]=0;
41     }
42     return ans;
43 }
44 int main(){
45     n=in(),m=in();
46     For(i,1,n)
47         For(j,1,m)
48             a[i][j]=in();
49     printf("%d",bfs());
50 }
1027

1028：又一次的01背包。。

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int f[45001],a[501],n,v;
 5 inline int in(){
 6     int x=0,f=1;
 7     char ch=getchar();
 8     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
 9     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
10     return x*f;
11 }
12 int main(){
13     v=in(),n=in();
14     for (int i=1; i<=n; i++) a[i]=in();
15     for (int i=1; i<=n; i++)
16         for (int j=v; j>=a[i]; j--)
17             f[j]=max(f[j],a[i]+f[j-a[i]]);
18     printf("%d",f[v]);
19 }
1028

1029：暴力枚举答案检查就行了吧（你要无聊加个二分也行= =）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 using namespace std;
19 string a,b;
20 inline int in(){
21     int x=0,f=1;
22     char ch=getchar();
23     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
24     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
25     return x*f;
26 }
27 bool check(string a,string b,int l){
28     For(i,0,l-1)
29         if (a[i]!=b[b.size()-l+i]) return 0;
30     return 1;
31 }
32 int main(){
33     cin>>a;cin>>b;
34     Ford(i,min(a.size(),b.size()),1)
35         if (check(a,b,i)||check(b,a,i)){
36             printf("%d",i);
37             break;
38         }
39 }
1029

1030：BFS经典题

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 struct fff{
 5     int nn,x,y;
 6 }a[100001];
 7 int dx[9]={0,1,-1,1,-1,1,-1,0,0},dy[9]={0,0,0,1,1,-1,-1,1,-1},h,t,n,m,x,y;
 8 char aa[101];
 9 bool b[101][101];
10 int main(){
11     cin>>n>>m>>y>>x;
12     for (int i=m; i>=1; i--){
13         cin>>aa;
14         for (int j=0; j<n; j++)
15             b[i][j+1]=aa[j]=='.'?0:1;   
16     }
17     h=0,t=1;
18     a[1].x=x;
19     a[1].y=y;
20     a[1].nn=0;
21     b[x][y]=1;
22     do{
23         h++;
24         for (int i=1; i<=8; i++){
25             x=a[h].x+dx[i];
26             y=a[h].y+dy[i];
27             if (x>0&&x<=m&&y>0&&y<=n&&!b[x][y]){
28                 t++;
29                 a[t].nn=a[h].nn+1;
30                 a[t].x=x;
31                 a[t].y=y;
32                 b[x][y]=1;
33             }
34         }
35     }while(h<t);
36     cout<<a[t].nn;
37 }
1030

1031:典型最短路，我用的是SPFA：）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 int dis[2501],n,m,s,e,x,y,z,a[2501][101][3],pp[100001],h,t;
 6 bool b[3001];
 7 int main(){
 8     cin>>n>>m>>s>>e;
 9     for (int i=1; i<=m; i++){
10         scanf("%d%d%d",&x,&y,&z);
11         a[x][++a[x][0][0]][1]=z;
12         a[x][a[x][0][0]][2]=y;
13         a[y][++a[y][0][0]][1]=z;
14         a[y][a[y][0][0]][2]=x;
15     }
16     h=0,t=1;
17     pp[1]=s;
18     b[s]=1;
19      
20     memset(dis,127/3,sizeof(dis));
21     dis[s]=0;
22     do{
23         h++;
24         for (int i=1; i<=a[pp[h]][0][0]; i++)
25             if (dis[a[pp[h]][i][2]]>dis[pp[h]]+a[pp[h]][i][1]){
26                 dis[a[pp[h]][i][2]]=dis[pp[h]]+a[pp[h]][i][1];
27                 if (!b[a[pp[h]][i][2]]){
28                     t++;
29                     pp[t]=a[pp[h]][i][2];
30                     b[a[pp[h]][i][2]]=1;
31                 }
32             }
33         b[pp[h]]=0;
34     }while(h<t);
35     cout<<dis[e];
36 }
1031

1032:由于大面额的钱币是小面额的倍数，我们容易想到一个贪心思路：先拿大面额凑，再拿小面额凑，最后注意一下钱不够和最大面额大于所需支付工资的情况即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 using namespace std;
19 struct zxy{
20     int n,v;
21 }a[21];
22 int n,v,ans;
23 inline int in(){
24     int x=0,f=1;
25     char ch=getchar();
26     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
27     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
28     return x*f;
29 }
30 bool cmp(zxy a,zxy b){
31     return a.v<b.v;
32 }
33 int main(){
34     n=in(),v=in();
35     For(i,1,n)
36         a[i].v=in(),a[i].n=in();
37     sort(a+1,a+n+1,cmp);
38     Ford(i,n,1)
39         if(a[i].v>v){
40             n--;
41             ans+=a[i].n;
42         }
43     while(1){
44         int nt=0;
45         Ford(i,n,1)
46             while(a[i].v+nt<v&&a[i].n)
47                     nt+=a[i].v,a[i].n--;
48         For(i,1,n)
49             if(a[i].n){
50                 nt+=a[i].v;
51                 a[i].n--;
52                 break;
53             }
54         if (nt<v) break;
55         ans++;
56     }
57     printf("%d",ans);
58 }
1032

1033：题意就是叫你求一颗二叉树的深度，DP或者dfs一下就行了，时间效率O（n）。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 using namespace std;
19 struct zxy{
20     int lc,rc,deep;
21 }a[1001];
22 int n;
23 int dfs(int k){
24     a[a[k].lc].deep=a[a[k].rc].deep=a[k].deep+1;
25     if (!a[k].lc&&!a[k].rc) return a[k].deep;
26     if (!a[k].rc) return dfs(a[k].lc);
27     if (!a[k].lc) return dfs(a[k].rc);
28     return max(dfs(a[k].lc),dfs(a[k].rc));
29 }
30 inline int in(){
31     int x=0,f=1;
32     char ch=getchar();
33     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
34     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
35     return x*f;
36 }
37 int main(){
38     n=in();
39     int x,y,z;
40     For(i,1,n-1){
41         x=in(),y=in(),z=in();
42         a[x].lc=y,a[x].rc=z;
43     }
44     a[1].deep=1;
45     printf("%d",dfs(1));
46 }
1033

1034：按题意DP或者打个最短路就行了（最短路待更新），DP按题意做就好

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define max(a,b) (a<b?b:a)
15 #define min(a,b) (a<b?a:b)
16 #define ll long long
17 #define mod 1000000007
18 #define INF 2000000000
19 using namespace std;
20 int f[10002],c[10001],s[10001],n,k;
21 inline int in(){
22     int x=0,f=1;
23     char ch=getchar();
24     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
25     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
26     return x*f;
27 }
28 int main(){
29     n=in(),k=in();
30     For(i,1,k)  s[i]=in(),c[i]=in();
31     For(i,2,n) f[i]=-INF;
32     For(i,1,n){
33         bool b=0;
34         For(j,1,k)
35             if (s[j]==i){
36                 f[i+c[j]]=max(f[i+c[j]],f[i]);
37                 b=1;
38             }
39         if (!b) f[i+1]=max(f[i+1],f[i]+1);
40     }
41     printf("%d",f[n+1]);
42 }
1034DP

1035：原谅本人过蒻并不会二分图匹配。。。（容我以后填坑）

1036：排序以后处理一下即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 using namespace std;
18 int n,a[200001],b[200001];
19 inline int in(){
20     int x=0,f=1;
21     char ch=getchar();
22     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
23     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
24     return x*f;
25 }
26 int main(){
27     n=in();
28     For(i,1,n) a[i]=in();
29     sort(a+1,a+n+1);
30     int cnt=1;
31     For(i,2,n)
32         if (a[i]!=a[i-1]){
33             printf("%d %d
",a[i-1],cnt);
34             cnt=1;
35         }
36         else ++cnt;
37     printf("%d %d",a[n],cnt);
38 }
1036

1037：高精乘法维护抹零后的后20位即可，其余同1018

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 using namespace std;
18 struct zxy{
19     int begin,l,v[500001];
20     zxy(){
21         begin=1,l=1;
22         v[1]=1;
23     }
24     void friend operator *(zxy &a,int b){
25         For(i,a.begin,min(a.begin+20,a.l))
26             a.v[i]*=b;
27         For(i,a.begin,min(a.begin+20,a.l)){
28             a.v[i+1]+=a.v[i]/10;            
29             a.v[i]%=10;
30             if(a.v[a.l+1])a.l++;           
31             while(!a.v[a.begin])a.begin++;
32         }
33     }
34 }ans;
35 int n,k;
36 inline int in(){
37     int x=0,f=1;
38     char ch=getchar();
39     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
40     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
41     return x*f;
42 }
43 int main(){
44     n=in(),k=in();
45     For(i,1,n) ans*i;
46     Ford(i,ans.begin+k-1,ans.begin)
47         printf("%d",ans.v[i]);
48 }
1037

1038：线段树裸题（大神可以用RMQ，本人太蒻）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 #define mid ((l+r)>>1)
18 using namespace std;
19 struct zxy{
20     int mi;
21 }tr[400001];
22 int n,q;
23 inline int in(){
24     int x=0,f=1;
25     char ch=getchar();
26     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
27     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
28     return x*f;
29 }
30 inline void update(int l,int r,int k,int t,int add){
31     if (l==r) {
32         tr[k].mi=add;
33         return;
34     }
35     if (t<=mid) update(l,mid,k<<1,t,add);
36     else update(mid+1,r,k<<1|1,t,add);
37     tr[k].mi=min(tr[k<<1].mi,tr[k<<1|1].mi);
38     return;
39 }
40 inline int query(int l,int r,int a,int b,int k){
41     if (a==l&&b==r) return tr[k].mi;
42     if (b<=mid) return query(l,mid,a,b,k<<1);
43     if (a>mid) return query(mid+1,r,a,b,k<<1|1);
44     return min(query(l,mid,a,mid,k<<1),query(mid+1,r,mid+1,b,k<<1|1));
45 }
46 int main(){
47     n=in(),q=in();
48     For(i,1,n) update(1,n,1,i,in());
49     For(i,1,q){
50         int x=in(),y=in();
51         printf("%d ",query(1,n,x,y,1));
52     }
53 }
1038

1039：线段树裸题+1

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 #define mid ((l+r)>>1)
18 using namespace std;
19 struct zxy{
20     int mi;
21 }tr[400001];
22 int n,q;
23 inline int in(){
24     int x=0,f=1;
25     char ch=getchar();
26     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
27     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
28     return x*f;
29 }
30 inline void update(int l,int r,int k,int t,int add){
31     if (l==r) {
32         tr[k].mi=add;
33         return;
34     }
35     if (t<=mid) update(l,mid,k<<1,t,add);
36     else update(mid+1,r,k<<1|1,t,add);
37     tr[k].mi=min(tr[k<<1].mi,tr[k<<1|1].mi);
38     return;
39 }
40 inline int query(int l,int r,int a,int b,int k){
41     if (a==l&&b==r) return tr[k].mi;
42     if (b<=mid) return query(l,mid,a,b,k<<1);
43     if (a>mid) return query(mid+1,r,a,b,k<<1|1);
44     return min(query(l,mid,a,mid,k<<1),query(mid+1,r,mid+1,b,k<<1|1));
45 }
46 int main(){
47     n=in(),q=in();
48     For(i,1,n) update(1,n,1,i,in());
49     For(i,1,q){
50         int k=in(),x=in(),y=in();
51         if (!(k^1))
52             printf("%d ",query(1,n,x,y,1));
53         else update(1,n,1,x,y);
54     }
55 }
1039

1040&1041：裸的高精加减法，注意一下字符串处理的一些细节即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 using namespace std;
18 struct data{
19     int l,v[2001];
20     void clear(){
21         l=0;
22         mem(v,0);
23     }
24     data friend operator +(data a,data b){
25         data c;c.clear();
26         c.l=max(a.l,b.l);
27         For(i,1,c.l) c.v[i]=a.v[i]+b.v[i];
28         For(i,1,c.l) c.v[i+1]+=c.v[i]/10,c.v[i]%=10;
29         if (c.v[c.l+1]) ++c.l;
30         return c;
31     }
32     data friend operator -(data a,data b){
33         data c;c.clear();
34         c.l=a.l;
35         For(i,1,c.l)
36             if (a.v[i]>=b.v[i])
37                 c.v[i]=a.v[i]-b.v[i];
38             else {
39                 a.v[i+1]--;
40                 c.v[i]=a.v[i]+10-b.v[i];
41             }
42         while(!c.v[c.l]&&c.l) c.l--;
43         return c;
44     }
45 }ans,tmp[260];
46 char a[260],ch[260];
47 int cnt;
48 inline int in(){
49     int x=0,f=1;
50     char ch=getchar();
51     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
52     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
53     return x*f;
54 }
55 int main(){
56     scanf("%s",a);
57     cnt=1;
58     Ford(i,strlen(a)-1,0)
59         if (a[i]!='+'&&a[i]!='-') tmp[cnt].v[++tmp[cnt].l]=a[i]-'0';
60         else ch[cnt++]=a[i];
61     ans=tmp[cnt];
62     Ford(i,cnt-1,1)
63         if (ch[i]=='+') ans=ans+tmp[i]; else ans=ans-tmp[i];
64     Ford(i,ans.l,1) printf("%d",ans.v[i]);
65 }
1041&1042

1042&1043：栈的练习。。。。注意处理细节。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #include<stack>
11 #define For(i,a,b) for (int i=a; i<=b; i++)
12 #define Ford(i,a,b) for (int i=a; i>=b; i--)
13 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
14 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
15 #define ll long long
16 #define mod 1000000007
17 #define INF 2000000000
18 using namespace std;
19 stack<ll> num;
20 stack<char> ch; 
21 string s;
22 int cnt;
23 inline int in(){
24     int x=0,f=1;
25     char ch=getchar();
26     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
27     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
28     return x*f;
29 }
30 int inline getlevel(char x){
31     if (x=='+'||x=='-') return 1;
32     if (x=='*'||x=='/') return 2;
33     if (x=='^') return 3;
34     if (x=='(') return 100;
35     if (x=='#') return -INF;
36     return -100;
37 }
38 ll calc(){
39     char tmp=ch.top();ch.pop();
40     ll b=num.top();num.pop();
41     ll a=num.top();num.pop();
42     if(tmp=='+')return a+b;
43     if(tmp=='-')return a-b;
44     if(tmp=='*')return a*b;
45     if(tmp=='/')return a/b;
46     ll ans=1;
47     for(int i=1;i<=b;i++)
48         ans*=a;
49     return ans;
50 }
51 int main(){
52     cin>>s;
53     For(i,0,s.size()-1)
54         if (s[i]=='(') cnt++;
55         else if (s[i]==')') --cnt;
56     while(cnt>0) cnt--,s=s+")";
57     while(cnt<0) cnt++,s="("+s;
58     s=s+"#";
59     ch.push('#');
60     num.push(0);
61     int i=0;
62     while(s[i]!='#'||ch.top()!='#'){
63         if (s[i]<'0'||s[i]>'9'){
64             if(getlevel(s[i])>getlevel(ch.top())){
65                 s[i]=s[i]=='('?'[':s[i];
66                 ch.push(s[i]);i++;
67             }
68             else 
69                 if (ch.top()=='[') ch.pop(),i++;
70                 else num.push(calc());
71         }
72         else{
73                 ll x=0;
74                 while(s[i]>='0'&&s[i]<='9') x=x*10+s[i++]-'0';
75                 num.push(x);
76         }
77     }
78     cout<<num.top();
79 }
1042&1043

1044：递推

#include<cstdio>
#include<iostream>
#define For(i,a,b) for (int i=1; i<=a; i+=b)
#define in(a) scanf("%d",&a)
using namespace std;
int n,f[26][26],a[26][26],ans=-0x7ffffff;
int main(){
    in(n);
    For(i,n,1)
        For(j,i,1)
            in(a[i][j]);
    f[1][1]=a[1][1];
    for (int i=2; i<=n; i++)
        For(j,i,1){
            f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
        }
    For(i,n,1) ans=max(ans,f[n][i]);
    cout<<ans;
}
1044

1045：区间DP，f[i][j][k]表示在[i,j]内用了k个乘号,f[l][r][k]=max(f[l][i][j]+f[i+1][r][k-j],f[l][i][j]*f[i+1][r][k-j-1])(1<=l,r<=n;l<=i<r;0<=j<=k;注意非法情况的剪枝，以及r-l=k的情况）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 using namespace std;
18 int f[101][101][101],a[101],n,num;
19 inline int in(){
20     int x=0,f=1;
21     char ch=getchar();
22     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
23     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
24     return x*f;
25 }
26 inline int dp(int l,int r,int k){    
27     if (r<l||r-l<k||k<0) return -1;    
28     if (f[l][r][k]>0) return f[l][r][k];
29     if (r-l==k){
30         f[l][r][k]=1;
31         For(i,l,r)
32             f[l][r][k]*=a[i];
33         return f[l][r][k];
34     }
35     For(i,l,r-1)
36         For(j,0,k)
37             f[l][r][k]=max(f[l][r][k],max(dp(l,i,j)+dp(i+1,r,k-j),dp(l,i,j)*dp(i+1,r,k-j-1)));
38     return f[l][r][k];
39 }
40 int main(){
41     n=in(),num=in();
42     mem(f,(-1));
43     For(i,1,n) f[i][i][0]=a[i]=in();
44     printf("%d",dp(1,n,num));
45 }
1045

1046:DP,用f[i][j]表示a串排了i个，b串拍了j个，状态转移方程是f[i][j]=min(f[i-1][j-1]+abs(a[i-1]-b[j-1]),min(f[i-1][j]+k,f[i][j-1]+k))，边界条件是f[i][0]=i*k,f[0][j]=j*k。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 #define MAXN 2001 
18 using namespace std;
19 int f[MAXN][MAXN],n,m,k;
20 char a[MAXN],b[MAXN];
21 inline int in(){
22     int x=0,f=1;
23     char ch=getchar();
24     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
25     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
26     return x*f;
27 }
28 int dp(){
29     mem(f,127/3);
30     f[0][0]=0;
31     For(i,1,n) f[i][0]=i*k;
32     For(i,1,m) f[0][i]=i*k;
33     For(i,1,n)
34         For(j,1,m)
35             f[i][j]=min(f[i-1][j-1]+abs(a[i-1]-b[j-1]),min(f[i-1][j]+k,f[i][j-1]+k));
36     return f[n][m]; 
37 }
38 int main(){
39     scanf("%s%s%d",a,b,&k);
40     n=strlen(a);
41     m=strlen(b);
42     printf("%d",dp());
43 }
1046

1048：我们不妨假设齐王的马是从快到小依次出的，用f[l][r]表示田忌可以从自己第l强到第r蒻的马中任选一匹在本轮出战，此时赛马已经比过了(n-r+l-1)轮,我们容易想到一个DP的状态方程式：

f[l][r]=max(f[l+1][r]+price(l,n-r+l),f[l][r-1]+price(r,n-r+l));price(i,j)表示用田忌的第i匹马和第j匹马在本轮出战能拿到的money。然后用记忆化搜索实现即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 1000000000
17 using namespace std;
18 int f[1001][1001],n,a[1001],b[1001];
19 inline int in(){
20     int x=0,f=1;
21     char ch=getchar();
22     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
23     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
24     return x*f;
25 }
26 inline int price(int x,int y){
27     if (a[x]>b[y]) return 200;
28     if (a[x]<b[y]) return (-200);
29     return 0;
30 }
31 inline int dp(int l,int r){
32     if (f[l][r]>(-INF)) return f[l][r];
33     if (r<l) return -INF;
34     if (l==r) {
35         f[l][r]=price(l,n);
36         return f[l][r];
37     }
38     f[l][r]=max(dp(l+1,r)+price(l,n-r+l),dp(l,r-1)+price(r,n-r+l));
39     return f[l][r];
40 }
41 int main(){
42     mem(f,-127/2);
43     n=in();
44     For(i,1,n) a[i]=in();
45     For(i,1,n) b[i]=in();
46     sort(a+1,a+n+1,greater<int>());
47     sort(b+1,b+n+1,greater<int>());
48     printf("%d",dp(1,n));
49 }
1048

1049：裸DP题，方程式都没什么好讲的。。。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 using namespace std;
18 int f[5001],a[5001],n,ans;
19 inline int in(){
20     int x=0,f=1;
21     char ch=getchar();
22     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
23     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
24     return x*f;
25 }
26 int main(){
27     n=in();
28     For(i,1,n) a[i]=in();
29     f[0]=0;
30     For(i,1,n)
31         For(j,0,i-1)
32             if (a[i]>=a[j]){
33                 f[i]=max(f[i],f[j]+1);
34                 ans=max(f[i],ans);
35             }
36     printf("%d",ans);
37 }
1049

1050：用f[i][j]表示a串前i个字符与b串前j个字符进行匹配的最长子串长度，状态转移方程式是：f[i][j]=max(f[i-1][j],f[i][j-1])(a[i]!=b[j])&f[i][j]=f[i-1][j-1]+1(a[i]=a[j]).然后用记忆化搜索实现即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 using namespace std;
18 int f[2001][2001];
19 string a,b;
20 inline int in(){
21     int x=0,f=1;
22     char ch=getchar();
23     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
24     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
25     return x*f;
26 }
27 inline int dp(int i,int j){
28     if (i<0||j<0) return 0;
29     if (f[i][j]) return f[i][j];
30     if (a[i]==b[j]) return f[i][j]=dp(i-1,j-1)+1;
31     return f[i][j]=max(dp(i-1,j),dp(i,j-1));
32 }
33 int main(){
34     cin>>a>>b;
35     printf("%d",dp(a.size()-1,b.size()-1));
36 }
1050

1051:典型的树形DP题，我们采用左儿子右兄弟法存树，f[i][j]表示第i个节点还能选j门课的最优值，枚举DP到儿子时可以选的课数l(1<=l<=j)，可以发现

f[i][j]=max(f[儿子][j-i-1]+f[兄弟][i]+i节点的权值,f[兄弟][j]);然后我们使用记忆化搜索实现树上DP即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 using namespace std;
18 struct zxy{
19     int v,son,bra;
20 }tr[301];
21 int n,f[301][301],m,ans;
22 inline int in(){
23     int x=0,f=1;
24     char ch=getchar();
25     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
26     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
27     return x*f;
28 }
29 inline int dp(int k,int t){
30     if (!(k&&t)) return 0;
31     if (f[k][t]) return f[k][t];
32     f[k][t]=tr[k].v;
33     For(i,1,t)
34         f[k][t]=max(f[k][t],dp(tr[k].son,t-i)+dp(tr[k].bra,i-1)+tr[k].v);
35     f[k][t]=max(dp(tr[k].bra,t),f[k][t]);
36     return f[k][t];
37 }
38 int main(){
39     n=in(),m=in();
40     For(i,1,n){
41         int x=in(),y=in();
42         tr[i].bra=tr[x].son;
43         tr[x].son=i;
44         tr[i].v=y;
45     }
46     f[0][0]=0;
47     tr[0].v=0;
48     printf("%d",dp(tr[0].son,m));
49 }
1051

1052：显然又是一题树上DP，用f[i][0/1]表示取不取第i节点时的最优状态，采用了很暴力的方法存树，找到root，跑一次dfs枚举儿子累加状态即可。

状态转移方程：f[i][0]=Σmax(f[儿子][1],f[儿子][0])，f[i][1]=第i点的权值+∑f[儿子][0].

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 using namespace std;
18 int n,f[6001][2],fa[6001];
19 bool b[6001];
20 inline int in(){
21     int x=0,f=1;
22     char ch=getchar();
23     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
24     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
25     return x*f;
26 }
27 inline void treedp(int k){
28     b[k]=0;
29     For(i,1,n)
30         if (b[i]&&fa[i]==k){
31             treedp(i);
32             f[k][1]+=f[i][0];
33             f[k][0]+=max(f[i][1],f[i][0]);
34         }
35 }
36 int main(){
37     n=in();
38     For(i,1,n) f[i][1]=in();
39     For(i,1,n-1){
40         int x=in(),y=in();
41         fa[x]=y;
42         b[x]=1;
43     }
44     int s;
45     For(i,1,n) if (!b[i]){
46         s=i;
47         break;
48     }
49     treedp(s);
50     printf("%d",max(f[s][0],f[s][1]));
51 }
1052

1053：字符串处理，按题意做，注意连续'-'和开头以及结尾的处理就行了。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (char i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i<=b; i++)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 using namespace std;
18 string a;
19 int p1,p2,p3;
20 inline int in(){
21     int x=0,f=1;
22     char ch=getchar();
23     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
24     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
25     return x*f;
26 }
27 inline bool digit(char k){
28     return k>='0'&&k<='9';
29 }
30 inline bool alpha(char k){
31     return k>='a'&&k<='z';
32 }
33 inline void get_(char a,char b){
34     if (b<=a||(alpha(a)&&digit(b))||(digit(a)&&alpha(b))||a=='-'||b=='-') {
35         putchar('-');
36         return;
37     }
38     int cnt=0;
39     if (p3-1){
40         if (p1==3) For(i,a+1,b-1)
41                         Ford(j,1,p2)
42                             putchar('*');
43         if (p1==2&&alpha(a)) 
44             for(char i=b-1; i>a; i--)
45                 Ford(j,1,p2)
46                     putchar(i-'a'+'A');
47         if (p1==1||(p1==2&&digit(a))) for(char i=b-1; i>a; i--)
48                     Ford(j,1,p2)
49                         putchar(i);
50         return;
51     }
52     if (p1==3) For(i,a+1,b-1)
53                         Ford(j,1,p2)
54                             putchar('*');
55     if (p1==2&&alpha(a)) 
56         For(i,a+1,b-1)
57             Ford(j,1,p2)
58                 putchar(i-'a'+'A');
59     if (p1==1) For(i,a+1,b-1)
60                 Ford(j,1,p2)
61                     putchar(i);
62 }
63 int main(){
64     p1=in(),p2=in(),p3=in();
65     cin>>a;
66     Ford(i,0,a.size()-1)
67         if (a[i]!='-'||i==0) putchar(a[i]);
68         else get_(a[i-1],a[i+1]);
69 }
1053

1055:又是区间DP,用f[l][r]表示将[l,r]合并成一堆以后的最优值，这样的话状态转移方程式是：f[l][r]=f[l][i]+f[i+1][r]+∑(j=l,j<=r)a[j](l<=i<=r)，其中我们可以用前缀和简化∑，然后使用记忆化搜索即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 100000000
17 using namespace std;
18 int f[301][301],n,s[301];
19 inline int in(){
20     int x=0,f=1;
21     char ch=getchar();
22     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
23     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
24     return x*f;
25 }
26 inline int dp(int l,int r){
27     if (f[l][r]<INF) return f[l][r]; 
28     if (l==r) return 0;
29     For(i,l,r-1) f[l][r]=min(dp(l,i)+dp(i+1,r)+s[r]-s[l-1],f[l][r]);
30     return f[l][r];
31 }
32 int main(){
33     n=in();
34     For(i,1,n) s[i]=s[i-1]+in();
35     mem(f,127/3)
36     printf("%d",dp(1,n));
37 }
1055

1056：still区间DP，首先对循环这个特性我们进行处理，用[n+1,2*n]复制与[1,n]的相同信息，这样之后从1~n都进行一次长度为n的DP取最优即可。

DP的方法：用f[l][r]表示将[l,r]合并后的最优值，状态转移方程：f[l][r]=f[l][i]+f[i+1][r]+a[l]*a[i+1]*a[r](l<=i<=r)，边界是f[i][i]=0；

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 using namespace std;
18 int f[205][205],a[205],n,ans;
19 inline int in(){
20     int x=0,f=1;
21     char ch=getchar();
22     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
23     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
24     return x*f;
25 }
26 inline int dp(int l,int r){
27     if (f[l][r]) return f[l][r];
28     if (l==r) return 0;
29     For(i,l,r-1) f[l][r]=max(f[l][r],dp(l,i)+dp(i+1,r)+a[l]*a[i+1]*a[r+1]);
30     return f[l][r];
31 }
32 int main(){
33     n=in();
34     For(i,1,n) a[i]=in();
35     For(i,n+1,2*n) a[i]=a[i-n];
36     For(i,1,n)
37         ans=max(ans,dp(i,i+n-1));
38     printf("%d",ans);
39 }
1056

1057：裸01背包，处理一下依附关系即可，具体参见程序。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 using namespace std;
18 struct zxy{
19     int ls,rs,v,imp;
20     bool pp;
21 }tr[61];
22 int n,m,f[3201];
23 inline int in(){
24     int x=0,f=1;
25     char ch=getchar();
26     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
27     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
28     return x*f;
29 }
30 int main(){
31     m=in(),n=in();
32     m/=10;
33     For(i,1,n){
34         tr[i].v=in();
35         tr[i].v/=10;
36         tr[i].imp=in();
37         int y=in();
38         if (y){
39             tr[i].pp=1;
40             if (tr[y].ls) tr[y].rs=i;
41             else tr[y].ls=i;
42         }
43     }
44     tr[0].v=tr[0].imp=0;
45     For(i,1,n)
46         if (!tr[i].pp)
47             Ford(j,m,tr[i].v){
48                 int ls=tr[i].ls,rs=tr[i].rs;
49                 if (j-tr[i].v>=tr[ls].v)
50                     f[j]=max(f[j],f[j-tr[i].v-tr[ls].v]+tr[i].v*tr[i].imp+tr[ls].v*tr[ls].imp);
51                 if (j-tr[i].v>=tr[rs].v)
52                     f[j]=max(f[j],f[j-tr[i].v-tr[rs].v]+tr[i].v*tr[i].imp+tr[rs].v*tr[rs].imp);
53                 if (j-tr[i].v>=tr[rs].v+tr[ls].v)
54                     f[j]=max(f[j],f[j-tr[i].v-tr[rs].v-tr[ls].v]+tr[i].v*tr[i].imp+tr[rs].v*tr[rs].imp+tr[ls].v*tr[ls].imp);
55                 f[j]=max(f[j],f[j-tr[i].v]+tr[i].v*tr[i].imp);
56             }
57     printf("%d",f[m]*10);
58 }
1057

1058：单纯的模拟，题意自己去外面找去┑(￣Д ￣)┍

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 using namespace std;
18 struct zxy{
19     int no,no2;
20 }order[401];
21 int use[21][21],n,m,cnt[21],t[21][21],mac[21][21],mact[21],ans,end[21];
22 bool used[21][401];
23 inline int in(){
24     int x=0,f=1;
25     char ch=getchar();
26     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
27     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
28     return x*f;
29 }
30 inline bool pd(int ma,int s,int e){
31     For(i,s,e)
32         if (used[ma][i]) return 0;
33     return 1;
34 }
35 int main(){
36     m=in(),n=in();
37     For(i,1,m*n) order[i].no=in(),order[i].no2=++cnt[order[i].no];
38     For(i,1,n)
39         For(j,1,m) mac[i][j]=in();
40     For(i,1,n)
41         For(j,1,m) t[i][j]=in();
42     For(i,1,m*n){
43         int gj=order[i].no,no=order[i].no2;
44         int tim=t[gj][no],macc=mac[gj][no];
45         For(j,end[gj],INF)
46             if (pd(macc,j,j+tim-1)){
47                 For(k,j,j+tim-1)
48                     used[macc][k]=1;
49                 end[gj]=j+tim;
50                 if (j+tim>ans) ans=j+tim;
51                 break;
52             }
53     }
54     printf("%d",ans);
55 }
1058

1062:题目都说了和合并方法和合并傻子沙子差不多，这里就不多说怎么做了，做法与1055类似，详见代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 100000000
17 using namespace std;
18 int f[101][101],n,s[101],m;
19 inline int in(){
20     int x=0,f=1;
21     char ch=getchar();
22     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
23     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
24     return x*f;
25 }
26 inline int dpmi(int l,int r){
27     if (f[l][r]<INF) return f[l][r]; 
28     if (l==r) return 0;
29     For(i,l,r-1) f[l][r]=min(dpmi(l,i)+dpmi(i+1,r)+s[r]-s[l-1],f[l][r]);
30     return f[l][r];
31 }
32 inline int dpma(int l,int r){
33     if (f[l][r]) return f[l][r];
34     if (l==r) return 0;
35     For(i,l,r-1) f[l][r]=max(dpma(l,i)+dpma(i+1,r)+s[r]-s[l-1],f[l][r]);
36     return f[l][r];
37 }
38 int main(){
39     n=in();m=in();
40     For(i,1,n) s[i]=s[i-1]+in();
41     int ma=dpma(1,n);
42     mem(f,127/3);
43     int mi=dpmi(1,n);
44     if (m<mi) printf("I am..Sha...X");
45     else if (m>ma) printf("It is easy");
46         else printf("I will go to play WarIII");
47 }
1062

1063：我们可以比较容易的想到一种贪心的方法，用头指针h和尾指针t来在数字串上模拟一个队列，对于队列判断一下是否符合条件，进行答案更新，这样的话效率还是很慢（O（mn）），我们可以考虑对队列中不同元素的数量进行一个统计，这样当cnt=m时，自然队列就符合条件，具体实现方法见代码，时间效率为O（n）。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 2000000000
17 using namespace std;
18 int n,m,a[200001],b[200001],h,t;
19 inline int in(){
20     int x=0,f=1;
21     char ch=getchar();
22     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
23     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
24     return x*f;
25 }
26 int main(){
27     n=in(),m=in();
28     For(i,1,n) a[i]=in();
29     int cnt=0,ans=n+1;
30     h=1,t=0;
31     while(h<=n-m+1&&t<=n){
32         while(cnt!=m&&t<=n)
33             cnt=b[a[++t]]?cnt:cnt+1,b[a[t]]++;
34         if (t-h+1<ans) ans=t-h+1;
35         b[a[h]]--;
36         if (!b[a[h]]) cnt--;
37         h++;
38     }        
39     if (ans<=n)printf("%d",ans);    
40     else printf("NO");
41 }
1063

1065：纯模拟

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstdlib>
 4 using namespace std;
 5 int n,c,x;
 6 int main(){
 7     for (int i=1; i<=12; i++){
 8         n+=300;
 9         scanf("%d",&x);
10         n-=x;
11         if (n<0){
12             cout<<-i;
13             exit(0);
14         }
15         c+=n/100*120;
16         n%=100;
17     }
18     cout<<c+n;
19 }
1065

1066：STL练习题，可以采用系统优先队列，自带堆等（本人采用自带堆排）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 #include<cmath>
11 #define For(i,a,b) for (int i=a; i<=b; i++)
12 #define Ford(i,a,b) for (int i=a; i>=b; i--)
13 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
14 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
15 #define ll long long
16 #define mod 1000000007
17 #define INF 2000000000
18 using namespace std;
19 int heap[25001],hp,n,ans;
20 void in(int x){
21     heap[++hp]=x;
22     push_heap(heap+1,heap+hp+1,greater<int>());
23 }
24 int out(){
25     pop_heap(heap+1,heap+hp+1,greater<int>());
26     return heap[hp--];
27 }
28 int main(){
29     cin>>n;
30     for (int i=1; i<=n; i++){
31         int x;
32         scanf("%d",&x);
33         in(x);
34     }
35     while(hp!=1){
36         int x=out(),y=out();
37         ans+=(x+y);
38         in(x+y);
39     }
40     cout<<ans;
41 }
1066

1067:用DP从前往后和从后往前各求一次到每个人的最长连续上升子序列长度，这样以来选每个人作为最高点时的答案就很好求了。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<cmath>
10 #define For(i,a,b) for (int i=a; i<=b; i++)
11 #define Ford(i,a,b) for (int i=a; i>=b; i--)
12 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
13 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
14 #define ll long long
15 #define mod 1000000007
16 #define INF 700000000
17 using namespace std;
18 int upp[102],n,a[102],dow[102],ans=0x7fffffff;
19 inline int in(){
20     int x=0,f=1;
21     char ch=getchar();
22     while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
23     while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
24     return x*f;
25 }
26 int main(){
27     n=in();    
28     For(i,1,n) a[i]=in();
29     For(i,1,n)
30         For(j,0,i-1)
31             if (a[i]>a[j])
32                 upp[i]=max(upp[i],upp[j]+1);
33     Ford(i,n,1)
34         Ford(j,n+1,i+1)
35             if (a[i]>a[j])
36                 dow[i]=max(dow[i],dow[j]+1);
37     For(i,1,n)
38         ans=min(ans,n-upp[i]-dow[i]+1);
39     printf("%d",ans);
40 }
1067

1075：数字三角形无脑递推系列...

 1 #include<cstdio>
 2 #include<iostream>
 3 #define For(i,a,b) for (int i=1; i<=a; i+=b)
 4 #define in(a) scanf("%d",&a)
 5 using namespace std;
 6 int n,a[26][26],ans=-32767;bool f[26][26][100];
 7 int main(){
 8     in(n);
 9     For(i,n,1)
10         For(j,i,1)
11             in(a[i][j]);
12     f[1][1][a[1][1]%100]=1;
13     for (int i=2; i<=n; i++)
14         For(j,i,1){
15             for (int k=0; k<=99; k++) if (f[i-1][j][k]) f[i][j][(k+a[i][j])%100]=1;
16             for (int k=0; k<=99; k++) if (f[i-1][j-1][k]) f[i][j][(k+a[i][j])%100]=1;
17         }
18     For(j,n,1)  
19         for (int i=99; i>=0; i--) if (f[n][j][i]) ans=max(ans,i);
20     cout<<ans;
21 }
1075

1079：数字三角形无脑递推系列...

 1 #include<cstdio>
 2 #include<iostream>
 3 #define For(i,a,b) for (int i=a; i<=b; i++)
 4 #define in(a) scanf("%d",&a)
 5 using namespace std;
 6 int n,f[26][26],a[26][26],ans=-0x7ffffff;
 7 int main(){
 8     in(n);
 9     For(i,1,n)
10         For(j,1,i)
11             in(a[i][j]);
12     f[1][1]=a[1][1];
13     For(i,2,n/2)
14         For(j,1,i)
15             f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
16     For(i,1,n/2-1) f[n/2][i]=0;
17     For(i,n/2+1,n)
18         For(j,n/2,i)
19             f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
20     For(i,n/2,n) ans=max(ans,f[n][i]);
21     cout<<ans;
22 }
1079

1084：数字三角形无脑递推系列...

 1 #include<cstdio>
 2 #include<iostream>
 3 #define For(i,a,b) for (int i=a; i<=b; i++)
 4 #define in(a) scanf("%d",&a)
 5 using namespace std;
 6 int n,f[26][26],a[26][26],ans=-0x7ffffff,x,y;
 7 int main(){
 8     in(n);
 9     For(i,1,n)
10         For(j,1,i)
11             in(a[i][j]);
12     in(x);in(y);
13     f[1][1]=a[1][1];
14     For(i,2,x)
15         For(j,1,i)
16             f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
17     For(i,1,x)if (i!=y) f[x][i]=-2147483647;
18     For(i,x+1,n)
19         For(j,y,i)
20             f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
21     For(i,y,n) ans=max(ans,f[n][i]);
22     cout<<ans;
23 }
1084

 本文由Melacau编写，Melacau代表M星向您问好，如果您不是在我的博客http://www.cnblogs.com/Melacau上看到本文，请您向我联系，email:13960948839@163.com.

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Melacau/p/tyvj.html