1994(div1+div2)

A. Diverse Game

佩特看了谢尔盖的数据流，得出了一个 $n \times m$ 的矩阵 $a$ ， $1 \leq a_{i} \leq n \times m, a_{i} \neq a_{j}$ 构造矩阵 $b$ ，使得 $b$ 对于任意 $1 \leq i \leq n, 1 \leq j \leq m$ ， $a_{i, j} \neq b_{i, j}$ 都成立。

给你一个矩阵 $a$ ，请构造出满足 Petr 要求的矩阵 $b$ ，或者确定这是不可能的。

只有 $n = 1, m = 1$ 的时候不可能，其他一定可以构造。

直接暴力构造会有一个问题：若 $a_{n, m} = n \times m$ ，则最后一个数字不会变，随便和前面的数字交换即可。

void solve() {
    int n, m;cin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(m + 1)), b(n + 1, vector<int>(m + 1));
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> a[i][j];b[i][j] = a[i][j];
        }
    }
    if (n == 1 && m == 1) {
        cout << "-1\n";return;
    }
    vector<int> vis(n * m + 1);
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            for (int k = 1;k <= n * m;k++) {
                if (a[i][j] != k && !vis[k]) {
                    b[i][j] = k;vis[k] = 1;break;
                }
            }
        }
    }
    if (b[n][m] == a[n][m])swap(b[1][1], b[n][m]);

    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cout << b[i][j] << " \n"[j == m];
        }
    }
}

标准答案：

直接输出 a[(i + 1) % n][(j + 1) % m] 即可，没有想到...

B. Fun Game

游戏开始时，沃瓦选择长度为 $n$ 的两个二进制序列 $s$ 和 $t$ ，并把它们交给万亚。二进制序列是仅由数字 $0$ 和 $1$ 组成的序列。凡亚可以选择整数 $l, r$ ，使得 $1 \leq l \leq r \leq n$ ，并且对于所有 $l \leq i \leq r$ 同时将 $s_{i}$ 替换为 $s_{i} \oplus s_{i - l + 1}$ ，其中 $s_{i}$ 是序列 $s$ 中的第 $i$ 个元素。

判断序列 $s$ 能不能变为 $t$ 。

当字符串 $s$ 有前置 0 时， $t$ 字符串前面必须也是 0，不然无法变为 $t$ ，其他情况都能变为 $t$

void solve() {
    int n;cin >> n;
    string s, t;cin >> s >> t;
    for (int i = 0;i < s.size();i++) {
        if (s[i] == '0') {
            if (t[i] != s[i]) {
                cout << "NO\n";
            }
        } else {
            break;
        }
    }
    cout << "YES\n";
}

C. Hungry Games

雅罗斯拉夫正在玩一款电脑游戏，在其中一个关卡中，他遇到了 $n$ 个排列成一排的蘑菇。每种蘑菇都有自己的毒性级别；从一开始的第 $i$ 个蘑菇的毒性级别为 $a_{i}$ 。雅罗斯拉夫可以选择两个整数 $1 \leq l \leq r \leq n$ ，然后他的角色就会从左到右轮流逐个吃掉这个分段中的蘑菇，也就是数字为 $l, l + 1, l + 2, \dots, r$ 的蘑菇。

角色的毒性等级为 $g$ ，最初等于 $0$ 。电脑游戏由数字 $x$ 定义--即任何时候的最大毒性级别。当食用毒性等级为 $k$ 的蘑菇时，会发生以下情况：

角色的毒性等级会增加 $k$ 。
如果 $g \leq x$ ，过程继续；否则， $g$ 变为零，过程继续。

雅罗斯拉夫感兴趣的是，有多少种方法可以选择 $l$ 和 $r$ 的值，使得 $g$ 的最终值不为零。帮助雅罗斯拉夫找到这个数字！

Solution

新知识：

想要直接将某个数组做前缀和直接：partial_sum(a.begin() + 1, a.end(), a.begin() + 1);
(针对下标 1~n)

