CSP2025
T0mle
·
·
生活·游记
Day -???
我是 gesp 忠实用户！
充钱，不打 S 初赛了。
Day -???
报名 J 了。
Day -51
获得 J 准考证号 SD-J06994。
Day -42
考 J。
感觉 AK 了。
怎么有个题我记得选对了，但是誊抄到准考证那张纸的答案错了。不确定答题卡填的对不对。
怎么办，慌了。
算了，无所谓，肯定会过的。
Day -41
多虑了。
神秘 101 分，并非 F12。
ccf 的恩情还不完。
入门组成绩因技术原因统一多加3分，现已更正，请大家通知入门组重新查询成绩。因工作失误给大家带来不便，深感抱歉![表情][表情][表情]
98pts，并没 ak。
Day -10
获得准考证号，SD-J01372，SD-S00912。
Day -3
停课了。
写一下要打的板子，高强度复习几遍，加粗是要打的，虽然感觉没什么用：
图论：割边，割点，边双，点双，强连通分量，欧拉路径，dij。
字符串：hash，kmp，exkmp，manacher，acam，sa。
ds：fenwick，smt1，smt2，smt3，trie，st 表，dsu，笛卡尔树。
树：重心，直径，lca，树剖，淀粉质。
数学：bezout，exgcd，crt，筛，wilson，欧拉定理/扩展定理，二项式定理，catalan。
线代：矩阵快速幂，高消。
感觉有点烫，但是不考别的只能复习这些。
Day -2
颓，啥也没干。
Day -1
上午仍然颓。
下午去日照了。
因为【数据删除】晚上差点没有 j 组试机。
Day 0
上午 J。
30min AK 了，何意味。
罚坐 3h，无所事事，在草稿纸上发表神秘言论。
当 S 的热身赛了。
下午 S。
先开 T1。
首先，如果我们让所有人都选最满意的部门，最多会有一个部门的人数超了。
那么调整这个部门里的人。随便维护一下就行了。
正确性显然吧，咕了。
写完是 22min。
开 T2。
$m$ 是容易干掉的，我们发现对于一种状态，只有原来在最小生成树里的边和新加的边有用，于是 $nk2^k\log n$。
然后感觉干掉 $\log$ 就差不多了。
干掉 $\log$ 有一万种做法吧，可以归并，也可以把所有边放一块排序。
然后 $\log n$ 没了，但注意 kruskal 有个 $\alpha(n)$。
最后是 $nk2^k\alpha(n)$，大样例挺稳的，跑了。
写完大约 1h20min。
然后把 T3，T4 看了一遍，T3 是串串题，先跳。T4 显然 $O(n^3)$ dp 吧，他的特殊性质有何意义，看不懂。
回来赤 T3。我们发现查询的两个串有一段不相等的区间必须覆盖的，假设是 $[l,r]$。然后发明一个诡异 acam，字符集是 $26\times 26$，对模式串建 trie 然后搞 fail。
询问串放 acam 上跑，我们要的模式串是完全覆盖 $[l,r]$ 的，比较难做。我们可以省掉左端点的限制，然后从 $(l+1)$ 处再跑一遍，剪掉就行。
但是我不太擅长 acam，我只会 $|\Sigma|^2L$ 求 fail。
现场再次发明，我们对字符集分块，比较神秘，反正最后干到 $|\Sigma|L$ 了。
写完大约 2.5h。
还有 1.5h，优势在我。
开 D。
这种 dp 状态难点在于你不知道哪些人被选了。
神秘思路，我们先不计算不好算也不重要的人的贡献。
假如当前有 $x$ 个人失败，那么 $\le x$ 的人不必区分，而 $>x$ 的人不好处理。
那就不管这些人。
dp：$f_{i,j,k}$：选了 $i$ 个人，其中 $j$ 个失败了，选了 $k$ 个人的 $c>j$，并且只知道这 $k$ 个人 $c>j$，不知道他们具体是谁。
转移 trivial，瞪了一会大样例 2 才过。
感觉这个 T4 就是点啊，贡献后置的 trick 在 arc 见过。
然后惊恐发现大样例都水完了，于是造极限数据。
T3 本地跑 3s+，但是读入就 600ms，这我优化个吊啊。
不管了跑路了。
回去的车上知道了一个悲伤的事。逝者安息。
我该在哪里停留？我问我自己。
# Day 1
才知道 T3 询问串长度不等，那我不四万了。
【数据删除】
熨斗上 j ak 了，s $100+80+100+100$，sd rk14。
洛谷上 s $100+88+90+100$。
T2 问题不大，相信少爷机。
T3 卡就卡吧，给孩子留点分就行了。
想去冬令营，能赢吗？
# Day 4
通过【数据删除】得到分数：
J：$100+100+100+100=400$。
S：$100+80+100+100=380$。
S T2 的并查集没写按秩合并。
之前一直认为只路径压缩就是 $\alpha(n)$。但是只路径压缩或只按秩合并都是 $\log$，一起用才能 $\alpha(n)$。
严肃学习了。
ccf 还我 20 分！！！
算了，本质是没做到 $n2^k\alpha(n)$。
附代码：
::::info[J T1]
```cpp
#include <bits/stdc++.h>
using namespace std;
int n;
char s[1000005];
char ans[1000005];
int tot;
int main() {
freopen("number.in", "r", stdin);
freopen("number.out", "w", stdout);
cin >> s + 1;
n = strlen(s + 1);
for (int i = 1; i <= n; i++) {
if (isdigit(s[i])) ans[++tot] = s[i];
}
sort(ans + 1, ans + tot + 1);
for (int i = tot; i; i--) putchar(ans[i]);
return 0;
}
```
::::
::::info[J T2]
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m;
struct node {
int val, id;
} a[105];
bool cmp(node a, node b) {
return a.val > b.val;
}
int main() {
freopen("seat.in", "r", stdin);
freopen("seat.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n * m; i++) {
cin >> a[i].val;
a[i].id = i;
}
sort(a + 1, a + n * m + 1, cmp);
int p;
for (int i = 1; i <= n * m; i++) {
if (a[i].id == 1) {
p = i;
break;
}
}
int a = (p - 1) / n;
int b = (p - 1) % n + 1;
if (a & 1) {
cout << a + 1 << " " << (n - b + 1) << endl;
} else {
cout << a + 1 << " " << b << endl;
}
return 0;
}
```
::::
::::info[J T3]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int n, k;
int a[N], f[N], mp[1 << 20];
inline void rd(int &a, int c = 0) {
while (!isdigit(c = getchar()));
for (a = 0; isdigit(c); c = getchar()) a = (a << 3) + (a << 1) + (c ^ 48);
}
int main() {
freopen("xor.in", "r", stdin);
freopen("xor.out", "w", stdout);
memset(mp, -1, sizeof(mp));
rd(n), rd(k);
mp[0] = 0;
for (int i = 1; i <= n; i++) {
rd(a[i]);
a[i] ^= a[i - 1];
if (~mp[a[i] ^ k]) {
f[i] = f[mp[a[i] ^ k]] + 1;
}
mp[a[i]] = i;
f[i] = max(f[i], f[i - 1]);
}
cout << f[n];
return 0;
}
```
::::
::::info[J T4]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 5005, mod = 998244353;
int n, a[N], f[N];
int main() {
freopen("polygon.in", "r", stdin);
freopen("polygon.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
f[0] = 1;
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = a[i] + 1; j <= 5001; j++) ans = (ans + f[j]) % mod;
for (int j = 5001; ~j; j--) f[min(j + a[i], 5001)] = (f[min(j + a[i], 5001)] + f[j]) % mod;
}
cout << ans;
return 0;
}
```
::::
::::info[S T1]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, a[N][3], cho[N];
priority_queue <int, vector <int>, greater <int> > q;
inline void rd(int &a, int c = 0) {
while (!isdigit(c = getchar()));
for (a = 0; isdigit(c); c = getchar()) a = (a << 3) + (a << 1) + (c ^ 48);
}
void wrt(int x) {
if (x > 9) wrt(x / 10);
putchar(x % 10 ^ 48);
}
void solve() {
int c0 = 0, c1 = 0, c2 = 0;
rd(n);
int ans = 0;
for (int i = 1; i <= n; i++) {
rd(a[i][0]), rd(a[i][1]), rd(a[i][2]);
if (a[i][0] >= a[i][1] && a[i][0] >= a[i][2]) c0++, cho[i] = 0;
else if (a[i][1] >= a[i][0] && a[i][1] >= a[i][2]) c1++, cho[i] = 1;
else c2++, cho[i] = 2;
ans += max(max(a[i][0], a[i][1]), a[i][2]);
}
if (c1 * 2 > n) {
for (int i = 1; i <= n; i++) {
swap(a[i][0], a[i][1]);
if (cho[i] != 2) cho[i] ^= 1;
}
swap(c0, c1);
}
if (c2 * 2 > n) {
for (int i = 1; i <= n; i++) {
swap(a[i][0], a[i][2]);
if (cho[i] != 1) cho[i] ^= 2;
}
swap(c0, c2);
}
while (q.size()) q.pop();
for (int i = 1; i <= n; i++) {
if (cho[i] == 0) q.push(a[i][0] - max(a[i][1], a[i][2]));
}
while (c0 * 2 > n) {
int x = q.top(); q.pop();
ans -= x;
c0--;
}
wrt(ans), putchar(10);
}
int main() {
freopen("club.in", "r", stdin);
freopen("club.out", "w", stdout);
int T; rd(T);
while (T--) solve();
return 0;
}
```
::::
:::info[S T2]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
typedef long long ll;
bool Mbe;
int n, m, k, x;
struct edge {
int u, v, w;
} e[2000005];
int ect;
int c[11];
struct DSU {
int a[N + 10];
void init() {
for (int i = 1; i <= n + 10; i++) a[i] = i;
}
int find(int k) {
return k == a[k] ? k : a[k] = find(a[k]);
}
inline void merge(int u, int v) {
a[find(u)] = find(v);
}
} f[1 << 10];
ll ans[1 << 10];
bool Med;
inline void rd(int &a, int c = 0) {
while (c = getchar(), c < 48 || c > 57);
for (a = 0; c >= 48 && c <= 57; c = getchar()) a = (a << 3) + (a << 1) + (c ^ 48);
}
template <class T> void wrt(T x) {
if (x > 9) wrt(x / 10);
putchar(x % 10 ^ 48);
}
bool cmp(edge a, edge b) {
return a.w < b.w;
}
int main() {
// int _ = clock();
freopen("road.in", "r", stdin);
freopen("road.out", "w", stdout);
rd(n), rd(m), rd(k);
for (int i = 1; i <= m; i++) {
rd(e[i].u), rd(e[i].v), rd(e[i].w);
}
ect = m;
for (int i = 1; i <= k; i++) {
rd(c[i]);
for (int j = 1; j <= n; j++) rd(x), e[++ect] = {n + i, j, x};
}
// cerr << clock() - _ << endl;
sort(e + 1, e + ect + 1, cmp);
// cerr << clock() - _ << endl;
for (int i = 0; i < (1 << k); i++) {
f[i].init();
for (int j = 1; j <= k; j++) {
if (i >> j - 1 & 1) ans[i] += c[j];
}
}
// cerr << clock() - _ << endl;
for (int i = 1; i <= ect; i++) {
if (e[i].u <= n) {
int u = e[i].u, v = e[i].v, w = e[i].w;
if (f[0].find(u) != f[0].find(v)) {
for (int j = 0; j < (1 << k); j++) {
if (f[j].find(u) != f[j].find(v)) {
ans[j] += w;
f[j].merge(u, v);
}
}
}
} else {
int u = e[i].u, v = e[i].v, w = e[i].w;
for (int j = 0; j < (1 << k); j++) {
if (j >> u - n - 1 & 1) {
if (f[j].find(u) != f[j].find(v)) {
ans[j] += w;
f[j].merge(u, v);
}
}
}
}
}
ll anss = 1e18;
for (int i = 0; i < (1 << k); i++) anss = min(anss, ans[i]);
wrt(anss);
// cerr << clock() - _;
return 0;
}
```
::::
::::info[S T3]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N1 = 200005, N2 = 5000005;
typedef long long ll;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
template <class T> inline void ckmn(T &a, T b) { (a > b) && (a = b); }
template <class T> inline void ckmx(T &a, T b) { (a < b) && (a = b); }
bool Mbe;
int n, q, a[N2][26], b[N2][26], tot1, tot2;
char s1[N2], s2[N2];
int f[N2], fail[N2];
int qu[N2], ql, qr;
bool Med;
inline void rd(int &a, int c = 0) {
while (!isdigit(c = getchar()));
for (a = 0; isdigit(c); c = getchar()) a = (a << 3) + (a << 1) + (c ^ 48);
}
template <class T> void wrt(T x) {
if (x > 9) wrt(x / 10);
putchar(x % 10 ^ 48);
}
void ins(int len) {
int p = 0;
rep(i, 1, len) {
int c1 = s1[i] - 'a', c2 = s2[i] - 'a';
if (!a[p][c1]) a[p][c1] = ++tot1;
if (!b[a[p][c1]][c2]) b[a[p][c1]][c2] = ++tot2;
p = b[a[p][c1]][c2];
}
f[p]++;
}
void build_acam() {
ql = 1, qr = 0;
rep(i, 0, 25) {
if (!a[0][i]) continue;
rep(j, 0, 25) {
if (b[a[0][i]][j]) qu[++qr] = b[a[0][i]][j];
}
}
while (qr >= ql) {
int u = qu[ql++];
// cout << "+ " << u << endl;
rep(i, 0, 25) {
// cout << u << " " << i << " " << a[u][i] << endl;
if (!a[u][i]) continue;
int p = fail[u];
while (p && !a[p][i]) p = fail[p];
rep(j, 0, 25) {
int &v = b[a[u][i]][j];
// cout << u << " " << v << endl;
if (v) fail[v] = b[a[p][i]][j], f[v] += f[fail[v]], qu[++qr] = v;
else v = b[a[p][i]][j];
}
}
}
}
ll play(int len, int st, int tog) {
int p = 0;
ll ans = 0;
rep(i, st, len) {
int c1 = s1[i] - 'a', c2 = s2[i] - 'a';
while (p && !a[p][c1]) p = fail[p];
p = b[a[p][c1]][c2];
if (i >= tog) ans += f[p];
}
return ans;
}
int main() {
freopen("replace.in", "r", stdin);
freopen("replace.out", "w", stdout);
rd(n), rd(q);
int sm1 = 0;
rep(i, 1, n) {
scanf("%s %s", s1 + 1, s2 + 1);
// cout << " " << s1 + 1 << " " << s2 + 1 << endl;
int len = strlen(s1 + 1);
ins(len);
sm1 += len;
}
build_acam();
// rep(i, 0, tot2) {
// cout << i << " " << fail[i] << endl;
// rep(j, 0, 25) {
// rep(k, 0, 25) {
// if (b[a[i][j]][k]) cout << i << " " << j << " " << k << " " << b[a[i][j]][k] << endl;
// }
// }
// }
int sm2 = 0;
while (q--) {
scanf("%s %s", s1 + 1, s2 + 1);
int len = strlen(s1 + 1);
sm2 += len;
int mn = 1e9, mx = 0;
rep(i, 1, len) {
if(s1[i] != s2[i]) {
ckmn(mn, i);
ckmx(mx, i);
}
}
// cout << mn << " " << mx << endl;
wrt(play(len, 1, mx) - play(len, mn + 1, mx)), putchar(10);
}
// cerr << sm1 << " " << sm2;
return 0;
}
```
::::
::::info[S T4]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 505, mod = 998244353;
typedef long long ll;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define repr(i, a, b) for (int i(a); i < (b); ++i)
#define per(i, a, b) for (int i(a); i >= (b); --i)
template <class T> inline void ckmn(T &a, T b) { (a > b) && (a = b); }
template <class T> inline void ckmx(T &a, T b) { (a < b) && (a = b); }
int n, m, s[N], t[N], p[N], x, f[N][N][N];
int fac[N], fiv[N];
inline void rd(int &a, int c = 0) {
while (!isdigit(c = getchar()));
for (a = 0; isdigit(c); c = getchar()) a = (a << 3) + (a << 1) + (c ^ 48);
}
void wrt(int x) {
if (x > 9) wrt(x / 10);
putchar(x % 10 ^ 48);
}
int qpw(int a, int b) {
int R = 1;
for (; b; b >>= 1) {
if (b & 1) R = 1ll * R * a % mod;
a = 1ll * a * a % mod;
}
return R;
}
void init() {
rep(i, fac[0] = 1, 500) fac[i] = 1ll * fac[i - 1] * i % mod;
fiv[500] = qpw(fac[500], mod - 2);
per(i, 499, 0) fiv[i] = fiv[i + 1] * (i + 1ll) % mod;
}
inline void ad(int &a, ll b) { a = (a + b) % mod; }
inline int C(int n, int m) {
if (n < m || n < 0 || m < 0) return 0;
return 1ll * fac[n] * fiv[m] % mod * fiv[n - m] % mod;
}
int main() {
freopen("employ.in", "r", stdin);
freopen("employ.out", "w", stdout);
init();
rd(n), rd(m);
rep(i, 1, n) {
while (isspace(x = getchar()));
s[i] = x ^ 48;
}
rep(i, 1, n) rd(x), t[x]++;
p[0] = t[0];
rep(i, 1, n) p[i] = p[i - 1] + t[i];
// rep(i, 0, n) cout << t[i] << " "; cout << endl;
// rep(i, 0, n) cout << p[i] << " "; cout << endl;
// #define cha(a, b, c) ((a) == 3 && (b) == 2 && (c) == 0)
f[0][0][0] = 1;
repr(i, 0, n) {
rep(j, 0, i) {
rep(k, 0, i) {
if (!f[i][j][k]) continue;
// cout << i << " " << j << " " << k << " " << f[i][j][k] << endl;
if (s[i + 1] == 0) {
// lose men count: j + 1
rep(l, 0, min(t[j + 1], k)) {
// c <= j:
// count: p[j] - (i - k)
// if (cha(i + 1, j + 1, k - l)) cout << i << " " << j << " " << k << " " << f[i][j][k] << " " << (p[j] - j) % mod * fac[t[j + 1]] % mod * fiv[t[j + 1] - l] % mod * C(k, l) % mod << endl;
ad(f[i + 1][j + 1][k - l], 1ll * f[i][j][k] * (p[j] - (i - k)) % mod * fac[t[j + 1]] % mod * fiv[t[j + 1] - l] % mod * C(k, l));
// c = j+1, s.t. l != t[j+1]
if (l != t[j + 1]) {
// if (cha(i + 1, j + 1, k - l)) cout << i << " " << j << " " << k << " " << f[i][j][k] << " " << fac[t[j + 1]] % mod * fiv[t[j + 1] - l - 1] % mod * C(k, l) % mod << endl;
ad(f[i + 1][j + 1][k - l], 1ll * f[i][j][k] * fac[t[j + 1]] % mod * fiv[t[j + 1] - l - 1] % mod * C(k, l));
}
// c > j+1
// if (cha(i + 1, j + 1, k - l + 1)) cout << i << " " << j << " " << k <<" " << f[i][j][k] << " " << fac[t[j + 1]] % mod * fiv[t[j + 1] - l] % mod * C(k, l) % mod << endl;
ad(f[i + 1][j + 1][k - l + 1], 1ll * f[i][j][k] * fac[t[j + 1]] % mod * fiv[t[j + 1] - l] % mod * C(k, l));
}
} else {
// c <= j
// count: p[j] - (i - k)
rep(l, 0, min(t[j + 1], k)) {
// if (cha(i + 1, j + 1, k - l)) cout << i << " " << j << " " << k << " " << f[i][j][k] << " " << (p[j] - j) % mod * fac[t[j + 1]] % mod * fiv[t[j + 1] - l] % mod * C(k, l) % mod <<endl;
ad(f[i + 1][j + 1][k - l], 1ll * f[i][j][k] * (p[j] - (i - k)) % mod * fac[t[j + 1]] % mod * fiv[t[j + 1] - l] % mod * C(k, l));
}
// c > j
// if (cha(i + 1, j, k + 1)) cout << i << " " << j << " " << k << " " << f[i][j][k] << " " << 1 << endl;
ad(f[i + 1][j][k + 1], f[i][j][k]);
}
}
}
}
// cout << " " << f[3][2][0] << endl;
int ans = 0;
rep(j, 0, n - m) {
rep(k, 0, n) {
if (f[n][j][k]) {
if (p[j] + k == n) ad(ans, 1ll * f[n][j][k] * fac[k]);
}
}
}
wrt(ans);
return 0;
}
```
::::