Practice link: https://codeforces.ml/contest/1395
A. Boboniu Likes to Color Balls
思路：要构成回文，就要至少有三个颜色的数量是偶数，那么只需要判断两种情况，就是一个都不减的情况和 r g b 三种颜色减一，w 加一时的情况。
代码：
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define MOD 1e9+7 4 #define INF 0x3f3f3f3f 5 #define mem(a,x) memset(a,x,sizeof(a)) 6 #define _for(i,a,b) for(int i=a; i< b; i++) 7 #define _rep(i,a,b) for(int i=a; i<=b; i++) 8 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 9 using namespace std; 10 const int NUM = 200005; 11 12 ll n,m; 13 int main() 14 { 15 int T; 16 scanf("%d",&T); 17 while(T--){ 18 int r,g,b,w; 19 cin>>r>>g>>b>>w; 20 if(r%2==1&&g%2==1&&b%2==1){ 21 cout<<"YES"<<endl; 22 }else{ 23 int sum=0; 24 if(r%2==1)sum++; 25 if(g%2==1)sum++; 26 if(b%2==1)sum++; 27 if(w%2==1)sum++; 28 if(sum<=1){ 29 cout<<"YES"<<endl; 30 }else{ 31 sum=0; 32 if(r*g*b!=0){ 33 r--; 34 g--; 35 b--; 36 w+=3; 37 if(r%2==1)sum++; 38 if(g%2==1)sum++; 39 if(b%2==1)sum++; 40 if(w%2==1)sum++; 41 if(sum<=1){ 42 cout<<"YES"<<endl; 43 }else{ 44 cout<<"NO"<<endl; 45 } 46 }else{ 47 cout<<"NO"<<endl; 48 } 49 50 } 51 } 52 } 53 return 0; 54 }
B. Boboniu Plays Chess
思路：条件只有 可以向这个方格的相同行和相同列移动，且输出没有重复的格子，但没有说一个格子只能经过一次，那么题目就很简单了，移动思路见下。
代码：
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define MOD 1e9+7 4 #define INF 0x3f3f3f3f 5 #define mem(a,x) memset(a,x,sizeof(a)) 6 #define _for(i,a,b) for(int i=a; i< b; i++) 7 #define _rep(i,a,b) for(int i=a; i<=b; i++) 8 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 9 using namespace std; 10 const int NUM = 200005; 11 12 int n,m,x,y; 13 int mp[105][105]; 14 int main() 15 { 16 mem(mp,0); 17 scanf("%d %d %d %d",&n,&m,&x,&y); 18 int num=0; 19 int px=x,py=1; 20 printf("%d %d ",x,y); 21 mp[x][y]=++num; 22 for(int i=1;i<=m;i++){ 23 if(mp[px][py]==0){ 24 printf("%d %d ",px,py); 25 mp[px][py]=++num; 26 } 27 py++; 28 } 29 py=m; 30 px--; 31 int xx=x*m; 32 while(num<xx){ 33 if(py==m){ 34 for(int i=m;i>=1;i--){ 35 printf("%d %d ",px,i); 36 mp[px][i]=++num; 37 } 38 py=1; 39 px--; 40 }else{ 41 for(int i=1;i<=m;i++){ 42 printf("%d %d ",px,i); 43 mp[px][i]=++num; 44 } 45 py=m; 46 px--; 47 } 48 } 49 px=x+1; 50 while(num<n*m){ 51 if(py==m){ 52 for(int i=m;i>=1;i--){ 53 printf("%d %d ",px,i); 54 mp[px][i]=++num; 55 } 56 py=1; 57 px++; 58 }else{ 59 for(int i=1;i<=m;i++){ 60 printf("%d %d ",px,i); 61 mp[px][i]=++num; 62 } 63 py=m; 64 px++; 65 } 66 } 67 return 0; 68 }
C. Boboniu and Bit Operations
思路：由于答案的范围很小，且两个数组也很小，那么考虑暴力枚举答案即可，范围是 0~(1<<9-1)，从小到大枚举就可以保证答案最小，只需要该范围内的某个 i 与 a 数组中的所有数与 b 数组中的某个数的或操作 结果为 i 即可。
代码：
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define MOD 1e9+7 4 #define INF 0x3f3f3f3f 5 #define mem(a,x) memset(a,x,sizeof(a)) 6 #define _for(i,a,b) for(int i=a; i< b; i++) 7 #define _rep(i,a,b) for(int i=a; i<=b; i++) 8 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 9 10 using namespace std; 11 const int NUM = 200005; 12 13 inline int rd() { 14 int res = 0,flag = 0; 15 char ch; 16 if ((ch = getchar()) == '-')flag = 1; 17 else if(ch >= '0' && ch <= '9')res = ch - '0'; 18 while ((ch = getchar()) >= '0' && ch <= '9')res = (res<<1) + (res<<3) + (ch - '0'); 19 return flag ? -res : res; 20 } 21 int n,m; 22 int a[205],b[205]; 23 int main() 24 { 25 n=rd(); 26 m=rd(); 27 for(int i=1;i<=n;i++){ 28 scanf("%d",&a[i]); 29 } 30 for(int i=1;i<=m;i++){ 31 scanf("%d",&b[i]); 32 } 33 for(int i=0;i<=(1<<9)-1;i++){ 34 int flag=1; 35 for(int j=1;j<=n;j++){ 36 int flag2=0; 37 for(int k=1;k<=m;k++){ 38 if((i|(a[j]&b[k]))==i){ 39 flag2=1; 40 break; 41 } 42 } 43 if(flag2==0){ 44 flag=0; 45 break; 46 } 47 } 48 if(flag){ 49 cout<<i<<endl; 50 return 0; 51 } 52 } 53 return 0; 54 }
D. Boboniu Chats with Du
思路：数据不大，枚举使用大于 m 的数的数量，首先将小于等于 m 和大于 m 的数分别存入两个数组，在将两个数组从大到小排序，在求前缀和，来保证每次枚举时的值最大，设 i 为大于 m 的值的数量，那么 i 个数中有一个数一定要在末尾才可以保证值最大，因为它不会让下面的数变成0，那么 i 个大于 m 的数让 (i - 1) * d 个数变成 0 ，则此时还有 min( x , n - (i - 1) * d - i )个 小于等于m的数 ，因此此时结果为 a[ i ] + b[ min( x , n - (i - 1) * d - i ) ] 。
还需要注意数据范围，防止在运算过程是越界。
代码：
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define MOD 1e9+7 4 #define INF 0x3f3f3f3f 5 #define mem(a,x) memset(a,x,sizeof(a)) 6 #define _for(i,a,b) for(int i=a; i< b; i++) 7 #define _rep(i,a,b) for(int i=a; i<=b; i++) 8 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 9 10 using namespace std; 11 const int MAXN = 100005 ; 12 13 inline int rd() { 14 int res = 0,flag = 0; 15 char ch; 16 if ((ch = getchar()) == '-')flag = 1; 17 else if(ch >= '0' && ch <= '9')res = ch - '0'; 18 while ((ch = getchar()) >= '0' && ch <= '9')res = (res<<1) + (res<<3) + (ch - '0'); 19 return flag ? -res : res; 20 } 21 int n,d,m; 22 ll a[MAXN]; 23 ll b[MAXN]; 24 bool cmp(ll x,ll y) 25 { 26 return x>y; 27 } 28 int main() 29 { 30 n=rd(); 31 d=rd(); 32 m=rd(); 33 ll z; 34 int x=0,y=0; 35 for(int i=1;i<=n;i++){ 36 scanf("%lld",&z); 37 if(z<=m)a[++x]=z; 38 else b[++y]=z; 39 } 40 sort(a+1,a+x+1,cmp); 41 sort(b+1,b+y+1,cmp); 42 for(int i=1;i<=x;i++)a[i]+=a[i-1]; 43 for(int i=1;i<=y;i++)b[i]+=b[i-1]; 44 ll ans=0; 45 for(int i=0;i<=y;i++){ 46 if(n-i<1ll*(i-1)*d)continue; 47 ll res=min((ll)x,(ll)n-i-(i-1)*d); 48 ans=max(1ll*a[res]+b[i],ans); 49 } 50 cout<<ans; 51 return 0; 52 }