A
题意
n个数挑x个 能不能令其和为奇数
题解
判断一下奇偶数个数即可
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
| #include<cstdio>
#include<algorithm>
using namespace std;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,x;
scanf("%d%d",&n,&x);
int odd=0,even=0,tmp;
for(int i=0;i<n;++i){
scanf("%d",&tmp);
if(tmp&1){
++odd;
}else{
++even;
}
}
bool can=1;
if(odd==0){
can=0;
}else{
int oddpair=(odd-1)/2*2;
int need=(x-1)/2*2;
int actual=min(need,oddpair);
if((x-1-actual)>even){
can=0;
}
}
if(can){
printf("Yes\n");
}else{
printf("No\n");
}
}
return 0;
}
|
B
题意
给一个01串 一次操作可以把0变1 反之亦然 最少操作几次能让序列不出现101 010 的格式
题解
实际就是要将串转化为从某个分界点开始 向前全为0或1，向后全为0或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
| #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int main(){
int T;
scanf("%d",&T);
char dat[1020];
int num[1020][2];
while(T--){
scanf("%s",dat);
int n=strlen(dat);
if(n<3){
printf("0\n");
continue;
}
num[0][0]=0,num[0][1]=0;
for(int i=0;i<n;++i){
if(dat[i]=='0'){
num[i+1][0]=num[i][0]+1;
num[i+1][1]=num[i][1];
}else{
num[i+1][0]=num[i][0];
num[i+1][1]=num[i][1]+1;
}
}
int ans=1040;
for(int i=0;i<=n;++i){
ans=min(ans,num[i][1]+num[n][0]-num[i][0]);
ans=min(ans,num[i][0]+num[n][1]-num[i][1]);
}
printf("%d\n",ans);
}
return 0;
}
|
C
题意
给一颗树 每次只能取叶子节点 谁取到x节点谁赢 问谁能赢
题解
。。太菜了。。这里开始想不透了 开始看题解。。
好吧又是我想复杂了。。实际上很简单 如果要求得x已经是叶子节点 那么显然是先手直接获胜 其他情况 只需要数孩子节点个数就能够知道是谁胜出了 因为实际上每种形式都可以从最简单的三节点取中间节点的模型通过一步步加节点转化来 加一个必胜态必败态转变一次。。就很显然了。。
D
题意
n个元素的数组 分成k个互不相交的子集 给你每个子集包含元素的index 要求的结果串长度为k，每一位是去除对应子集的所有元素的最大值，可以做最多12次查询，每次给定要查的index而后返回这些index中最大值
题解
有一个点很关键 想通了就很好解决。。因为所有数组有一个最大值 只会包含在一个子集里 所以所有除了这个子集的最大值都是固定的 可以通过二分来查 10次查询能够确定 除此以外 查一次所有元素最大值 查一次除了最大值子集的最大值 12次查询正好够使用