这场比赛因为坐火车没有做，到学校了， 坑爹的学校晚上要熄灯。 还有一些原因以后cf就不能及时的做了。 但是每场我肯定都不会落下.
这场b题严重坑， 被坑了1个半小时，关键还是自己的心理在作祟，思维不行， 看看zerom 16分钟就把题给a了...
a. 很水的题
b.看完题意后觉得这个很水呀，但是实现起来就坑了. 其实写起来也不是很难，关键就是当我用一种方法写到一半的时候我就觉得有点烦，然后就想会不会是我想错了，于是又去想其他方法，然后用其他方法写，要么是错的，要么更烦，无奈最后只能挑一种方法硬着头皮写.
这个是我的代码，又长又臭
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 using namespace std; 5 6 int n,m; 7 int sum; 8 char g[55][55]; 9 int cnt=0; 10 int up[4]={1,-1,0,0}; 11 int rl[4]={0,0,1,-1}; 12 int mark[55][55]; 13 14 /*void dfs(int i,int j) 15 { 16 cnt++; 17 mark[i][j]=1; 18 if(cnt == sum) return ; 19 for(int i1=0;i1<4;i1++) 20 { 21 int ci,cj; 22 ci=i+up[i1]; 23 cj=j+rl[i1]; 24 if((ci>=1&&ci<=n)&&(cj>=1&&cj<=m)&&g[ci][cj]=='B'&&mark[ci][cj]==0) 25 { 26 dfs(ci,cj); 27 } 28 29 } 30 }*/ 31 32 33 int main() 34 { 35 scanf("%d%d",&n,&m); 36 sum=0; 37 for(int i=1;i<=n;i++) 38 for(int j=1;j<=m;j++) 39 { 40 cin>>g[i][j]; 41 if(g[i][j]=='B') sum++; 42 } 43 int flag=0; 44 for(int i=1;i<=n;i++) 45 for(int j=1;j<=m;j++) 46 { 47 int cnt; 48 memset(mark,0,sizeof(mark)); 49 if(g[i][j]=='B') 50 { 51 cnt=0; 52 if(mark[i][j]==0) 53 { 54 cnt++; 55 mark[i][j]=1; 56 } 57 for(int k=j+1;k<=m;k++) 58 { 59 if(g[i][k]=='W') break; 60 if(mark[i][k]==0) 61 { 62 cnt++; 63 mark[i][k]=1; 64 } 65 for(int k1=1;k1+i<=n;k1++) 66 { 67 if(g[k1+i][k]=='W') break; 68 if(mark[k1+i][k]==0) 69 { 70 cnt++; 71 mark[k1+i][k]=1; 72 } 73 } 74 for(int k1=1;i-k1>=1;k1++) 75 { 76 if(g[i-k1][k]=='W') break; 77 if(mark[i-k1][k]==0) 78 { 79 cnt++; 80 mark[i-k1][k]=1; 81 } 82 } 83 } 84 ///////////// 85 for(int k=j-1;k>=1;k--) 86 { 87 if(g[i][k]=='W') break; 88 if(mark[i][k]==0) 89 { 90 cnt++; 91 mark[i][k]=1; 92 } 93 for(int k1=1;k1+i<=n;k1++) 94 { 95 if(g[k1+i][k]=='W') break; 96 if(mark[k1+i][k]==0) 97 { 98 cnt++; 99 mark[k1+i][k]=1; 100 } 101 } 102 for(int k1=1;i-k1>=1;k1++) 103 { 104 if(g[i-k1][k]=='W') break; 105 if(mark[i-k1][k]==0) 106 { 107 cnt++; 108 mark[i-k1][k]=1; 109 } 110 } 111 } 112 ///////////////// 113 for(int k=i+1;k<=n;k++) 114 { 115 if(g[k][j]=='W') break; 116 if(mark[k][j]==0) 117 { 118 cnt++; 119 mark[k][j]=1; 120 } 121 for(int k1=1;k1+j<=m;k1++) 122 { 123 if(g[k][k1+j]=='W') break; 124 if(mark[k][k1+j]==0) 125 { 126 cnt++; 127 mark[k][k1+j]=1; 128 } 129 } 130 for(int k1=1;j-k1>=1;k1++) 131 { 132 if(g[k][j-k1]=='W') break; 133 if(mark[k][j-k1]==0) 134 { 135 cnt++; 136 mark[k][j-k1]=1; 137 } 138 } 139 } 140 /////////////////// 141 for(int k=i-1;k>=1;k--) 142 { 143 if(g[k][j]=='W') break; 144 if(mark[k][j]==0) 145 { 146 cnt++; 147 mark[k][j]=1; 148 } 149 for(int k1=1;k1+j<=m;k1++) 150 { 151 if(g[k][k1+j]=='W') break; 152 if(mark[k][k1+j]==0) 153 { 154 cnt++; 155 mark[k][k1+j]=1; 156 } 157 } 158 for(int k1=1;j-k1>=1;k1++) 159 { 160 if(g[k][j-k1]=='W') break; 161 if(mark[k][j-k1]==0) 162 { 163 cnt++; 164 mark[k][j-k1]=1; 165 } 166 } 167 } 168 ////////////////////// 169 if(cnt!=sum) 170 { 171 printf("NO\n"); 172 return 0; 173 } 174 } 175 } 176 printf("YES\n"); 177 return 0; 178 }
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 char map[55][55]; 7 int visit[55][55]; 8 int n,m,sum; 9 struct Node 10 { 11 int x,y; 12 Node(int a,int b) 13 { 14 x=a,y=b; 15 } 16 }; 17 queue<Node>q; 18 int f[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; 19 int BFS(int x,int y) 20 { 21 memset(visit,0,sizeof(visit)); 22 while(!q.empty())q.pop(); 23 q.push(Node(x,y)); 24 visit[x][y]=1; 25 int num=1; 26 for(int i=0;i<4;++i) 27 { 28 int xx=x+f[i][0],yy=y+f[i][1]; 29 while(xx>=0&&xx<n&&yy>=0&&yy<m&&map[xx][yy]!='W') 30 { 31 ++num; 32 visit[xx][yy]=1; 33 q.push(Node(xx,yy)); 34 xx+=f[i][0],yy+=f[i][1]; 35 } 36 } 37 while(!q.empty()) 38 { 39 x=q.front().x,y=q.front().y; 40 q.pop(); 41 for(int i=0;i<4;++i) 42 { 43 int xx=x+f[i][0],yy=y+f[i][1]; 44 while(xx>=0&&xx<n&&yy>=0&&yy<m&&map[xx][yy]!='W') 45 { 46 if(!visit[xx][yy])++num; 47 visit[xx][yy]=1; 48 xx+=f[i][0],yy+=f[i][1]; 49 } 50 } 51 } 52 if(num==sum)return 1; 53 return 0; 54 } 55 int main() 56 { 57 while(scanf("%d%d",&n,&m)!=EOF) 58 { 59 for(int i=0;i<n;++i) 60 scanf("%s",map[i]); 61 sum=0; 62 for(int i=0;i<n;++i) 63 for(int j=0;j<m;++j) 64 if(map[i][j]=='B')++sum; 65 int flag=1; 66 for(int i=0;i<n&&flag;++i) 67 for(int j=0;j<m&&flag;++j) 68 if(map[i][j]=='B')flag=BFS(i,j); 69 if(flag)printf("YES\n"); 70 else printf("NO\n"); 71 } 72 return 0; 73 }
c. 这题连看题到a ，10分钟都没要， 想法很简单实现也很简单. 就是从小的开始选择（这个数除以K如果没有出现在找过的序列中）入列。 因为对于数 N 和 N*K 选择当然选N好，因为选了N*K 可能就选不了N*K*K
数据量有点大，要用二分
#include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> using namespace std; int g[100100]; int save[100100]; int cnt=0; int find(int k) { int b=0; int d=cnt-1; while(b<=d) { int mid=(b+d)/2; if(save[mid]==k) return 1; if(save[mid]<k) b=mid+1; else d=mid-1; } return 0; } int main() { int n,k; scanf("%d%d",&n,&k); for(int i=0;i<n;i++) scanf("%d",&g[i]); sort(g,g+n); for(int i=0;i<n;i++) { if(g[i]%k!=0) { save[cnt++]=g[i]; continue; } if(find(g[i]/k)==0) { save[cnt++]=g[i]; } } printf("%d",cnt); return 0; }
d. 挺好一道 dfs 的题， 题意思很简单，给你一颗树， 每个结点有一定的权值， 你每次操作可以选一颗包括1结点的子树， 然后增加或减少一个这颗子树上每个结点的权值. （可以把树看成以1结点为根结点的树）
求使这颗树结点的权都变为0的最小操作次数.
解法： 可以分步来看， 对于每一个结点，如果进行操作那么他的子树都可以一起操作， 只要能知道他的子树最少需要多少然后就可以知道包括这个结点在内的树最小需要多少。 这样就产生递归求解的可能。至于递归的步骤，想想也能想明白
#include <stdio.h> #include <string> #include <math.h> #include <string.h> #include <algorithm> #include <iostream> using namespace std; #define N 100100 typedef __int64 LL; struct node { int to,next; }edge[2*N]; struct K { LL mi,mx; }; int n; int g[N]; int pre[N],cnt; int mark[N]; void add_edge(int u,int v) { edge[cnt].to=v; edge[cnt].next=pre[u]; pre[u]=cnt++; } K dfs(int s) { LL mi=0,mx=0; K tmp; for(int p=pre[s];p!=-1;p=edge[p].next) { int v=edge[p].to; if(mark[v]==0) { mark[v]=1; tmp=dfs(edge[p].to); if(tmp.mx>mx) mx=tmp.mx; if(tmp.mi<mi) mi=tmp.mi; //找出这个结点的子树中 } } if(mx+mi+g[s]>=0) mi=mi-(mx+mi+g[s]); else mx=mx-(mx+mi+g[s]); tmp.mi=mi; tmp.mx=mx; return tmp; } int main() { cnt=0; memset(pre,-1,sizeof(pre)); scanf("%d",&n); for(int i=0;i<n-1;i++) { int x,y; scanf("%d%d",&x,&y); add_edge(x,y); add_edge(y,x); // 双向的边 } for(int i=1;i<=n;i++) { scanf("%d",&g[i]); } memset(mark,0,sizeof(mark)); mark[1]=1; K tmp=dfs(1); printf("%I64d",tmp.mx-tmp.mi); return 0; }