对于下标 $l$ ，找到后面的最小下标 $k$ 使得 $a_{l} + a_{l + 1} + \dots + a_{k} > x \to p r e_{k} - p r e_{l - 1} > x$ ，

即 $a_{l} + a_{l + 1} + \dots + a_{k - 1} \leq x \to p r e_{k - 1} - p r e_{l - 1} \leq x$ ，则有 $k - l$ 种满足要求。

$⟹ p r e_{k} - p r e_{l - 1} ⟹ 0$ ，这个时候下标 $l \to k$ 之后结果为 0 ，若继续吃还有可能会有结果，即为 $f_{k + 1}$

$f_{i}$ 代表左边界为 $i$ 的满足条件的区间个数。

DP 动态转移方程： $f_{l} = (k - l) + f_{k + 1}$

#define int long long
void solve() {
    int n, x;cin >> n >> x;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    partial_sum(a.begin() + 1, a.end(), a.begin() + 1);
    vector<int> f(n + 2);
    for (int i = n - 1;i >= 0;i--) {
        int j = upper_bound(a.begin(), a.end(), a[i] + x) - a.begin();
        f[i] = f[j] + j - i - 1;
    }
    cout << accumulate(f.begin(), f.end(), 0ll) << '\n';
}

D. Funny Game

Vanya 有一个包含 $n$ 个顶点（编号从 $1$ 到 $n$ ）和 $a$ 个 $n$ 个整数的数组的图形；最初，图形中没有边。万尼亚觉得无聊，为了找点乐子，他决定进行 $n - 1$ 次运算。

操作数 $x$ （操作数从 $1$ 开始依次编号）如下：

选择 $2$ 个不同的数字 $1 \leq u, v \leq n$ ，使得 $| a_{u} - a_{v} |$ 可以被 $x$ 整除。
在顶点 $u$ 和 $v$ 之间添加一条无向边。

使用 $n - 1$ 运算帮助凡亚得到一个连通的图，或者确定这是不可能的。

Solution

抽屉原理

操作需要倒着进行(对答案没有影响)：从操作数 $n - 1$ 开始(后面依次递减)，需要找到 $x | | a_{u} - a_{v} |$ ，即 $a_{u} \equiv a_{v} (\mod x)$ 。

根据抽屉原理，每一次操作都一定能够找到两个点 $u, v$ 满足要求。

void solve() {
    int n;cin >> n;
    vector<int> a(n), p(n);
    iota(p.begin(), p.end(), 0);
    vector<pair<int, int>> ans;
    for (auto& i : a)cin >> i;
    for (int i = n - 1;i >= 1;i--) {
        vector<int> occ(i, -1);
        for (auto j : p) {
            if (occ[a[j] % i] != -1) {
                ans.push_back({j, occ[a[j] % i]});
                p.erase(find(p.begin(), p.end(), j));
                break;
            }
            occ[a[j] % i] = j;
        }
    }
    cout << "YES\n";
    reverse(ans.begin(), ans.end());
    for (auto [x, y] : ans)cout << x + 1 << " " << y + 1 << "\n";
}

E. Wooden Game

有一片森林，里面有 $k$ 棵有根的树木。伐木工蒂莫菲想通过以下操作砍伐整片森林：

选择其中一棵树的任意顶点的子树，并将其从树中移除。

蒂莫菲喜欢位运算，因此他希望删除的子树的大小的 bitwise OR 是最大的。请帮助他，找出他能得到的最大结果。

Solution

这个题目所给出的树没有任何用处，只有顶点个数 $a_{i}$ 有用。

对于某个树，设每次删除的子树大小为 $d_{1}, d_{2}, \dots, d_{t}$ ，易得： $\sum_{i = 1} d_{i} = n$ ，且 $d_{1} | d_{2} | \dots | d_{t} \leq n$ 。

若无子树大小为 $k$ ，可以将子树中的节点一个一个删除从而构造出 $k$

因此，对于这个树，可以构造 $[1, n]$ 中的所有答案

