最后一次 CSP —— 2025 CSP-S2 游记

const int N = 1e5 + 29;

int n, m;
int d[N];
vector<int> a, b, c;
priority_queue<int, vector<int>, greater<int> > q;

void tbcclear() {
	a.clear();
	b.clear();
	c.clear();
	rep (i, 1, n) d[i] = 0;
	while (q.size()) q.pop();
}

void tbcsolve() {
	cin >> n;
	tbcclear();
	int cnt1 = 0, cnt2 = 0, cnt3 = 0, ans = 0;
	rep (i, 1, n) {
		int x, y, z;
		cin >> x >> y >> z;
		if (x >= y && x >= z) { // 如果对第一个部门最满意的话
			cnt1++; // 加入第一个部门的人数 +1
			ans += x; // 将该满意度加进答案里
			a.pb(i); // 记录目前在第一个部门的人员
			if (y > z) d[i] = x - y; // 记录第 i 个人最大满意度和次大满意度的差值
			else d[i] = x - z;
		}
		else if (y >= x && y >= z) {
			cnt2++;
			ans += y;
			b.pb(i);
			if (x > z) d[i] = y - x;
			else d[i] = y - z;
		}
		else {
			cnt3++;
			ans += z;
			c.pb(i);
			if (x > y) d[i] = z - x;
			else d[i] = z - y;
		}
	}
	int maxn = max({cnt1, cnt2, cnt3});
	if (maxn <= (n >> 1)) { // 如果人数都没有超过 n/2 的话直接输出答案
		cout << ans << '\n';
		return; 
	}
	if (cnt1 == maxn) {
		for (auto i : a) q.push(d[i]); // 把人数超了的部门的人的满意度差值扔进小顶堆里
		while (cnt1 > (n >> 1)) { // 重复调整人员直到人数不大于 n/2
			ans -= q.top(); // 用答案减去这个差值
			q.pop();
			cnt1--;
		}
	}
	else if (cnt2 == maxn) {
		for (auto i : b) q.push(d[i]);
		while (cnt2 > (n >> 1)) {
			ans -= q.top();
			q.pop();
			cnt2--;
		}
	}
	else {
		for (auto i : c) q.push(d[i]);
		while (cnt3 > (n >> 1)) {
			ans -= q.top();
			q.pop();
			cnt3--;
		}
	}
	cout << ans << '\n';
}

const int N = 1e4 + 29;
const int M = 2e6 + 29;

int n, m, k, ans, tot;
int a[N], fa[N];
struct node {
	int a, b, w;
} e[M];

bool cmp(node x, node y) {
	return x.w < y.w;	
}

int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
	int fx = find(x), fy = find(y);
	fa[fy] = fx;
}

void tbcsolve() {
	cin >> n >> m >> k;
	rep (i, 1, m) cin >> e[i].a >> e[i].b >> e[i].w;
	int cnt = m;
	rep (i, n + 1, n + k) {
		int c; cin >> c;
		rep (j, 1, n) {
			cin >> e[++cnt].w;
			e[cnt].a = j;
			e[cnt].b = i;
		}
	}
	n += k;
	sort(e + 1, e + 1 + cnt, cmp);
	rep (i, 1, n) fa[i] = i;
	rep (i, 1, cnt) {
		int u = e[i].a, v = e[i].b, w = e[i].w;
		if (find(u) == find(v)) continue;
		merge(u, v);
		ans += w;
		if (++tot >= n - 1) break;
	}
	cout << ans << '\n';
}

const int N = 2e5 + 29;

int n, q;
struct node {
	bool lr; // 记录 b 是向左移动还是向右移动，向左为 0 向右为 1
	int d; // 前后 b 的移动距离
	int left; // 左边的 b 左边 a 的个数
	int right; // 右边的 b 右边 a 的个数
} a[N];
vector<int> l, r;

void tbcsolve() {
	cin >> n >> q;
	rep (i, 1, n) {
		string s1, s2;
		cin >> s1 >> s2;
		int len = s1.size();
		int pos1, pos2; // 记录两个字符串里 b 的位置
		rep (j, 0, len - 1) if(s1[j] == 'b') pos1 = j;
		rep (j, 0, len - 1) if(s2[j] == 'b') pos2 = j;
		if (pos1 < pos2) {
			a[i] = {1, pos2 - pos1, pos1, len - 1 - pos2}; // 这个自己写一下结合结构体的注释就能理解了
			r.pb(i);
		}
		else {
			a[i] = {0, pos1 - pos2, pos2, len - 1 - pos1};
			l.pb(i);
		}
	}
	while (q--) {
		string t1, t2;
		cin >> t1 >> t2;
		int len = t1.size();
		int pos1, pos2;
		rep (j, 0, len - 1) if(t1[j] == 'b') pos1 = j;
		rep (j, 0, len - 1) if(t2[j] == 'b') pos2 = j;
		int ans = 0;
		if (pos1 < pos2) {
			for (auto i : r) {
                // 如果 b 的移动距离一样且左右 a 的个数比选中的 s 中的个数要多说明可以使用
				if (a[i].d == pos2 - pos1 && a[i].left <= pos1 && a[i].right <= len - 1 - pos2) ans++; 
			}
		}
		else {
			for (auto i : l) {
				if (a[i].d == pos1 - pos2 && a[i].left <= pos2 && a[i].right <= len - 1 - pos1) ans++; 
			}
		}
		cout << ans << '\n';
	}
}

const int N = 500 + 29;
const int mod = 998244353;

int n, m;
int c[N];
string s;

bool judgeA() {
	for (auto i : s) if (i == '0') return false;
	return true;
}
bool judge0() {
	rep (i, 1, n) if (c[i] == 0) return false;
	return true;
}
int all(int x) {
	int res = 1;
	rep (i, 2, x) res = (res * i) % mod;
	return res;
} 

void tbcsolve() {
	cin >> n >> m;
	cin >> s;
	rep (i, 1, n) cin >> c[i];
	if (m == n) {
		if (!judgeA() || !judge0()) {
			cout << 0 << '\n';
			return;
		}
		cout << all(n) << '\n';
		return;
	}
}