Codeforces Round #249 (Div. 2 Only)（A-E)

A. Queue on Bus Stop

题意：现在有n个队伍，每个对于有ai个人（1<=ai<=m），现在要用公交车按照队伍顺序拉走所有人，一辆公交车最多能拉m个人，一个队伍所有的人必须在同一辆车上，问至少需要多少俩车才能拉走所有人

思路：简单模拟

代码：

#include<bits/stdc++.h> using namespace std; int n,m; int main(){ scanf("%d%d",&n,&m); int bef=0,ans=1; for(int i=0;i<n;i++){ int temp; scanf("%d",&temp); if(temp+bef<=m) bef+=temp; else{ ans++; bef=temp; } } printf("%d\n",ans); }

---

B. Pasha Maximizes

题意：给你一个数字，相邻两位可以互相交换，问最多交换k次的情况下，这个数字最大变成多少 思路：从最左一位开始贪心，每次都在距离k的范围内，找到最大的进行交换

代码：

#include<bits/stdc++.h> using namespace std; char a[20]; int main(){ scanf("%s",a); int n; scanf("%d",&n); int x=strlen(a); int now=0; while(n>0&&now<x) { int maxn=now; int top=min(n+now,x-1); for(int i=now+1;i<=top;i++) { if(a[maxn]<a[i]) maxn=i; } if(a[now]<a[maxn]){ char temp=a[maxn]; for(int i=maxn;i>now;i--) { a[i]=a[i-1]; } a[now]=temp; n-=maxn-now; } now++; } for(int i=0;i<x;i++) printf("%c",a[i]); puts(""); }

---

C - Cardiogram

题意：用n个数字模拟心电图，一个数字表示向上几个，一个数字表示向下几个，最后要求输出最终的心电图（注意：某一行最后需要空格补全） 思路：用一个vector储存某一行的输出信息，如果需要输出’/’或者’\’，就储存一个数字，正数是’/’，负数是’\’，然后中间的值用空格补全

代码：

#include<bits/stdc++.h> using namespace std; vector<int> q[2100]; int main(){ int n; scanf("%d",&n); int now=1000; int len=0; for(int i=0;i<n;i++) { int temp; scanf("%d",&temp); if(i%2==0){ for(int j=0;j<temp;j++) q[now++].push_back(len++); now--; } else{ for(int j=0;j<temp;j++) q[now--].push_back(-1*(len++)); now++; } } for(int i=2010;i>=0;i--) { if(q[i].size()!=0) { int bef=0; for(int j=0;j<q[i].size();j++) { for(int k=bef;k<abs(q[i][j]);k++) printf(" "); bef=abs(q[i][j])+1; if(q[i][j]>=0) printf("/"); else printf("\\"); } for(int l=bef;l<len;l++) printf(" "); puts(""); } } }

---

D. Special Grid

题意：给你一个n*m的矩阵，1是黑色，0是白色，这些点之间，八个方向的点都会相连，现在，要求数出，边上只有白点且边都在各个点相连的线上时的三角形有多少个 思路：预处理+思路，因为三角形的边必须在线上，所以思考下就能得出，所有符合题目要求的三角形，必定为等腰直角三角形，那么，我就可以枚举每个顶点，同时算出八个方向的最长的连续白点的个数，那么，如果我八个方向是按顺序求的，那我a方向就能和(a+2)%8方向的边组成三角形，显然，为了组成三角形，我必须这两者中取小的作为我的最大长度maxn，然后，我枚举的顶点，同时在a和(a+2)%8方向上的长度为1-maxn的另外两个顶点能组成等腰直角三角形，同时这两个直角边必定没有黑点，那我只需要判断下斜边有没有黑点就好了，而判断的这个过程我可以预处理，把横着，竖着，斜向上，斜向下的这四种情况都预处理出来，在枚举顶点和八个方向后就能进行o(1)的判断了

代码：

