第十九届东南大学大学生程序设计竞赛（春、夏季）- 题解 - 帖子

整体难度:

题目名称	难度
C. 猫狗大战	*800
K. Going to Find Your Love	*1200
F. Bracket Distance	*1200
H. 石头剪刀布	*1800
G. Dingding and His Favorite Finite Binary String	*1900
I. YiYi and Her Unsorted Array	*2000
L. 聪明的小高	*2000
B. Infinite Binary String	*2100
E. It's not Ashamed to Feel Sad	*2100
A. 破晓狂想曲	*2300
D. 弱者都是群居者	*2500
J. 小Q的机器	*2500

A. 破晓狂想曲

提示1：在完成这题前，请先学习莫比乌斯反演、欧拉函数、数论分块。

使用莫比乌斯反演对于该柿子进行变形

\sum_{i=1}^n\sum_{j=1}^m\frac{\gcd(i,j)}{ij}\ mod\ 998244353

假设 $n\le m$ ，

\sum_{i=1}^n\sum_{j=1}^m\frac{\gcd(i,j)}{ij}=\\ \sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^n \frac{d}{ij}[gcd(i,j)==d]=\\ \sum_{d=1}^{n}\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\frac{1}{ijd}[gcd(i,j)==1]=\\ \sum_{d=1}^{n}\frac{1}{d}\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\frac{1}{ij}[gcd(i,j)==1]=\\ \sum_{d=1}^{n}\frac{1}{d}\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\frac{1}{ij}\sum_{p|gcd(i,j)}\mu(p)=\\ \sum_{d=1}^{n}\frac{1}{d}\sum_{p=1}^{n/d}\mu(p)\frac{1}{p^2}\sum_{i=1}^{n/dp}\sum_{j=1}^{m/dp}\frac{1}{ij}=\\ \sum_{d=1}^{n}\sum_{p|d}^{n/d}\mu(p)\frac{1}{p^2}\frac{p}{d}\sum_{i=1}^{n/dp}\sum_{j=1}^{m/dp}\frac{1}{ij}=\\ \sum_{d=1}^{n}\frac{1}{d}\sum_{i=1}^{n/dp}\sum_{j=1}^{m/dp}\frac{1}{ij}\sum_{p|t}^{n/d}\mu(p)\frac{1}{p}=\\ \sum_{d=1}^{n}\frac{1}{d}\frac{\phi(d)}{d}\sum_{i=1}^{n/dp}\sum_{j=1}^{m/dp}\frac{1}{ij}\\

其中， $\frac{\phi(d)}{d^2}$ 可以 $O(n)$ 预处理，后面的可以分块计算，时间复杂度 $O(n+t\sqrt{n})$ 。

代码:

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

typedef long long ll;

vector<bool> isnotprime;
vector<int> primes;
vector<ll> phi;
vector<ll> inv;

