赛时 5/7，中途有点事，G 没打完。

A

直接将 $x$ 和 $y$ 相加后对 $12$ 取模即可。

特判取模后为 $0$ 的情况。

#include<bits/stdc++.h>
#define ll long long 

int T;

void solve() {
    int x, y;
    std::cin >> x >> y;
    int ans = (x + y) % 12;
    if(!ans) ans = 12;
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    T = 1;

    while(T--) {
        solve();
    }
    
    return 0;
}

B

模拟题，直接根据题意模拟即可。

#include<bits/stdc++.h>
#define ll long long 

int T;

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::string> s(n + 1);
    for(int i = 1; i <= n; i++) {
        std::cin >> s[i];
        s[i] = ' ' + s[i];
    }
    
    std::vector<int> score(n + 1, 0), ans;
    int maxn = 0;
    for(int i = 1; i <= m; i++) {
        int x = 0, y = 0;
        for(int j = 1; j <= n; j++) {
            if(s[j][i] == '0') x++;
            else y++;
        }
        if(x < y) {
            for(int j = 1; j <= n; j++) {
                if(s[j][i] == '0') score[j]++;
                maxn = std::max(maxn, score[j]);
            }
        }
        else {
            for(int j = 1; j <= n; j++) {
                if(s[j][i] == '1') score[j]++;
                maxn = std::max(maxn, score[j]);
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if(score[i] == maxn) ans.push_back(i);
    }
    for(auto x: ans) {
        std::cout << x << " ";
    }
    std::cout << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    T = 1;

    while(T--) {
        solve();
    }
    
    return 0;
}

C

维护答案，修改时先减去，修改后再加上即可。

#include<bits/stdc++.h>
#define ll long long 

int T;

void solve() {
    int n, q;
    std::cin >> n >> q;
    std::vector<ll> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    for(int i = 1; i <= n; i++) {
        std::cin >> b[i];
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        ans += std::min(a[i], b[i]);
    }
    for(int i = 1; i <= q; i++) {
        char c;
        ll x, y;
        std::cin >> c >> x >> y;
        ans -= std::min(a[x], b[x]);
        if(c == 'A') {
            a[x] = y;
        }else {
            b[x] = y;
        }
        ans += std::min(a[x], b[x]);
        std::cout << ans << "\n";
    }

}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    T = 1;

    while(T--) {
        solve();
    }
    
    return 0;
}

D

稍微麻烦一点的走迷宫问题。

BFS即可，对于开关操作，用开关反转的两个图，记录开关次数来判断在哪个图上跑。

#include<bits/stdc++.h>
#define ll long long 

int T;

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::string> g(n + 1), f(n + 1);
    for(int i = 1; i <= n; i++) {
        std::cin >> g[i];
        g[i] = ' ' + g[i];
        f[i] = g[i];
    }

    int sx, sy, gx, gy;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(f[i][j] == 'o') f[i][j] = 'x';
            else if(f[i][j] == 'x') f[i][j] ='o';
            if(g[i][j] == 'S') {
                sx = i;
                sy = j;
            }
            if(g[i][j] == 'G') {
                gx = i;
                gy = j;
            }
        }
    }

    std::queue<std::array<int, 4>> q;
    std::map<std::array<int, 3>, bool> flag;
    q.push({sx, sy, 0, 0});
    flag[{sx, sy, 0}] = true;
    bool is_find = false;
    int ans = -1;
    while(!q.empty()) {
        auto [x, y, step, sw] = q.front();
        // std::cout << x << " " << y << " " << step << " " <<sw <<"\n";
        q.pop();
        for(int i = 0; i < 4; i++) {
            int h = x + dx[i], l = y + dy[i];
            if(h >= 1 && h <= n && l >= 1 && l <= m) {
                if(flag[{h, l, sw & 1}]) continue;
                if(sw&1) {
                    if(f[h][l] == '#' || f[h][l] == 'x') continue;
                    if(f[h][l] == 'G') {
                        ans = step + 1;
                        is_find = true;
                        break;
                    }
                    else {
                        flag[{h, l, sw & 1}] = true;
                        q.push({h, l, step + 1, sw + (f[h][l] == '?')});
                    }
                } else {
                    if(g[h][l] == '#' || g[h][l] == 'x') continue;
                    if(g[h][l] == 'G') {
                        ans = step + 1;
                        is_find = true;
                        break;
                    }
                    else {
                        flag[{h, l, sw & 1}] = true;
                        q.push({h, l, step + 1, sw + (g[h][l] == '?')});
                    }
                }
            }
        }
        if(is_find) break;
    }

    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    T = 1;

    while(T--) {
        solve();
    }
    
    return 0;
}

