A. Odd Selection
题目链接:https://codeforces.ml/contest/1363/problem/A
题目意思大概就是输入一个长度为n的数组,然后问能不能在这个数组中选择x个数,使其相加的和为奇数。
思考:
我们都知道,奇数+奇数=偶数
偶数+偶数=偶数
偶数+奇数=奇数
其中我们可以发现,一个数加上偶数并不会改变这个数的奇偶,再然后我们发现奇数个奇数相加为奇数,偶数个奇数相加为偶数.
这样我们就可以把x拆分为n1,n2,其中n1则为从数组中选择的奇数的个数,n2为选择偶数的个数
比赛时这道题想太久了,所以有点着急,代码写的有点乱
#include <iostream> using namespace std; int t,n,x,ji,ou; int a[1007]; int main(){ scanf("%d",&t); while(t--){ scanf("%d%d",&n,&x); ji=0,ou=0; for(int i=1;i<=n;i++){\\统计数组中奇数和偶数的个数 scanf("%d",&a[i]); if(a[i]%2==0) ou++; else ji++; } if(x%2==0){ int n1=x-1,n2=1,flag=0;\\将x拆分 while(n1>0){\\遍历拆分的x if(ji>=n1&&ou>=n2){ flag=1; } n1-=2,n2+=2; } if(flag) cout<<"Yes"<<endl; else cout<<"No"<<endl; }else{ int n1=x,n2=0,flag=0; while(n1>0){ if(ji>=n1&&ou>=n2){ flag=1; } n1-=2,n2+=2; } if(flag) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } }
B. Subsequence Hate
题目链接:https://codeforces.ml/contest/1363/problem/B
题目意思大概是输入一个由0或1组成的字符串,如果子序列不包含“101”或“010”则称作为好字符串,可以任意转换一个字符串的字符
则输入的字符串最少可以经过多少次修改得到好字符串
思考:从题中我们可以看出,要想得到好字符串,我们必须让其,字符串一边为0另一边为1,反之亦然,例如111000或000111或111111或000000
我们可以遍历所有好字符串,最后比较需其操作最少的。
#include <iostream> #include <cstring> using namespace std; int t; char s[1007]; int pre[1007]; int main(){ scanf("%d",&t); while(t--){ scanf("%s",s+1); int n=strlen(s+1); for(int i=0;i<=n;i++){ pre[i]=pre[i-1]+(s[i]=='1'); } int ans=9999; for(int i=0;i<=n;i++){ ans=min(ans,pre[i]+(n-i-(pre[n]-pre[i]))); ans=min(ans,i-pre[i]+(pre[n]-pre[i])); } cout<<ans<<endl; } }
C. Game On Leaves
题目链接:https://codeforces.ml/contest/1363/problem/C
思考: 如果特殊节点不是“叶子节点”,我们就把这个无根树中的特殊节点当做根节点,其中Ayush和Ashish就得从节点末端开始删节点,
通过观察我们发现只有当根节点只有两条边的才能删到根节点,那么Ayush和Ashish得从最深层数一层一层的删除(要把能删的都删了)
最多需要删除的节点数为n-1。
如果特殊节点是‘叶子节点’,那么直接是Ayush赢
#include <iostream> using namespace std; int t; int n,x,u,v; int main(){ scanf("%d",&t); while(t--){ scanf("%d %d",&n,&x); int b=0; for(int i=1;i<=n-1;i++){ scanf("%d %d",&u,&v); if(u==x||v==x) b++; } if(b<=1){ cout<<"Ayush"<<endl; }else{ if((n-1)%2==0) cout<<"Ashish"<<endl; else cout<<"Ayush"<<endl; }