void getphi(int n, ll mod) {
    isnotprime.resize(n + 1, 0);
    phi.resize(n + 1, 0);
    inv.resize(n + 1, 1);
    phi[1] = 1, isnotprime[1] = 1;
    for (int i = 2; i <= n; i++) {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        if (isnotprime[i] == 0) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for (size_t j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            isnotprime[i * primes[j]] = 1;
            if (i % primes[j] == 0) {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
        }
    }
}

const ll mod = 998'244'353;
const int maxn = 1e6 + 5;
vector<ll> p(maxn), preinv(maxn);
void solve() {
    ll n, m;
    cin >> n >> m;
    if (n > m)
        swap(n, m);
    ll ans = 0;
    for (int l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans += (p[r] - p[l - 1] + mod) % mod * preinv[n / l] % mod * preinv[m / l];
        ans %= mod;
    }
    cout << ans << '\n';
}
int main() {
    getphi(maxn, mod);
    for (int i = 1; i <= maxn; i++)
        p[i] = (inv[i] * inv[i] % mod * phi[i] % mod + p[i - 1]) % mod,
        preinv[i] = (preinv[i - 1] + inv[i]) % mod;
    int _t;
    cin >> _t;
    while (_t--) solve();
}

B. Infinite Binary String

提示1：有什么可以维护区间操作的数据结构吗。

答案：线段树

提示2：数据范围很大怎么办。

答案：离散化或者动态开点。

提示3：对于询问怎么办。

答案：二分即可。

操作 $1,2$ 是线段树的区间复制操作，对于操作 $3$ 采取二分即可，本题难度在于代码实现，时间复杂度 $O(q\log n\log n)$ 。

代码(离散化)：

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <map>
#include <assert.h>
using namespace std;
#define fer(i, a, n) for (int i = (a); i <= (n); ++i)
using ll = long long;
#define double long double
const int maxn = 1e6 + 5;
ll f[maxn << 2], v[maxn << 2];
double arr[maxn];
#define ls k << 1
#define rs k << 1 | 1
#define mid ((l + r) >> 1)
void up(int k) { f[k] = f[ls] + f[rs]; }
void down(int k, int l, int r) {
    if (v[k] == 0) {
        v[ls] = v[rs] = 0;
        f[ls] = f[rs] = 0;
    }
    if (v[k] == 1) {
        v[ls] = v[rs] = 1;
        f[ls] = arr[mid + 1] - arr[l], f[rs] = arr[r + 1] - arr[mid + 1];
    }
    v[k] = -1;
}
void build(int k, int l, int r) {
    v[k] = -1;
    if (l == r)
        return;
    build(ls, l, mid), build(rs, mid + 1, r);
}
void assign(int k, int l, int r, int x, int y, ll z) {
    if (l == x && r == y) {
        v[k] = z;
        f[k] = (arr[y + 1] - arr[x]) * z;
        return;
    }
    down(k, l, r);
    if (y <= mid)
        assign(ls, l, mid, x, y, z);
    else if (x > mid)
        assign(rs, mid + 1, r, x, y, z);
    else
        assign(ls, l, mid, x, mid, z), assign(rs, mid + 1, r, mid + 1, y, z);
    up(k);
}
ll que(int k, int l, int r, int x, int y) {
    if (l == x && r == y) {
        return f[k];
    }
    down(k, l, r);
    ll ans;
    if (y <= mid)
        ans = que(ls, l, mid, x, y);
    else if (x > mid)
        ans = que(rs, mid + 1, r, x, y);
    else
        ans = que(ls, l, mid, x, mid) + que(rs, mid + 1, r, mid + 1, y);
    up(k);
    return ans;
}
#undef ls
#undef rs
#undef mid
signed main() {
    int q;
    cin >> q;
    vector<double> v{ -0.5, 2e18 + 1.5 };
    vector<tuple<char, ll, ll>> ops(q + 1);
    fer(i, 1, q) {
        char op;
        double x1, x2 = -1;
        cin >> op;
        if (op == '+') {
            cin >> x1 >> x2;
            v.push_back(x1 - 0.5), v.push_back(x2 + 0.5);
        }
        if (op == '-') {
            cin >> x1 >> x2;
            v.push_back(x1 - 0.5), v.push_back(x2 + 0.5);
        }
        if (op == '?')
            cin >> x1;
        ops[i] = { op, ll(x1), ll(x2) };
    }
    map<double, int> hs;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int sz = v.size();
    fer(i, 0, sz - 1) arr[i + 1] = v[i], hs[v[i]] = i + 1;
    --sz;
    build(1, 1, sz);
    fer(i, 1, q) {
        const auto& [ch, x1, x2] = ops[i];
        if (ch == '+')
            assign(1, 1, sz, hs[(double)(x1)-0.5], hs[(double)(x2) + 0.5] - 1, 1);
        if (ch == '-')
            assign(1, 1, sz, hs[(double)(x1)-0.5], hs[(double)(x2) + 0.5] - 1, 0);
        if (ch == '?') {
            int l = 1, r = sz, ans = -1;
            //	ll out=0;
            while (l <= r) {
                int mid = (l + r) >> 1;
                ll sum = que(1, 1, sz, 1, mid);
                ll rig = arr[mid + 1] - 0.5;
                if (rig - sum + 1 >= x1)
                    ans = mid, r = mid - 1;
                else
                    l = mid + 1;
            }
            assert(ans != -1);
            ll sum = que(1, 1, sz, 1, ans);
            ll rig = arr[ans + 1] - 0.5;
            cout << rig - (rig - sum + 1 - x1) << '\n';
        }
    }
}

代码（动态开点）By 软件质量爆炸-(姜禹丞,姚力文,蒋承欢)：

#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;
using ll = long long;
const int MAXN = 3e5 + 10;

struct segtree {
    struct node {
        ll len{ 0 };
        ll cto{ 0 };
        int all{ -1 };
        node *l{ nullptr };
        node *r{ nullptr };

        ~node() { clear(); }

        node *left() {
            if (!l) {
                l = new node();
                l->len = (len - 1) / 2 + 1;
                if (all != -1)
                    l->all = all;
                l->cto = all == 1 ? l->len : 0;
            }
            return l;
        }
        node *right() {
            if (!r) {
                r = new node();
                r->len = len - (len - 1) / 2 - 1;
                if (all != -1)
                    r->all = all;
                r->cto = all == 1 ? r->len : 0;
            }
            return r;
        }

        void clear() {
            if (l) {
                delete l;
                l = nullptr;
            }
            if (r) {
                delete r;
                r = nullptr;
            }
        }

        void pushup() {
            cto = 0;
            if (l)
                cto += l->cto;
            if (r)
                cto += r->cto;
            all = -1;
            if (cto == 0)
                all = 0;
            if (cto == len)
                all = 1;
        }

        void pushdown() {
            left();
            right();
            all = -1;
        }
    };

    node root{ ll(2e18) + 1 };

    void ins(node *n, ll l, ll r, ll x, ll y, bool v) {
        if (n->all == v)
            return;
        if (x <= l && r <= y || l == r) {
            if (v)
                n->cto = r - l + 1;
            else
                n->cto = 0;
            n->all = v ? 1 : 0;
            n->clear();
            return;
        }
        n->pushdown();
        ll mid = l + (r - l) / 2;
        if (y <= mid) {
            ins(n->left(), l, mid, x, y, v);
        } else if (x > mid) {
            ins(n->right(), mid + 1, r, x, y, v);
        } else {
            ins(n->left(), l, mid, x, mid, v);
            ins(n->right(), mid + 1, r, mid + 1, y, v);
        }
        n->pushup();
    }
    void ins(ll x, ll y, bool v) { ins(&root, 0, 2e18, x, y, v); }
    ll query(node *n, ll l, ll r, ll k) {  // k is number of zero
        if (!n || n->all == 0) {           // all zero
            return l + k - 1;
        }
        n->pushdown();
        n->pushup();
        if (n->len != r - l + 1) {
            cout << "Fail " << l << " " << n->len - (r - l + 1) << endl;
        }
        if (n->all == 1 && n->cto != n->len) {
            cout << "Fail 1" << endl;
        }
        if (n->all == 0 && n->cto != 0) {
            cout << "Fail 2" << endl;
        }
        if (l == r) {
            return l;
        }
        ll mid = l + (r - l) / 2;
        ll cto_l = n->all == 1 ? mid - l + 1 : (n->all == 0 ? 0 : (n->l ? n->l->cto : 0));
        ll ctz_l = mid - l + 1 - cto_l;
        if (ctz_l >= k)
            return query(n->l, l, mid, k);
        else
            return query(n->r, mid + 1, r, k - ctz_l);
    }
    ll query(ll k) { return query(&root, 0, 2e18, k); }

    void print(node *n, ll l, ll r) {
        if (!n)
            return;
        if (n->all == 1) {
            printf("[%lld, %lld]\n", l, r);
            return;
        }
        ll mid = l + (r - l) / 2;
        if (n->l && n->r && n->l->all == 1 && n->r->all == 1) {
            printf("[%lld, %lld]\n", l, r);
            return;
        }
        print(n->l, l, mid);
        print(n->r, mid + 1, r);
    }
};

int main() {
    int q;
    cin >> q;
    segtree st;
    while (q--) {
        string c;
        cin >> c;
        if (c == "+") {
            ll x1, x2;
            cin >> x1 >> x2;
            st.ins(x1, x2, 1);
        } else if (c == "-") {
            ll x1, x2;
            cin >> x1 >> x2;
            st.ins(x1, x2, 0);
        } else {
            ll k;
            cin >> k;
            cout << st.query(k) << '\n';
        }
    }
    return 0;
}

C. 猫狗大战

签到题，按照题意模拟即可，时间复杂度 $O(\sum|s|)$ 。

代码1 By 软件质量爆炸-(姜禹丞,姚力文,蒋承欢)：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
using ll = long long;

string check(string &s) {
    transform(s.begin(), s.end(), s.begin(), [](auto c) { return tolower(c); });
    s.erase(unique(s.begin(), s.end()), s.end());
    if (s == "meow")
        return "0_0";
    if (s == "waov")
        return "*_*";
    return "???";
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        string s;
        cin >> n >> s;
        cout << check(s) << '\n';
    }
    return 0;
}

