AtCoder Grand Contest 001

官方题解：https://img.atcoder.jp/agc001/editorial.pdf

听说多做 AGC 可以提升智力，于是来尝试提升一下智力~~（虽然都是抄的题解）~~。

A - BBQ Easy

$2n$ 个数，最大化两两一组分组后，每组两个数取 $\min$ 的和。

从小到大排序之后，两两组合，答案是奇数位置的和。

#include <bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

vector<int> a;

int main() {
	int n = (rd() << 1);
	for (int i = 1; i <= n; ++i) a.push_back(rd());
	sort(a.begin(), a.end());
	int ans = 0;
	for (int i = 0; i < n; i += 2) ans += a[i];
	printf("%d\n", ans);
	return 0;
}

B - Mysterious Light

边长为 $n$ 的正三角形 ABC 的边 AB 上 $x$ 处平行 BC 射出一条激光。

碰到边界反射，碰到此前的光线也反射，求回到起点的路径长度。

没看懂官方题解的简单做法。

首先前两段光路长度和是 $n$ ，会切掉两个角，变成一个平行四边形。

对于平行四边形（边长分别为 $a$ 和 $b$ ），光线从一个 $120^\circ$ 角出发，沿角平分线射出距离为 $f(a,b)$

有 $f(a,0)=-a, f(a,b) = 2 \ast \displaystyle\lfloor \frac{a}{b}\rfloor \ast b +f(b, a \% b)$ ，也就是每次都切短边直到长短边交换，减掉最后一次多算的。

