Odd Selection 模拟
题意
给你一串数字，问你能不能挑x个数字，使和为奇数。
思路
- 不能的情况有：
- 这串数字里面奇数数量为0
- 所有数字都要选->所有奇数都要选，而且有偶数个奇数
- 所有都是奇数->所有奇数都要选，而且有偶数个奇数 //易忘
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN];
int main(){
int T,n,x;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&x);
int tot = 0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]&1) tot++;
}
if(!(tot&1)&&n==x) printf("No
");
else if(!tot) printf("No
");
else if(tot==n&&!(x&1)) printf("No
");
else printf("Yes
");
}
return 0;
}
Odd Selection 暴力 前缀和
题意
给你一个只有0和1的字符串，问你怎么样才能让字符串不含有字串'010'和'101'
思路
- 也就是变为'111000', '000111', '00000', '11111'这几种情况，全为一种数字，或者数字都在一边
- 全0，全1
- 可以用前缀和记录 前面有多少个1, a[i]=a[i-1]+1，或者a[i]=a[i-1]
- 然后计算以i为分界：即i前面全是1后面全是0，或者i前面全是0后面全是1的情况
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
char s[MAXN];
int a[MAXN];
int len;
int main()
{
int T;
scanf("%d",&T);
while(T--){
scanf("%s",&s);
len = strlen(s);
int ans=len;
int totx=0,toty=0;
memset(a,0,sizeof(0));
for(int i=0;i<len;i++){
if(s[i]=='1'){
a[i+1] = a[i]+1;
totx++;
}
else{
toty++;
a[i+1]=a[i];
}
}
ans = min(totx,toty);
for(int i=1;i<=len;i++){
ans = min(ans,i-a[i]+totx-a[i]); //111000
ans = min(ans,a[i]+(toty-(i-a[i])));//000111
}
printf("%d
",ans);
}
return 0;
}
Game On Leaves 博弈
题意
有一颗树，题目说：A tree is a connected undirected graph without cycles，所以这个树是可以有度数为0的点的。两个人可以删掉一个叶子然后删掉这个叶子带着的边，谁能删掉结点x，谁赢。Ayush是先手，Ashish是后手，问你谁赢。
思路
- 如果x是叶子(度数为1)，或者x的度数为0，则先手赢。
- 下面讨论x不是叶子的情况。
- 反向分析，最后一步肯定是x是叶子的情况，x-A这样。不可能只是x，因为这样的话上一个人根本不可能拿走A而不拿x，让自己输。
- 倒数第二步，应该是A-x-B这样，因为大家的目标都是让x的度数不为1，即不让x为叶子结点，因为如果自己让x为叶子结点，那么下个人就可以赢了。
- 所以判断结点数n的奇偶，如果n为奇数，则后手赢，否则先手赢。
代码
#include<bits/stdc++.h>
using namespace std;
int T,n,x;
const int MAXN=1005;
int deg[MAXN];
int main()
{
scanf("%d",&T);
while(T--){
memset(deg,0,sizeof(deg));
scanf("%d%d",&n,&x);
int a,b;
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
deg[a]++;
deg[b]++;
}
if(deg[x]==1||!deg[x])
printf("Ayush
");
else if(n&1){
printf("Ashish
");
}
else printf("Ayush
");
}
return 0;
}