2024“钉耙编程”中国大学生算法设计超级联赛（1）§
循环位移§
由于查询的子串长度固定，所以可以用哈希线性跑，带上
set也就只是多了个log。#include <bits/stdc++.h> using i64 = long long; template <int seed, int mod, class T = std::string> struct Hash { std::vector<i64> h, p; Hash(T a) { int n = a.size(); h.assign(n + 1, 0); p.assign(n + 1, 1); for (int i = 0; i < n; ++i) { h[i + 1] = (h[i] * seed + a[i]) % mod; p[i + 1] = (p[i] * seed) % mod; } } i64 get(int l, int r) { return (h[r] + mod - h[l - 1] * p[r - l + 1] % mod) % mod; } }; void solve() { std::string a, b; std::cin >> a >> b; Hash<1333331, 998244353> hash1(a + a + b); Hash<1145141, (int)(1e9 + 7)> hash2(a + a + b); std::set<std::pair<int, int>> set; for (int i = 1; i <= a.size(); i++) { set.insert(std::make_pair(hash1.get(i, i + a.size() - 1), hash2.get(i, i + a.size() - 1))); } int ans = 0; for (int i = 1; i <= b.size() - a.size() + 1; i++) { int h1 = hash1.get(i + a.size() * 2, i + a.size() * 3 - 1), h2 = hash2.get(i + a.size() * 2, i + a.size() * 3 - 1); if (set.count(std::make_pair(h1, h2))) ans++; } std::cout << ans << '\n'; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t; std::cin >> t; while (t--) { solve(); } return 0; }
星星§
常规动态规划题，
O(n*k)复杂度能过。#include <bits/stdc++.h> using i64 = long long; void solve() { int n, k; std::cin >> n >> k; std::vector<std::vector<i64>> dp(n + 1, std::vector<i64>(k + 1, 1e18)); dp[0][0] = 0; for (int i = 1; i <= n; i++) { std::vector<int> a(5, 0); for (int x = 1; x <= 4; x++) { std::cin >> a[x]; } for (int x = 0; x <= 4; x++) { for (int j = x; j <= k; j++) { dp[i][j] = std::min(dp[i][j], dp[i - 1][j - x] + a[x]); } } } std::cout << dp[n][k] << '\n'; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t; std::cin >> t; while (t--) { solve(); } return 0; }
树§
难点不在于公式的推导，而是在于维护所需要的信息。
不难想到可以用权值树状数组来维护所需数据。
但需要合并多个子树的信息，同时还要计算子树之间的新的贡献。
这里可以借助树上启发式合并（dsu on tree）来解决这个问题。
假如我们遍历到某个节点
u，我们需要计算以该点为根的子树对答案的贡献。显然我们会先计算
u节点子树的答案。维护节点子树的信息很简单，但是如何计算子树之间的答案？
暴力的做法是每次清空或者再开一个树状数组，然后把子树节点一个个加进去算。
这样复杂度是 \(O(n^{2}log(n))\) 。
但树上启发式合并（dsu on tree）的思想却不想盲目的清空，它想着留下一些有用的信息。
这时我们就需要接触一个崭新的名词：重儿子（最大的那颗子树）。
我们完全可以让重儿子最后执行计算，并且不会清空信息。
这样计算
u节点的答案时，就直接遍历重儿子以外的节点，每次计算后就把这个点加入到维护的信息中。计算完成后，我们根据
u节点是不是重儿子来决定是否清空现场（注意，我们并不会每次都构建一个树状数组，而是共用一个，当然你也可以在dfs过程中构造，每次只接收重儿子返回的树状数组，但这样可能会造成不必要的开销）。时间复杂度为 \(O(nlog^{2}(n))\) 。
理解这个复杂度的由来可以参照树上合并子树的点集，每次都是将小的集合合并到大的集合里，也就是说只会遍历小的集合。
这个的时间复杂度一般为 \(O(nlog(n))\) 。
#include <bits/stdc++.h> using u64 = unsigned long long; template <typename T> struct Fenwick { int n; std::vector<T> tr; Fenwick(int n) : n(n), tr(n + 1) {} inline int lowbit(int x) { return x & -x; } void add(int i, T val) { for (; i <= n; i += lowbit(i)) { tr[i] += val; } } T sum(int i) { T res = 0; for (; i > 0; i -= lowbit(i)) { res += tr[i]; } return res; } T query(int l, int r) { if (l > r) return 0; return sum(r) - sum(l - 1); } T kth(int k) { int x = 0; T res = 0; for (int i = 1 << std::__lg(n); i; i /= 2) { if (x + i <= n && k >= tr[x + i]) { x += i; k -= tr[x]; res += tr[x]; } } return (k ? -1 : res); } }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<std::vector<int>> eg(n + 1); for (int i = 0; i < n - 1; i++) { int u, v; std::cin >> u >> v; eg[u].push_back(v); eg[v].push_back(u); } std::vector<u64> a(n + 1); for (int i = 1; i <= n; i++) { std::cin >> a[i]; } std::vector<int> dfn(n + 1), end(n + 1), name(n + 1), size(n + 1, 0), son(n + 1, 0); std::vector<u64> ans(n + 1, 0ULL); int timestamp = 0; auto dfs1 = [&](auto &dfs, int u, int fa) -> void { dfn[u] = ++timestamp; name[timestamp] = u; size[u] = 1; for (auto it : eg[u]) { if (it == fa) continue; dfs(dfs, it, u); size[u] += size[it]; if (size[it] > size[son[u]]) { son[u] = it; } } end[u] = timestamp; }; dfs1(dfs1, 1, 0); std::vector<Fenwick<u64>> fenwick(3, Fenwick<u64>(1e6)); u64 now = 0ULL; auto add = [&](int u) { u64 v = a[u]; now += v * (fenwick[0].sum(v - 1) * v - fenwick[1].sum(v - 1)); now += fenwick[2].query(v + 1, 1e6) - v * fenwick[1].query(v + 1, 1e6); fenwick[0].add(v, 1ULL); fenwick[1].add(v, v); fenwick[2].add(v, v * v); }; auto del = [&](int u) { u64 v = a[u]; now -= v * (fenwick[0].sum(v - 1) * v - fenwick[1].sum(v - 1)); now -= fenwick[2].query(v + 1, 1e6) - v * fenwick[1].query(v + 1, 1e6); fenwick[0].add(v, -1ULL); fenwick[1].add(v, -v); fenwick[2].add(v, -v * v); }; auto dfs2 = [&](auto &dfs, int u, int fa, bool exist) -> void { for (auto it : eg[u]) { if (it == fa || it == son[u]) continue; dfs(dfs, it, u, 0); } if (son[u]) dfs(dfs, son[u], u, 1); for (auto it : eg[u]) { if (it == fa || it == son[u]) continue; for (int i = dfn[it]; i <= end[it]; i++) { add(name[i]); } } add(u); ans[u] = now; if (!exist) { for (int i = dfn[u]; i <= end[u]; i++) { del(name[i]); } } }; dfs2(dfs2, 1, 0, 1); u64 res = 0; for (auto it : ans) { res ^= it * 2ULL; } std::cout << res << '\n'; return 0; }
传送§
该题的边是有时效性的，考虑线段树分治
+可撤销并查集。「线段树分治」模型：
给定一些仅在 给定时间范围 内有效的操作。
询问某个时间点所有操作的贡献。
「可撤销并查集」：
使用栈维护操作。
无路径压缩，并需要按秩合并（启发式合并），时间复杂度为
log级别。考虑线段树每个叶子节点代表时刻的贡献，设此时刻为
i，则此时所有包含节点1的连通块内的所有节点的答案都应该加i。在此过程中我们用并查集维护连通性，可以在
1所在联通块的祖先上打上一个+i标记，代表这个连通块内的所有节点贡献+i。具体计算贡献的过程中，在撤销时会把标记下放。
为了防止贡献重复累加，连边时孩子应减去父亲自带的标记。
时间复杂度为 \(O(nlog^{2}(n)+mlog(n))\) 。
#include <bits/stdc++.h> using i64 = long long; constexpr int N = 6e5 + 1; int p[N], sz[N], top; i64 tag[N]; std::array<int, 3> stack[N]; std::pair<int, int> eg[N]; std::vector<int> t[N << 2]; int find(int u) { while (u != p[u]) u = p[u]; return u; } void merge(int u, int v) { int fu = find(u), fv = find(v); if (sz[fu] < sz[fv]) std::swap(fu, fv); stack[top++] = {fu, fv, sz[fv]}; if (fu != fv) { p[fv] = fu, sz[fu] += sz[fv], sz[fv] = 0; tag[fv] -= tag[fu]; } } void restore() { auto [fu, fv, size] = stack[--top]; if (fu != fv) { p[fv] = fv, sz[fv] = size, sz[fu] -= size; tag[fv] += tag[fu]; } } void modify(int u, int L, int R, int l, int r, int val) { if (L >= l && R <= r) { t[u].push_back(val); return; } int mid = (L + R) >> 1; if (l <= mid) modify(u << 1, L, mid, l, r, val); if (r >= mid + 1) modify(u << 1 | 1, mid + 1, R, l, r, val); } void query(int u, int L, int R) { for (auto it : t[u]) { merge(eg[it].first, eg[it].second); } if (L == R) { tag[find(1)] += L; } else { int mid = (L + R) >> 1; query(u << 1, L, mid), query(u << 1 | 1, mid + 1, R); } for (int i = 0; i < t[u].size(); i++) { restore(); } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; for (int i = 0; i < m; i++) { std::cin >> eg[i].first >> eg[i].second; int l, r; std::cin >> l >> r; modify(1, 1, n, l, r, i); } for (int i = 1; i <= n; i++) { p[i] = i, sz[i] = 1; } query(1, 1, n); i64 ans = 0; for (int i = 1; i <= n; i++) { ans ^= tag[i]; } std::cout << ans << '\n'; return 0; }
博弈§
由于是等概率选取字符，如果是轮流拿取的话，其实谁先谁后无所谓的。
在没有平局的情况下，两者获胜的概率是相等的。
什么情况下没有平局？
奇数个字符出现次数大于
1时永远不会存在平局。接下来只需要讨论
01的情况。在这之前我们需要先算出两种情况平局的概率。
需要计算给定一个集合，将集合中的元素两两凑一对的方案数（集合可能有奇数个元素）。
答案是：\(\frac {n!}{\left \lfloor \frac{n}{2} \right \rfloor !(n-\left \lfloor \frac{n}{2} \right \rfloor)!}(n-\left \lfloor \frac{n}{2} \right \rfloor)!=\frac {n!}{\left \lfloor \frac{n}{2} \right \rfloor !}\) 。
那么对于平局的情况，我们只需要统计合法方案数，和全部方案数，就能算出平局概率（并不需要在意每个元素对先选还是后选，这对结果没有影响，也就是说不用在于元素对的排列问题）。
总方案数：\(\frac {sum!}{\left \lfloor \frac{sum}{2} \right \rfloor !}\) 。
合法方案数：\(\prod \frac {c_{i}!}{\left \lfloor \frac{c_{i}}{2} \right \rfloor !}\)
平局概率：\(\frac{\prod \frac {c_{i}!}{\left \lfloor \frac{c_{i}}{2} \right \rfloor !}}{\frac {sum!}{\left \lfloor \frac{sum}{2} \right \rfloor !}}\)
对于
0情况，只需要减去平局概率然后均分即可。对于
1情况，平局概率实际上是第 \(\left \lfloor \frac{n}{2} \right \rfloor\) 轮后平局的概率，这其实意味着先手会获胜，因此答案是 \(\frac {1-p}{2}+p=\frac {1+p}{2}\)。#include <bits/stdc++.h> using i64 = long long; constexpr i64 mod = 998244353, N = 1e7 + 1; class modint { i64 num; public: modint(i64 num = 0) : num(num % mod) {} i64 val() const { return num; } modint pow(i64 other) { modint res(1), temp = *this; while (other) { if (other & 1) res = res * temp; temp = temp * temp; other >>= 1; } return res; } constexpr i64 norm(i64 num) const { if (num < 0) num += mod; if (num >= mod) num -= mod; return num; } modint inv() { return pow(mod - 2); } modint operator+(modint other) { return modint(num + other.num); } modint operator-() { return {-num}; } modint operator-(modint other) { return modint(-other + *this); } modint operator*(modint other) { return modint(num * other.num); } modint operator/(modint other) { return *this * other.inv(); } modint &operator*=(modint other) { num = num * other.num % mod; return *this; } modint &operator+=(modint other) { num = norm(num + other.num); return *this; } modint &operator-=(modint other) { num = norm(num - other.num); return *this; } modint &operator/=(modint other) { return *this *= other.inv(); } friend std::istream &operator>>(std::istream &is, modint &other) { is >> other.num; other.num %= mod; return is; } friend std::ostream &operator<<(std::ostream &os, modint other) { other.num = (other.num + mod) % mod; return os << other.num; } }; modint fc[N], ifc[N]; void init() { int n = N - 1; fc[0] = 1; for (int i = 1; i <= n; i++) fc[i] = fc[i - 1] * i; ifc[n] = modint(1) / fc[n]; for (int i = n - 1; i >= 0; i--) ifc[i] = ifc[i + 1] * (i + 1); } modint C(int n, int m) { if (n < m) return 0; if (m == 0) return 1; return fc[n] * ifc[n - m] * ifc[m]; } void solve() { int n; std::cin >> n; std::vector<int> cnt(26, 0); int sum = 0, x = 0; while (n--) { char c; int h; std::cin >> c >> h; cnt[c - 'a'] = h; sum += h; x += h & 1; } if (x >= 2) { std::cout << modint(1) / modint(2) << '\n'; return; } modint ans = 1; for (int i = 0; i < 26; i++) { ans *= fc[cnt[i]] * ifc[cnt[i] >> 1]; } ans *= ifc[sum] * fc[sum >> 1]; if (x == 0) { std::cout << (modint(1) - ans) / modint(2) << '\n'; } else { std::cout << (modint(1) + ans) / modint(2) << '\n'; } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t; std::cin >> t; init(); while (t--) { solve(); } return 0; }
序列立方§
答案等价于任选三个子序列使它们相同的方案数。
\(\sum\sum\sum[a=b=c],(a\in S,b\in S,c\in S)\)
问题可以转化成
DP问题 。设 \(f_{i,j,k}\) 表示选择第一个序列结尾为 \(a_i\) ，第二个序列结尾为 \(a_j\) ，第三个序列结尾为 \(a_k\) 时的合法方案数。
则有：
\[f_{i,j,k}=\sum\sum\sum f_{i^{'},j^{'},k^{'}}(0\le i^{'}<i,0\le j^{'}<j,0\le k^{'}<k,a_i=a_j=a_k)\]答案为 \(\sum f_{i,j,k}(a_i=a_j=a_k)\)
具体实现可以用三维前缀和来优化。
时间复杂度为 \(O(n^3)\) 。
注意，模数常量应加上
constexpr前缀，否则会TLE，常量和变量性能差距非常大。#include <bits/stdc++.h> using i64 = long long; constexpr i64 mod = 998244353; int n, a[251]; i64 ans = 0, dp[251][251][251], g[251][251][251]; int main() { std::cin >> n; for (int i = 1; i <= n; i++) { std::cin >> a[i]; } dp[0][0][0] = 1; for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { g[i][j][0] = g[i][0][j] = g[0][i][j] = 1; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; k++) { if (a[i] == a[j] && a[j] == a[k]) { dp[i][j][k] = g[i - 1][j - 1][k - 1]; ans += dp[i][j][k]; ans %= mod; } g[i][j][k] = dp[i][j][k]; g[i][j][k] += g[i - 1][j][k] + g[i][j - 1][k] + g[i][j][k - 1]; g[i][j][k] %= mod; g[i][j][k] -= g[i - 1][j - 1][k] + g[i - 1][j][k - 1] + g[i][j - 1][k - 1]; g[i][j][k] %= mod, g[i][j][k] += mod, g[i][j][k] %= mod; g[i][j][k] += g[i - 1][j - 1][k - 1]; g[i][j][k] %= mod; } } } std::cout << ans << '\n'; return 0; }
位运算§
思路很简单，对于每一位分开考虑就行了，之后结果相乘。
注意要开
long long。#include <bits/stdc++.h> using i64 = long long; int get(int u) { int sum = 0; for (int i = 0; i < (1 << 4); i++) { sum += (((((i >> 3) & (i >> 2)) ^ (i >> 1)) | (i >> 0)) & 1) == u; } return sum; } void solve() { int n, k; std::cin >> n >> k; i64 ans = 1; for (int i = 0; i < k; i++) { ans *= get((n >> i) & 1); } std::cout << ans << '\n'; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t; std::cin >> t; while (t--) { solve(); } return 0; }