AtCoder Grand Contest 036 题解

AtCoder Grand Contest 036

Triangle

考虑 $\triangle (0,0)(x,n)(n,y)$ 的面积为 $n^2 - xy$，找到最小的 $n$ 满足 $n^2 \ge S$，设 $k = n^2 - S$，有 $0 \le k \le 2n-1$。

若 $k < n$，则 $\triangle (0,0)(k,n)(n,1)$ 满足条件，否则 $\triangle (0,0)(k-n,n-1)(n,1)$ 满足条件。

注意可能会有精度误差，要简单调一下。

inline void out(ll x, ll y) {
	print(x, ' '), print(y, ' ');
}

int main() {
	ll s;
	rd(s);
	ll n = sqrt(s);
	while (n * n >= s) --n;
	while (n * n < s) ++n;
	ll k = n * n - s;
	if (k < n) out(0, 0), out(k, n), out(n, 1);
	else out(0, 0), out(k - n, n - 1), out(n, 1);
	return 0;
}

Do Not Duplicate

考虑对于每个 $i$ 求出以 $a_i$ 开始的情况下需要多少步会清空，清空后下一个填的数。

设步数为 $d_i$，填的数为 $t_i$，连一条 $(i,t_i,d_i)$ 的有向边，则会形成一个 $n$ 个点的基环内向边带权森林。

整个过程会从起点开始，走到环上之后，绕环若干圈，最后再走不到整环的一段。

模拟就好了，时间复杂度 $\mathcal O(n)$。

const int N = 2e5 + 7;
int n, a[N<<1|1], b[N<<1|1], t[N], d[N], p[N];
ll k, s[N];
bool v[N];

inline void work(int &o, ll &k, int ed = 0) {
	while (o != ed && k >= d[o])
		k -= d[o], o = t[o];
}

int main() {
	rd(n), rd(k), k *= n;
	rda(a, n);
	for (int i = 1; i <= n; i++) a[i+n] = a[i];
	for (int i = n << 1; i; i--) b[i] = p[a[i]], p[a[i]] = i;
	for (int i = 1; i <= n; i++)
		t[i] = b[i] % n + 1, d[i] = b[i] - i + 1;
	int o = 1;
	v[o] = 1;
	while (!v[t[o]]) {
		v[t[o]] = 1;
		s[t[o]] = s[o] + d[o];
		o = t[o];
	}
	ll g = s[o] + d[o] - s[t[o]];
	int x = t[o];
	o = 1;
	work(o, k, x);
	k %= g;
	work(o, k);
	for (int i = 1; i <= n; i++) v[i] = 0;
	vi ans;
	while (k--) {
		if (o == n + 1) o = n;
		int w = a[o++];
		if (v[w]) while (v[w]) v[ans.back()] = 0, ans.pop_back();
		else ans.pb(w), v[w] = 1;
	}
	for (int x : ans) print(x, ' ');
	return 0;
}

GP 2

满足条件的序列等价于（从 $1$ 开始编号）：

• $a_i \le 2m$。
• $\sum_{i=1}^n a_i = 3m$。
• $\sum_{i=1}^n \lfloor \frac {a_i}2 \rfloor \ge m$。

枚举 $\sum_{i=1}^n \lfloor \frac {a_i}2 \rfloor$ 的值，剩下就是一个多重集组合数，容斥一下发现计算量是常数，时间复杂度 $\mathcal O(n)$。

int n, m;
modint ans;

int main() {
	rd(n, m), init(n + 3 * m / 2);
	for (int k = m; k <= 3 * m / 2; k++) {
		int b = 3 * m - 2 * k, a = n - b;
		if (a < 0 || b < 0) continue;
		ans += binom(n, a) * (binom(n + k - 1, n - 1) - a * binom(n + k - m - 2, n - 1) - b * binom(n + k - m - 1, n - 1));
	}
	print(ans);
	return 0;
}

Negative Cycle

题意

• 有一张 $n$ 个点的有向图，点的编号为 $0 \sim n - 1$。
• 一开始有 $n-1$ 条边，对于 $i\in [0,n-2]$，有边 $(i,i+1,0)$。
• 另外若 $i<j$，加边 $(i,j,-1)$；若 $i>j$，加边 $(i,j,1)$。这些边都可以删除，边 $(i,j)$ 删除的代价为 $a_{i,j}$。
• 你希望用最小的代价删除某些边，使得图中不存在负环。
• $n \le 500$，$a_{i,j} \le 10^9$。

题解

考虑差分约束模型，图中不存在负环等价于存在一组合法的差分约束的解。

将每个节点作为一个变量，第 $i$ 个节点对应的变量为 $x_i$。因为初始的边不能删去，所以一定有 $x_i \ge x_{i + 1}$。