#include<bits/stdc++.h> using namespace std; int a[410][410];//原地图 int h[410][410];//横方向的预处理 int s[410][410];//竖方向的预处理 int xs[410][410];//斜上方向的预处理 int xx[410][410];//斜下方向的预处理 int b[8];//储存八个方向的最长的连续白点个数 int nex[8][2]={1,0,1,1,0,1,-1,1,-1,0,-1,-1,0,-1,1,-1}; int n,m; int num(int i,int j,int way,int now)//用来判断这个方向上，最长的连续白点个数 { if(i+nex[way][0]>=n||i+nex[way][0]<0||j+nex[way][1]>=m||j+nex[way][1]<0||a[i+nex[way][0]][j+nex[way][1]]!=0) return now; return num(i+nex[way][0],j+nex[way][1],way,now+1); } void init(){//预处理 for(int i=0;i<n;i++) { int now=0; for(int j=0;j<m;j++) { if(a[i][j]==1) now++; h[i][j]=now; } }//横向 for(int j=0;j<m;j++) { int now=0; for(int i=0;i<n;i++) { if(a[i][j]==1) now++; s[i][j]=now; } }//竖向 for(int i=0;i<n;i++) { int j=i; int k=0; int now=0; while(j>=0&&k<m) { if(a[j][k]==1) now++; xs[j][k]=now; j--; k++; } } for(int i=1;i<m;i++) { int j=i; int k=n-1; int now=0; while(k>=0&&j<m) { if(a[k][j]==1) now++; xs[k][j]=now; k--; j++; } } //斜向上 for(int i=0;i<m;i++) { int j=i; int k=0; int now=0; while(j<m&&k<n){ if(a[k][j]==1) now++; xx[k][j]=now; k++; j++; } } for(int i=1;i<n;i++) { int j=i; int k=0; int now=0; while(j<n&&k<m){ if(a[j][k]==1) now++; xx[j][k]=now; j++; k++; } } //斜向下 } bool judge(int i,int j,int k,int l)//判断这两个点之间有没有黑点 { if(i==k||j==l) { if(i==k)//横 { if(j>l) swap(j,l); if(h[k][l]-h[i][j]!=0) return false; return true; } else//竖 { if(i>k) swap(i,k); if(s[k][l]-s[i][j]!=0) return false; return true; } } else { if(i>k)//i,j在上边 { swap(i,k); swap(j,l); } if(j<l)//斜下 { if(xx[k][l]-xx[i][j]!=0) return false; return true; } else { if(xs[i][j]-xs[k][l]!=0) return false; return true; } } return true; } int main(){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("",&a[i][j]); init(); long long ans=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){//枚举直角点 if(a[i][j]==0){ for(int k=0;k<8;k++)//判断八个方向 b[k]=num(i,j,k,0); for(int k=0;k<8;k++){ int minn=min(b[k],b[(k+2)%8]); while(minn>0){ if(judge(i+minn*nex[k][0],j+minn*nex[k][1],i+minn*nex[(k+2)%8][0],j+minn*nex[(k+2)%8][1])) ans++; minn--; } } } } } printf("%I64d\n",ans); }

---

E. Special Graph

题意：给你一个和D题相似的图，但是这次各个顶点要染色，相连接的点不能颜色相同，一开始有的点已经染过色了，要求输出一种方案，如果没有的话输出0 思路：通过题目给的图，就有了一个大胆的猜测，答案只能有两种情况，一种是每行两种颜色，一种每列两种颜色，然后证明的话也很简单，自己造一组每行3-4种颜色的数据，然后自己向下推导，你会发现，这个时候，他的列会满足每行两个颜色（代码有点丑，建议跳过）

代码：

#include<bits/stdc++.h> using namespace std; int a[1100][1100]; int b[5]; int c[5]; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("",&a[i][j]); memset(b,-1,sizeof(b)); bool judge=true; for(int i=0;i<n;i++) { int c[2]; memset(c,-1,sizeof(c)); for(int j=0;j<m;j++) if(a[i][j]!=0) { int temp=i%2+1; if((b[a[i][j]]!=-1&&b[a[i][j]]!=temp)||(c[(j+1)%2]==a[i][j])||c[j%2]!=a[i][j]&&c[j%2]!=-1) judge=false; else { c[j%2]=a[i][j]; b[a[i][j]]=temp; } } }//先算每行两种的情况 if(judge){ int d=0; int s=0; for(int i=1;i<5;i++) { if(b[i]==-1) continue; if(b[i]%2==0) s++; else d++; }//判断每行是哪两种颜色 for(int i=1;i<5;i++) { if(b[i]==-1) { if(d<2) { b[i]=1; d++; } else b[i]=2; } } for(int i=0;i<n;i++) { int l=-1,r=-1; for(int j=1;j<5;j++) { if(i%2!=b[j]%2) if(l==-1) l=j; else r=j; } int now=0; for(int j=0;j<m;j++) { if(a[i][j]!=0) { if(j%2==0) if(a[i][j]!=l)now=0; else now=1; else if(a[i][j]!=l) now=1; else now=0; } }//判断这两种的输出顺序 for(int j=0;j<m;j++) if((j+now)%2!=0) printf("%d",l); else printf("%d",r); puts(""); } } else{//和之前同理，这次是每列 memset(b,-1,sizeof(b)); judge=true; for(int j=0;j<m;j++) { int c[2]; memset(c,-1,sizeof(c)); for(int i=0;i<n;i++) if(a[i][j]!=0) { int temp=j%2+1; if((b[a[i][j]]!=-1&&b[a[i][j]]!=temp)||(c[(i+1)%2]==a[i][j])||c[i%2]!=a[i][j]&&c[i%2]!=-1) judge=false; else { c[i%2]=a[i][j]; b[a[i][j]]=temp; } } } if(judge){ int d=0; int s=0; for(int i=1;i<5;i++) { if(b[i]==-1) continue; if(b[i]%2==0) s++; else d++; } for(int i=1;i<5;i++) { if(b[i]==-1) { if(d<2) { b[i]=1; d++; } else b[i]=2; } } for(int j=0;j<m;j++) { int l=-1,r=-1; for(int i=1;i<5;i++) { if(j%2!=b[i]%2) if(l==-1) l=i; else r=i; } int now=0; for(int i=0;i<n;i++) { if(a[i][j]!=0) { if(i%2==0) if(a[i][j]!=l)now=0; else now=1; else if(a[i][j]!=l) now=1; else now=0; } } for(int i=0;i<n;i++) if((i+now)%2!=0) a[i][j]=l; else a[i][j]=r; } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) printf("%d",a[i][j]); puts(""); } } else printf("0\n"); } }