答案就是 $n+f(x,n-x)$ ，递归形式和 gcd 相同，所以复杂度是 $\mathcal O(\log n)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll rd() {
	ll x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

inline ll f(ll a, ll b) {
	return b ? 2 * (a / b) * b + f(b, a % b) : -a;
}

int main() {
	ll n = rd(), x = rd();
	printf("%lld\n", n + f(x, n - x));
	return 0;
}

C - Shorten Diameter

给一棵树，每次可以删掉一个叶子，问最少删多少次使得直径不超过 $k$

本来想贪心每次删一个直径的端点，但是不对，因为有可能这个点会被保留到最后。

因为 $n$ 只有 $2000$ ，所以可以 $\mathcal{O}(n^2)$ 暴力，那么枚举中心就好了。

如果 $k$ 是奇数，枚举中心的边，把树分成两棵，根就是这条边的两个端点，每棵只保留深度小于 $\lfloor k/2\rfloor$ 的点
如果 $k$ 是偶数，枚举中心的点，以这个点为根，只保留深度小于 $\lfloor k/2\rfloor$ 的点

找到上述情况里需要删除的点最少的情况即可。

#include <bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 2007
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>

vector<pii> r;
vector<int> e[N];

int dep[N];

void dfs(int u) {
	for (auto v : e[u])
		if (dep[v] < 0) {dep[v] = dep[u] + 1; dfs(v);}
}

int main() {
	int n = rd(), k = rd();
	for (int i = 1, u, v; i < n; ++i) {
		u = rd(); v = rd();
		e[u].pb(v); e[v].pb(u);
		if (k & 1) r.pb(mp(u, v));
	}
	int ans = 0;
	if (k & 1) {
		for (auto [u, v] : r) {
			memset(dep, -1, sizeof(dep));
			dep[u] = 0; dep[v] = 0; dfs(u); dfs(v);
			int tmpans = 0;
			for (int j = 1; j <= n; ++j) tmpans += (dep[j] <= k / 2);
			ans = max(ans, tmpans);
		}
	} else {
		for (int i = 1; i <= n; ++i) {
			memset(dep, -1, sizeof(dep));
			dep[i] = 0; dfs(i);
			int tmpans = 0;
			for (int j = 1; j <= n; ++j) tmpans += (dep[j] <= k / 2);
			ans = max(ans, tmpans);
		}
	}
	printf("%d\n", n - ans);
	return 0;
}

D - Arrays and Palindrome

给定序列 $\{A_i\}$ ，满足 $\sum A_i=N$ ，需要重排 $\{A_i\}$ ，并且构造 $\{B_i\}$ ，满足 $\sum B_i=N$ ，且满足：

如果一个长度为 $N$ 的串 $S$ 满足（ $S[l,r]$ 表示 $S[l]S[l+1]\dots S[r]$ 这一段子串）：

$\forall i,\ S[\sum_{j=1}^{i-1}A_j+1, \sum_{j=1}^i A_j]$ 是回文的（也就是按照 $A_i$ 分割成若干段子串，都是回文的）

$\forall i,\ S[\sum_{j=1}^{i-1}B_j+1, \sum_{j=1}^i B_j]$ 是回文的（也就是按照 $B_i$ 分割成若干段子串，都是回文的）

那么 一定能推出 $S$ 中全部字符都相同。

好有意思的题目啊！！建议先看官方题解。

假如我们确定了 $\{A\}$ 的顺序，那么 $\{A\}$ 把序列分成若干段，每段对称的位置字符要相同。

我们如果把 $N$ 个位置看作 $N$ 个点，那么可以把 $A$ 的所有要求对称的位置连一条边。

现在 $B$ 相当于是要补一些边，使得所有点都连通。

假设所有的 $A_i$ 均为偶数，那么令$|\{B\}|=|\{A\}|$ ，先让 $B_i=A_i$ ，然后 $B_1 B_1-1,B_{|{B}|}B_{|{B}|}+1 $

那么（除第一段外）每一段的最后一个都和前一段的最后一个连边，连通了两段；

此外每一段内的连边都是奇偶位置错开的，所以整个图是连通的。

然后考虑 $A_i$ 有奇数，可以证明最多允许有两段奇数，把这两段放在两边，还是不影响答案的。

如果奇数长度段超过两个，一定无解，具体证明看官方题解，大概方法就是证明了边数凑不到 $n-1$ 。

感觉这个构造真的很 useful 啊（

#include <bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define ppb pop_back
#define psb push_back
#define ppf pop_front
#define psf push_front

deque<int> s, odd;

int main() {
	int m = rd(), n = rd();
	for (int i = 1, x; i <= n; ++i) {
		x = rd();
		(x & 1) ? odd.psb(x) : s.psb(x);
	}
	if (odd.size() > 2) {puts("Impossible"); return 0;}
	if (odd.size() > 0) s.psf(odd[0]);
	if (odd.size() > 1) s.psb(odd[1]);
	for (auto x : s) printf("%d ", x); puts("");
	//需要注意只有一个元素和第一个元素是1的情况
	if (s.size() == 1) s.psb(0);
	--s.front(); ++s.back();
	if (s.front() == 0) s.ppf();
	printf("%d\n", s.size());
	for(auto x : s) printf("%d ", x);
	return 0;
}

E - BBQ Hard

给定 $N$ 个 $(A_i,B_i)$ ，求： \[ \sum_{i=1}^{n-1}\sum_{j=i+1}^n {A_i+A_j+B_i+B_j\choose A_i+A_j} \mod 10^9+7 \] 数据范围 $2\le n\le 2\times 10^5,1\le a_i,b_i\le 2000$

只能往右和往上走，计数从 $(x_0,y_0)$ 到 $(x_1,y_1)$的路径方案数，考虑哪些步是横向走，是 $\displaystyle{ {x_1-x_0+y_1-y_0} \choose {x_1-x_0}}$ 。

当然也可以用一个二维递推，令 f[x0][y0]=1 ，每次f[i][j] = f[i - 1][j] + f[i][j - 1] ，答案f[x1][y1] 。

把式中 $\displaystyle{A_i+A_j+B_i+B_j\choose A_i+A_j}$ 变形为 $\displaystyle {A_i-(-A_j)+B_i-(-B_j)\choose A_i-(-A_j)}$ ，可解读为从 $(-A_j,-B_j)$ 到 $(A_i,B_i)$ 的路径数。

那么把求和改一下形式，两个循环都改成从 $1$ 到 $n$ ，然后扣掉自己到自己的贡献，再除 $2$ 就是答案。 \[ ans = \frac{\sum_{i=1}^{N} \sum_{j=1}^{N} \displaystyle{A_{i} +B_{i}+A_{j}+B_{j} \choose A_{i}+B_{i}}-\sum_{i=1}^{N} {2\ast A_{i}+2\ast B_{i} \choose 2 \ast A_{i}}}{2} \mod 10^9+7 \] 前一半考虑用上面提到的递推方法整体一起求（加个偏移量把坐标调成正的）：

先给所有的 f[-a[i]][-b[i]] += 1 ，然后递推完查所有的 f[a[i]][b[i]] 即可。

后一半用组合数直接算就好了。总复杂度 $\mathcal{O}(n+4\ast \max a_i\ast \max b_i)$ 。

#include <bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define A 4007
#define G 2001
#define M 8007
#define N 200007
#define mod 1000000007
#define inv2 500000004

int f[A][A], fac[M], ifac[M], x[N], y[N];

inline int fpow(int x, int t = mod - 2) {
	int res = 1;
	for (; t; t >>= 1, x = 1ll * x * x % mod)
		if (t & 1) res = 1ll * res * x % mod;
	return res;
}

inline int mo(int x) {
	for (; x < 0; x += mod);
	for (; x >= mod; x -= mod);
	return x;
}

inline int C(int n, int m) {
	if (n < m) return 0;
	return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

int main() {

	fac[0] = ifac[0] = 1;
	for (int i = 1; i < M; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
	ifac[M - 1] = fpow(fac[M - 1]);
	for (int i = M - 2; i; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;

	int n = rd();
	for (int i = 1; i <= n; ++i) {
		x[i] = rd(); y[i] = rd();
		++f[-x[i] + G][-y[i] + G];
	}
	for (int i = 1; i < A; ++i)
		for (int j = 1; j < A; ++j)
			f[i][j] = mo(f[i][j] + f[i - 1][j] + f[i][j - 1]);
	int ans = 0;
	for (int i = 1; i <= n; ++i)
		ans = mo(ans + f[x[i] + G][y[i] + G] - C(2 * (x[i] + y[i]), 2 * x[i]));
	printf("%lld\n", 1ll * ans * inv2 % mod);
	return 0;
}

F - Wide Swap

给定一个 $\{1,2,\dots,n\}$ 的排列 $\{P\}$ ，每次操作：

选取两个距离至少为 $k$ 的位置 $i,j$ 且 $|P_i-P_j|=1$ ，交换 $i,j$ 两个位置上的数。

你可以任意次数操作，问可能得到的最小字典序排列是什么。

排列求个逆（即 $Q_{P_i}=i$ ），$Q_i$ 的含义就是数字 $i$ 的位置。

问题转化为：相邻并且差值至少为 $k$ 的两个 $Q$ 可以交换，$Q$ 可能最小字典序是什么（小的数字位置靠前）。

如果 $|Q_i-Q_j|<k$ ，那么 $Q_i$ 和 $Q_j$在序列里的相对顺序永远都不能改变（换到相邻就不能操作了）。

反之如果两个位置差值 $\ge k$，只要能换到相邻，就一定可以交换，如果换不到相邻，一定是上面的约束导致的。

所以如果 $|Q_i-Q_j|\ge k$ ，那么$Q_i$ 和 $Q_j$ 在序列里的顺序没有任何要求。

只有 " $a$ 一定要在 $b$ 前" 这种约束的最小字典序排列显然可以用优先队列的拓扑排序求。

但是边的级别是 $\mathcal{O}(n^2)$ 的： $Q_i$ 会向 $\forall j>i,Q_j\in[Q_i-k + 1,Q_i + k-1]$ 的所有 $Q_j$ 连边。

考虑去掉一些没有意义的边：假设 $(x,y),(y,z),(x,z)$ 都存在，那么 $(x,z)$ 显然是没必要存的。

把区间拆成两块 $[Q_i-k+1,Q_i],[Q_i,Q_i+k-1]$ ，这两个区间内部有约束的肯定会两两连边（单向）。

因此 $Q_i$ 并不需要向这里面的全部点连边，完全可以继承区间里最靠前的位置的所有边，然后让自己指向这个位置即可。

形式化的说，对于某个区间，找到 $pos = \min_{Q_j\in [\text{interval}]} j$ ，那么只需要连 $Q_i\to Q_{pos}$ ，其余边都间接继承 $Q_{pos}$ 的。

这样边的级别（也就是拓扑排序复杂度）就是 $\mathcal{O}(n)$ 的，找 $pos$ 需要单点更新查区间 $\min$ ，用线段树复杂度 $\mathcal{O}(n\log n)$ 。

#include <bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 500007
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) >> 1)

int mn[N << 2];

void pushup(int rt) {
	mn[rt] = min(mn[ls], mn[rs]);
}

void upd(int rt, int l, int r, int k, int v) {
	if (l == r) {
		mn[rt] = v; return;
	}
	if (k <= mid) upd(ls, l, mid, k, v);
	else upd(rs, mid + 1, r, k, v);
	pushup(rt);
}

int qmn(int rt, int l, int r, int L, int R) {
	if (L <= l && r <= R) return mn[rt];
	int ans = 1e9;
	if (L <= mid) ans = min(ans, qmn(ls, l, mid, L, R));
	if (R > mid) ans = min(ans, qmn(rs, mid + 1, r, L, R));
	return ans;
}

int p[N], q[N], deg[N];

vector<int> e[N];

#define pb push_back

priority_queue<int, vector<int>, greater<int> >que;

int main() {
	int n = rd(), k = rd();
	memset(mn, 0x3f, sizeof(mn));
	for (int i = 1; i <= n; ++i) q[p[i] = rd()] = i;
	for (int i = n; i; --i) {
		int j = qmn(1, 1, n, q[i], min(n, q[i] + k - 1));
		if (j <= n) {e[q[i]].pb(q[j]); ++deg[q[j]];}
		j = qmn(1, 1, n, max(1, q[i] - k + 1), q[i]);
		if (j <= n) {e[q[i]].pb(q[j]); ++deg[q[j]];}
		upd(1, 1, n, q[i], i);
	}
	for (int i = 1; i <= n; ++i)
		if (!deg[i]) que.push(i);
	for (int i = 1; i <= n; ++i) {
		int u = q[i] = que.top(); que.pop();
		for (auto v : e[u]) 
			if (!(--deg[v])) que.push(v);
	}
	for (int i = 1; i <= n; ++i) p[q[i]] = i;
	for (int i = 1; i <= n; ++i) printf("%d\n", p[i]);
	return 0;
}

AtCoder AtCoder Grand Contest

Constructive Algorithm

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

Dynamic Programming on Intervals Previous

AtCoder Beginner Contest 244 Next