令 $q_i = x_i - x_{i + 1}$，有 $q_i \ge 0$。

假设保留了一条边权为 $-1$ 的 $i \to j(i < j)$ 的边，有 $x_i - 1 \ge x_j$，即 $x_i - x_j \ge 1$，即 $q_i + q_{i + 1} + \cdots + q_{j - 1} \ge 1$；假设保留了一条边权为 $1$ 的 $i \to j(i>j)$ 的边，有 $x_i + 1 \ge x_j$，即 $x_j - x_i \le 1$，即 $q_j + q_{j + 1} + \cdots + q_{i - 1} \le 1$。

反过来想，如果确定了所有的 $q_i$，那么每一条边就应该尽可能地保留下来，这样代价最小。

对于边权为 $-1$ 的边，是区间和 $\ge 1$ 才能保留，也就是说如果区间和 $= 0$ 就必须删除；对于边权为 $1$ 的边，是区间和 $\le 1$ 才能保留，也就是说如果区间和 $\ge 2$ 就必须删除。

也就是说，对于一种 $q$ 的取值方案，$q_i = 0$ 的每个连续段，都对应着一系列的边权为 $-1$ 的边的删除，而区间和 $\ge 2$ 的区间也对应着边权为 $1$ 的边的删除。

可以发现如果出现了 $q_i \ge 2$，不如把它变成 $1$，这样一定更优，所以只需要考虑 $q$ 的取值为 $0/1$ 的情况。

考虑 DP，设 $f_{i,j}$ 表示最后一个 $1$ 取在 $q_i$ 处，倒数第二个 $1$ 取在 $q_j$ 处的情况下，前缀 $i$ 的代价的最小值。

转移枚举下一个 $1$ 的位置即可，二维前缀和预处理转移系数后，时间复杂度 $\mathcal O(n^3)$。

代码

const int N = 507;
const ll inf = 1e18;
int n;
ll a[N][N], b[N][N], f[N][N], ans = inf;

