被C坑的不行不行的。。。其他题目都还可以。
求1，2，3,...,n的加和，其中2^x（x>=0）为负。
因为2^x的个数很少，所以以每个2^x为分界点进行判断.
初始化x=0;
如果n>2^x,求出2^(x-1)到2^(x)之间的加和，用等差数列求和公式即可，然后x++,
如果n<=2^x,求出2^(x-1)到n之间的加和，然后结束.
#include <iostream> #include <stdio.h> #include <string> #include <string.h> using namespace std; int main(int argc, const char * argv[]) { // insert code here... int T; scanf("%d",&T); while (T--) { int n; scanf( "%d",&n); long long tmp=1; long long sum=0; while(tmp<=n) { if( tmp-1 >= tmp/2+1 ) { sum += (tmp+tmp/2)*(tmp-tmp/2-1)/2; } sum -= tmp; tmp*=2; } sum += (tmp/2+1+n)*(n-tmp/2)/2; cout<<sum<<endl; } return 0; }
(感触：以后写等差数列求和时写个函数，方便些)
看懂题目，模拟即可。
#include <iostream> #include <stdio.h> #include <string> #include <string.h> using namespace std; char str[2][10100]; int main(int argc, const char * argv[]) { // insert code here... scanf("%s",str[0]); int m; scanf("%d",&m); int a=0,b=1; for (int i=0;i<m; i++) { int l,r,k; scanf("%d%d%d",&l,&r,&k); l--; r--; int tlen=(r-l+1); k%=tlen; strcpy(str[b],str[a]); for(int j=l;j<=r;j++) { str[b][l+ (j-l+k)%tlen ]=str[a][j]; } swap(a,b); //printf("%s ",str[a]); } printf("%s ",str[a]); return 0; }
这题可以看这里，里面有我写这题的崎岖之路。
很裸的BFS。 不同的是，到一个格点，搜索一下周围四个方向上墙的个数。
#include <iostream> #include <stdio.h> #include <string> #include <math.h> #include <algorithm> #include <string.h> using namespace std; int n,m,k; char g[1010][1010]; int mark[1010][1010]; int id; struct node { int x,y; }que[1001000]; int qf,qd; int save[1001000]; int up[4]={1,-1,0,0}; int rl[4]={0,0,1,-1}; void bfs(int x,int y) { qf=qd=0; node fi; fi.x=x; fi.y=y; int cnt=0; que[qf++]=fi; mark[x][y]=id; while(qf>qd) { node cur=que[qd++]; for(int i=0;i<4;i++) { int tx=cur.x+up[i]; int ty=cur.y+rl[i]; if( tx>=0&&tx<n &&ty>=0&&ty<m ) { if(g[tx][ty]=='.'&&mark[tx][ty]==-1 ) { mark[tx][ty]=id; node newnode; newnode.x=tx; newnode.y=ty; que[qf++]=newnode; } else if(g[tx][ty]=='*') cnt++; } } } save[id]=cnt; id++; } int main(int argc, const char * argv[]) { // insert code here... scanf("%d%d%d",&n,&m,&k); for(int i=0;i<n;i++) scanf("%s",g[i]); id=0; memset(mark,-1,sizeof(mark)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { if( mark[i][j] ==-1 && g[i][j] == '.' ) { bfs(i,j); } } for(int i=0;i<k;i++) { int x,y; scanf("%d%d",&x,&y); x--;y--; printf("%d ",save[ mark[x][y] ]); } return 0; }
DP.
状态：
dp[i][j][k] 表示高为i，宽为j的巧克力被分成能拼成k的最小花费。
转移：
考虑每一种横着切和竖着切的情况。具体看代码。
#include <iostream> #include <stdio.h> #include <string> #include <math.h> #include <algorithm> #include <string.h> using namespace std; #define INF 100000000 int dp[33][33][55]; int main(int argc, const char * argv[]) { dp[1][1][1]=0; memset(dp,0,sizeof(dp)); for(int i=1;i<=30;i++) for(int j=1;j<=30;j++) for(int k=1;k<=50;k++) dp[i][j][k]=INF; dp[1][1][1]=0; for(int i=1;i<=30;i++) for(int j=1;j<=30;j++) { if(i==j&&i==1) continue; for(int k=1;k<=min(i*j,50);k++) { if(i*j==k) { dp[i][j][k]=0; continue; } int mi=INF; for(int i1=1;i1<i;i1++) { if( i1*j <= k) mi=min(mi,dp[(i-i1)][j][k-i1*j]+j*j); if( (i-i1)*j <= k ) mi=min(mi,dp[i1][j][k-(i-i1)*j]+j*j); if( i1*j >= k) mi=min(mi,dp[i1][j][k]+j*j); if( (i-i1)*j >=k ) mi=min(mi,dp[i-i1][j][k]+j*j); } for(int j1=1;j1<j;j1++) { if( j1*i <= k ) mi=min(mi,dp[i][j-j1][k-j1*i]+i*i); if( (j-j1)*i <=k ) mi=min(mi,dp[i][j1][k-(j-j1)*i]+i*i); if( j1*i >= k) mi=min(mi,dp[i][j1][k]+i*i); if( (j-j1)*i >=k ) mi=min(mi,dp[i][j-j1][k]+i*i); } //有四种情况 dp[i][j][k]=mi; } } int n; scanf("%d",&n); while(n--) { int x,y,z; scanf("%d%d%d",&x,&y,&z); printf("%d ",dp[x][y][z]); } return 0; }