题目传送门

A. Odd Selection

分析

• 题意

1. 从n个数中选择m个数，问能使这个m个数的和位奇数？

• 思路

2. 首先对于这个n个数我们可以统计出其中的 奇数与偶数 的数量分别设为 x、y，
3. 如果要想让m个数想加位奇数的话，在m个数中，奇数的数量必须是 奇数个，而偶数的数量 奇、偶对答案都不会有影响（前提是 奇数量 + 偶数量 = m），
4. 那么一种是思路是我们考虑 奇数的数量 在m个数中，尽可能的多使用奇数，这样对偶数的需求数量就减少了，这样更容易得出ans ，首先我们令 x = min(x, m) ,因为奇数的数量> m是没有意义的，然后我们要特殊考虑 这个时候如果 x偶数的话，我们在令 x-=1，这样就一定保证了 使用的奇数数量是 奇数个，
5. 之后我们只需要检测 偶数的数量y是否 >= m-x,如果是的话 就输出yes

代码

#include <bits/stdc++.h> using namespace std; void fre() { freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); } void Fre() { freopen("A.txt", "r", stdin);} #define ios ios::sync_with_stdio(false) #define Pi acos(-1) #define pb push_back #define fi first #define se second #define ll long long #define ull unsigned long long  #define db double #define Pir pair<int, int> #define PIR pair<Pir, Pir> #define INF 0x3f3f3f3f #define mod 998244353 const int mxn = 2e5 + 10; int ar[mxn]; int main() { /* fre(); */ int T; scanf("%d", &T); while(T --) { int n, x; scanf("%d %d", &n, &x); int odd = 0, eve = 0; for(int i = 1; i <= n; i ++) { scanf("%d", &ar[i]); if(ar[i] % 2) odd ++; else eve ++; }          odd = min(odd, x); if(odd % 2 == 0) odd --; if(odd > 0 && odd + eve >= x) printf("Yesn"); else printf("Non"); } return 0; } 

B. Subsequence Hate(前后缀和)

分析

• 题意

1. 给我们一个有0、1组成的字符串s，我们可以对其中的元素进行变化操作，把0变成1或1变成0，问最少需要多少次这样的变换操作，是s中所有 子序列 中不会出现 010、101 的情况

• 思路

2. 我们考虑 什么样的 字符串 才不会出现 子序列存在 010、101的情况？

   1. 元素全为 0 的字符串
   2. 元素全为 1 的字符串
   3. 字符串 前半部分全为0，后半部分全为1
   4. 字符串 前半部分全为1，后半部分全为0

3. 其中我们 可以认为 情况 1. 、2. 分别为 3. 、4. 情况的特殊情况，所以只要考虑 3.、4.情况，

4. 对于3情况，我们预处理 前缀1的数量p1[i],在预处理后缀0的数量s0[i],这样我们我们循环遍历每一个i位置把i位置之前的1都变成0，把i以及其之后的位置的0都变成1，用预处理的 数据计算出花费的代价，在遍历的时候维护 代价的最小值

5. 对与4.情况我们 同样进行预处理，同样的循环维护最小花费，

6. 最终 就是两种的 花费的最小值就是答案

代码

#include <bits/stdc++.h> using namespace std; void fre() { freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); } void Fre() { freopen("A.txt", "r", stdin);} #define ios ios::sync_with_stdio(false) #define Pi acos(-1) #define pb push_back #define fi first #define se second #define ll long long #define ull unsigned long long  #define db double #define Pir pair<int, int> #define PIR pair<Pir, Pir> #define INF 0x3f3f3f3f #define mod 998244353 const int mxn = 2e3 + 10; int p0[mxn], p1[mxn]; int s0[mxn], s1[mxn]; char ar[mxn]; int main() { /* fre(); */ int T; scanf("%d", &T); while(T --) { scanf("%s", ar + 1); int n = strlen(ar + 1); for(int i = 1; i <= n; i ++) {             p0[i] = p0[i - 1];             p1[i] = p1[i - 1]; if(ar[i] == '0')                 p0[i] ++; else                 p1[i] ++; }          s0[n + 1] = 0;         s1[n + 1] = 0; for(int i = n; i >= 1; i --) {             s0[i] = s0[i + 1];             s1[i] = s1[i + 1]; if(ar[i] == '0')                 s0[i] ++; else                 s1[i] ++; } int ans = INF; for(int i = 1; i <= n; i ++) {             ans = min(ans, p1[i - 1] + s0[i]);             ans = min(ans, p0[i - 1] + s1[i]); }         ans = min(ans, p0[n]); printf("%dn", ans); } return 0; } 

C. Game On Leaves（贪心+博弈？）

