康复场1。
https://codeforces.com/contest/1363
A - Odd Selection
题意：问是否能在给出的 (n) 个数中选恰好 (x) 个数，使得他们的和为奇数。
题解：必须选择奇数个奇数，然后不用思考这么复杂，枚举选择 ([1,x]) 个奇数是否可行，即可。
int n, x;
void TestCase() {
scanf("%d%d", &n, &x);
int odd = 0, even = 0;
for(int i = 1; i <= n; ++i) {
int ai;
scanf("%d", &ai);
if(ai % 2 == 1) {
++odd;
} else {
++even;
}
}
bool suc = 0;
for(int i = 1; i <= x; i += 2) {
if(i > odd)
break;
if(x - i > even)
continue;
suc = 1;
break;
}
if(suc) {
puts("Yes");
} else {
puts("No");
}
return;
}
想预处理之后 (O(1)) 来做，就要先使用（不超过x的）奇数个奇数，然后尽可能使用偶数。最后还要验证这些和确实是奇数才行（有可能使用了）
B - Subsequence Hate
题意：给一个01串，每次操作可以翻转一个位置，求至少多少次操作才能使得给出的01串中不含子序列"010"也不含子序列"101"。
题解：构造出的串必须是先0后1或者先1后0，搞个前缀和和后缀和统计就行。
int n;
char s[1005];
void TestCase() {
scanf("%s", s + 1);
n = strlen(s + 1);
int sum0 = 0;
int sum1 = 0;
for(int i = 1; i <= n; ++i) {
sum0 += (s[i] == '0');
sum1 += (s[i] == '1');
}
int ans = sum0;
int cnt0 = 0;
int cnt1 = 0;
for(int i = 1; i <= n; ++i) {
sum0 -= (s[i] == '0');
sum1 -= (s[i] == '1');
cnt0 += (s[i] == '0');
cnt1 += (s[i] == '1');
ans = min(ans, cnt0 + sum1);
ans = min(ans, cnt1 + sum0);
}
printf("%d
", ans);
return;
}
C - Game On Leaves
题意：给出一棵 (n) 个点的无根树和一个节点 (x) ，两个人玩游戏，轮流操作。每次操作可以选择一个叶子（度数不超过1的节点）去除，谁去除了节点 (x) 谁就获胜，问最优策略下谁赢。
题解：若 (x) 是叶子，直接去除，先手赢，否则必须要经过一个状态（因为最优策略下没有人会先把 (x) 变成叶子，所以总是保留至少度数为2），就是 text P - X - P ，这个状态是后手必胜，然后求出初始状态里这个状态相差的节点个数的奇偶性就可以了。
D - Guess The Maximums
题意：交互题，题意太复杂见原题。
提示：注意 (S_i) 的并集未必是 ([1,n]) 。
题解：看到这个12，大概都会往折半去想，有一个办法就是先用1次确定全集的最大值是多少，然后用至多10次来确定这个最大值在哪里（最坏情况下每次询问的长度是500-250-125-63-32-16-8-4-2-1），然后知道最大值的位置之后，找出最大值所在的 (S_i) （假如有的话），然后把其他的合并再询问最后一次。
int n, k;
int color[1005];
int maxnum, maxidx;
int query(int L, int R) {
printf("? %d", R - L + 1);
for(int i = L; i <= R; ++i) {
printf(" %d", i);
}
printf("
");
fflush(stdout);
int x;
scanf("%d", &x);
assert(1 <= x && x <= n);
return x;
}
bool check(int L, int R) {
return query(L, R) == maxnum;
}
vector<int> tmp;
void TestCase() {
scanf("%d%d", &n, &k);
memset(color, -1, sizeof(color));
for(int i = 1; i <= k; ++i) {
int s;
scanf("%d", &s);
for(int j = 1; j <= s; ++j) {
int x;
scanf("%d", &x);
color[x] = i;
}
}
maxnum = query(1, n);
int L = 1, R = n, M;
while(1) {
M = (L + R) / 2;
if(L == M) {
if(check(L, M)) {
maxidx = L;
} else {
maxidx = R;
}
break;
}
if(check(L, M)) {
R = M;
} else {
L = M + 1;
}
}
tmp.clear();
for(int i = 1; i <= n; ++i) {
if(color[i] != color[maxidx]) {
tmp.push_back(i);
}
}
if(color[maxidx] == -1) {
printf("!");
for(int i = 1; i <= k; ++i) {
printf(" %d", maxnum);
}
printf("
");
fflush(stdout);
char s[20];
scanf("%s", s + 1);
assert(s[1] == 'C');
return;
}
printf("? %d", (int)tmp.size());
for(auto &v : tmp) {
printf(" %d", v);
}
printf("
");
fflush(stdout);
int x;
scanf("%d", &x);
assert(1 <= x && x <= n);
printf("!");
for(int i = 1; i < color[maxidx]; ++i) {
printf(" %d", maxnum);
}
printf(" %d", x);
for(int i = color[maxidx] + 1; i <= k; ++i) {
printf(" %d", maxnum);
}
printf("
");
fflush(stdout);
char s[20];
scanf("%s", s + 1);
assert(s[1] == 'C');
return;
}
*E - Tree Shuffling
题意：给出一棵 (n) 个点的有根树，根是1号点。每个节点有三个值 (a,b,c) ， (a) 表示这个节点的操作代价， (b) 表示节点的初始状态（只能是0或1）， (c) 表示节点的目标状态（只能是0或1）。每次操作可以选择一个节点，然后选择其子树中的任意个节点，然后把这些节点的值交换到你想要的样子，求把整棵树变成目标状态的最小代价。
题解：一开始想了一个树dp，是错的，这个树dp是 (dp[u]) 表示节点 (u) 的子树复原的最小代价，然后若不能复原则为无穷。若 (u) 可以复原，则 (dp[u]=sumlimits_{vin son(u)}min(dp[v],a[u]*dif[v])) ，其中 (dif[v]) 表示节点 (v) 中初始状态和目标状态不同的数量。后来打了一个 (a[u]=min(a[u],a[p])) 的补丁，还是错的。错在一棵树就算没办法复原也可以尽可能复原（利用子树中的低代价来复原大部分，只留下一种不能复原的）。
int n, x;
int a[200005];
int b[200005];
int c[200005];
vector<int> G[200005];
int siz[200005];
int cnt01[200005];
int cnt10[200005];
ll res;
void dfs(int u, int p, int ap) {
a[u] = min(a[u], ap);
siz[u] = 1;
cnt01[u] = (b[u] == 0 && c[u] == 1);
cnt10[u] = (b[u] == 1 && c[u] == 0);
for(auto &v : G[u]) {
if(v == p)
continue;
dfs(v, u, a[u]);
siz[u] += siz[v];
cnt01[u] += cnt01[v];
cnt10[u] += cnt10[v];
}
int tmp = min(cnt01[u], cnt10[u]);
cnt01[u] -= tmp;
cnt10[u] -= tmp;
res += 2ll * tmp * a[u];
return;
}
void TestCase() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
G[i].clear();
scanf("%d%d%d", &a[i], &b[i], &c[i]);
}
for(int i = 1; i <= n - 1; ++i) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
res = 0;
dfs(1, 0, INF);
if(cnt01[1] || cnt10[1])
res = -1ll;
printf("%lld
", res);
return;
}