Codeforces Round #249 (Div. 2)

A. Queue on Bus Stop

题目大意：有n组人乘车，每组人有a [ i ]，每辆车可以载 m 个人，保证 a[ i ]小于m，每组人中的人都不能分开，

问，最少要几辆车。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[105];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int now=1,ans=0;
while(now<=n)
{
ans++;int res=m-a[now];now++;
while(res>=a[now] && now<=n) res-=a[now],now++;
}
cout<<ans<<endl;
return 0;
}

 

B - Pasha Maximizes

题目大意：给你一个数，每次操作能交换任意相邻两位上的数字，问你k次操作后，这个数的最大值。

 

思路：刚开始的时候我就是，循环k次，每次取最前面的两个逆序数交换，这样的贪心是错误的。

正确的思路是我们需要尽可能保证最大位的数大，所以我们要一位一位考虑。

我代码写的有点搓，懒得改了。。

#include<bits/stdc++.h>
using namespace std;
char s[20];
int k,len;
struct node
{
char t;
int id;
bool operator < (const node &p)const
{
if(t==p.t) return id<p.id;
else return t>p.t;
}
}w[20];
void change(int l,int r)
{
for(int i=r;i>l;i--)
{
int t=s[i];
s[i]=s[i-1];
s[i-1]=t;
}
for(int i=0;i<len;i++)
{
w[i].t=s[i];
w[i].id=i;
}
sort(w,w+len);
}
int main()
{
scanf("%s%d",s,&k);
len=strlen(s);
for(int i=0;i<len;i++)
{
w[i].t=s[i];
w[i].id=i;
}
sort(w,w+len);
int pos=0;node g;
while(pos<len-1)
{
for(int i=0;i<len;i++)
{
if(w[i].id>pos && k>=w[i].id-pos && w[i].t>s[pos])
{
k-=w[i].id-pos;
//printf("%d %d****n",pos,w[i].id);

change(pos,w[i].id);
break;
}
}
pos++;
}
puts(s);
return 0;
}

 

C - Cardiogram

题目大意：不好描述直接贴地址。

 

思路：模拟题，不过很多细节要注意，挺恶心的。

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
using namespace std;
int n;
pii p[1005];
char ans[2005][2005];
int n_x,n_y,up,down;
void work(int x1,int y1,int x2,int y2)
{
if(x1<x2)
{
while(x1<x2)
{
ans[n_x][n_y]='/';
n_x+=1;n_y+=1;
x1+=1;y1+=1;
}
n_x-=1;
up=max(n_x,up);
}
else
{
while(x1>x2)
{
ans[n_x][n_y]='\';
x1-=1;y1+=1;
n_x-=1;n_y+=1;
}
n_x+=1;
down=min(n_x,down);
}
}
int main()
{
cin>>n;
p[1].fi=0;p[1].se=1000;
bool flag=true;
up=1000,down=1000;
n_x=1000;n_y=0;
for(int i=2;i<=n+1;i++)
{
int g; scanf("%d",&g);
p[i].fi+=p[i-1].fi+g;
if(flag) p[i].se+=p[i-1].se+g;
else p[i].se+=p[i-1].se-g;
flag=!flag;
}
for(int i=1;i<=n;i++)
{
work(p[i].se,p[i].fi,p[i+1].se,p[i+1].fi);
}
//cout<<up<<endl;
//cout<<down<<endl;
//cout<<n_y-1<<endl;
//cout<<n_y-1<<endl;
for(int i=up;i>=down;i--)
{
for(int j=0;j<=n_y-1;j++)
{
//cout<<i<<"
"<<j<<endl;
if(ans[i][j]!='/' && ans[i][j]!='\') putchar(' ');
else putchar(ans[i][j]);
}
puts("");
}
return 0;
}

 

D - Special Grid

题目大意：给你n*m个点，要么是黑点，要么是白点，问你由白点组成的三角形有多少个，即边上全是白点。

 

思路：首先我们可以明确，三角形全部都是等腰直角三角形，我们可以枚举他的直角顶点，然后向八个方向

扩展，问题就在于怎么判断他的斜边有没有黑点，我们可以预处理处每个点，0°，45°，90°，145°四个方向

的黑点前缀和，这样就能o( 1 )判断了。

#include<bits/stdc++.h>
using namespace std;
int n,m,w[405][405],c0[405][405],c45[405][405],c90[405][405],c135[405][405];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%1d",&w[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(!w[i][j])
{
for(int k=1;k<j;k++) if(w[i][k]) c0[i][j]++;
for(int k=1;k<i;k++) if(w[k][j]) c90[i][j]++;
for(int k=1;i-k>=1 && j-k>=1;k++) if(w[i-k][j-k]) c135[i][j]++;
for(int k=1;i-k>=1 && j+k<=m;k++) if(w[i-k][j+k]) c45[i][j]++;
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(!w[i][j])
{
for(int k=1;i-k>=1 && j+k<=m;k++)
{
if(!w[i-k][j] && !w[i][j+k])
{
if(c135[i-k][j]-c135[i][j+k]==0) ans++;
}
else break;
}
for(int k=1;i+k<=n && j+k<=m;k++)
{
if(!w[i+k][j] && !w[i][j+k])
{
if(c45[i+k][j]-c45[i][j+k]==0) ans++;
}
else break;
}
for(int k=1;i+k<=n && j-k>=1;k++)
{
if(!w[i+k][j] && !w[i][j-k])
{
if(c135[i+k][j]-c135[i][j-k]==0) ans++;
}
else break;
}
for(int k=1;i-k>=1 && j-k>=1;k++)
{
if(!w[i-k][j] && !w[i][j-k])
{
if(c45[i-k][j]-c45[i][j-k]==0) ans++;
}
else break;
}
for(int k=1;j+k<=m && i-k>=1 && i+k<=n;k++)
{
if(!w[i-k][j+k] && !w[i+k][j+k])
{
if(c90[i-k][j+k]-c90[i+k][j+k]==0) ans++;
}
else break;
}
for(int k=1;i+k<=n && j-k>=1 && j+k<=m;k++)
{
if(!w[i+k][j+k] && !w[i+k][j-k])
{
if(c0[i+k][j+k]-c0[i+k][j-k]==0) ans++;
}
else break;
}
for(int k=1;j-k>=1 && i-k>=1 && i+k<=n;k++)
{
if(!w[i-k][j-k] && !w[i+k][j-k])
{
if(c90[i-k][j-k]-c90[i+k][j-k]==0) ans++;
}
else break;
}
for(int k=1;i-k>=1 && j-k>=1 && j+k<=m;k++)
{
if(!w[i-k][j+k] && !w[i-k][j-k])
{
if(c0[i-k][j+k]-c0[i-k][j-k]==0) ans++;
}
else break;
}
//cout<<i<<" "<<j<<"
ans:"<<ans<<endl;

}
}
}
printf("%dn",ans);
return 0;
}