349

A - Zero Sum Game

void solve() {
    int n;cin >> n;
    int ans = 0;
    for (int i = 0;i < n - 1;i++) {
        int x;cin >> x;ans += x;
    }
    cout << -ans;
}

B - Commencement

由小写英文字母组成的字符串 $S$ 是一个好字符串，当且仅当它满足以下属性，且所有整数 $i$ 不小于 $1$ ：

在 $S$ 中出现 $i$ 次的字母恰好为零或恰好为两个。

给定一个字符串 $S$ ，判断它是否是一个好字符串。

void solve() {
    string s;cin >> s;
    map<char, int>mp;
    for (int i = 0;i < s.size();i++) {
        mp[s[i]]++;
    }
    vector<int> a(110);
    for (auto [x, y] : mp) {
        a[y]++;
    }
    bool ok = true;
    for (int i = 0;i <= 100;i++) {
        if (a[i] != 0 && a[i] != 2)ok = false;
    }
    if (ok)cout << "Yes\n";
    else cout << "No\n";
}

C - Airport Code

长度为 $3$ 的由大写英文字母组成的字符串 $T$ 是由小写英文字母组成的字符串 $S$ 的机场代码，当且仅当 $T$ 可以通过以下方法之一从 $S$ 推导出来：

从 $S$ 取长度为 $3$ 的子序列 (不一定连续)，并将其转换为大写英文字母，形成 $T$ 。
从 $S$ (不一定连续)中提取长度为 $2$ 的子序列，将其转换为大写字母，并在末尾添加 X，形成 $T$ 。

给定字符串 $S$

S 和 $T$ ，判断 $T$ 是否是 $S$ 的机场代码。

void solve() {
    string s, t;cin >> s >> t;
    for (int i = 0;i < t.size();i++) {
        t[i] = tolower(t[i]);
    }
    int ok = 0, k = 0;
    for (int i = 0;i < s.size();i++) {
        if (s[i] == t[k]) {
            k++;
        }
    }
    if (k == 3 || k == 2 && t[2] == 'x') {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

D - Divide Interval

对于非负整数 $l$ 和 $r$ $(l < r)$ ，让 $S (l, r)$ 表示将 $l$ 至 $r - 1$ 的整数依次排列而形成的序列 $(l, l + 1, \dots, r - 2, r - 1)$ 。此外，当且仅当一个序列可以用非负整数 $i$ 和 $j$ 表示为 $S (2^{i} j, 2^{i} (j + 1))$ 时，它才被称为好序列。

给你非负整数 $L$ 和 $R$ $(L < R)$ 。将序列 $S (L, R)$ 除以最少的好序列，并打印序列数和除法。更具体地说，找出有一对非负整数序列 $(l_{1}, r_{1}), (l_{2}, r_{2}), \dots, (l_{M}, r_{M})$ 满足下面条件的最小正整数 $M$ ，并打印出这样的 $(l_{1}, r_{1}), (l_{2}, r_{2}), \dots, (l_{M}, r_{M})$ 。

$L = l_{1} < r_{1} = l_{2} < r_{2} = \dots = l_{M} < r_{M} = R$
$S (l_{1}, r_{1}), S (l_{2}, r_{2}), \dots, S (l_{M}, r_{M})$ 是良好序列。

可以证明只有一种除法能使 $M$ 最小化。

Solution

位运算

注：

当 $l = 0$ 时需要特判。
位运算时加上 long long 以防不时之需：1ll << i

#define int long long
void solve() {
    int l, r;cin >> l >> r;
    vector<pair<int, int>> res;
    if (!l) {
        int i = 1;
        for (;i <= r;) {
            i *= 2;
            if (i > r) {
                i /= 2;break;
            }
        }
        res.push_back({0,i});
        l = i;
    }
    int p = l;
    for (;p <= r;) {
        int j = p, cnt = 1;
        while (j % 2 == 0) {
            cnt *= 2;j /= 2;
        }
        int pre = p;
        p += cnt;
        if (p > r) {
            p -= cnt;break;
        }
        res.push_back({pre,p});
    }
    bitset<60>s1(p), s2(r);
    for (int i = 59;i >= 0;i--) {
        if (s1[i] != s2[i]) {
            int ans = (1ll << i);
            res.push_back({p,ans + p});
            p += ans;
        }
    }
    cout << res.size() << '\n';
    for (auto [x, y] : res)cout << x << " " << y << "\n";
}

E - Weighted Tic-Tac-Toe

给定一个井子棋，在每个格子中含有对应的分数，两个人一人选择一个格子。

若有人先连三格，则直接赢，若平局，则分数高的分数。

Solution

博弈

(待更 $\dots$ )

官方题解

判定胜负的方法

游戏的每个时点的棋盘可以用一个 $3 \times 3$ 的二维数组 $C$ 来表示，其中每个元素都取值为 ${$ 白，红，蓝 $}$ 中的一个，表示了对应格子的颜色。因此，从盘面 $C$ 开始进行游戏，最终获胜的玩家记作 $f (C)$ 。

我们将全白的 $3 \times 3$ 的二维数组记为 $I$ （对应初始状态），所以我们要求的答案就是 $f (I)$ ，如果能快速地求得对于任意给定的 $C$ ，其 $f (C)$ ，就可以解决这个问题。

让我们考虑怎样计算 $f (C)$ 。以下，将当前的玩家记作 $x$ ，另一个玩家记作 $y$ 。

如果 $C$ 已经是终止状态（有 $3$ 个相同颜色的格子连成一条线，或者没有白色格子），那么很容易判断出胜负。

如果 $C$ 不是终止状态，那么 $x$ 可以选择一个白色格子，用自己的颜色来填充，从而转移到另一个盘面 $C^{'}$ 。这时有以下情况：

如果 $C$ 能够经过 $1$ 步操作转移到 $C^{'}$ ，且 $f (C^{'}) = x$ ，则说明 $x$ 可以通过这一步操作获胜
相反，对于 $C$ 能够经过 $1$ 步操作转移到的所有 $C^{'}$ ，如果 $f (C^{'}) = y$ ，那么无论 $x$ 怎么操作都无法获胜

根据上述性质，当我们知道了 $C$ 能够转移到的所有盘面 $C^{'}$ 的 $f (C^{'})$ 之后，就可以求得 $f (C)$ 。这种处理可以通过递归函数来实现。

