专栏文章

CSP2025

TT0mle
生活·游记参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miny6xjv
此快照首次捕获于
2025/12/02 10:17
3 个月前
此快照最后确认于
2025/12/02 10:17
3 个月前
查看原文

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。
k≤10k\leq 10 不就是引着状压吗，一秒会了 2kmlog⁡m2^km\log m。
mm 是容易干掉的，我们发现对于一种状态，只有原来在最小生成树里的边和新加的边有用，于是 nk2klog⁡nnk2^k\log n。
然后感觉干掉 log⁡\log 就差不多了。
干掉 log⁡\log 有一万种做法吧，可以归并，也可以把所有边放一块排序。
然后 log⁡n\log n 没了，但注意 kruskal 有个 α(n)\alpha(n)。
最后是 nk2kα(n)nk2^k\alpha(n)，大样例挺稳的，跑了。
写完大约 1h20min。
然后把 T3，T4 看了一遍，T3 是串串题，先跳。T4 显然 O(n3)O(n^3) dp 吧，他的特殊性质有何意义，看不懂。
回来赤 T3。我们发现查询的两个串有一段不相等的区间必须覆盖的，假设是 [l,r][l,r]。然后发明一个诡异 acam，字符集是 26×2626\times 26，对模式串建 trie 然后搞 fail。
询问串放 acam 上跑，我们要的模式串是完全覆盖 [l,r][l,r] 的，比较难做。我们可以省掉左端点的限制，然后从 (l+1)(l+1) 处再跑一遍，剪掉就行。
但是我不太擅长 acam，我只会 ∣Σ∣2L|\Sigma|^2L 求 fail。
现场再次发明，我们对字符集分块，比较神秘，反正最后干到 ∣Σ∣L|\Sigma|L 了。
写完大约 2.5h。
还有 1.5h，优势在我。
开 D。
这种 dp 状态难点在于你不知道哪些人被选了。
神秘思路，我们先不计算不好算也不重要的人的贡献。
假如当前有 xx 个人失败，那么 ≤x\le x 的人不必区分，而 >x>x 的人不好处理。
那就不管这些人。
dp：fi,j,kf_{i,j,k}：选了 ii 个人，其中 jj 个失败了，选了 kk 个人的 c>jc>j，并且只知道这 kk 个人 c>jc>j，不知道他们具体是谁。
转移 trivial，瞪了一会大样例 2 才过。
感觉这个 T4 就是点啊，贡献后置的 trick 在 arc 见过。
然后惊恐发现大样例都水完了，于是造极限数据。
T3 本地跑 3s+，但是读入就 600ms，这我优化个吊啊。
不管了跑路了。
回去的车上知道了一个悲伤的事。逝者安息。
我该在哪里停留？我问我自己。

Day 1

才知道 T3 询问串长度不等，那我不四万了。
【数据删除】
熨斗上 j ak 了，s 100+80+100+100100+80+100+100，sd rk14。
洛谷上 s 100+88+90+100100+88+90+100。
T2 问题不大，相信少爷机。
T3 卡就卡吧，给孩子留点分就行了。
想去冬令营，能赢吗？

Day 4

通过【数据删除】得到分数：
J：100+100+100+100=400100+100+100+100=400。
S：100+80+100+100=380100+80+100+100=380。
S T2 的并查集没写按秩合并。
之前一直认为只路径压缩就是 α(n)\alpha(n)。但是只路径压缩或只按秩合并都是 log⁡\log，一起用才能 α(n)\alpha(n)。
严肃学习了。
ccf 还我 20 分！！！
算了，本质是没做到 n2kα(n)n2^k\alpha(n)。
附代码：
J T1CPP
#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;
}
J T2CPP
#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;
}
J T3CPP
#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; 
}
J T4CPP
#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;
}
S T1CPP
#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;
}
S T2CPP
#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;
}
S T3CPP
#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;
}
S T4CPP
#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;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...