(Codeforces) (Round) (632)
A. Little Artem
(Description:)
(n)行(m)列的表格，每个格子可以染成黑色或白色
记(W)为周围没有黑格子的白格子数
记(B)为周围没有白格子的黑格子数
要求构造出一种染色方案，使得(B=W+1)
(Solution:)
小学奥数题
直接将第一行第一列染成白色，其他的都染成黑色
此时(W=1)，(B=2)
显然该方案对所有尺寸的表格都成立
(Code:)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,t;
int main(){
int i,j;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
printf("W");
for(i=2;i<=m;i++)printf("B");
printf("
");
for(i=2;i<=n;i++){
for(j=1;j<=m;j++)
printf("B");
printf("
");
}
}
return 0;
}
B. Kind Anton
(Description:)
给定一个长度为(n)的数组(a_n)((a_iinlbrace-1,0,1 brace))
每次操作可以将(a)中的任意一元素(a_i)累加到其后方的(a_j)上((i<j))
问经过任意次操作之后，能否将(a)转变成数组(b)
(Solution:)
由于(a)中元素只有(1,0,-1)三种取值，不难发现以下两点：
1.若一个数前面有(1)，那么它可以变成任何一个比它大的整数
2.若一个数前面有(-1)，那么它可以变成任何一个比它小的整数
那么我们就只需要比较(a_i)和(b_i)的大小关系，然后再统计一下(1)和(-1)的出现情况即可。
(Code:)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,t,a[100005],b[100005];
int main(){
int i,j;
scanf("%d",&t);
while(t--){
int f1=0,f2=0;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)scanf("%d",&b[i]);
int flag=1;
for(i=1;i<=n;i++){
if(f1&&f2)break;
if(b[i]>a[i]&&f1==0){flag=0;break;}
if(b[i]<a[i]&&f2==0){flag=0;break;}
if(a[i]==1)f1=1;
if(a[i]==-1)f2=1;
}
if(flag)printf("YES
");
else printf("NO
");
}
return 0;
}
C. Eugene and an array
(Description:)
给定一个长度为(n)的数组，求其中所有子列的和都不为零的子列的个数
(Solution:)
考虑子列的两个端点(l)和(r)，以下令((l,r))表示左端点为(l)，右端点为(r)的子列，容易得到以下结论：
1.如果当前子列不合法，那么包含当前子列的所有子列都不合法
2.如果当前子列合法，那么它的所有子列都合法
3.若((l,r+1))合法，那么其相较于((l,r))所增加的合法子列为数(r-l+1)
于是得到如下算法：
1.预处理出前缀和，然后排序，再进行编号，以方便统计
2.对于当前的左右端点(l)和(r)，尽可能的将(r)右移，直到当前子列不合法，每次右移更新答案
3.将(l)右移，直到当前子列合法
4.重复第(2)，(3)步，直到遍历完整个数组
5.输出答案
(Code:)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>//kai long long
using namespace std;
typedef long long lol;
int n,a[200005],cnt[200005];
lol ans;
struct node{
lol sum;
int x,k;
}b[200005];
bool cmp1(const node a,const node b){return a.sum<b.sum;}
bool cmp2(const node a,const node b){return a.x<b.x;}
int main(){
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++){
b[i].sum=b[i-1].sum+a[i];
b[i].x=i;
}
sort(b,b+n+1,cmp1);
for(i=0,j=0;i<=n;i++)
if(i==0||b[i].sum!=b[i-1].sum)b[i].k=++j;
else b[i].k=j;
sort(b,b+n+1,cmp2);
cnt[b[0].k]++;
i=1;j=0;
while(1){
while(cnt[b[j+1].k]==0){
j++;
cnt[b[j].k]++;
ans+=j-i+1;
if(j>=n)break;
}
if(j>=n)break;
while(cnt[b[j+1].k]){
cnt[b[i-1].k]--;
i++;
}
}
printf("%lld
",ans);
return 0;
}
D. Challenges in school №41
(Description:)
一些小孩子上课不听讲左右乱看
给出小孩子的个数(n)，并给出他们看向的方向((L) (or) (R))
每次操作可以选出一对或几对当前正在深情对视的相邻的小孩子，并将他们反向
问能否经过(k)次操作使得不再有小孩子深情对视
(Solution:)
设每次调转两个小孩子的方向为一次调整，并将当前状态下所有小孩子反向设为一轮操作
不难发现，调整的次数是确定的，不会随顺序的变化而变化
对于(n)个小孩子，操作的论述不会超过(n-1)
于是统计出调整的次数(sum)，需要操作的轮数(max)，并记录每次调整的位置
如果(sumgeq k)并且(kgeq max)，则一定有解，输出一组解即可
其他情况无解
(Code:)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,ans[3005][3005],cnt[3005],sum,mmax;
char s[3005];
int main(){
int i,j,k,len,o;
scanf("%d%d",&n,&m);
scanf("%s",s+1);
len=strlen(s+1);
for(i=1;i<n;i++){
j=1;
while(j<=n){
if(s[j]=='R'&&s[j+1]=='L'){
swap(s[j],s[j+1]);
ans[i][++cnt[i]]=j;
j+=2;
}
else j++;
}
sum+=cnt[i];
if(cnt[i])mmax=i;
}
if(sum<m||m<mmax){
printf("-1
");
return 0;
}
else{
int need=sum-m;
j=1;k=1;
for(i=1;i<=m;i++){
if(need==0){
printf("%d %d
",1,ans[j][k]);
k++;
if(k>cnt[j]){j++;k=1;}
}
else{
int s=min(need,cnt[j]-k);
need-=s;
printf("%d ",s+1);
for(k,o=k+s;k<=o;k++)printf("%d ",ans[j][k]);
printf("
");
if(k>cnt[j]){j++;k=1;}
}
}
}
return 0;
}
E. Road to 1600
(Description:)
构造一个(n*n)的棋盘，上面写着数字(1)~(n*n)，然后有一个“车”一个“后”，棋子都遵循下面的规则移动：
1.若(1)步移动可达的格子中有未遍历的，则选择未遍历的格子中数字最小的格子移动。
2.若(1)步移动可达的格子全部被遍历过，若还有未遍历的格子，则选择未遍历的格子中数字最小的格子传送。
棋子一开始在(1)号格，并且视作已经遍历了(1)号格。
构造的棋盘要使得“车”的传送次数严格小于“后”的传送次数。
(Solution:)
(nleq 2)时，显然无解，因为这种情况下“后”的传送次数为0，下面讨论其他情况
考虑到“后”与“车”的不同点在于“后”可以沿对角方向走，我们可以得到大致思路：
用斜方向上的数将“后”勾引走，使得“后”最后需要通过传送才能到达终点，而“车”不用
（本蒟蒻也只能想到这个大致思路了，代码参考了CF上的AC代码，构造很神奇，等官方解释吧）
(Code:)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,a[505][505];
int main(){
int i,j;
scanf("%d",&n);
if(n<=2){
printf("-1
");
return 0;
}
a[1][n-1]=n*n;
for(i=1;i<n;i++)
a[i][n]=n*n-i-1;
a[n][n]=n*n-1;
int cnt=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(!a[i][j])a[i][j]=++cnt;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
printf("%d ",a[i][j]);
printf("
");
}
return 0;
}
F. Kate and imperfection
(Description:)
给定一个数(n)，输出(n-1)个数
第(i)个数表示在区间([1,n])中选出一个(i)元组，使得这(i)个数两两之间(gcd)的最大值最小，输出这个最小值
(Solution:)
构造这样一个集合，要使gcd的最大值最小，首先就把所有的素数全部放进去，这样最小值就是1
然后再放进去使得最小值变成2的数，然后是3、4等等
如果我们放进去一个合数，那么它的所有约数必定已经在集合里
不难发现这是一个埃氏筛法的过程，所以用埃氏筛法维护一下这个贪心
然后排序之后输出即可
(Code:)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int isprime[500005],size,prime[500005],ans[500005];
int main(){
int n,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)ans[i]=1;
for(i=2;i<=n;i++)
for(j=i*2;j<=n;j+=i)
ans[j]=i;
sort(ans+1,ans+n+1);
for(i=2;i<=n;i++)printf("%d ",ans[i]);
printf("
");
return 0;
}
BBT
T1一个小学奥数题居然想了十分钟
T3码了大半天都没码出来，代码还贼丑，像个弱智一样
T4居然能看错题，第二天早上十分钟就做出来了
T5T6就看了一眼题。。。
退役两年的OI选手还真就可以菜得体无完肤呗~