AtCoder Grand Contest 040 题解

AtCoder Grand Contest 040

><

对于每个 <<...<>>...> 必然是两端 $0$，往中间 $+1$。

头尾特判一下。

const int N = 5e5 + 7;
int n;
char s[N];
ll ans;
vector<pair<char, int>> p;

int main() {
	rds(s, n);
	for (int i = 1, t = 1; i <= n; i++)
		if (i == n || s[i] != s[i+1]) p.pb(mp(s[i], t)), t = 1;
		else ++t;
	if (p.size() == 1u) return print(1ll * p[0].se * (p[0].se + 1) / 2), 0;
	if (p[0].fi == '>') ans += 1ll * p[0].se * (p[0].se + 1) / 2;
	if (p.back().fi == '<') ans += 1ll * p.back().se * (p.back().se + 1) / 2;
	for (ui i = 1; i < p.size(); i++)
		if (p[i].fi == '>') {
			int x = p[i-1].se, y = p[i].se;
			if (x < y) swap(x, y);
			ans += 1ll * x * (x + 1) / 2 + 1ll * y * (y - 1) / 2;
		}
	print(ans);
	return 0;
}

Two Contests

答案只有两种情况：

• 一个区间 + $n-1$ 个区间。
• 按 $l$ 排序之后，某个前缀一个集合，后缀一个集合。

const int N = 1e5 + 7;
int n, ans;
pi a[N];
int l[N], r[N];

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(a[i].fi, a[i].se);
	sort(a + 1, a + n + 1);
	l[0] = r[n+1] = 1e9;
	for (int i = 1; i <= n; i++) l[i] = min(a[i].se, l[i-1]);
	for (int i = n; i; i--) r[i] = min(a[i].se, r[i+1]);
	for (int i = 1; i <= n; i++)
		ans = max(ans, a[i].se - a[i].fi + 1 + max(0, min(l[i-1], r[i+1]) - a[n-(i==n)].fi + 1));
	for (int i = 1; i < n; i++)
		if (a[i].fi <= l[i] && a[n].fi <= r[i+1])
			ans = max(ans, l[i] - a[i].fi + 1 + r[i+1] - a[n].fi + 1);
	print(ans);
	return 0;
}

Neither AB nor BA

将偶数位上的 A 变成 B，B 变成 A，问题等价于不能删 AA 和 BB。

不删 AA 能把 A 删光当且仅当 A 的数量 $\le \frac n2$，B 同理。

于是用总数减去 A 超过 $\frac n2$ 的方案数 $\times 2$ 就是答案。

枚举 A 的个数，时间复杂度 $\mathcal O(n)$。

const int N = 1e7 + 7;
int n;
modint a[N], now;

int main() {
	rd(n), init(n);
	a[0] = 1;
	for (int i = 1; i <= n; i++) a[i] = a[i-1] * 2;
	for (int i = n / 2 + 1; i <= n; i++) now += binom(n, i) * a[n-i];
	print(((modint)3 ^ n) - 2 * now);
	return 0;
}

Balance Beam

首先对于一个排列，合法的起点范围是一段前缀，所以目标就是相当于最大化前缀的右端点。

考虑借助图象，设 $a_i$ 之和为 $s_a$，$b_i$ 之和为 $s_b$，建立时间关于位移的折线图，则形成的是两条从 $(0,0)$ 开始分别到 $(n,s_a),(n,s_b)$ 的折线 $A,B$。

将折线 $B$ 向下平移到恰好与 $A$ 有交点的最低处，此时 $B$ 与 $x$ 轴的交点横坐标就是起点的位置 $(x,0)$。

考虑这样一条折线：从 $(x,0)$ 开始沿着 $B$ 向上走，与 $A$ 相交之后，沿着 $A$ 走到 $(n,s_a)$。

考虑枚举 $(x,0)$ 所在的段 $k$，则目标就是尽可能最大化 $k$ 右侧折线的斜率。显然对于段 $i$ 的斜率为 $\max(a_i, b_i)$，因此按照 $\max(a_i,b_i)$ 从大到小排序之后在 $k$ 右侧的折线一定是一个前缀。

最后计算一下 $k$ 中有多少部分需要放到 $x$ 的后面，对所有答案取 $\max$ 即可。

const int N = 1e5 + 7;
int n, k;
pi p[N];
ll s, ss;

int main() {
	rd(n);
	for (int i = 1; i <= n; i++)
		rd(p[i].fi, p[i].se), s += p[i].fi, p[i].fi = max(p[i].fi, p[i].se);
	sort(p + 1, p + n + 1, [&](pi x, pi y) { return x.fi > y.fi; });
	for (int i = 1; i <= n; i++)
		if ((ss += p[i].fi) >= s) {
			k = i;
			break;
		}
	ll P = 1, Q = 1;
	for (int i = 1; i <= n; i++) {
		ll w = s - (ss - p[min(i,k)].fi);
		if (w <= p[i].se && w * Q < P * p[i].se) P = w, Q = p[i].se;
	}
	P = Q - P + (n - k) * Q, Q *= n;
	ll g = __gcd(P, Q);
	print(P / g, Q / g);
	return 0;
}

Prefix Suffix Addition

设通过操作 $1$ 使第 $i$ 个数增加了 $c_i$，有 $0 \le c_i \le a_i$，操作次数为 $\sum_{i=1}^n ([c_i > c_{i+1}] + [a_i - c_i > a_{i-1} - c_{i-1}])$。

考虑 DP，设 $f_{i,j}$ 表示 $c_i = j$ 时前 $i$ 个数的最小操作次数，有转移 $f_{i+1,j^\prime} \leftarrow f_{i,j} + [j > j^\prime] + [a_{i+1} - j^\prime > a_i - j]$，时间复杂度 $\mathcal O(nw^2)$。

注意到对于 $f_{i,j}$ 相同的状态，只用保留 $j$ 最小的一个。同时若 $f_{i,j^\prime} > f_{i,j}+1$，那么 $f_{i,j^\prime}$ 也没用，于是状态数压缩到了 $\mathcal O(n)$，时间复杂度 $\mathcal O(n)$。

const int N = 2e5 + 7;
int n, a[N];
map<int, int> f[N];

inline void upd(int i, int j, int k) {
	if (f[i].find(j) == f[i].end()) f[i][j] = k;
	else f[i][j] = min(f[i][j], k);
}

int main() {
	rd(n), rda(a, n);
	f[0][0] = 0;
	for (int i = 0; i <= n; i++) {
		int x = 1e9;
		for (pi o : f[i]) x = min(x, o.se);
		auto it = f[i].begin();
		bool ok0 = 0, ok1 = 0;
		while (it != f[i].end())
			if ((it -> se) > x + 1) f[i].erase(it++);
			else if ((it -> se) == x + 1) {
				if (ok1) f[i].erase(it++);
				else ok1 = 1, it++;
			} else {
				if (ok0) f[i].erase(it++);
				else ok0 = 1, it++;
			}
		for (pi o : f[i]) {
			int j = o.fi, x = o.se;
			int p = j, q = a[i+1] - a[i] + j;
			if (p > q) swap(p, q);
			if (p > 0) upd(i + 1, 0, x + 2);
			if (p != q && q > 0 && p <= a[i+1]) upd(i + 1, max(p, 0), x + 1);
			if (q >= 0 && q <= a[i+1]) upd(i + 1, max(q, 0), x);
		}
	}
	print(f[n+1][0]);
	return 0;
}

Two Pieces

咕