发挥相当差，最好笑的是 1h 没写出一个三维偏序、30min 没写出一个字符串哈希。甚至 1h 没意识到组合数式子推错了。
A
我写了点阴间东西。
假设模式串为 ABC，考虑一个形如 ABCABCABC 的东西，如果长度是 \(x\)，会贡献 \(x-n+1\) 个子串。
枚举 \(i\)，从 \(i\) 把 \(T\) 分成两部分，一部分与 \(S\) 拼一起跑 Z 函数得到 \(T[i \dots n]\) 能与 \(S\) 的前缀匹配几位，再翻转 \(S\) 与 \(T\) 得到 \(T[i-1 \dots 0]\) 能与 \(T\) 的后缀从后面匹配几位，两边拼一起得到 BCABCABCABC.. 类似物的长短。
因为一次考虑 \(S\) 的很多次重复，开始要把 \(S\) 复制到长度不小于 \(T\)。
没解绑同步流过的。感觉第一发 Hash 被卡常可能真的是输入的锅。
#include <bits/stdc++.h>
#define LL long long
const int M = 2e7 + 5;
using string = std::string;
std::vector<int> getz(string s) {
int n = s.length();
std::vector<int> z(n);
z[0] = n;
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
z[i] = i <= r ? std::min(r - i + 1, z[i - l]) : 0;
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
}
return z;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T; std::cin >> T; while (T--) {
string s, t;
std::cin >> s >> t;
int n0 = s.length(), m = t.length(), n = n0;
int x = m / n0 + 1;
s.resize(n = n0 * x);
for (int i = n0; i < n; i++) {
s[i] = s[i - n0];
}
std::vector<int> z1 = getz(s + '@' + t);
std::reverse(s.begin(), s.end()), std::reverse(t.begin(), t.end());
auto z2 = getz(s + '@' + t);
z1.erase(z1.begin(), z1.begin() + n + 1);
z2.erase(z2.begin(), z2.begin() + n + 1);
std::reverse(z2.begin(), z2.end());
std::vector<int> z3(n);
for (int i = 0; i < m; i++)
z3[i - z2[i] + 1] = std::max(z3[i - z2[i] + 1], z2[i]);
int ans = 0;
int pre = -1;
for (int i = 0; i < m; i++) {
if (i + z1[i] - n0 + 1 > m || i + z1[i] - n0 + 1 < 0) continue;
if (z1[i] + (i ? z2[i - 1] : 0) >= n0) {
if (pre == i + z1[i]) continue;
ans += z1[i] + (i ? z2[i - 1] : 0) - n0 + 1;
pre = i + z1[i];
}
}
std::cout << ans << "\n";
}
}
B
朴素背包。
std 告诉我们先随机打乱，前 \(i\) 关期望获得 \(E=ik/n\) 颗星星，找一个阈值 \(B\)，只更新 \([E-B, E+B]\) 内的 dp 值就行。
#include <bits/stdc++.h>
using LL = long long;
int main() {
int t; scanf("%d", &t); while (t--) {
int n, k; scanf("%d %d", &n, &k);
std::vector<LL> f(k + 1, 1e17);
f[0] = 0;
for (int i = 0; i < n; i++) {
std::vector<LL> g(f);
for (int j = 1, t; j <= 4; j++) {
scanf("%d", &t);
for (int x = 0; x <= k - j; x++)
g[x + j] = std::min(g[x + j], f[x] + t);
}
f.swap(g);
}
printf("%lld\n", f[k]);
}
}
C
不是我开的。
\(\max(x, y) \cdot |x-y| = \max(x, y)^2 - \max(x, y) \min(x, y) = \max(x, y)^2 - xy\)。
后者是容易的，前者用树上启发式合并，\(O(n \log^2 n)\)。
队友赛时写了个线段树合并，好强啊。
D
晚点写。
E
若 \(S\) 为偶数，设平局概率为 \(p\)，答案是 \((1-p)/2\)。
否则看一下前 \((n-1)/2\) 局就平的概率，如果平了是 A 赢，否则是 \(1/2\)。
如何算平局的概率？给每个字母标号，统计 \(A_i - B_i\) 有序对构成的可重集。因为可重，总方案数是 \(S!/(S/2)!\)，而合法的方案数是 \(\prod c_i!/(c_i/2)!\)。
能算错平局的概率，脑子已经失去了。想钦定顺序，忘了两边并不等价。
#include <bits/stdc++.h>
// 省略 modint
int main() {
initC(1e7 + 1);
int T; scanf("%d", &T); while (T--) {
int n; scanf("%d", &n);
std::vector<int> c(26, 0);
int sum = 0;
modint ans = 1;
for (int i = 0, x; i < n; i++) {
char s; scanf(" %c %d", &s, &x);
c[s - 'a'] += x, sum += x;
}
int cnt = 0;
for (int i = 0; i < n; i++) if (c[i] % 2 == 1) ++cnt;
if (cnt > 1) { printf("%d\n", (mod + 1) / 2); continue; }
for (int i = 0; i < 26; i++) {
ans *= fac[c[i]] * ifac[c[i] >> 1];
}
ans *= ifac[sum] * fac[sum >> 1];
// printf("%d\n", ans);
if (cnt == 0)
printf("%d\n", (1 - ans) / 2);
else
printf("%d\n", (1 + ans) / 2);
}
}
F
赛时在想拆贡献 dp，越想越远。
但三次方有另一个拆贡献方法：挑三个位于该集合内的数的方案数。据此 dp 即可，前缀和优化转移。
G
竞赛图三元环的经典转化是：考虑非三元环，必存在一个点出度为 \(2\)。
三维偏序求每个点出度即可。
H
拆位即可。
I
假设已经确定了数字串，考虑 dp：\(f_{i, j, k}\) 表示扫完了数字串前 \(i\) 位，匹配模式串到第 \(j\) 位，且最后一位为 \(k\) 的方案数。
数位 dp 会把答案转化为：\(n |\sum|\) 次先确定前面若干位，再让后面随便填。
前半相当于数字串已经被确定，对于后半，\(f_{0/1, i, j, k}\) 表示前面是否全部是前导零，还能填 \(i\) 位，匹配模式串到第 \(j\) 位，最后一位为 \(k\) 的方案数，暴力合并。
#include <bits/stdc++.h>
const int mod = 998244353;
using v2 = std::vector<std::vector<int>>;
using v3 = std::vector<v2>;
using v4 = std::vector<v3>;
void solve() {
std::string l, r, s; std::cin >> l >> r >> s;
std::reverse(r.begin(), r.end());
r = r + '0';
for (int i = 0; i < (int)r.length(); i++) {
if (r[i] < '9') { ++r[i]; break; }
r[i] = '0';
}
while (r.length() && r.back() == '0') r.pop_back();
std::reverse(l.begin(), l.end());
while (l.length() < r.length()) l.push_back('0');
std::reverse(r.begin(), r.end());
std::reverse(l.begin(), l.end());
// std::cerr << l << " " << r << std::endl;
int n = r.length(), m = s.length();
v4 f(2, v3(n + 1, v2(m + 2, std::vector<int>(10, -1))));
// 是否全是 0 T 匹配到第 p 位 子序列选出了 q 个数 最后一个数为 x
std::function<int(int, int, int, int)> dfs = [&](int b, int p, int q, int x) {
// std::cerr << b << " " << p << " " << q << " " << x << std::endl;
int &ans = f[b][p][q][x];
if (ans != -1) return ans;
if (p == n) return ans = (q == m + 1);
if (q == m + 1) return ans = 10ll * dfs(0, p + 1, q, x) % mod;
ans = 0;
for (int y = 0; y < 10; y++) {
(ans += dfs(b && !y, p + 1, q, x)) %= mod;
if (b && !y) continue;
if (q && s[q - 1] == '<' && x >= y) continue;
if (q && s[q - 1] == '>' && x <= y) continue;
(ans += dfs(0, p + 1, q + 1, y)) %= mod;
}
return ans;
};
auto solve = [&](std::string x) {
int n = x.length();
auto p = x;
// 已经匹配模式串的前 i 位，最后一位为 j
v2 f(n + 1, std::vector<int>(10, 0));
// 在 f 后面放一个 y
auto nxt = [&](int y) {
auto g = f;
++g[0][y];
for (int i = 0; i < m; i++) {
for (int x = 0; x < 10; x++) {
if (s[i] == '<' && x >= y) continue;
if (s[i] == '>' && x <= y) continue;
(g[i + 1][y] += f[i][x]) %= mod;
}
}
return g;
};
int ans = 0;
bool c = 1;
int i = 0; while (x[i] == '0') ++i;
for (; i < n; i++) {
int t = x[i] - '0';
for (int y = 0; y < t; y++) {
(ans += dfs(c && !y, i + 1, 0, 0)) %= mod;
if (c && !y) continue;
auto g = nxt(y);
for (int j = 0; j <= m; j++)
for (int x = 0; x < 10; x++) if (g[j][x]) {
(ans += 1ll * g[j][x] * dfs(0, i + 1, j + 1, x) % mod) %= mod;
}
}
c &= (x[i] == '0');
f = nxt(t);
}
return ans;
};
int R = solve(r);
f.assign(2, v3(n + 1, v2(m + 2, std::vector<int>(10, -1))));
// std::cout << R << " " << solve(l) << "\n";
std::cout << (R - solve(l) + mod) % mod << "\n";
}
int main() {
std::ios::sync_with_stdio(0);
int T; std::cin >> T; while (T--) {
solve();
}
}
J
从大到小枚举众数。开一个优先队列，
标签：钉耙,std,begin,int,编程,2024,++,vector,z2 From： https://www.cnblogs.com/purplevine/p/18313459