准备Div.1和Div.2放在一起做个集锦,快要蓝桥杯了抱抱佛脚
A.Boboniu Likes to Color Balls
题目大意:给出三原色三种颜色的球,还有白色球,每次操作可以把三原色中的球各取一个变白,求是否能操作使这些球按一定顺序排列构成回文
Solution
球总数是奇数和偶数分开判断,是奇数则四种颜色仅有一种颜色是奇数就可以,偶数则所有颜色均为偶数就可以,我们可以发现每次操作改变一次奇偶性,所以最多进行两次操作即可判断
Code
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 59 60 61 |
#include<bits/stdc++.h> using namespace std; int T,r,g,b,w; bool check() { if (r && g && b) return true; return false; } int getnum() { int Count=0; if (r&1) ++Count; if (g&1) ++Count; if (b&1) ++Count; if (w&1) ++Count; return Count; } int main() { scanf("%d",&T); while (T--) { bool flag=false; int sum=0,Count=0; scanf("%d%d%d%d",&r,&g,&b,&w),sum=r+g+b+w; if (sum&1) { if (getnum()==1 && !flag) flag=true,cout<<"Yes"<<endl; if (check()) { --r,--g,--b,w+=3; if (getnum()==1 && !flag) flag=true,cout<<"Yes"<<endl; } if (check()) { --r,--g,--b,w+=3; if (getnum()==1 && !flag) flag=true,cout<<"Yes"<<endl; } if (!flag) flag=true,cout<<"No"<<endl; } else { if (!getnum() && !flag) flag=true,cout<<"Yes"<<endl; if (check()) { --r,--g,--b,w+=3; if (!getnum() && !flag) flag=true,cout<<"Yes"<<endl; } if (check()) { --r,--g,--b,w+=3; if (!getnum() && !flag) flag=true,cout<<"Yes"<<endl; } if (!flag) flag=true,cout<<"No"<<endl; } } return 0; } |
B.Boboniu Plays Chess
题目大意:给出一个的矩阵,每个矩阵的数互不相同,每次操作可以移动到当前行或者当前列的任一位置,给出起始位置,求矩阵每个数都经过一次的序列
Solution
既然可以在当前行或当前列任意跳,我们就直接把这行的跳完,行跳完跳列,直到行和列都被跳完时说明矩阵里的每一个位置都被跳过了,用数组来记录某行或者某列是否被跳完
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include<bits/stdc++.h> using namespace std; #define N 110 int n,m,Sx,Sy,row[N],column[N],px,py,sum=1; bool flag[N][N]; vector<pair<int,int>>ans; int main() { scanf("%d%d%d%d",&n,&m,&Sx,&Sy),ans.push_back(make_pair(Sx,Sy)),px=Sx,py=Sy,flag[px][py]=true,++row[px],++column[py]; while (sum!=n*m) { if (row[px]!=m) for (int i=1;i<=m;++i) if (!flag[px][i]) ++row[px],flag[px][i]=true,ans.push_back(make_pair(px,i)),py=i,++sum; if (column[py]!=n) for (int i=1;i<=n;++i) if (!flag[i][py]) ++column[py],flag[i][py]=true,ans.push_back(make_pair(i,py)),px=i,++sum; } for (int i=0;i<ans.size();++i) printf("%d %d\n",ans[i].first,ans[i].second); return 0; } |
C.Boboniu and Bit Operations
题目大意:给出和
两个序列,对于
,选择一个
(
),令
,使得
最小,求这个最小值
Solution
手玩了好久,还以为有什么规律,首先可以想到,如果序列中的数某个二进制位为
的话,在进行与操作后还是为
,所以我们的任务是尽可能使二进制位为
的在与操作变为
,这样在或操作时才能尽可能使所得的数小,想了好久,以为是个非常nb的贪心,结果发现答案范围在
区间内,
和
的数量级也为
,这才明白原来正解直接暴力枚举答案,然后暴力选择判断即可→_→
Code
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 |
#include<bits/stdc++.h> using namespace std; #define N 210 int n,m,a[N],b[N]; int main() { int num,ans; scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%d",&a[i]); for (int i=1;i<=m;++i) scanf("%d",&b[i]); for (ans=0;ans<(1<<9);++ans) { bool flag=true; for (int i=1;i<=n;++i) { num=0; for (int j=1;j<=m;++j) { int p=a[i]&b[j]; for (int k=0;k<=9;++k) if ((p&(1<<k)) && !(ans&(1<<k))) { ++num; break; } } if (num==m) { flag=false; break; } } if (flag) break; } return printf("%d",ans),0; } |
D.Boboniu Chats with Du
题目大意:给出个数,每天选择一个数,如果选的数大于
接下来的
天将不能再选,求选的所有数最大值
Solution
又是cf经典的思维题,很明显是个贪心,怎么才能更贪是这种题的精髓,我的思维过程在这里记录一下方便日后总结,首先想到将大于的从大到小排序,小于等于
的从小到大排序,用一个大于
的就会有
个小于等于
的不能用,用前缀和辅助判断是否选择这个大于
的,这种情况只针对小于等于
的数足够多,而小于等于
的数较少的话,完全可以用小于等于
的数进行填充,在最后一个再填上大于
的数,这种情况也并不全面,例如我们能够通过计算得知最多能填充多少个大于
的数,那么我们在选择前面几个大于
的数的时候可以选择用用不到的大于
的数进行消耗,使得最后能够填充的小于等于
的数尽可能多,说了这么多其实还不够清晰,网上有个大神的思路非常清晰,假设我们需要
个大于
的数,那么需要占
个位置,所以我们只需要考虑这个条件是否满足即可,剩下
个位置就直接从大到小填充小于
的数即可,需要注意的是
会爆
,还有需要特判没有大于等于
的情况
Code
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 |
#include<bits/stdc++.h> using namespace std; typedef long long LL; #define N 100010 int n,m,d,a[N],Min[N],t,Max[N],T; LL ans,MinSum[N],MaxSum[N]; bool cmp(int x,int y) { return x>y; } int main() { scanf("%d%d%d",&n,&d,&m); for (int i=1;i<=n;++i) { scanf("%d",&a[i]); if (a[i]<=m) Min[++t]=a[i]; else Max[++T]=a[i]; } sort(Min+1,Min+t+1,cmp),sort(Max+1,Max+T+1,cmp); for (int i=1;i<=t;++i) MinSum[i]=MinSum[i-1]+(LL)Min[i]; for (int i=1;i<=T;++i) MaxSum[i]=MaxSum[i-1]+(LL)Max[i]; for (int i=1;i<=T;++i) { int num; if ((LL)(i-1)*(d+1)+1>(LL)n) break; ans=max(ans,MaxSum[i]+MinSum[(num=n-(i-1)*(d+1)-1)>=t?t:num]); } if (!T) ans=MinSum[t]; return cout<<ans,0; } |