代码2：

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

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    string t;
    for (int i = 0; i < n; i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            s[i] += 'a' - 'A';
        }
    }
    for (int i = 0; i < n; i++) {
        int j = i;
        while (j < n && s[j] == s[i]) j++;
        t += s[i];
        i = j - 1;
    }
    if (t == "meow")
        cout << "0_0" << endl;
    else if (t == "waov")
        cout << "*_*" << endl;
    else
        cout << "???" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

D. 弱者都是群居者

题解等待更新。

E. It's not Ashamed to Feel Sad

提示1：我们可以发现如果对于每个询问都进行 $dfs$ 时间复杂度为 $O(n^2)$ ，怎么保留一些信息减少时间。

答案：树上启发式合并。

我们把所有的询问离线，并且把询问放到询问的节点上，使用树上启发式合并“暴力”地去 $dfs$ ，每次删除轻儿子的信息，保留重儿子的信息，就可以得到所有字母分别出现的次数，时间复杂度 $O(n\log n+26m)$ 。

当一个字母的出现次数大于字母出现总次数的一半或者字母出现次数和为奇数不是反回文串。

代码（树上启发式合并）:

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

#define fer(i, a, n) for (int i = (a); i <= (n); ++i)

const int maxn = 2e5 + 5;

int n, q;
vector<int> e[maxn];
string s;
int dep[maxn], sz[maxn], hvson[maxn];
vector<pair<int, int> > asks[maxn];
int num[maxn][26];
string ans[maxn];

void dfs1(int u, int fa) {
    dep[u] = dep[fa] + 1, sz[u] = 1;
    int mxsz = 0;
    for (auto v : e[u]) {
        if (v == fa)
            continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > mxsz)
            mxsz = sz[v], hvson[u] = v;
    }
}

int nowhvson = -1;

void cacl(int u, int fa, int val) {
    num[dep[u]][s[u] - 'a'] += val;
    for (auto v : e[u]) {
        if (v == fa || v == nowhvson)
            continue;
        cacl(v, u, val);
    }
}

void getans(int u, int fa, int kp) {
    for (auto v : e[u]) {
        if (v == fa || v == hvson[u])
            continue;
        getans(v, u, 0);
    }
    if (hvson[u]) {
        getans(hvson[u], u, 1);
        nowhvson = hvson[u];
    }
    cacl(u, fa, 1);
    nowhvson = -1;
    for (auto [deep, id] : asks[u]) {
        int sum = accumulate(num[deep], num[deep] + 26, 0);
        int mx = *max_element(num[deep], num[deep] + 26);
        if (sum == 0 || sum % 2 == 1 || mx > sum / 2)
            ans[id] = "No";
        else
            ans[id] = "Yes";
    }
    if (!kp)
        cacl(u, fa, -1);
}
signed main() {
    cin >> n >> q;
    fer(i, 2, n) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v), e[v].push_back(u);
    }
    cin >> s;
    s = '?' + s;
    dfs1(1, 0);
    int mx = *max_element(dep + 1, dep + n + 1);
    fer(i, 1, q) {
        int now, dp;
        cin >> now >> dp;
        if (dp < dep[now] || dp > mx)
            ans[i] = "No";
        else
            asks[now].push_back({ dp, i });
    }
    getans(1, 1, 0);
    fer(i, 1, q) cout << ans[i] << '\n';
}

另外，我们也可以先 $bfs$ 处理将使得每层之间的节点编号连续，然后根据根节点信息二分得到每个询问每个字符出现次数，时间复杂度 $O(n\log n+26m)$ 。

代码（二分法）By 我口胡超强-(徐宽,肖旭杰,王梓鹏)

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

const int M = 2e5 + 5;

int n, q;

int read() {
    int x = 0, y = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') y = ch == '-' ? -1 : 1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * y;
}

int tot = 0, first[M];

struct Edge {
    int nxt, to;
} e[M << 1];

void add(int x, int y) {
    e[++tot] = (Edge){ first[x], y };
    first[x] = tot;
}

int cnt = 0, de[M], sz[M][27], dfn[M], siz[M];
vector<int> cun[M], pre[M][27];
char s[M];

void dfs(int u, int fa) {
    de[u] = de[fa] + 1;
    sz[u][0] = 1;
    siz[u] = 1;
    dfn[u] = ++cnt;
    cun[de[u]].push_back(u);
    for (int i = 1; i <= 26; i++) sz[u][i] = (s[u] - 'a' + 1 == i);
    for (int i = first[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == fa)
            continue;
        dfs(v, u);
        siz[u] += siz[v];
    }
}