对于某个树， $n$ 的第 $k$ 位是 1，则可以直接构造出 $2^{k}$ ，若答案已经拥有了这个部分，则可以构造出 $2^{k} - 1$ ，从而保证了最优。

非常妙！

void solve() {
    int k;cin >> k;
    vector<int> a(k);
    for (int i = 0;i < k;i++) {
        cin >> a[i];
        for (int j = 0;j < a[i] - 1;j++) {
            int x;cin >> x;
        }
    }
    sort(a.rbegin(), a.rend());
    int ans = 0;
    for (auto x : a) {
        for (int i = __lg(x);i >= 0;i--) {
            if ((x >> i) & 1) {
                int y = (ans >> i) & 1;
                if (y == 0) {
                    ans |= (1 << i);
                } else {
                    ans |= (1 << i) - 1;
                    break;
                }
            }
        }
    }
    cout << ans << '\n';
}

F. Stardew Valley

鹈鹕镇由 $m$ 条双向道路连接着 $n$ 座房屋。有些道路上站着 NPC。农民布巴需要在每条路上与 NPC 走一走，并与他们交谈。

帮助农夫找到一条符合以下属性的路线：

路线从某个房子开始，沿着道路走，最后在同一个房子结束。
每条道路经过次数不能超过一次。
所有含有 NPC 的路都要走一次，没有 NPC 的道路则不用。

可以保证：只需在有 NPC 的道路上行走，就可以从任何其他房屋到达任何其他房屋。

Solution

欧拉图

类似的题目还有：F - Perils in Parallel

题目意思即这个图是 NPC 边的全集 加上 无 NPC 边的子集 (即删除一些无 NPC 的边) ，求这个图的欧拉回路。

拥有欧拉图的条件是每个顶点的度数都是偶数

对于删除单独的某一条边，可以使用代码中的技巧，g[u].push(i),edge[i]=u^v->int to=edge[i]^u 。

对于这个题，可能需要删除部分无 NPC 的边组成的图来做欧拉回路。只要图中的每个顶点的度数都是偶数，则一定存在欧拉回路，否则一定不存在欧拉回路。

将图中无 NPC 的边组成一个图，对于这个图进行处理，若能够使得所有顶点度数为偶，则继续求欧拉回路。

若有奇数个顶点有奇数的度数，则无法通过删边达到都为偶数度数，在搜索的过程中若某个顶点的度数为奇数，则需要将这个顶点和其连接的顶点之间的边删去一个

void solve() {
    int n, m;cin >> n >> m;
    vector<vector<int>> g(n + 1), blk(n + 1);
    vector<int> edge(m + 1);
    for (int i = 1;i <= m;i++) {
        int u, v, is;cin >> u >> v >> is;
        g[u].push_back(i);
        g[v].push_back(i);
        edge[i] = u ^ v;
        if (!is) {
            blk[u].push_back(i);
            blk[v].push_back(i);
        }
    }
    vector<int> deg(n + 1);
    for (int i = 1;i <= n;i++)deg[i] = g[i].size() & 1;
    vector<int> del(m + 1), vis(n + 1);
    auto dfs = [&](auto self, int u)->void {
        vis[u] = 1;
        for (auto x : blk[u]) {
            int to = edge[x] ^ u;
            if (vis[to])continue;
            self(self, to);
            if (deg[to]) {
                del[x] = 1;
                deg[to] ^= 1;
                deg[u] ^= 1;
            }
        }
        };
    int ok = 1;
    for (int i = 1;i <= n;i++) {
        if (vis[i])continue;
        dfs(dfs, i);
        ok &= !deg[i];
    }
    if (!ok) {
        cout << "NO\n";return;
    }
    cout << "YES\n";
    cout << m - accumulate(del.begin() + 1, del.end(), 0) << '\n';
    auto euler = [&](auto self, int u) ->void {
        while (g[u].size()) {
            int x = g[u].back();g[u].pop_back();
            int to = edge[x] ^ u;
            if (del[x])continue;
            del[x] = 1;
            self(self, to);
        }
        cout << u << " ";
        };

    euler(euler, 1);
    cout << '\n';
}