专栏文章

AtCoder Beginner Contest 432

TT0mle
个人记录参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min75yoy
此快照首次捕获于
2025/12/01 21:40
3 个月前
此快照最后确认于
2025/12/01 21:40
3 个月前
查看原文
顺序：ABCDEGF
本来想倒序开的，但 zzr 说要拉爆我于是正序。

A

可以排序简单写。
CPP
int a[4];

void solve() {
	cin >> a[1] >> a[2] >> a[3];
	sort(a + 1, a + 4);
	cout << a[3] << a[2] << a[1];
}
0:36

B

csp-j2025 T1 加强版。
先输出一个非 0 的数，然后按顺序输出。
CPP
string s;
int buc[11];

void solve() {
	cin >> s;
	for (auto c : s) buc[c ^ 48]++;
	rep(i, 1, 9) {
		if (buc[i]) {
			cout << i;
			buc[i]--;
			break;
		}
	}
	rep(i, 0, 9) {
		while (buc[i]--) cout << i;
	}
}
2:16

C

最唐的一次，在 C 题时间花时间最长。
猎奇思路：
假设每个人的唐总重量是 SS，第 ii 个人吃了 nn 个小的和 mm 个大的，有：
{n+m=ainx+my=S\begin{cases} n+m=a_i\\ nx+my=S \end{cases}
解得
{n=aiy−Sy−xm=S−aixy−x\begin{cases} n=\frac{a_iy-S}{y-x}\\ m=\frac{S-a_ix}{y-x} \end{cases}
由于 n,mn,m 都是非负整数，可得所有 aix mod (y−x)a_ix\bmod (y-x) 和所有 aiy mod (y−x)a_iy\bmod (y-x) 需相等。对于 SS 需要有 S≡aix mod (y−x),S∈[max⁡{aix},min⁡{aiy}]S\equiv a_ix\bmod (y-x),S\in[\max\{a_ix\},\min\{a_iy\}]。然后算一算。
脑子不清醒，28:01 过的。
CPP
void solve() {
	rd(n), rd(x), rd(y);
	int sm = 0;
	rep(i, 1, n) rd(a[i]), sm += a[i];
	int gl = 1ll * a[1] * x % (y - x), LB = 0, UB = 1e18;
	rep(i, 1, n) {
		if (1ll * a[i] * x % (y - x) != gl) { puts("-1"); return; }
		if (1ll * a[i] * y % (y - x) != gl) { puts("-1"); return; }
		ckmx(LB, 1ll * a[i] * x);
		ckmn(UB, 1ll * a[i] * y);
	}
	int mod = y - x, ans;
	if (UB % mod >= gl) ans = UB - (UB % mod - gl);
	else ans = UB - (UB % mod - gl + mod);
	// cout << LB << " " << UB << "  " << ans << endl;
	if (ans < LB) { puts("-1"); return; }
	ans *= n;
	wrt((ans - sm * x) / mod);
}

D

观后感：猎奇。
注意到 N≤14N\le14，我们可以维护一些矩形，每次操作后矩形数至多翻倍，最后有 2N2^N 个矩形，O(4N)O(4^N) 枚举矩形对然后并查集合并。
写完 50:35，怎么已经过半了。
CPP
int n, x, y;
char c;
int a, b;
struct mat { int x1, y1, x2, y2; };
vector <mat> dat;
int dsu[1 << 14], siz[1 << 14];

int find(int k) { return k == dsu[k] ? k : dsu[k] = find(dsu[k]); }
void solve() {
	cin >> n >> x >> y;
	dat.pb({0, 0, x - 1, y - 1});
	while (n--) {
		cin >> c >> a >> b;
		int siz = dat.size();
		repr(i, 0, siz) {
			if (c == 'X') {
				if (dat[i].x2 < a) {
					dat[i].y1 -= b, dat[i].y2 -= b;
				} else if (dat[i].x1 >= a) {
					dat[i].y1 += b, dat[i].y2 += b;
				} else {
					dat.pb({a, dat[i].y1 + b, dat[i].x2, dat[i].y2 + b});
					dat[i] = {dat[i].x1, dat[i].y1 - b, a - 1, dat[i].y2 - b};
				}
			} else {
				if (dat[i].y2 < a) {
					dat[i].x1 -= b, dat[i].x2 -= b;
				} else if (dat[i].y1 >= a) {
					dat[i].x1 += b, dat[i].x2 += b;
				} else {
					dat.pb({dat[i].x1 + b, a, dat[i].x2 + b, dat[i].y2});
					dat[i] = {dat[i].x1 - b, dat[i].y1, dat[i].x2 - b, a - 1};
				}
			}
		}
	}
	int n = dat.size();

	repr(i, 0, n) dsu[i] = i, siz[i] = (dat[i].x2 - dat[i].x1 + 1) * (dat[i].y2 - dat[i].y1 + 1);
	repr(i, 0, n) {
		repr(j, 0, n) {
			if (find(i) == find(j)) continue;
			int a = max(dat[i].x1, dat[j].x1), b = min(dat[i].x2, dat[j].x2), c = max(dat[i].y1, dat[j].y1), d = min(dat[i].y2, dat[j].y2);
			if (a > b && c > d) continue;
			if (a - 1 <= b && c - 1 <= d) {
				siz[find(i)] += siz[find(j)];
				dsu[find(j)] = find(i);
			}
		}
	}
	vi ans;
	repr(i, 0, n) {
		if (find(i) == i) {
			ans.pb({siz[i]});
		}
	}
	sort(ans.begin(), ans.end());
	cout << ans.size() << endl;
	for (auto x : ans) cout << x << " ";
}
上面这个东西只跑 1ms，何意味。

E

唐，放这个 E 是中场休息吗。
7min 打了个线段树。
57:38。
CPP
int n, q, a[N], op, x, y;

struct Seg {
	int l, r, sm, ct;
	#define l(p) tr[p].l
	#define r(p) tr[p].r
	#define sm(p) tr[p].sm
	#define ct(p) tr[p].ct
} tr[N << 2];
#define M (l(p) + r(p) >> 1)
#define ls (p << 1)
#define rs (p << 1 | 1)

inline void pushup(int p) {
	sm(p) = sm(ls) + sm(rs);
	ct(p) = ct(ls) + ct(rs);
}
void build(int p, int l, int r) {
	l(p) = l, r(p) = r;
	if (l == r) return;
	build(ls, l, M), build(rs, M + 1, r);
}
void modify(int p, int x, int k) {
	if (l(p) == r(p)) {
		ct(p) += k;
		sm(p) += x * k;
		return;
	}
	modify(x <= M ? ls : rs, x, k), pushup(p);
}
int query1(int p, int l, int r) {
	if (l > r) return 0;
	if (l <= l(p) && r >= r(p)) return ct(p);
	if (r <= M) return query1(ls, l, r);
	if (l > M)  return query1(rs, l, r);
	return query1(ls, l, r) + query1(rs, l, r);
}
int query2(int p, int l, int r) {
	if (l > r) return 0;
	if (l <= l(p) && r >= r(p)) return sm(p);
	if (r <= M) return query2(ls, l, r);
	if (l > M)  return query2(rs, l, r);
	return query2(ls, l, r) + query2(rs, l, r);
}
void solve() {
	rd(n), rd(q);
	build(1, 0, 5e5);
	rep(i, 1, n) {
		rd(a[i]);
		modify(1, a[i], 1);
	}
	while (q--) {
		rd(op), rd(x), rd(y);
		if (op == 1) {
			modify(1, a[x], -1);
			modify(1, a[x] = y, 1);
		} else {
			int l = x, r = y;
			if (l >= r) cout << n * l << endl;
			else {
				int ans = query2(1, l, r);
				ans += r * query1(1, r + 1, 5e5);
				ans += l * query1(1, 0, l - 1);
				cout << ans << endl;
			}
		}
	}
}

G

依旧 G 放 poly 板子。
令 cxc_x 为 xx 在 BB 出现次数，答案为：
∑i=1nai!∑j=0aicjj!⋅1(ai−j)!\sum_{i=1}^na_i!\sum_{j=0}^{a_i}\frac{c_j}{j!}\cdot\frac1{(a_i-j)!} CPP
void solve() {
	repr(i, fac[0] = 1, N) fac[i] = 1ll * fac[i - 1] * i % mod;
	fiv[N - 1] = qpw(fac[N - 1], mod - 2);
	per(i, N - 2, 0) fiv[i] = fiv[i + 1] * (i + 1ll) % mod;

	rd(n), rd(m);
	rep(i, 1, n) rd(a[i]);
	rep(i, 1, m) rd(b[i]), c[b[i]]++;
	rep(i, 0, 5e5) c[i] = 1ll * c[i] * fiv[i] % mod, d[i] = fiv[i];
	int tot = 1; while (tot <= 1e6) tot <<= 1;
	ntt(c, tot, 0), ntt(d, tot, 0);
	repr(i, 0, tot) c[i] = 1ll * c[i] * d[i] % mod;
	ntt(c, tot, 1);
	int ans = 0;
	rep(i, 1, n) {
		ans = (ans + 1ll * fac[a[i]] * c[a[i]]) % mod;
	}
	cout << ans;
}
66:49

F

全场最好题。
判掉 N∤∑AN\nmid\sum A。
对于任意一个平均值等于 Aˉ\bar A 的子集，都可以用长度减一次操作调整。
我们考虑对每个状态求一个子集，子集内部可以调整。
这部分可以 sosdp 做到 O(N2N)O(N2^N)。
然后随便搞一下。
CPP
void dfs(int sta) {
	if (f[sta] == sta) {
		int tot = 0;
		rep(i, 1, n) {
			if (sta >> i - 1 & 1) b[++tot] = {a[i], i};
		}
		sort(b + 1, b + tot + 1, greater <pii> ());
		repr(i, 1, tot) {
			ans.pb({b[i].se, b[i + 1].se, b[i].fi - gl});
			b[i + 1].fi += b[i].fi - gl;
		}
		return;
	}
	dfs(f[sta]), dfs(sta ^ f[sta]);
}
void solve() {
	cin >> n;
	int sm = 0;
	rep(i, 1, n) cin >> a[i], sm += a[i];
	if (sm % n) { puts("-1"); return; }
	gl = sm / n;
	repr(i, 0, 1 << n) {
		f[i] = 1e9;
		if (!i) continue;
		int sm = 0, len = __builtin_popcount(i);
		rep(j, 1, n) if (i >> j - 1 & 1) sm += a[j];
		if (sm % len == 0 && sm / len == gl) {
			f[i] = i;
		}
	}
	repr(i, 0, n) {
		repr(j, 0, 1 << n) {
			if (j >> i & 1) ckmn(f[j], f[j ^ 1 << i]);
		}
	}
	dfs((1 << n) - 1);
	cout << ans.size() << endl;
	for (auto [a, b, c] : ans) cout << a << " " << b << " " << c << endl;
}

评论

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

正在加载评论...