int findl(int d, int x) {
    int l = 0, r = cun[d].size() - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (dfn[cun[d][mid]] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return r;
}

int findr(int d, int x) {
    int l = 0, r = cun[d].size() - 1;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (dfn[cun[d][mid]] <= x)
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

int query(int u, int d, int id) {
    int D = d;
    if (D > n || cun[D].size() == 0)
        return sz[u][id];
    int L = dfn[u], R = dfn[u] + siz[u] - 1;
    int l = findl(D, L), r = findr(D, R);
    if (l == 0)
        return pre[D][id][r];
    return pre[D][id][r] - pre[D][id][l - 1];
}

void solve() {
    n = read(), q = read();
    for (int i = 1; i < n; i++) {
        int x = read(), y = read();
        add(x, y), add(y, x);
    }
    scanf("%s", s + 1);
    de[0] = 0;
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        int len = cun[i].size();
        if (len == 0)
            continue;
        for (int k = 0; k <= 26; k++) {
            pre[i][k].push_back(sz[cun[i][0]][k]);
            for (int j = 1; j < len; j++) pre[i][k].push_back(pre[i][k][j - 1] + sz[cun[i][j]][k]);
        }
    }
    while (q--) {
        int u = read(), d = read();
        int sum = query(u, d, 0);
        if (sum % 2 == 1 || sum == 0)
            printf("No\n");
        else {
            int maxn = 0;
            for (int i = 1; i <= 26; i++) maxn = max(maxn, query(u, d, i));
            if (maxn > sum / 2)
                printf("No\n");
            else
                printf("Yes\n");
        }
    }
}

signed main() { solve(); }

F. Bracket Distance

提示1：贪心地去选择单层括号序列。

提示2：使用 $set$ 去维护两个括号的位置。

我们假设选定的单层括号子序列左括号与右括号的下标序列为 $x_1,y_1,\dots,x_n,y_n$ ，那么此时的答案为 $y_n-x_n + \dots y_1 -x_1$ ，又因为对于任意的两对相邻的括号对 $y_{m-1}<x_m$ ，所以很明显可知当且仅当选择一对括号对的时候答案最大，即尝试选择最右的右括号与最左的左括号，时间复杂度 $O(q\log n)$ 。

代码:

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

#define fer(i, a, n) for (int i = (a); i <= (n); ++i)

int main() {
    int n, q;
    string s;
    cin >> n >> q;
    cin >> s;
    set<int> leftbracket, rigthbracket;
    fer(i, 0, n - 1) if (s[i] == '(') leftbracket.insert(i);
    else rigthbracket.insert(i);
    fer(i, 1, q) {
        int pos;
        char c, lstc;
        cin >> pos >> c;
        --pos;
        lstc = s[pos];
        s[pos] = c;
        if (lstc == '(')
            leftbracket.erase(pos);
        else
            rigthbracket.erase(pos);
        if (c == '(')
            leftbracket.insert(pos);
        else
            rigthbracket.insert(pos);
        if (leftbracket.empty() || rigthbracket.empty()) {
            cout << 0 << '\n';
            continue;
        }
        int mi = *leftbracket.begin(), mx = *prev(rigthbracket.end());
        cout << max(0, mx - mi) << '\n';
    }
}

G. Dingding and His Favorite Finite Binary String

提示1：考虑如何翻转使得翻转次数最少

提示2：考虑什么情况下会出现多种翻转方案

为了使得总的翻转次数最少，我们一定要使得一段内翻转后的字符与其原先出现次数多的那个字符相同。

当 $k$ 为奇数时，为了翻转次数最少，翻转方案一定只有 $1$ 种，例如我们考虑 $k=3$ ， $010$ 一定只能翻转成 $000$ ， $011$ 一定只能翻转成 $111$ 。

只有当 $k$ 为偶数时，我们才需要考虑翻转段数最少与翻转方案数，从 $k=2$ 开始考虑，假如有一段是这样 00 01 10 00 ，那么我们一定要把中间两端翻转成 $00$ ，这样才可以使得总的段数最少，即为了使得段数最少，那么我们一定要让一段翻转结束后与最邻近的左右两个翻转后确定的两个段之一（或者全部）相同。

当 $k$ 为偶数且两端的翻转后确定的两个段不同时，会出现多种情况，比如 $k=2$ 时的 00 01 01 01 11，那么此时就会出现 $4$ 种情况即 00 11 11 11 11 , 00 00 11 11 11, 00 00 00 11 11, 00 00 00 00 11，即把答案数乘以两个不同的翻转后确定的段之间的段的数量加 $1$ 。

时间复杂度 $O(n)$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

#define fer(i, a, n) for (int i = (a); i <= (n); ++i)

const int mod = 998244353;

pii check(string s, int k) {
    int sum1 = count(s.begin(), s.end(), '1');
    if (sum1 * 2 == k)
        return { sum1, -1 };
    if (sum1 > k / 2)
        return { k - sum1, 1 };
    if (sum1 <= k / 2)
        return { sum1, 0 };
    return { -114514, -1919180 };
}

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s = '?' + s;
    tuple<int, int, long long> ans{ 0, 0, 1 };
    auto& [a, b, c] = ans;
    vector<pii> v;
    for (int i = 1; i <= n; i += k) {
        auto [add, tag] = check(s.substr(i, k), k);
        if (~tag)
            v.push_back({ tag, i / k });
        a += add;
    }
    int sz = v.size();
    for (int i = 0; i <= sz - 2; i++)
        if (v[i].first != v[i + 1].first)
            b++, c = (c * (v[i + 1].second - v[i].second)) % mod;
    if (v.empty())
        c = 2;
    cout << a << ' ' << b + 1 << ' ' << c % mod << '\n';
}
main() {
    int t;
    cin >> t;
    while (t--) solve();
}

H. 石头剪刀布

每次使用石头对剪刀，剪刀对布，布对石头可以使得赢的次数最多。、

相同的，如何考虑赢得次数最少，即输的和平局的次数最多，那么就使用石头对石头和布，剪刀对剪刀与石头，布对布与剪刀即可，时间复杂度 $O(t)$ 。

代码（贪心）：

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int a1, b1, c1, a2, b2, c2;
        cin >> a1 >> b1 >> c1 >> a2 >> b2 >> c2;
        int n = a1 + b1 + c1;
        assert(a1 + b1 + c1 == a2 + b2 + c2);
        cout << n - min(a2, n - b1) - min(b2, n - c1) - min(c2, n - a1) << ' '
             << min(a2, b1) + min(b2, c1) + min(c2, a1) << '\n';
    }
}