递归函数的实现

在递归函数的实现中，当针对盘面 $C$ 调用函数 $f$ 时，会进行以下处理：

如果 $C$ 是终止状态，则判断胜负并返回答案
如果 $C$ 不是终止状态，则列举出从 $C$ 经过 $1$ 步操作可以到达的所有盘面 $C^{'}$
计算每个 $C^{'}$ 对应的 $f (C^{'})$
根据计算得到的 $f (C^{'})$ 结果，根据前述讨论判断出 $f (C)$ 的值

在处理函数 $f$ 的过程中，通过调用自身计算 $f (C^{'})$ （步骤 3），因此这样的处理方式称为递归。这里要注意，由于转移可以使盘面趋向终止状态，因此这种递归调用不会无限延续（形式上，构成了一个有向无环图 (DAG)）。

让我们来粗略地估计一下 $f$ 的调用次数。在第一回合中可以进行的操作有 $9$ 种，第二回合中有 $8$ 种……因此，直到从初始状态到终止状态为止，可能的操作组合大约有 $9! \approx 3.6 \times 10^{5}$ 种，因此这个处理方式是足够快速的（实际上，当有 $3$ 个相同颜色的格子连成一线时游戏就已结束了，递归调用会在那一点被终止，所以实际的调用次数会更少）。

实现示例 (Python)

扩展：通过记忆化递归实现

在这个问题中，即使采用朴素的递归函数也足够快速。但是，通过进行称为记忆化的优化，可以减少递归调用的次数。

在递归函数中，如果存在多种操作组合能够到达相同的盘面 $C$ ，那么针对 $C$ 的 $f (C)$ 就会被计算多次。但是，由于对于同一个盘面 $C$ ， $f (C)$ 总是相同的，因此不必每次都通过递归调用来求得 $f (C)$ 的值。可以在第一次计算 $f (C)$ 时将结果保存下来，在之后的调用中直接返回这个已经保存的值。

通过记忆化，在对 $C$ 进行递归调用时，可以有效地减少递归的次数。可以粗略地估计一下记忆化后 $f$ 的调用次数： $C$ 可能出现的情况大约有 $3^{3 \times 3} = 19683$ 种，而每个盘面能够转移到的盘面最多有 $9$ 种，因此 $f$ 的调用次数至多为 $19683 \times 9 \approx 1.7 \times 10^{5}$ 次。与不采用记忆化时估计的 $3.6 \times 10^{5}$ 相比，这个数字要小得多。

在这个问题中，并不需要使用记忆化，但是对于盘面数目较多或者可能的转移次数较多的问题，通过记忆化优化可以大幅改善计算量。

F - Subsequence LCM

给你一个长度为 $N$ 的正整数序列 $A = (A_{1}, A_{2}, \dots, A_{N})$ 和一个正整数 $M$ 。求以 $998244353$ 为模数， $A$ 的非空且不一定连续的子序列的个数，使得子序列中元素的最小公倍数（LCM）为 $M$ 。如果两个子序列取自序列中的不同位置，即使它们作为序列重合，也会被区分开来。此外，序列中单个元素的 LCM 就是该元素本身。