A

我人傻了, 没理解清题意

设有x个奇数, y个偶数

且两个奇数等于一个偶数

所以就让偶数和成对的奇数去凑(m - 1), 并保证剩下一个奇数 则YES

我真就sb, 忘了用奇数凑偶数的时候是凑出的成对的, 罚时全是A贡献 淦

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef double db;
 
const int N = 1e5 + 5;
 
int n, m, _, k;
int a[N];
 
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    for (cin >> _; _; --_)
    {
        cin >> n >> m;
        int x = 0, y = 0;
        rep (i, 1, n) 
        {
            cin >> a[i];
            if (a[i] & 1) ++x;
            else ++y;
        }
 
        m -= y;
        if (m <= 1 && x) { cout << "YES\n"; continue; }
        
        if (m % 2 == 0 && y) ++m; 
 
        if (m % 2 == 1 && (x - 1) / 2 * 2 >= m - 1 && x > 1) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

B

最后无非是 全零, 全一, (零)(一), (一)(零)

你就正反求出 到i 使得1 ~ i (i ~ n) 全为零(一)的花费, 拼接一下就行

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef double db;
 
const int N = 1e3 + 5;
 
int n, m, _, k;
int f[2][N];
char s[N];
 
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    for (cin >> _; _; --_)
    {
        cin >> s + 1;
        int len = 1, x = 0, y = 0;
        for (int& i = len; s[len]; ++len)
        {
            if (s[i] == '1')
            {
                f[0][i] = f[0][i - 1];
                f[1][i] = f[1][i - 1] + 1;
                ++y;
            }
            else 
            {
                f[0][i] = f[0][i - 1] + 1;
                f[1][i] = f[1][i - 1];
                ++x;
            }
        }
        --len;
        int ans = min(x, y);
        x = 0, y = 0;
        per (i, len, 1)
        {
            if (s[i] == '1') ++y;
            else ++x;
            ans = min(ans, f[1][i - 1] + x);
            ans = min(ans, f[0][i - 1] + y);
        }
        cout << ans << '\n';
    }
    return 0;
}

C

博弈

如果X入度小于等于1, 直接赢

否则就轮流挑其他点, 让对手将X的入度变为小于1, 就变成了奇偶判断

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef double db;
 
const int N = 1e3 + 5;
 
int n, m, _, k;
 
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    for (cin >> _; _; --_)
    {
        cin >> n >> m;
        int cnt = 0;
        rep (i, 2, n)
        {
            int u, v; cin >> u >> v;
            if (u == m) ++cnt;
            else if (v == m) ++cnt;
        }
 
        if (cnt <= 1) cout << "Ayush\n";
        else if (n & 1)  cout << "Ashish\n";
        else cout << "Ayush\n";
    }
    return 0;
}

D

交互题, 我是吐了, 读题看了最少20min, 没时间写了

E

dfs

首先, 要认识到, 孩子自己调, 和父亲调, 结果是一样的(花费不同)

所以dfs遍历子节点, 并 a[u] = min(a[u], a[fa]), 就变成了子树能调节多少就多少, 反正花费最少

然后字数调不了, 就是0多1少(1多0少), 让父亲去调把

最后特判是不是 -1 就行

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef double db;
 
const int N = 2e5 + 5;
 
int n, m, _, k;
int h[N], ne[N << 1], to[N << 1], tot;
int a[N], b[N], c[N];
int p[N], q[N];
 
void add(int u, int v)
{
    ne[++tot] = h[u]; h[u] = tot; to[tot] = v;
}
 
ll dfs(int u, int fa)
{
    ll co = 0;
    if (a[u] > a[fa]) a[u] = a[fa];
 
    if (b[u] != c[u])
        if (c[u]) ++q[u];
        else ++p[u];
 
    for (int i = h[u]; i; i = ne[i])
    {
        int y = to[i];
        if (y == fa) continue;
        co += dfs(y, u);
        //cout << ' ' << y << ' ' << p[y] << ' ' << q[y] << '\n';
        q[u] += q[y]; p[u] += p[y];
         //cout << '!' << u << ' ' << p[u] << ' ' << q[u] << '\n';
    }
 
    int s = min(q[u], p[u]);
    co += 2ll * s * a[u];
    q[u] -= s, p[u] -= s;
 
    //cout << u << ' ' << co << ' ' << q[u] << ' ' << p[u] << '\n';
    if (fa == 0 && (q[u] || p[u])) return -1;
 
    return co;
}
 
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n; a[0] = 2e9;
    rep (i, 1, n) cin >> a[i] >> b[i] >> c[i];
 
    rep (i, 1, n - 1) 
    {
        int u, v; cin >> u >> v;
        add(u, v); add(v, u);
    }
 
    cout << dfs(1, 0);
    return 0;
}