C - Not Equal 285
求长度为 n，两两不同，且满足 \(1\le a_i\le c_i\) 的数组的数量
数组 c 排序，答案就是 \(\prod\limits_i(c_i-(i-1))\)，其中 \(i-1\) 个位置被前面占了
D - Collision 686
给定一棵树，q 次询问，一个人从 u 走向 v，另一个人从 v 走向 u，同时同速。问两人在点上还是在边上相遇
若 u 和 v 深度奇偶性相同则在点上相遇，否则在边上
E - Shiritori 2153
两个人成语接龙，每个人说的单词前三个字母须与上一个人说的最后三个字母同。给定单词表，单词可重复使用，不能说者输，问从每个单词出发谁会赢（或者平局）
把每个单词视为边，把边（单词）的状态放在它的终端点（三个字母）上，按拓扑排序的逆序递推状态，最后没有状态的点是平局
（似乎我对输赢的定义跟大家相反）
先手必败点：存在先手必胜后继点
先手必胜点：所有后继点必败
注意：跟正常拓扑排序不同，不是度为0才入队，而是状态确定就入队，度只是为状态的推断服务的。否则，若 u 的后继既有必胜点又有个环，可能导致 u 的状态没法更新，但实际上 u 是必败点
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<string> edges;
map<string, vector<string>> g;
map<string, int> deg;
while (n--) {
string s;
cin >> s;
string u = s.substr(0, 3), v = s.substr(s.size() - 3); // u -> v
edges.push_back(v);
g[v].push_back(u); // 反图
deg[u]++;
if (!deg.count(v)) deg[v] = 0; // 别漏了
}
queue<string> q;
map<string, int> f;
for (auto [s, d] : deg) {
if (!d) q.push(s), f[s] = 1; // 先手胜
}
while (q.size()) {
auto v = q.front(); q.pop();
for (auto u : g[v]) {
deg[u]--;
if (f[v] == 1 && f[u] != 2) f[u] = 2, q.push(u); //首次确定u为必败态
else if (!deg[u] && f[u] != 2) f[u] = 1, q.push(u); //拆完出边仍未必败的才是必胜态
}
}
string ans[] = {"Draw", "Takahashi", "Aoki"};
for (auto s : edges) {
cout << ans[f[s]] << '\n';
}
return 0;
}
F - Deforestation 2307
把 n 棵树砍完，每次选择一棵树 \(i\)，花费 \(a_{i-1}+a_i+a_{i+1}\) 然后使 \(a_i\) 变成 \(0\)。问有多少种砍树顺序的花费并列最小