代码（网络流）By MMSD的队-(周天逸,殷晓铭,戴高乐)

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 10;
const int maxn = 100, maxm = 1200;
typedef long long LL;

struct Edge {
    int v, f, nxt;
};
int n, src, sink;
int g[maxn + 10];
int nume;
Edge e[maxm * 2 + 10];

void addEdge(LL u, LL v, LL c) {
    e[++nume].v = v;
    e[nume].f = c;
    e[nume].nxt = g[u];
    g[u] = nume;
    e[++nume].v = u;
    e[nume].f = 0;
    e[nume].nxt = g[v];
    g[v] = nume;
}

queue<int> que;
bool vis[maxn + 10];
LL dist[maxn + 10];

void bfs() {
    memset(dist, 0, sizeof(dist));
    while (!que.empty()) que.pop();
    vis[src] = true;
    que.push(src);

    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int i = g[u]; i; i = e[i].nxt)
            if (e[i].f && !vis[e[i].v]) {
                {
                    que.push(e[i].v);
                    dist[e[i].v] = dist[u] + 1;
                    vis[e[i].v] = true;
                }
            }
    }
}

int dfs(int u, int delta) {
    if (u == sink) {
        return delta;

    } else {
        int ret = 0;
        for (int i = g[u]; delta && i; i = e[i].nxt)
            if (e[i].f && dist[e[i].v] == dist[u] + 1) {
                int dd = dfs(e[i].v, min(e[i].f, delta));
                e[i].f -= dd;
                e[i ^ 1].f += dd;
                delta -= dd;
                ret += dd;
            }
        return ret;
    }
}

int maxflow() {
    int ret = 0;
    while (true) {
        memset(vis, 0, sizeof(vis));
        bfs();
        if (!vis[sink])
            return ret;
        ret += dfs(src, inf);
    }
}

