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("%dn",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("%1d",&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("%I64dn",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("%1d",&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("0n");
}
}

最后

以上就是顺利夏天为你收集整理的Codeforces Round #249 (Div. 2 Only)（A-E)的全部内容，希望文章能够帮你解决Codeforces Round #249 (Div. 2 Only)（A-E)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。