分析

• 题意

1. 给我们一个n个节点的无根树，玩家A、B轮流操作，对于每次操作玩家可以选择 这棵树的一个叶子节点，把它摘去，谁先摘去 x 节点那个玩家就获胜？在问A先手，他们都已最优的状态比赛情况下

• 思路

2. 首先我们 考虑特殊情况，如果 x节点的入度位 0、1时（对应 树只有一个姐节点、x节点为叶子🍃节点），玩家A可以直接摘去x，则A必胜
3. 去除上面特殊情况以后，我们把x看做根节点，最后分出胜负的一定是，还剩下两个节点（x和 与x相连的一个节点）的时候，这个时候 该那个玩家出手，那个玩家获胜，
4. 证明：为什么一定是剩余两个节点？，我们假设一个例子：

x-1-3
|
4-5-6

我们假设 叶子的节点的深度为0，那么其它叶子节点的深度都是确定的，，，
我们之后在假设，A先后 摘取了一个深度位2的节点（3节点），这个时候，聪明的B玩家肯定不会选择深度为1节点（如果选择了话 A直接就赢了），它可定会选择6节点；之后聪明的A也肯定不会选择深度为1的节点，它肯定会选择深度 > 1 的节点，这样防止对手直接获胜，就这样一直轮流操作下去…，总回出现剩余两最后两个节点的情况，，，

我们在考虑这种情况，玩家a不得不选择摘去一个深度为1的节点（假设摘去的节点为1），但是这个时候另一个玩家b是没法立刻就直接摘去x节点，因此此时x的度为2，表明x还不是叶子节点，所以没法摘，所以b玩家只能被迫摘去深度为1的🍃叶子节点（设为2）,那么这个时候又出现了最后两个叶子节点分胜负的 情况了
3-x-1
|
2
通过两个特殊的例子 大概的证明出了 最后一定会剩余2个节点，而其它的节点都被玩家再去了，综上 当 （n – 1) % 2 为奇数的时候先手玩家获胜，否则后手获胜

代码

#include <bits/stdc++.h> using namespace std; void fre() { freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); } void Fre() { freopen("A.txt", "r", stdin);} #define ios ios::sync_with_stdio(false) #define Pi acos(-1) #define pb push_back #define fi first #define se second #define ll long long #define ull unsigned long long  #define db double #define Pir pair<int, int> #define PIR pair<Pir, Pir> #define INF 0x3f3f3f3f #define mod (ll)(1e9 + 7) const int mxn = 2e5 + 10; int in[mxn]; int main() { /* fre(); */ int T; scanf("%d", &T); while(T --) { int n, x; scanf("%d %d", &n, &x); for(int i = 1, u, v; i < n; i ++) { scanf("%d %d", &u, &v);             in[u] ++, in[v] ++; } if(in[x] <= 1 || (n - 1) % 2) printf("Ayushn"); else printf("Ashishn"); memset(in, 0, n * 4 + 4); } return 0; } 

D. Guess The Maximums（交互题 + 二分）

分析

• 题意

1. 首先有一个长度为n的序列A，我们只知道A中元素的值在[1,n]之间（A中元素之间可以相同），之后又给我们k个序列分别为：s1 s2 … sk,这个k个序列的元素值各不相同(这题的突破口)si序列中的元素值为 A中元素的下标,先我们从这个k个序列中得出我们的长度为k的密码p序列，第i为密码为pi为 不在si序列中的序列A的下标以外的A中其它元素的最大值，
2. 我们可以 与题目交互 不超过12次（这个这么少的次数 能提醒我们用 二分法），对于每次交互，我们 可以输入一些列的A中元素的下标，系统返回这些下标所代表的最大值，让我们求出中密码p序列

• 思路

3. 首先用一次 将所有下标输出，来的出 整个A序列的最大值吗mx，
4. 用10次二分去求出 mx 在A中的下标设为idx，（注意：A中的由于元素可以重复，所以最大值mx可以有多个，说明idx坐标也有多个，这并不影响做题，我们只要求出其中一个就行了，这是因为 k个s序列中的元素各不相同，也就是只可能有一个si序列包含 idx，对这个序列我们单独的用 一次询问 去得出这个位置i出的密码pi，对于与其它位置它的密码pj（j != i,1<=j<=k）最大值就已经确定了，就是mx）

代码