void solve() {
    LL a, b, c, x, y, z;
    cin >> x >> y >> z >> a >> b >> c;
    memset(g, 0, sizeof(g));
    nume = 1;
    src = 0;
    sink = 7;
    addEdge(1, 4, min(a, x));
    addEdge(1, 6, min(a, z));
    addEdge(2, 4, min(b, x));
    addEdge(2, 5, min(b, y));
    addEdge(3, 6, min(c, z));
    addEdge(3, 5, min(c, y));
    addEdge(0, 1, a);
    addEdge(0, 2, b);
    addEdge(0, 3, c);
    addEdge(4, 7, x);
    addEdge(5, 7, y);
    addEdge(6, 7, z);
    cout << a + b + c - maxflow() << " ";
    LL res = 0;
    res = min(a, y) + min(b, z) + min(x, c);
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

I. YiYi and Her Unsorted Array

提示1：什么情况下无解。

答案：按照不能移动的位置将序列分段，假如连续的两段中右侧的最小值小于左侧的最大值无解。

提示2：怎么计算最小代价。

答案：使用 dp 。

我们反着考虑，为了使得移动的数字的和最小，那么我们需要找到和最大的单调不减的序列，这个可以使用dp完成，即 $dp_i=\max(dp_j+a[i])[j<i\&\&a[j]<a[i]]$ ，朴素的dp是 $O(n^2)$ 的。我们可以把每个位置的数字离散化后使用线段树区间查询优化dp，时间复杂度 $O(n\log n)$ 。

代码（dp）:

#include <bits/stdc++.h>
using namespace std;
#define fer(i, a, n) for (int i = (a); i <= (n); ++i)
using ll = long long;
const ll inf = 1145141919180;
struct segmeettree {
    vector<ll> mn, mx, a;
    int n;
    segmeettree(int n) {
        this->n = n;
        mn.resize(4 * n + 5, inf), mx.resize(4 * n + 1);
    }
    segmeettree(vector<ll>& a) {
        this->a = a;
        n = a.size() - 1;
        mn.resize(4 * n + 5, inf), mx.resize(4 * n + 1);
    }
    void build(int k, int l, int r) {
        if (l == r) {
            mn[k] = mx[k] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(k << 1, l, mid);
        build(k << 1 | 1, mid + 1, r);
        mx[k] = max(mx[k << 1], mx[k << 1 | 1]);
        mn[k] = min(mn[k << 1], mn[k << 1 | 1]);
    }
    void modify(int k, int l, int r, int pos, ll z) {
        if (l == r) {
            mx[k] = mn[k] = z;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            modify(k << 1, l, mid, pos, z);
        else
            modify(k << 1 | 1, mid + 1, r, pos, z);
        mx[k] = max(mx[k << 1], mx[k << 1 | 1]);
        mn[k] = min(mn[k << 1], mn[k << 1 | 1]);
    }
    ll qmin(int k, int l, int r, int a, int b) {
        if (l == a && r == b)
            return mn[k];
        int mid = (l + r) >> 1;
        if (b <= mid)
            return qmin(k << 1, l, mid, a, b);
        else if (a > mid)
            return qmin(k << 1 | 1, mid + 1, r, a, b);
        else
            return min(qmin(k << 1, l, mid, a, mid), qmin(k << 1 | 1, mid + 1, r, mid + 1, b));
    }
    ll qmax(int k, int l, int r, int a, int b) {
        if (l == a && r == b)
            return mx[k];
        int mid = (l + r) >> 1;
        if (b <= mid)
            return qmax(k << 1, l, mid, a, b);
        else if (a > mid)
            return qmax(k << 1 | 1, mid + 1, r, a, b);
        else
            return max(qmax(k << 1, l, mid, a, mid), qmax(k << 1 | 1, mid + 1, r, mid + 1, b));
    }
};

void solve() {
    int n, k;
    cin >> n >> k;
    vector<ll> a(n + 1), ban(k + 1);
    fer(i, 1, n) cin >> a[i];
    fer(i, 1, k) cin >> ban[i];
    sort(ban.begin() + 1, ban.end());
    ban.erase(unique(ban.begin() + 1, ban.end()), ban.end());
    k = ban.size() - 1;
    segmeettree tree1(a);
    tree1.build(1, 1, n);
    vector<pair<int, int>> ck;
    fer(i, 1, k) {
        if (ban[i] - 1 >= ban[i - 1] + 1)
            ck.push_back({ ban[i - 1] + 1, ban[i] - 1 });
        ck.push_back({ ban[i], ban[i] });
        if (i == k && ban[i] != n)
            ck.push_back({ ban[i] + 1, n });
    }
    if (k == 0)
        ck.push_back({ 1, n });
    int szck = ck.size();
    fer(i, 0, szck - 2) {
        auto [l1, r1] = ck[i];
        auto [l2, r2] = ck[i + 1];
        ll nowmx = tree1.qmax(1, 1, n, l1, r1);
        ll nowmn = tree1.qmin(1, 1, n, l2, r2);
        if (nowmn < nowmx) {
            cout << "-1\n";
            return;
        }
    }
    //在每个段中找到单调上升的最大值的和
    ll ans = 0;
    fer(i, 0, szck - 1) {
        auto [l, r] = ck[i];
        if (l == r)
            continue;
        vector<ll> aa{ 0 };
        fer(j, l, r) aa.push_back(a[j]);
        r = r - l + 1, l = 1;
        vector<ll> dp(r + 1);
        segmeettree tree2(r);
        auto bb = aa;
        sort(bb.begin() + 1, bb.end());
        bb.erase(unique(bb.begin() + 1, bb.end()), bb.end());
        map<ll, ll> idx;
        int sz = bb.size() - 1;
        fer(i, 1, sz) idx[bb[i]] = i;
        fer(j, 1, r) {
            ll nowid = idx[aa[j]];
            dp[j] = aa[j] + tree2.qmax(1, 1, r, 1, nowid);
            tree2.modify(1, 1, r, nowid, dp[j]);
        }
        ll mx = *max_element(dp.begin() + 1, dp.end()), sum = accumulate(aa.begin() + 1, aa.end(), 0ll);
        ans += sum - mx;
    }
    cout << ans << '\n';
}
signed main() {
    int _;
    cin >> _;
    while (_--) solve();
}

代码(dp) By 戚雨林

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

const int N = 500005;

typedef long long LL;
LL dat[N];
int a[N], b[N], c[N], d[N], n;

LL Ask(int x) {
    LL res = 0ll;
    while (x) {
        res = max(dat[x], res);
        x -= x & (-x);
    }
    return res;
}

void Add(int x, LL w) {
    while (x <= n) {
        dat[x] = max(dat[x], w);
        x += x & (-x);
    }
}

void Rem(int x) {
    while (x <= n) {
        dat[x] = 0ll;
        x += x & (-x);
    }
}

LL Calc(int l, int r) {
    LL res = 0ll, w;
    for (int i = l; i <= r; ++i) {
        d[i] = lower_bound(a + 1, a + n + 1, c[i]) - a;
        w = Ask(d[i]) + (LL)(c[i]);
        Add(d[i], w);
        // cout<<i<<' '<<d[i]<<' '<<Ask(d[i])<<endl;
        res = max(res, w);
    }
    for (int i = l; i <= r; ++i) {
        Rem(d[i]);
    }
    return res;
}

int main() {
    int T, k;
    LL ans;
    bool flag;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        ans = 0ll;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            c[i] = a[i];
            ans += c[i];
        }
        for (int i = 1; i <= k; ++i) {
            scanf("%d", &b[i]);
        }
        sort(b + 1, b + k + 1);
        b[0] = 0;
        b[k + 1] = n + 1;
        for (int i = 0; i <= k; ++i)
            if (b[i] + 1 < b[i + 1])
                sort(a + b[i] + 1, a + b[i + 1]);
        flag = true;
        for (int i = 1; i < n; ++i)
            if (a[i] > a[i + 1]) {
                flag = false;
                break;
            }
        if (!flag) {
            printf("-1\n");
            continue;
        }
        for (int i = 0; i <= k; ++i)
            if (b[i] + 1 < b[i + 1]) {
                ans -= Calc(b[i] + 1, b[i + 1] - 1);
            }
        for (int i = 1; i <= k; ++i)
            if (b[i] != b[i - 1])
                ans -= c[b[i]];
        printf("%lld\n", ans);
    }
    return 0;
}

J. 小Q的机器

题解等待更新。

K. Going to Find Your Love

提示1：这题是不是很像单源最短路。

提示2：考虑使用类似dp的方法完成此题。

我们记 $dist_{i,j}$ 表示到达 $i$ 点搬走 $j$ 次箱子的最短距离，那么：

dist[v][j]=\min(dist[u][j]+w[u][v])\ \ \ 假如v点没有障碍物\\ dist[v][j]=\min(dist[u][j-1]+w[u][v])\ \ \ 假如v点有障碍物

使用单源最短路优化dp即可，时间复杂度 $O(kn\log m)$ 。

代码1（spfa）：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define fer(i, a, n) for (int i = (a); i <= (n); ++i)

const int maxn = 1e5 + 5;
const int maxk = 6;

int n, m, p, k;
ll dist[maxn][maxk];
vector<pair<int, ll>> e[maxn];
int isbad[maxn];
int isque[maxn][maxk];

void spfa() {
    memset(dist, 0x1f, sizeof(dist));
    dist[1][0] = 0;
    isque[1][0] = 1;
    queue<pair<int, int>> q;
    q.push({ 1, 0 });
    while (!q.empty()) {
        auto [u, tim] = q.front();
        q.pop();
        isque[u][tim] = 0;
        for (auto [v, w] : e[u]) {
            if (isbad[v])
                fer(i, 1, k) {
                    if (dist[v][i] > w + dist[u][i - 1]) {
                        dist[v][i] = w + dist[u][i - 1];
                        if (!isque[v][i])
                            isque[v][i] = 1, q.push({ v, i });
                    }
                }
            else
                fer(i, 0, k) {
                    if (dist[v][i] > w + dist[u][i]) {
                        dist[v][i] = w + dist[u][i];
                        if (!isque[v][i])
                            isque[v][i] = 1, q.push({ v, i });
                    }
                }
        }
    }
}

signed main() {
    cin >> n >> m >> p >> k;
    fer(i, 1, p) {
        int x;
        cin >> x;
        isbad[x] = 1;
        assert(x != 1);
    }
    fer(i, 1, m) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        e[u].push_back({ v, w });
    }
    spfa();
    fer(i, 1, n) {
        ll ans = 1e16;
        fer(j, 0, k) ans = min(ans, dist[i][j]);
        if (ans > 100000000000000)
            cout << "-1 ";
        else
            cout << ans << ' ';
    }
}

