今天来打个div4。
A. Division?
题目描述
题目分析
这应该是描述了 cf
四个层次比赛的最高积分要求,超过将 unrated
进行比赛。直接按他的要求把四个等级判断输出一下就好了。
标程
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| #include<bits/stdc++.h> using namespace std; char a[50][50]; void solve(){ int n; cin>>n; int k=0; if(n<=1399){ k=4; } else if(n<=1599){ k=3; } else if(n<=1899){ k=2; } else{ k=1; } printf("Division %d\n",k); } int main(){ #ifndef ONLINE_JUDGE freopen("1.in","r",stdin); #endif int t=1; cin>>t; while(t--)solve();
return 0; }
|
B. Triple
题目描述
题目分析
随便输出一个出现过三次的数就好了,但是要注意出现之后不要马上结束,把剩下的输入读完。
标程
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| #include<bits/stdc++.h> using namespace std; map<int,int>ma; void solve(){ int n; cin>>n; map<int,int>().swap(ma); int flag=0; for(int i=1;i<=n;i++){ int x; cin>>x; if(!flag){ ma[x]++; if(ma[x]==3){ printf("%d\n",x); flag=1; } } } if(!flag){ puts("-1"); } } int main(){ #ifndef ONLINE_JUDGE freopen("1.in","r",stdin); #endif int t=1; cin>>t; while(t--)solve(); return 0; }
|
C. Odd/Even Increments
题目描述
题目分析
偶数位置或者奇数位置同时+1,问能否达到全奇数或者全偶数的状态,直接判断奇数位置上是否全为奇数或者全为偶数和偶数位置上是否全为奇数或者全为偶数即可。
标程
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| #include<bits/stdc++.h> using namespace std; map<int,int>ma; int a[200005]; void solve(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } if(n<=2){ puts("YES"); return ; } for(int i=3;i<=n;i+=2){ if(a[i]%2!=a[i-2]%2){ puts("NO"); return ; } } for(int i=4;i<=n;i+=2){ if(a[i]%2!=a[i-2]%2){ puts("NO"); return ; } } puts("YES"); } int main(){ #ifndef ONLINE_JUDGE freopen("1.in","r",stdin); #endif int t=1; cin>>t; while(t--)solve(); return 0; }
|
D. Colorful Stamp
题目描述
题目分析
有一个长度为2的红蓝印章,每次打印上去可以使相邻两个格子的颜色一个为红,一个为蓝,颜色可以覆盖。那么格子将出现三种状态:白,红,蓝。我们以白色方格作为分割,容易发现不可能存在长度为1的红色或者蓝色色块,所以只有一个格子的时候那个格子必为白色,不可能是红色或者蓝色。对于一个连续的色块,可以发现必须同时存在蓝色和红色。因此只要所有的连续色块满足这个要求就可以啦。
标程
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
| #include<bits/stdc++.h> using namespace std; map<int,int>ma; char s[200005]; void solve(){ int n; cin>>n; scanf("%s",s); if(n==1){ if(s[0]=='W'){ puts("YES"); } else{ puts("NO"); } return ; } s[n++]='W'; int flag=0,len=0; for(int i=0;i<n;i++){ if(s[i]=='W'){ if(len==1){ puts("NO"); return ; } if(len>1&&flag!=3){ puts("NO"); return ; } len=0; flag=0; } else{ len++; if(s[i]=='R'){ flag|=1; } if(s[i]=='B'){ flag|=2; } } } puts("YES"); } int main(){ #ifndef ONLINE_JUDGE freopen("1.in","r",stdin); #endif int t=1; cin>>t; while(t--)solve(); return 0; }
|
E. 2-Letter Strings
题目描述
题目分析
给定若干个长度只有2的字符串,要求输出符合要求的对数,要求为两对字符串有且仅有1个位置字符不一样。由于数据点较小,我们很容易想到把字符串转int类型比较,由于字符只有11种,理论上可以一个char压缩字符串,但是我选择用short进行,因为复杂度绰绰有余。
然后对于转换成的整数类型进行比较,若发现高位或者低位相同,则将答案加上 $num[i]*num[j]$,题目已经提示long long,其它的也没啥了。
标程
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| #include<bits/stdc++.h> using namespace std; map<int,int>ma; const int N=3000; int a[N+10]; void solve(){ int n; cin>>n; char s[5]; memset(a,0,sizeof(a)); for(int i=1;i<=n;i++){ scanf("%s",s); a[((s[0]-'a')<<8)|(s[1]-'a')]++; } long long ans=0; for(int i=0;i<N;i++){ for(int j=i+1;j<=N;j++){ if( (i&0x0000ff00)==(j&0x0000ff00)||(i&0x000000ff)==(j&0x000000ff) ){ if(a[i]&&a[j]){ ans+=1ll*a[i]*a[j]; } } } } printf("%lld\n",ans); } int main(){ #ifndef ONLINE_JUDGE freopen("1.in","r",stdin); #endif int t=1; cin>>t; while(t--)solve(); return 0; }
|
F. Eating Candies
题目描述
题目分析
就是一个人只能从左吃,另一个人只能从右开始吃,问最后吃的重量一样的情况下的最多糖果。这个直接贪心好了,如果左边人少了那就左边的人吃,否则右边的人吃,一旦重量一样了保存结果,最后输出即可。
标程
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| #include<bits/stdc++.h> using namespace std; map<int,int>ma; const int N=2e5; int w[N+10]; void solve(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>w[i]; } int i=1,j=n; int a=0,b=0,ans=0; while(i<=j){ if(a==b){ ans=i-1+n-j; } if(a<b){ a+=w[i]; i++; } else{ b+=w[j]; j--; } } if(a==b)ans=n; printf("%d\n",ans); } int main(){ #ifndef ONLINE_JUDGE freopen("1.in","r",stdin); #endif int t=1; cin>>t; while(t--)solve(); return 0; }
|
G. Fall Down
题目描述
题目分析
模拟题,直接按要求下落石块就行,注意判断一下下落条件即可。
标程
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| #include<bits/stdc++.h> using namespace std; map<int,int>ma; int a[55][55]; int n,m; void fall(int x,int y){ while(y!=n&&a[y+1][x]=='.'){ a[y][x]='.'; y++; a[y][x]='*'; } } void solve(){ cin>>n>>m; string s; for(int i=1;i<=n;i++){ cin>>s; for(int j=1;j<=m;j++){ a[i][j]=s[j-1]; } } for(int i=n-1;i>=1;i--){ for(int j=1;j<=m;j++){ if(a[i][j]=='*'){ fall(j,i); } } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ putchar(a[i][j]); } putchar(10); } puts(""); } int main(){ #ifndef ONLINE_JUDGE freopen("1.in","r",stdin); #endif int t=1; cin>>t; while(t--)solve(); return 0; }
|
H. Maximal AND
题目描述
题目分析
有k次机会让某一个数的二进制位变成1,最后求所有数的与最大值。我们直接统计所有位的情况,从最高位开始,如果当前k的值允许变为全1则直接给了,然后答案加上那一位即可。
标程
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| #include<bits/stdc++.h> using namespace std; map<int,int>ma; int a[60]; void get_bit(int x){ int i=0; while(x){ if(x&1){ a[i]++; } x>>=1; i++; } }
void solve(){ int n,k; cin>>n>>k; memset(a,0,sizeof(a)); for(int i=1;i<=n;i++){ int x; cin>>x; get_bit(x); } int ans=0; for(int i=30;i>=0;i--){ if(k>=n-a[i]){ k-=n-a[i]; ans|=(1<<i); } } printf("%d\n",ans); } int main(){ #ifndef ONLINE_JUDGE freopen("1.in","r",stdin); #endif int t=1; cin>>t; while(t--)solve(); return 0; }
|
第一次在cf上ak,也算成功吧,虽然都挺简单的hhh。