inline ll calc(int k, int j, int i) {
	return b[j+1][i] + a[n][j] - a[n][k] - a[i][j] + a[i][k];
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (i != j) rd(a[i][j]);
	for (int j = 1; j <= n; j++)
		for (int i = j; i; i--)
			b[i][j] = b[i+1][j] + b[i][j-1] - b[i+1][j-1] + a[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
	for (int i = 1; i < n; i++) {
		f[i][0] = calc(0, 0, i);
		ans = min(ans, f[i][0] + calc(0, i, n));
		for (int j = 1; j < i; j++) {
			f[i][j] = inf;
			for (int k = 0; k < j; k++)
				f[i][j] = min(f[i][j], f[j][k] + calc(k, j, i));
			ans = min(ans, f[i][j] + calc(j, i, n));
		}
	}
	print(ans);
	return 0;
}

ABC String

题意

• 给定一个仅包含 ABC 的字符串 $s$。
• 要求 $s$ 的一个最长子序列，满足 ABC 出现次数相同，且相邻字符不同。
• $|s| \le 10^6$。

题解

考虑将 $s$ 中相邻的相同字符缩成一个，这显然不影响答案。

记 $s$ 中 A,B,C 的出现次数分别为 $c_A,c_B,c_C$，不妨设 $c_A \le c_B \le c_C$。

将 A 看作分隔符，则将当前串分成了 $c_A + 1$ 段，每段只有 B,c。记 B,C 都有的段数为 $c_1$，单个 B 的段数为 $c_2$，单个 C 的段数为 $c_3$，若 $c_1 + c_2 \ge c_3$，可以构造取到答案的上界 $3c_A$：

1. 每次找到一个 C，满足删去它之后串内相邻字符依然不相同，删去它，直到 $c_B = c_C$。
2. 每次找到相邻的 B 和 C，满足删去它们之后串内相邻字符依然不相同，删去它们，直到 $c_A = c_B = c_C$。

若 $c_1 + c_2 < c_3$，每次找到单个 C 段，删去 C 以及 $0/1$ 个 A（优先考虑首尾，这样不用删 A），直到 $c_1+c_2 \ge c_3$，然后使用上面的构造方法即可。

使用链表维护，时间复杂度 $\mathcal O(n)$；使用 set 维护，时间复杂度 $\mathcal O(n \log n)$。

代码

const int N = 1e6 + 7;
int n, t[3];
char s[N], c[3];
set<int> p;

inline void del(int x, int c) {
	p.erase(x), --t[c];
}

int main() {
	rds(s, n);
	for (int i = 0; i < 3; i++) c[i] = 'A' + i;
	for (int i = 1; i <= n; i++)
		if (s[i] != s[i+1]) p.insert(i), ++t[s[i]-'A'];
	if (t[1] > t[2]) swap(t[1], t[2]), swap(c[1], c[2]);
	if (t[0] > t[1]) swap(t[0], t[1]), swap(c[0], c[1]);
	if (t[1] > t[2]) swap(t[1], t[2]), swap(c[1], c[2]);
	int c1 = 0, c2 = 0, c3 = 0, o1 = 0, o2 = 0;
	for (int x : p)
		if (s[x] == c[0]) {
			if (o1 && o2) ++c1;
			else if (o1) ++c2;
			else if (o2) ++c3;
			o1 = o2 = 0;
		} else if (s[x] == c[1]) o1 = 1;
		else o2 = 1;
	if (o1 && o2) ++c1;
	else if (o1) ++c2;
	else if (o2) ++c3;
	o1 = o2 = 0;
	if (c1 + c2 < c3) {
		if (s[*p.begin()] == c[2] && s[*++p.begin()] == c[0])
			del(*p.begin(), 2), --c3;
		if (c1 + c2 < c3) {
			if (s[*--p.end()] == c[2] && s[*--(--p.end())] == c[0])
				del(*--p.end(), 2), --c3;
			if (c1 + c2 < c3)
				for (int x : p)
					if (s[x] == c[0]) {
						if (o1 && o2) {
							del(o1, 0), del(o2, 2);
							o1 = x, o2 = 0;
							if (c1 + c2 == --c3) break;
						} else o1 = x, o2 = 0;
					} else if (s[x] == c[1]) o1 = 0, o2 = 0;
					else if (s[x] == c[2]) {
						if (o1 && !o2) o2 = x;
						else o1 = 0, o2 = 0;
					}
		}
	}
	if (t[1] < t[2]) {
		auto it = p.begin();
		while (it != p.end()) {
			auto itl = it, itr = it;
			if (s[*it] != c[2] || !(it == p.begin() || ++itr == p.end() || s[*--itl] != s[*itr])) {
				++it;
				continue;
			}
			del(*it++, 2);
			if (t[1] == t[2]) break;
		}
	}
	if (t[0] < t[1]) {
		auto it = p.begin();
		while (it != p.end()) {
			auto itl = it, itr = it, itrr = it;
			if (s[*it] == c[0] || ++itr == p.end() || s[*itr] == c[0] || s[*it] == s[*itr] || !(it == p.begin() || (itrr = itr, ++itrr) == p.end() || s[*--itl] != s[*itrr])) {
				++it;
				continue;
			}
			int x = s[*it] == c[1] ? 1 : 2, y = x == 1 ? 2 : 1;
			del(*it++, x), del(*it++, y);
			if (t[0] == t[1]) break;
		}
	}
	for (int x : p) printc(s[x]);
	return 0;
}

Square Constraints

题意

• 给定 $n$，求满足以下条件的 $0 \sim 2n-1$ 的排列 $p_{0\dots2n-1}$ 的个数。
  • 对于 $i \in [0,2n-1]$，满足 $n^2 \le i^2 + p_i^2 \le (2n)^2$。
• $n \le 250$，答案对 $P$ 取模。

题解

本质上，这依然是一个 $p_i \in [l_i,r_i]$ 的计数问题。

在没有下界限制的情况下，我们有个经典的做法是，将 $r_i$ 从小到大排序，这样当考虑第 $i$ 个数时，由于前面的 $r$ 都 $\le r_i$，因此无论前面怎么填，第 $i$ 个数的方案数都为 $r_i + 1 - i$（编号从 $0$ 开始），总方案数为 $\prod_{i=0}^{2n-1} r_i + 1 - i$。

在有下界时，我们可以考虑容斥，设 $f(k)$ 表示至少有 $k$ 个数小于下界时的方案数，则答案为 $\sum_{k=0}^{2n} (-1)^kf(k)$。

回到本题，题意的约束条件比较奇怪，考虑将它变得直观一点就是：

• 以原点为圆心在第一象限画两个半径分别为 $n,2n$ 的 $1/4$ 圆，对于 $i \in [0,2n-1]$，$(i,p_i)$ 必须在这两个 $1/4$ 圆之间（含圆上）。

于是我们有 $l_{n\dots2n-1} = 0$，因此只有对于 $i \in [0,n-1]$ 才有可能 $p_i < l_i$。

考虑枚举若干个 $i$ 要求 $p_i < l_i$，则此时相当于没有下界限制的计数，用上面的方法即可。

然而显然我们不能枚举每个 $i \in [0, n-1]$ 是否要求 $p_i < l_i$，有没有什么办法可以直接计算出 $f(k)$ 呢？

注意到对 $r$ 排序后求 $\prod_{i=0}^{2n-1} r_i + 1 - i$，本质上相当于对于每个 $i$，其贡献为，$\le r_i$ 的数的个数（$r_i+1$ 个），减去比 $r_i$ 小的限制的个数（$r_i$ 相同则钦定一个顺序）。

考虑：

• 对于 $i \in[0,n-1]$，以 $l_i - 1$ 为第一关键字，$r_i$ 为第二关键字。
• 对于 $i \in [n, 2n-1]$，以 $r_i$ 为第一关键字，$l_i-1$ 为第二关键字。

排序，设排序后的序列为 $q_{1\dots2n}$（注意，这里是从 $1$ 开始编号，也只有这里从 $1$ 开始编号）。

考虑 DP，设 $f_{i,j}$ 表示对于 $q_{1\dots i}$ 均满足 $\le r$，且其中有 $j$ 项满足 $< l$ 时对答案的贡献。

设 $q_{1\dots i-1}$ 中 $\in[0,n-1]$ 的有 $t$ 个，考虑如何转移，观察上面那个直观的限制图：

• 若 $q_i \in [0,n-1]$，且只要求 $p_{q_i} \le r_{q_i}$，其贡献为：
  $\le r_{q_i}$ 的数（$r_{q_i} + 1$ 个），减去比 $r_{q_i}$ 小的限制的个数：

  • 所有 $i \in [n,2n-1]$ 的 $r_i$（$n$ 个）
  • $q_{1\dots i-1}$ 中 $\in[0,n-1]$ 的 $q$（$t$ 个）
  • $q_{i+1\dots 2n-1}$ 中 $\in [0,n-1]$ 且要求 $<l$ 的 $q$（$k-j$ 个）

  转移：$f_{i,j}\leftarrow f_{i-1,j} \cdot (r_{q_i} + 1 - (n + t + k - j))$。

• 若 $q_i \in [0,n-1]$，且要求 $p_{q_i} < l_{q_i}$，其贡献为：
  $< l_{q_i}$ 的数（$l_{q_i}$ 个），减去比 $l_{q_i}-1$ 小的限制的个数：

  • $q_{1\dots i-1}$ 中 $\in [n,2n-1]$ 的 $q$（$i-1-t$ 个）
  • $q_{1\dots i-1}$ 中 $\in[0,n-1]$ 且要求 $<l$ 的 $q$（$j-1$ 个）

  转移：$f_{i,j} \leftarrow f_{i-1,j-1} \cdot (l_{q_i} - (i-1-t+(j-1)))$。

• 若 $q_{n,2n-1}$，其贡献为：
  $\le r_{q_i}$ 的数（$r_{q_i} + 1$ 个），减去比 $r_{q_i}$ 小的限制的个数：

  • $q_{1\dots i-1}$ 中 $\in [n,2n-1]$ 的 $q$（$i-1-t$ 个）
  • $q_{1\dots i-1}$ 中 $\in[0,n-1]$ 且要求 $<l$ 的 $q$（$j$ 个）

  转移：$f_{i,j} \leftarrow f_{i-1,j} \cdot (r_{q_i} + 1 - (i-1-t+j))$。

时间复杂度 $\mathcal O(n^3)$。

代码

const int N = 507;
int n, l[N], r[N], q[N];
modint f[N][N], ans;

inline modint calc(int k) {
	f[0][0] = 1;
	for (int i = 1, t = 0; i <= n << 1; t += q[i] < n, i++)
		for (int j = 0; j <= min(min(i, k), t + (q[i] < n)); j++)
			if (q[i] < n) f[i][j] = f[i-1][j] * (r[q[i]] + 1 - (n + t + k - j)) + (j ? f[i-1][j-1] * (l[q[i]] - (i - 1 - t + (j - 1))) : 0);
			else f[i][j] = f[i-1][j] * (r[q[i]] + 1 - (i - 1 - t + j));
	return f[n<<1][k];
}

int main() {
	rd(n, P);
	for (int i = 0; i < n << 1; i++)
		l[i] = max(0, (int)ceil(sqrt(n * n - i * i))),
		r[i] = min(2 * n - 1, (int)floor(sqrt(4 * n * n - i * i))),
		q[i+1] = i;
	sort(q + 1, q + (n << 1 | 1), [&](int i, int j) {
		pi x = i < n ? mp(l[i] - 1, r[i]) : mp(r[i], l[i] - 1);
		pi y = j < n ? mp(l[j] - 1, r[j]) : mp(r[j], l[j] - 1);
		return x < y;
	});
	for (int i = 0; i <= n; i++)
		if (i & 1) ans -= calc(i);
		else ans += calc(i);
	print(ans);
	return 0;
}