代码2（dijkstra）By 戚雨林

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

typedef long long LL;

const LL INF = (LL)(1e18);
const int N = 100005 * 6;

int tot;
int bl[100005];
int id[100005][6];
LL dis[N];
bool vis[N];
vector<int> e[N];
vector<LL> f[N];
priority_queue<pair<LL, int> > Q;

void Dj() {
    for (int i = 1; i <= tot; ++i) dis[i] = INF;
    dis[id[1][0]] = 0;
    Q.push(make_pair(0ll, id[1][0]));
    fill(vis, vis + tot + 1, 0);
    int x, y;
    while (!Q.empty()) {
        x = Q.top().second;
        Q.pop();
        if (vis[x])
            continue;
        vis[x] = true;
        for (int i = 0; i < e[x].size(); ++i) {
            y = e[x][i];
            if (dis[y] > dis[x] + f[x][i]) {
                dis[y] = dis[x] + f[x][i];
                Q.push(make_pair(-dis[y], y));
            }
        }
    }
}

int main() {
    int n, m, p, k;
    int x, y;
    LL wei;
    cin >> n >> m >> p >> k;
    for (int i = 0; i < p; ++i) {
        cin >> x;
        bl[x] = 1;
    }
    tot = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= k; ++j) id[i][j] = ++tot;
    for (int i = 0; i < m; ++i) {
        cin >> x >> y >> wei;
        for (int j = 0; j + bl[y] <= k; ++j) {
            e[id[x][j]].push_back(id[y][j + bl[y]]);
            f[id[x][j]].push_back(wei);
        }
    }
    Dj();
    LL ans;
    for (int i = 1; i <= n; ++i) {
        ans = dis[id[i][0]];
        for (int j = 1; j <= k; ++j) ans = min(ans, dis[id[i][j]]);
        if (ans == INF)
            ans = -1;
        printf("%lld ", ans);
    }
    return 0;
}

L. 聪明的小高

枚举第一轮的出牌情况，根据题意判断当前枚举第一轮出牌方式是否合理，并计算出胜者。

根据第一轮胜者和第一轮出牌情况计算出第二轮胜者，判断哪一家胜利即可。

小高也有可能一次出两张牌（如果两张牌）相同的情况下取得胜利。

注意，在小高第一次出牌确定的情况下，必须后面三人所有的合法出牌情况下第二轮均能小高或小黄获胜才能算作小高胜利。

时间复杂度 $O(32t)$ 。

代码1 By 黄天宇

#include <iostream>
#include <string>

using namespace std;
struct card {
    int rank;
    char suit;
};
card a[4][2];
bool choice[4], ok = 1;
int verify() {
    char suit_std = a[0][choice[0]].suit;
    int win = 0, mx = a[0][choice[0]].rank;
    for (int i = 1; i < 4; i++) {
        if (a[i][choice[i]].suit != suit_std && a[i][choice[i] ^ 1].suit == suit_std)
            return -1;
        if (a[i][choice[i]].suit == suit_std && a[i][choice[i]].rank > mx) {
            mx = a[i][choice[i]].rank;
            win = i;
        }
    }
    return win;
}

bool winner(int las) {
    char suit_std = a[las][choice[las] ^ 1].suit;
    int win = las, mx = a[las][choice[las] ^ 1].rank;
    for (int i = (las + 1) % 4; i != las; i = (i + 1) % 4) {
        if (a[i][choice[i] ^ 1].suit == suit_std && a[i][choice[i] ^ 1].rank > mx) {
            mx = a[i][choice[i] ^ 1].rank;
            win = i;
        }
    }
    return !(win & 1);
}

bool check_pair() {
    if (a[0][0].rank != a[0][1].rank || a[0][0].suit != a[0][1].suit)
        return 0;
    int win = 0, mx = a[0][0].rank;
    for (int i = 1; i < 4; i++) {
        if (a[i][0].suit != a[0][0].suit || a[i][1].suit != a[0][0].suit)
            continue;
        if (a[i][0].rank != a[i][1].rank)
            continue;
        if (a[i][0].rank > mx)
            mx = a[i][0].rank, win = i;
    }
    return !(win & 1);
}

void dfs(int cur) {
    if (cur == 4) {
        int k = verify();
        if (k >= 0)
            ok &= winner(k);
        return;
    }
    for (int i = 0; i < 2; i++) {
        choice[cur] = i;
        dfs(cur + 1);
    }
}
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        bool ans = false;
        for (int i = 0; i < 4; i++) {
            string s1, s2;
            cin >> s1 >> s2;
            a[i][0].rank = s1[0] - '0', a[i][0].suit = s1[1];
            a[i][1].rank = s2[0] - '0', a[i][1].suit = s2[1];
        }
        for (int i = 0; i < 2; i++) {
            ok = 1;
            choice[0] = i;
            dfs(1);
            ans |= ok;
        }
        ans |= check_pair();
        if (ans)
            puts("Gao");
        else
            puts("Yang");
    }
}

代码2 By 汪子杰

#include <bits/stdc++.h>

using namespace std;

struct pai {
    int num;
    char c;
} a[4][2];

void Print(pai x) { cout << x.num << ' ' << x.c << endl; }

int nx(int x) { return (x + 1) % 4; }