/*
. ：空单元格。
# : 障碍单元格。
S ：起始单元格。
G : 目标单元格。
o : 打开的单元格。
x : 关闭的单元格。
? : 开关单元。
*/

E

并查集。

每个点维护一个 set，用来存自己集合内的黑点，然后合并的时候启发式合并即可。

#include<bits/stdc++.h>
#define ll long long 

int T;

void solve() {
    int n, q;
    std::cin >> n >> q;

    std::vector<int> uf(n + 1), color(n + 1, 0);
    for(int i = 1; i <= n; i++) {
        uf[i] = i;
    }
    
    std::function<int(int)> find;
    find = [&](int x) {
        if (uf[x] != x) {
            uf[x] = find(uf[x]);
        }
        return uf[x];
    };

    std::vector<std::set<int>> s(n + 1);
    for(int i = 1; i <= q; i++) {
        int opt, u, v;
        std::cin >> opt;
        if(opt == 1) {
            std::cin >> u >> v;
            int fu = find(u), fv = find(v);
            if(fu == fv) continue;
            if(s[fu].size() < s[fv].size()) std::swap(fu, fv);
            uf[fv] = fu;
            for(auto x: s[fv]) {
                s[fu].insert(x);
            }
        }
        else if(opt == 2) {
            std::cin >> v;
            int fv = find(v);
            if(!color[v]) {
                s[fv].insert(v);
            } else {
                s[fv].erase(v);
            }
            color[v] ^= 1;
        } else {
            std::cin >> v;
            int fv = find(v);
            if(s[fv].size()) std::cout << "Yes\n";
            else std::cout << "No\n";
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    T = 1;

    while(T--) {
        solve();
    }
    
    return 0;
}

G

设 $\sqrt{n^2+n+X} = k$.
两边平方得 $n^2 + n + X = k^2$.
左边配方得 $(n + \frac{1}{2})^2 - \frac{1}{4} + X = k^2$.
移项并用平方差公式得 $(n+\frac{1}{2}+k)(n + \frac{1}{2}-k) = \frac{1}{4}-X$.
两边乘四得 $(2n+1+2k)(2n+1-2k)=1-4X$.
$X$ 已知，所以 $2n+1+2k$ 和 $2n+1-2k$ 都是 $1-4X$ 的因数。
所以 $O(\sqrt{X})$ 求出 $1-4X$ 的所有因数对后，一个因数对 $(a, b)$ 合法当且仅当 $a$ 和 $b$ 都是奇数，且 $a-b$ 是 $4$ 的倍数。对于一个合法的因数对，其对应的 $n=\dfrac{a+b-2}{4}$.

#include<bits/stdc++.h>
#define ll long long 

int T;

void solve() {
    ll x;
    std::cin >> x;
    ll C = 1 - 4 * x;
    
    std::set<ll> ans;
    ll sqrtC = std::sqrt(std::abs(C));
    for(ll i = 1; i <= sqrtC; i++) {
        if(std::abs(C) % i != 0) continue;
        std::vector<std::array<ll, 2>> factors;
        ll j = std::abs(C) / i;
        if(C > 0) {
            factors.push_back({i, j});
            factors.push_back({j, i});
            factors.push_back({-i, -j});
            factors.push_back({-j, -i});
        } else {
            factors.push_back({i, -j});
            factors.push_back({j, -i});
            factors.push_back({-i, j});
            factors.push_back({-j, i});
        }
        for(auto [a, b]: factors) {
            if(std::abs(a % 2) != 1 || std::abs(b % 2) != 1) continue;
            if((b - a) % 4 != 0) continue;
            ans.insert((a + b - 2) / 4);
        }
    }
    
    std::cout << ans.size() << "\n";
    for(auto x: ans) {
        std::cout << x << " ";
    }std::cout << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    T = 1;

    while(T--) {
        solve();
    }
    
    return 0;
}