比赛链接
A. Tetris
题目大意
长度为nn的序列，操作为：在aiai位置+1，如果序列的每个位置都有值，那么每个位置减一同时答案加1，重复操作指导有一个位置为0为止。重复mm次。
思路
这道题……按题目过程模拟。O(nm)O(nm)。
也可以将所有的操作都处理完后一次回答询问。O(n+m)O(n+m)。 话说我当时用的居然是O(nm)O(nm)算法？代码
#includeconst int maxn=1000;int a[maxn+10],n,m,ans;int main(){ scanf("%d%d",&n,&m); while(m--) { int pos,flag=1; scanf("%d",&pos); ++a[pos]; for(register int i=1; i<=n; ++i) { if(a[i]==0) { flag=0; break; } } if(flag) { ++ans; for(register int i=1; i<=n; ++i) { --a[i]; } } } printf("%d\n",ans); return 0;}
B. Lecture Sleep
题目大意
两个长度为nn的序列ai,biai,bi，bibi为0或1，可以使用一次操作使得b[m,m+k−1]b[m,m+k−1]全部变成1，求∑ni=1aibi∑i=1naibi的最大值。
思路
一开始把所有的bi=1bi=1的aiai全都设成0并加入答案，然后枚举mm，计算a[m,m+k−1]a[m,m+k−1]，用前缀和优化，O(n)O(n)。
代码
#include#include const int maxn=100000;int n,k,a[maxn+10],t[maxn+10],cnt,sum[maxn+10],ans;int main(){ scanf("%d%d",&n,&k); for(register int i=1; i<=n; ++i) { scanf("%d",&a[i]); } for(register int i=1; i<=n; ++i) { scanf("%d",&t[i]); if(t[i]) { cnt+=a[i]; a[i]=0; } } sum[0]=0; for(register int i=1; i<=n; ++i) { sum[i]=sum[i-1]+a[i]; } for(register int i=1; i<=n-k+1; ++i) { ans=std::max(ans,cnt+sum[i+k-1]-sum[i-1]); } printf("%d\n",ans); return 0;}
C. Chessboard
题目大意
给你一个黑白组成的4个矩形，大小都为n×nn×n，nn为奇数。问如何将它们拼成1个黑白交替的棋盘，使得将黑染成白，白染成黑的合计次数最小。
不允许翻转和旋转。思路
显然一个黑白交替的棋盘它的4个部分也是黑白交替的，这样我们只需要枚举每个部分的左上角是黑还是白。
预处理出每个部分左上角变成黑色和白色需要染色的次数。完整的棋盘，每个部分左上角的颜色，一定是两个黑两个白。压缩状态并枚举状态即可。 O(n)O(n)代码
#include#include #include const int maxn=200;const int inf=0x3f3f3f3f;int a[4][maxn+10][maxn+10],n,wt[4][2],ans;inline int cnt_bit(int x){ int res=0; while(x) { res+=x&1; x>>=1; } return res;}int main(){ scanf("%d",&n); char ch=getchar(); for(register int i=0; i<4; ++i) { for(register int j=1; j<=n; ++j) { for(register int k=1; k<=n; ++k) { while((ch<'0')||(ch>'9')) { ch=getchar(); } a[i][j][k]=ch-'0'; ch=getchar(); } } } for(register int i=0; i<4; ++i) { for(register int j=0; j<2; ++j) { for(register int k=1; k<=n; ++k) { for(register int l=1; l<=n; ++l) { if((k+l+j)%2!=a[i][k][l]) { ++wt[i][j]; } } } } } ans=inf; for(register int i=0; i<16; ++i) { if(cnt_bit(i)==2) { int res=0; for(register int j=0; j<4; ++j) { res+=wt[j][(i>>j)&1]; } ans=std::min(ans,res); } } printf("%d\n",ans); return 0;}
D. Pair Of Lines
题目大意
给你nn个点，问这nn个点是否能被两条直线覆盖。
思路
这道题是我赛后hack时研究别人代码做出来的。
代码
#include#include const int maxn=100000;struct point{ int x,y;};point p[maxn+10];int n,used[maxn+10];inline int one_line(int a,int b,int c){ if((a==0)||(b==0)||(c==0)) { return 1; } return 1ll*(p[c].x-p[a].x)*(p[b].y-p[a].y)==1ll*(p[c].y-p[a].y)*(p[b].x-p[a].x);}int check(int a,int b){ memset(used,0,sizeof used); used[a]=used[b]=1; for(register int i=1; i<=n; ++i) { if((!used[i])&&(one_line(a,b,i))) { used[i]=1; } } int u=0,v=0,w=0,flag=1; for(register int i=1; i<=n; ++i) { if(!used[i]) { u=v; v=w; w=i; if(!one_line(u,v,w)) { flag=0; break; } } } return flag;}int main(){ scanf("%d",&n); for(register int i=1; i<=n; ++i) { scanf("%d%d",&p[i].x,&p[i].y); } if(check(1,2)||check(2,3)||check(1,3)) { puts("YES"); } else { puts("NO"); } return 0;}
后面的题
E貌似很可写，FG没有看，不过估计不可写，有时间再去写吧。