int first, fi[4];
bool flag;
void firstPlay(int x) {
    if (x == first) {
        char col;
        col = a[first][fi[first]].c;
        int maxId = first;
        for (int i = 1; i < 4; i++) {
            if (a[i][fi[i]].c == col)
                if (a[i][fi[i]].num > a[maxId][fi[maxId]].num)
                    maxId = i;
        }
        int _first = maxId;
        for (int i = 0; i < 4; i++) {
            fi[i] = 1 - fi[i];
        }
        col = a[maxId][fi[maxId]].c;
        for (int i = nx(_first); i != _first; i = nx(i)) {
            if (a[i][fi[i]].c == col)
                if (a[i][fi[i]].num > a[maxId][fi[maxId]].num)
                    maxId = i;
        }
        for (int i = 0; i < 4; i++) {
            fi[i] = 1 - fi[i];
        }
        if (maxId % 2)
            flag = false;
        return;
    }

    if (a[x][0].c == a[first][fi[first]].c && a[x][1].c == a[first][fi[first]].c) {
        fi[x] = 0;
        firstPlay(nx(x));
        fi[x] = 1;
        firstPlay(nx(x));
    } else if (a[x][0].c == a[first][fi[first]].c) {
        fi[x] = 0;
        firstPlay(nx(x));
    } else if (a[x][1].c == a[first][fi[first]].c) {
        fi[x] = 1;
        firstPlay(nx(x));
    } else {
        fi[x] = 0;
        firstPlay(nx(x));
        fi[x] = 1;
        firstPlay(nx(x));
    }
}

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        string s;
        for (int i = 0; i < 4; i++) {
            cin >> s;
            a[i][0].num = s[0] - '0', a[i][0].c = s[1];
            cin >> s;
            a[i][1].num = s[0] - '0', a[i][1].c = s[1];
        }
        flag = true;
        first = 0;
        fi[first] = 0;
        firstPlay(1);

        if (flag) {
            cout << "Gao" << endl;
            memset(fi, 0, sizeof(fi));
            continue;
        }

        flag = true;
        first = 0;
        fi[first] = 1;
        firstPlay(1);

        if (flag) {
            cout << "Gao" << endl;
            memset(fi, 0, sizeof(fi));
            continue;
        }

        if (a[0][0].c == a[0][1].c && a[0][0].num == a[0][1].num) {
            int maxId = 0;
            for (int i = 1; i < 4; i++) {
                if (a[i][0].c == a[i][1].c && a[i][0].num == a[i][1].num && a[i][0].num > a[maxId][0].num &&
                    a[i][0].c == a[0][0].c) {
                    maxId = i;
                }
            }
            if (maxId % 2 == 0) {
                cout << "Gao" << endl;
                memset(fi, 0, sizeof(fi));
                continue;
            }
        }

        cout << "Yang" << endl;
        memset(fi, 0, sizeof(fi));
    }

    return 0;
}

代码3：

#include <bits/stdc++.h>
using namespace std;
#define fer(i, a, n) for (int i = (a); i <= (n); ++i)

struct card {
    int num, isuse;
    char se;
    card() { isuse = 0, num = 0, se = 'A'; }
    void reset() { isuse = 0, num = 0, se = 'A'; }
    void fead() {
        string s;
        cin >> s;
        num = s[0] - '0', se = s[1];
    }
    bool operator==(card oth) { return oth.num == num && oth.se == se && oth.isuse == isuse; }
};

card cd[5][2];

bool grt(card a, card b) {
    if (b.se == a.se && b.num > a.num)
        return false;
    return true;
}

bool same(card a, card b) { return a.se == b.se; }

bool check(card a, card b, card c)  // b的卡和a的卡比较，是否能出choice
{
    if (!b.isuse && same(a, b))
        return true;
    if (!b.isuse && (!same(a, c) || c.isuse))
        return true;
    return false;
}

pair<int, int> getwinner1(int x)  // x: 0~15
{
    vector<int> pai(5);
    fer(i, 0, 3) pai[i + 1] = x >> i & 1;
    card c1 = cd[1][pai[1]];
    int ans = 1;
    fer(i, 2, 4) if (!check(c1, cd[i][pai[i]], cd[i][pai[i] ^ 1])) return { -1, -1 };
    fer(i, 2, 4) if (!grt(c1, cd[i][pai[i]])) c1 = cd[i][pai[i]], ans = i;
    return { ans, x };
}

int getwinner2(int st, int x) {
    x = ((1 << 4) - 1) ^ x;  //第二轮卡牌
    vector<int> pai(4);
    fer(i, 0, 3) pai[i] = x >> i & 1;
    --st;  //第一轮胜者
    int win = st, now = st;
    card c = cd[win + 1][pai[win]];
    fer(i, 1, 3) {
        now++, now %= 4;
        if (!grt(c, cd[now + 1][pai[now]]))
            c = cd[now + 1][pai[now]], win = now;
    }
    return win + 1;
}
void solve() {
    fer(i, 1, 4) fer(j, 0, 1) {
        cd[i][j].reset();
        cd[i][j].fead();
    }
    int f1 = 1, f2 = 1;
    for (int i = 0; i < 16; i++) {
        auto [a, st] = getwinner1(i);
        if (~a) {
            int winner = getwinner2(a, st);
            if (i & 1)
                f2 &= (winner % 2 == 1);
            else
                f1 &= (winner % 2 == 1);
        }
    }
    if (f1 || f2) {
        puts("Gao");
        return;
    }
    int win = 0;
    card now;
    if (cd[1][0] == cd[1][1])  //出两张
    {
        win = 1;
        now = cd[1][0];
        fer(i, 2, 4) if (cd[i][0] == cd[i][1]) if (!grt(now, cd[i][0])) now = cd[i][0], win = i;
    }
    if (win & 1)
        puts("Gao");
    else
        puts("Yang");
}
main() {
    int t;
    cin >> t;
    while (t--) solve();
}

写在最后：

对于这次夏季赛，非常感谢东南大学和 $CPC$ 俱乐部能给我这次出题的机会。

也非常感谢一下所有的验题人，正是因为你们的帮助，确保了题目的正确。

最后，也非常感谢所有参赛选手的积极参加。