A

给出三个人分别的得票数，单独问每个人如果要赢还需要多少票。
三种情况 小中大，小小大，小大大，分类讨论一下即可。
我的做法稍微归纳了一下，显得没那么复杂。。

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t, a[3], b[3];
    cin >> t;
    while(t --)
    {
        int M = 0, cnt = 0;

        for(int i = 0; i < 3; i ++) cin >> a[i], M = max(M, a[i]);
        for(int i = 0; i < 3; i ++) if((b[i] = M - a[i] + 1) == 1) cnt ++;
        if(cnt == 1) for(int i = 0; i < 3; i ++) if(b[i] == 1) b[i] --;

        for(auto x : b) cout << x << ' ';
        cout << endl;
    }
}

B

手动模拟一下，从个位开始数，看看数到第几位的时候满足出现50或者00或者25或者75
其实可以只写一次循环，可是复制粘贴何乐而不为23333

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
    int t, n;
    cin >> t;
    while(t --)
    {
        cin >> n;
        vector<int> v;
        while(n) v.push_back(n % 10), n /= 10;//把每一位拎出来

        int i = 0, s = 0, vn = v.size(), res;
        while(i < vn) 
            if(!s)
            {
                if(v[i ++] == 0) s = 1;
            }
            else
            {
                if(v[i] == 5 || v[i] == 0) break;
                i ++;
            }
        res = i; s = 0; i = 0;
        while(i < vn) 
            if(!s)
            {
                if(v[i ++] == 5) s = 1;
            }
            else
            {
                if(v[i] == 7 || v[i] == 2) break;
                i ++;
            }
        res = min(i, res);

        cout << res - 1 << endl;
    }
}

C

贪心，越接近hole的越先走。
主要两个公式说明一下

if(n > x.f * x.s) res += x.s, n -= x.f * x.s;

res += (n - 1) / x.f;

思路都是，猫来到这个格子之前，能走的走了，没走的死了。
第一个公式是，猫还远呢，这个格子可以全走光
第二个共识是，猫近了，猫到这个格子的距离$(n-x.f)/(x.f)$向上取整
所以$(n-x.f+x.f-1)/(x.f)$

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;

signed main()
{
    int t, n, k, x;
    cin >> t;
    while(t --)
    {
        cin >> n >> k;
        map<int, int> p;
        for(int i = 0; i < k; i ++) cin >> x, p[n - x] ++;

        int res = 0;
        for(auto x : p)
            if(n > x.f * x.s) res += x.s, n -= x.f * x.s;
            else
            {
                res += (n - 1) / x.f;
                break;
            }

        cout << res << endl;
    }
}

D1

D1就是枚举这些数两两之间差值的gcd，我排序一下可以优化到$O(nlogn)$，不过没啥必要
1 gcd是什么 gcd：最小公因数
2 为什么是gcd：例如1 3 5他们的差值有2和4，如果我们取4，可以让1和5相同，但取gcd2可以让1 3 5都相同，因为它们之间的差值都是gcd2的倍数，一定可以通过加减若干个2变成相同的数。

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;

signed main()
{
    int t, n;
    cin >> t;
    while(t --)
    {
        cin >> n;
        vector<int> a(n);
        for(int i = 0; i < n; i ++) cin >> a[i];
        sort(a.begin(), a.end());

        if(a[0] == a[n - 1]) cout << -1 << endl;
        else 
        {
            int res = a[1] - a[0];
            for(int i = 1; i < n; i ++) res = __gcd(res, a[i] - a[i - 1]);
            cout << res << endl;
        }
    }
}

D2

D2我看数据量很小就暴力了
首先判断一下是否存在超过n/2个相同元素，存在则输出-1
否则，求出两两之间的差值，再求出差值间两两gcd，枚举每个gcd看能不能达到让n/2个数相同，也就是枚举每个数，看看有没有n/2个数和它的差值是这个gcd的倍数
（现在想想好像可以构造数据T掉啊，现在还可以hack，大家想到了的话快冲)

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;

signed main()
{
    int t, n;
    cin >> t;
    while(t --)
    {
        cin >> n;
        vector<int> a(n);
        for(int i = 0; i < n; i ++) cin >> a[i];

        int res = 0;
        map<int, int> cnt;
        for(int i = 0; i < n; i ++) cnt[a[i]] ++;
        for(auto x : cnt) if(x.s >= n / 2) res = -1;

        if(!res)
        {
            set<int> gcds, d;
            for(auto x : a) for(auto y : a) d.insert(abs(x - y));
            for(auto x : d)
                for(auto y : d)
                    gcds.insert(__gcd(x, y));

            for(auto x : gcds)
            {
                if(!x) continue;
                for(int i = 0; i < n; i ++)
                {
                    int c = 0;
                    for(int j = 0; j < n; j ++)
                        if(abs(a[i] - a[j]) % x == 0) c ++;
                    if(c >= n / 2) res = max(res, x);
                }
            }
        }

        cout << res << endl;
    }
}

E

如果只有1个点，那一定会被消掉
如果大于1个点，那就是拓扑排序，每次把度为1的节点去掉，并且把与之相连的节点度-1

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pb push_back
using namespace std;

signed main()
{
    int t, n, k, x, y;
    cin >> t;
    while(t --)
    {
        cin >> n >> k;
        if(n == 1)
        {
            cout << 0 << endl;
            continue;
        }

        vector<int> h[n], vs;
        for(int i = 1; i < n; i ++) cin >> x >> y, h[--x].pb(--y), h[y].pb(x);
        int d[n];
        for(int i = 0; i < n; i ++) if((d[i] = h[i].size()) == 1) vs.pb(i);

        int res = n;
        while(k --)
        {
            if(!vs.size()) break;
            res -= vs.size();
            vector<int> backup;
            for(auto x : vs) backup.pb(x);
            vs.clear();

            for(auto u : backup)
                for(auto v : h[u]) if(--d[v] == 1) vs.pb(v);
        }

        cout << res << endl;
    }
}

