A.Odd Selection

题意：

给定个数，从中取出个，判断能否存在一种方案使得取出的这个数之和为奇数

题解：

只有三种情况不存在

1. 不存在奇数
2. 并且奇数个数为偶数个
3. 个数全为偶数，要取的为偶数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n, x, od = 0;
    ;
    scanf("%d%d", &n, &x);
    int a[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]), od += (a[i] % 2);
    if (od >= 1 && !(x == n && od % 2 == 0) && !(od == n && x % 2 == 0))
        puts("Yes");
    else
        puts("No");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Subsequence Hate

题意：

给定一个串,询问至少经过多次操作可以使得中不存在字串和，每次操作可以将变为,将变为

题解：

可以发现满足条件的序列为、、和四种。而全和全可以看成交替的特殊情况，因此只会存在和两种情况。因此可以用前缀和维护前面所有和的个数，对于每一位枚举、两种情况的最小值即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
char s[1005];
int sum0[1005], sum1[1005];
void solve()
{
    scanf("%s", s + 1);
    int len = strlen(s + 1), ans = INF;
    for (int i = 1; i <= len; i++)
    {
        sum0[i] = sum0[i - 1] + (s[i] == '0');
        sum1[i] = sum1[i - 1] + (s[i] == '1');
    }
    for (int i = 1; i <= len; i++)
    {
        ans = min(ans, sum0[i - 1] - sum0[0] + sum1[len] - sum1[i - 1]);
        ans = min(ans, sum1[i - 1] - sum1[0] + sum0[len] - sum0[i - 1]);
    }
    printf("%d\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Game On Leaves

题意：

给定一棵个节点的无根树，和两人每次可以从树上拿走一个叶节点，如果谁能拿到号节点则谁获胜，询问最终谁能获胜，先手

题解：

如果号节点为叶节点那么肯定赢，否则将作为根节点，自己思考一下会发现最终一定会取到只剩个结点，且中间结点为的情况，因此只需要判断一下的奇偶性即可，

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n, x, cnt = 0;
    scanf("%d%d", &n, &x);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        if (u == x || v == x)
            cnt++;
    }
    if (cnt <= 1)
    {
        puts("Ayush");
        return;
    }
    puts((n - 3) & 1 ? "Ayush" : "Ashish");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Guess The Maximums(交互题)

题意：

有一个长度为n的数组（未知），长度为的不等长二维子集数组（给出），且这个数组完全不存在相同元素()。所求密码的长度同样为。现规定每位密码的值为中的下标不在对应中出现的最大值。形式上，。现在每次询问可以给出一系列的下标，我们会得到所查询的所有下标的数组中值的最大值。要求在次询问后得到正确的密码

题解：

既然所有独立，那么最多就只存在一个位置的密码不是的最大值。（有可能全是最大值，因为中可能不含最大值对应的下标。）所以我们先花次来查询个位置的最大值。然后二分搜索最大值所出现的位置。这里最多花费次（）。最后一次我们用来查询这个位置的最大值就行了。

#include <bits/stdc++.h>
using namespace std;
int query(vector<int> q)
{
    cout << "? " << q.size() << " ";
    for (auto i : q)
        cout << i << " ";
    cout << "\n";
    cout.flush();
    int x;
    cin >> x;
    return x;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        vector<vector<int>> s(k);
        vector<int> ans(k);
        for (int i = 0, c; i < k; i++)
        {
            cin >> c;
            s[i].resize(c);
            for (int j = 0; j < c; j++)
                cin >> s[i][j];
        }
        vector<int> q;
        for (int i = 1; i <= n; i++)
            q.push_back(i);
        int mx = query(q);
        int l = 0, r = k - 1;
        while (l < r)
        {
            int mid = (l + r) / 2;
            q.clear();
            for (int i = 0; i <= mid; i++)
                for (auto j : s[i])
                    q.push_back(j);
            int x = query(q);
            if (x == mx)
                r = mid;
            else
                l = mid + 1;
        }
        q.clear();
        vector<int> vis(n + 1);
        for (auto i : s[l])
            vis[i] = 1;
        for (int i = 1; i <= n; i++)
            if (!vis[i])
                q.push_back(i);
        for (int i = 0; i < k; i++)
        {
            if (i == l)
                ans[i] = query(q);
            else
                ans[i] = mx;
        }
        cout << "! ";
        for (auto i : ans)
            cout << i << " ";
        cout << "\n";
        cout.flush();
        string correct;
        cin >> correct;
    }
    return 0;
}

E.Tree Shuffling

题意：

给定一棵有个节点且以为根的树，每个节点都有三个值，其中。每次可以选择一个节点，用的代价交换节点子树中任意个节点的值，询问最少可以用多少花费使得所有节点的

题解：

对于每个节点，都可以选择该节点往上的节点进行操作，因此可以用dfs保证每个节点都在最小花费的那个子树内。在dfs的时候顺便记录下该节点的子节点有多少对可以两两交换，贪心的将它们进行配对，最终判断是否能完全匹配，如果是输出答案，否则输出

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll ans;
int n, a[maxn], b[maxn];
vector<int> G[maxn];

void dfs(int u, int fa)
{
    int tot = abs(b[u]);
    for (int v : G[u])
    {
        if (v == fa)
            continue;
        a[v] = min(a[u], a[v]);
        dfs(v, u);
        b[u] += b[v];
        tot += abs(b[v]);
    }
    ans += 1ll * (tot - abs(b[u])) * a[u];
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int u, v;
        scanf("%d%d%d", &a[i], &u, &v);
        b[i] = u - v;
    }
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    printf("%lld\n", b[1] ? -1 : ans);
    return 0;
}