#include <bits/stdc++.h> using namespace std; void fre() { freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); } void Fre() { freopen("A.txt", "r", stdin);} #define ios ios::sync_with_stdio(false) #define Pi acos(-1) #define pb push_back #define fi first #define se second #define ll long long #define ull unsigned long long  #define db double #define Pir pair<int, int> #define PIR pair<Pir, Pir> #define INF 0x3f3f3f3f #define mod 998244353 const int mxn = 2e3 + 10; vector<int> s[mxn]; int query(int n) { printf("? %d", n); for(int i = 1; i <= n; i ++) printf(" %d", i); printf("n"); fflush(stdout); //cout.flush(); int res; scanf("%d", &res); return res; } int n, k, mx; int find_max() {     mx = query(n); int l = 1, r = n; while(l < r) { int mid = (l + r) >> 1; if(query(mid) != mx)             l = mid + 1; else             r = mid; } return l; } void get_ans() {     vector<int> ans; int idx = find_max(); //最大值下标 for(int i = 1; i <= k; i ++) { auto it = find(s[i].begin(), s[i].end(), idx); if(it == s[i].end())             ans.pb(mx); else {             map<int, int> mk; for(auto x : s[i])                 mk[x] = 1; printf("? %lu", n - mk.size()); for(int j = 1; j <= n; j ++) { if(! mk[j]) printf(" %d", j); } printf("n"); fflush(stdout); int t_mx; scanf("%d", &t_mx);             ans.pb(t_mx); } } printf("!"); for(auto x : ans) printf(" %d", x); printf("n"); fflush(stdout);     string st;     cin >> st; } int main() { /* fre(); */ int T; scanf("%d", &T); while(T --) { scanf("%d %d", &n, &k); for(int i = 1, c; i <= k; i ++) { scanf("%d", &c); for(int j = 1, t; j <= c; j ++) { scanf("%d", &t);                 s[i].pb(t); } } get_ans(); for(int i = 1; i <= k; i ++)             s[i].clear(); } return 0; } 

E. Tree Shuffling（dfs）

分析

• 题意

1. 给我们一个以1为根有n个节点的树，每一个节点有一个值b[i] 为0或1，之后我们希望通过操作把 每一个节点值 变成对应给出的节点值c[i]为 0或1，每个节点还有一个属性就 变化操作所需要的花费a[i]，
2. 对于一次操作，我们可以选择 一个以u为节点的子树中的 某些节点（设节点数量为x） 令这些节点 b[i] 值进行交换，对于的这次操作的花费时 x * a[u]，
3. 问通过这样操作，把每个节点的b[i]变化为c[i]，总共需要的最小花费是多少？，如果不能 变化为 对应的c[i]输出-1

• 思路

4. 从根节点往下开始递归，维护每个子树u的 ct0[u]、ct1[u]的数量， 同时又维护 当前节点 进行变换操作时的最小花费 mon = min(mon, a[u]),如果在回溯的时候发现再次回溯到u节点的时候判读发现 mon == a[u] 的话(说明这个时候 u节点的费用比u节点的所有祖先的费用花费都小),以u为根节点的子树中的每一个节点所需的最小花费时 a[u]，，，

代码

#include <bits/stdc++.h> using namespace std; void fre() { freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); } void Fre() { freopen("A.txt", "r", stdin);} #define ios ios::sync_with_stdio(false) #define Pi acos(-1) #define pb push_back #define fi first #define se second #define ll long long #define ull unsigned long long  #define db double #define Pir pair<int, int> #define PIR pair<Pir, Pir> #define INF 0x3f3f3f3f #define mod 998244353 const int mxn = 2e5 + 10; int a[mxn], b[mxn], c[mxn]; int ct1[mxn], ct0[mxn]; vector<int> e[mxn * 2]; ll res = 0; void dfs(int u, int p, int mon) {     mon = min(mon, a[u]); for(auto v : e[u]) { if(v == p) continue; dfs(v, u, mon);         ct0[u] += ct0[v]; //这里是维护 u的子树中，还剩余多少个 等待交换值的0节点         ct1[u] += ct1[v]; } if(b[u] != c[u]) { if(b[u] == 0) ct0[u] ++; else          ct1[u] ++; } if(mon == a[u]) //在回溯的过程中 当前节点的费用==之前所有的祖先中最小的费用，那么我们就可确定，这个子树的所有需要变换数字的节点，所用的费用都应该是 a[u] { int c = min(ct0[u], ct1[u]);         res += 2LL * c * mon;         ct0[u] -= c;         ct1[u] -= c; } } int main() { /* fre(); */ int n; scanf("%d", &n); for(int i = 1; i <= n; i ++) scanf("%d %d %d", &a[i], &b[i], &c[i]); for(int i = 1, u, v; i < n; i ++) { scanf("%d %d", &u, &v);         e[u].pb(v);         e[v].pb(u); } dfs(1, 1, INF); if(ct0[1] || ct1[1]) printf("-1"); else printf("%lld", res); return 0; }