A Sleeping Time

知识点：模拟、取模

时刻每经过 $24$ 小时循环一次，因此起床时刻就是 $(x+t)\bmod 24$。

时间复杂度 $\mathcal{O}(1)$。

void solve() {
    int x, t;
    cin >> x >> t;
    cout << (x + t) % 24 << endl;
}

B Is it Palidrome?

知识点：字符串、回文、分类讨论

回文只要求每一对对称位置相同，各对位置之间互不影响。

枚举所有对称位置：

• 若存在两个不同的确定字母，无论如何替换都不能回文，输出 $\texttt{impossible}$；

• 否则一定能补成回文，此时只要某一对中存在问号，也能把这一对填成不同字母，输出 $\texttt{possible}$；若所有对称位置都是相同的确定字母，则输出 $\texttt{certainly}$。

奇数长度时，中间字符不影响回文性，即使它是问号也不用考虑。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n;
    string s;
    cin >> n >> s;
    bool f = 0;
    for (int i = 0; i < n / 2; ++i) {
        if (s[i] == s[n - i - 1]) {
            if (s[i] == '?') f = 1;
        } else if (s[i] == '?' || s[n - i - 1] == '?') {
            f = 1;
        } else {
            return cout << "impossible" << endl, void();
        }
    }
    cout << (f ? "possible" : "certainly") << endl;
}

C AND and OR

知识点：位运算、数学、哈希表

对于每一个二进制位，两个数在这一位上的和，都等于按位与、按位或在这一位上的和，因此

$$(x\mathbin{\&}y)+(x\mathbin{|}y)=x+y.$$

问题转化为寻找 $a_i+a_j=k$。从左到右枚举当前数 $x$，用哈希表记录之前出现的数及其下标；若 $k-x$ 已经出现，就找到了一组答案。先查询再插入，保证两个下标不同且前者小于后者。若始终未找到，输出 $-1$。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n, k;
    cin >> n >> k;
    unordered_map<int, int> mp;
    bool f = 0;
    int a, b;
    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        if (!f && mp.find(k - x) != mp.end()) a = mp[k - x], b = i, f = 1;
        mp[x] = i;
    }
    if (!f) return cout << -1 << endl, void();
    cout << a << " " << b << endl;
}

D Light up the Graph

知识点：图论、贡献拆分、贪心

点亮一个点，只会给它的每个白色邻点带来 $+1$ 的贡献、每个黑色邻点带来 $-1$ 的贡献。设 $a_u$ 为点 $u$ 的白色邻点数减去黑色邻点数，$c_u$ 表示是否点亮，则图的总价值为

$$\sum_{u=1}^{n}c_u a_u.$$

每个 $c_u$ 都可以独立选择，因此点亮所有 $a_u>0$ 的点即可；$a_u=0$ 的点不影响答案，可以不点亮。枚举每条边，用另一端的颜色更新两端的贡献。

时间复杂度 $\mathcal{O}(n+m)$。

void solve() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    vector<int> a(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        a[u] += s[v] == '0' ? 1 : -1;
        a[v] += s[u] == '0' ? 1 : -1;
    }

    vector<int> ans;
    for (int i = 0; i < n; ++i)
        if (a[i] > 0) ans.push_back(i + 1);
    cout << ans.size() << endl;
    for (auto v : ans) cout << v << " ";
    cout << endl;
}

E Rock-Paper-Scissors String Game

知识点：博弈、构造、分类讨论

有合法操作就先手必胜，因为总能一步删到无法操作的状态。

记 $x\succ y$ 表示字符 $x$ 能赢过字符 $y$。若首字符能赢尾字符，直接删掉整个串。否则，设首尾字符为 $x,y$，把开头连续的 $x$ 和结尾连续的 $y$ 留在外面，中间记为 $[l,r]$。既然存在合法操作，中间一定非空。

• 若 $s_l\succ y$，删除后缀 $[l,n]$，只留下 $x$。

• 若 $x\succ s_r$，删除前缀 $[1,r]$，只留下 $y$。

• 否则，由 $s_l\ne x,s_r\ne y$ 和循环克制关系，必有 $s_l\succ s_r$，删除 $[l,r]$。

剩余串至多是前面一段 $x$、后面一段 $y$，而 $x$ 不能赢过 $y$，所以后手无法操作。

因此，从左到右记录出现过的字符，只要有某个已出现的字符能赢当前字符，就输出 $\texttt{Alice}$；否则输出 $\texttt{Bob}$。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n;
    string s;
    cin >> n >> s;
    unordered_map<char, bool> vis;
    for (auto c : s) {
        if ((c == 'R' && vis.find('P') != vis.end()) ||
            (c == 'P' && vis.find('S') != vis.end()) ||
            (c == 'S' && vis.find('R') != vis.end()))
            return cout << "Alice" << endl, void();
        vis[c] = 1;
    }
    cout << "Bob" << endl;
}

F Permutation of RBS

知识点：括号树、组合计数、栈、乘法逆元

把每个括号对看作一个结点，父亲是直接包含它的括号对，便得到一片森林。题目要求祖先的权值小于后代，等价于每个父亲的权值小于儿子。设 $siz_u$ 为以 $u$ 为根的子树大小，则答案为

$$\frac{n!}{\displaystyle\prod_{u=1}^{n}siz_u}.$$

考虑一棵子树：根必须取分配给这棵子树的最小权值，剩余权值按各儿子的子树大小分组，再分别递归计数。设 $f_u$ 表示给定一组不同权值时，这棵子树的合法赋值数，则

$$f_u=\frac{(siz_u-1)!}{\displaystyle\prod_{v\text{ 是 }u\text{ 的儿子}}siz_v!}\prod_{v\text{ 是 }u\text{ 的儿子}}f_v.$$

给所有树根接一个权值固定为 $0$ 的虚根，把转移展开：每个真实结点留下因子 $(siz_u-1)!/siz_u!=1/siz_u$，虚根贡献 $n!$，就得到上面的公式。

用栈匹配括号即可求出子树大小：读到左括号时创建大小为 $1$ 的结点并入栈；读到右括号时，这个结点的子树已经统计完毕，将其大小累加到父亲，并让答案除以它的大小。

时间复杂度 $\mathcal{O}(n\log p)$。

constexpr int mod = 1E9 + 7;
using Z = MInt<mod>;

void solve() {
    int n;
    string s;
    cin >> n >> s;
    vector<int> siz(n), st;
    Z ans = 1;
    for (int i = 1; i <= n; ++i) ans *= i;

    int id = 0;
    for (auto c : s) {
        if (c == '(') {
            siz[id] = 1;
            st.push_back(id++);
        } else {
            int u = st.back();
            st.pop_back();
            ans /= siz[u];
            if (!st.empty()) siz[st.back()] += siz[u];
        }
    }

    cout << ans << endl;
}

约定

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pii array<int, 2>
#define endl "\n"
 
void solve() {
     
}
 
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(20);
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}

使用到的算法模板见 $\texttt{github}$ 仓库 [林月的XCPC模板库](https://github.com/Anoth3rr/XCPC)