F

dp，因为状态是有限的，然后注意$((a * 10 + b) % c = (a % c) * (10 % c) + b % c)$

#include<bits/stdc++.h>

using namespace std;

int t, n, a, b;
int dp[41][41][40][40], num[50];

struct state{
    int pos, n, rn, bn;
    char s[40];
};

struct
{
    int d;
    char s[40];
} res;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> t;
    while(t --)
    {
        cin >> n >> a >> b;
        string s;
        cin >> s;

        for(int i = 1; i <= n; i ++) num[i] = s[i - 1] - '0';
        queue<struct state> q;
        // struct state begin = 
        q.push({0, 0, 0, 0, {'R'}});

        memset(dp, 0, sizeof dp);
        dp[0][0][0][0] = 1;
        res = {0x3f3f3f3f, {'R'}};

        while(q.size())
        {
            auto x = q.front();
            q.pop();

            // cout << x.pos << ' ' << x.n << ' ' << x.rn << ' ' << x.bn << ' ' << x.s << endl;

            if(x.pos == n)
            {
                if(abs(2 * x.n - n) < res.d && !x.rn && !x.bn && x.n && x.n < n)
                {
                    res.d = abs(2 * x.n - n);
                    for(int i = 0; i < n; i ++) res.s[i] = x.s[i];
                }
                continue;
            }

            auto y = x;
            x.n ++;
            x.rn = (x.rn * 10 + num[x.pos + 1]) % a;
            x.s[x.pos ++] = 'R';
            if(!dp[x.pos][x.n][x.rn][x.bn])
                dp[x.pos][x.n][x.rn][x.bn] = 1,
                q.push(x);

            y.bn = (y.bn * 10 + num[y.pos + 1]) % b;
            y.s[y.pos ++] = 'B';
            if(!dp[y.pos][y.n][y.rn][y.bn])
                dp[y.pos][y.n][y.rn][y.bn] = 1,
                q.push(y);
        }

        if(res.d == 0x3f3f3f3f) cout << -1 << endl;
        else cout << res.s << endl;
    }
}

G

方法一
线段树，枚举各种情况，pushup的时候注意，每个线段只保留010101或者10101序列
也就是说00和11会被消掉，这里的1表示小括号，0表示中括号。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

string s;
char str[N];

struct segtr
{
    int l, r;
    int xiao, num;
} tr[4 * N];

void pushup(segtr & u, segtr l, segtr r)
{
    if(!l.num) 
        u = {l.l, r.r, r.xiao, r.num};
    else if(!r.num)
        u = {l.l, r.r, l.xiao, l.num};
    else if(l.xiao == r.xiao && !(l.num & 1) || l.xiao != r.xiao && l.num & 1)
        u = {l.l, r.r, l.xiao, l.num + r.num};
    else if(l.num >= r.num) 
        u = {l.l, r.r, l.xiao, l.num - r.num};
    else if(r.xiao && !(l.num & 1) || !r.xiao && l.num & 1) 
        u = {l.l, r.r, 1, r.num - l.num};
    else 
        u = {l.l, r.r, 0, r.num - l.num};
}

void pushup(int u, int l, int r)
{
    pushup(tr[u], tr[l], tr[r]);
}

void build(int u, int l, int r)
{
    if(l >= r)
    {
        if(str[l] == '(') tr[u] = {l, r, 1, 1};
        else tr[u] = {l, r, 0, 1};
        return;
    }

    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);

    pushup(u, u << 1, u << 1 | 1);
}

segtr query(int u, int l, int r)
{
    if(l <= tr[u].l && tr[u].r <= r) return tr[u];

    int mid = tr[u].l + tr[u].r >> 1;
    if(l > mid) return query(u << 1 | 1, l, r);
    if(r <= mid) return query(u << 1, l, r);

    segtr res, lchild = query(u << 1, l, mid), rchild = query(u << 1 | 1, mid + 1, r);
    pushup(res, lchild, rchild);
    return res;
}

int main()
{
    int t, q, n;
    cin >> t;

    while(t --)
    {
        cin >> s >> q;
        n = s.size();

        for(int i = 0; i < n; i ++)
            if(s[i] == '(' || s[i] == ')') str[i + 1] = '(';
            else str[i + 1] = '[';

        build(1, 1, n);

        while(q --)
        {
            int l, r;
            cin >> l >> r;
            cout << query(1, l, r).num / 2 << endl;
        }
    }
}

方法二
前缀和，注意奇数位置的中括号只能和偶数位置的中括号消掉，我们看看有多少没有消掉的括号，那么代价就是多少。
统计一下，奇数位加一，偶数位减一即可，我是这样写的（因为懒得写判断

sum[i + 1] = sum[i] + (i & 1) * 2 - 1;

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int t, q, sum[N];
string s;

int main()
{
    cin >> t;
    while(t --)
    {
        cin >> s;
        int n = s.size();

        for(int i = 0; i < n; i ++)
            if(s[i] == '(' || s[i] == ')') sum[i + 1] = sum[i];
            else sum[i + 1] = sum[i] + (i & 1) * 2 - 1;

        cin >> q;
        while(q --)
        {
            int l, r;
            cin >> l >> r;
            cout << abs(sum[r] - sum[l - 1]) << endl;
        }
    }
}