mydcwfy's Blog

ARC Round#130

Posted on
Symbols count in article: 6.5k Reading time ≈ 14 mins.

顺风场，vp 的时候打到了 rk 27 左右，补题也还不算很困难。

A、B 略去。

C

题意：给定两个数位不包含 0 的数 $a, b$，要求重排后两个数的和的数位和最小。求重排后的 $a, b$。$a, b\leq 10 ^ {100000}$。

容易发现肯定是需要进位最多。进位有 3 个源头：

  1. 最低位满足两个数加起来 $\geq 10$。
  2. 从低位向高位一段区间，满足两个数加起来 $\geq 9$。
  3. $a, b$ 位数不同，假设 $b$ 更高，$b$ 从 $a$ 没有的位置开始有一段 9，且 $a$ 有的位置都产生了进位。

首先容易发现不管是 $\geq 10$ 还是 $\geq 9$，我们都是一种双指针的策略贪心选取合法匹配中最小的一组。第一种情况和其他情况不同，我们暴力枚举 $a, b$ 的最低位知多少，然后高位直接贪心匹配 1 和 8，2 和 7，3 和 6……不能匹配就把后面的 +1，继续匹配。

由贪心易得正确性。不同答案的合并直接判进位次数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int getsum(std::string cura, std::string curb)
{
	std::reverse(cura.begin(), cura.end());
	std::reverse(curb.begin(), curb.end());
	while (cura.size() < curb.size()) cura += '0';
	int cnt = 0;
	for (int i = 0, ls = 0; i < (int) curb.size(); ++ i)
		ls = cura[i] - '0' + curb[i] - '0' + ls >= 10, cnt += ls;
	return cnt;
}
 
void solve(int _a, int _b)
{
	// std::cout << "Solve " << _a << ' ' << _b << '\n';
	auto ta = cnta, tb = cntb;
	std::string cura, curb;
	for (int i = 9, j = 1; i; -- i)
	{
		while (j <= 9 && ta[i]) {
			if (i + j < 9) {
				++ j;
				continue;
			}
			int del = std::min(ta[i], tb[j]);
			// std::cout << i << ' ' << j << ' ' << del << '\n';
			cura += std::string(del, i | 48), curb += std::string(del, j | 48);
			ta[i] -= del, tb[j] -= del;
			if (!tb[j]) ++ j;
		}
	}
	for (int i = 9; i; -- i) cura += std::string(ta[i], i | 48);
	for (int i = 9; i; -- i) curb += std::string(tb[i], i | 48);
	std::reverse(cura.begin(), cura.end());
	std::reverse(curb.begin(), curb.end());
	cura.push_back(_a | 48), curb.push_back(_b | 48);
	// std::cout << cura << ' ' << curb << ' ' << getsum(cura, curb) << '\n';
	if (getsum(cura, curb) > getsum(resa, resb) || resa.empty()) resa = cura, resb = curb;
}
 
int main()
{
	std::cin >> a >> b;
	bool rev = false;
	if (a.size() > b.size()) std::swap(a, b), rev = true;
	for (char &c : a) cnta[c & 15] ++;
	for (char &c : b) cntb[c & 15] ++;
	for (int i = 1; i <= 9; ++ i)
		for (int j = 1; j <= 9; ++ j)
			if (cnta[i] && cntb[j]) {
				cnta[i] --, cntb[j] --;
				solve(i, j);
				cnta[i] ++, cntb[j] ++;
			}
	if (!rev) std::cout << resa << '\n' << resb << '\n';
	else std::cout << resb << '\n' << resa << '\n';
	return 0;
}

D

题意：要将 $[1, n]$ 的排列放入一个 $n$ 个点的树，每个点对应一个权值，使得每个点都是局部最小或最大（比相邻点都大 / 小），问有多少种方案，对 998244353 取模。$n\leq 3000$。

套路树形 DP + 背包。记录 $f(i, j, k)$ 表示 $i$ 所在子树内 $i$ 是局部最小值还是最大值（$k = 0$ 表示最小，$k = 1$ 表示最大），且 $i$ 在子树内的排名是 $j$。直接暴力合并，即可得到答案。

看似我们需要枚举 $u, v$ 在对应子树内的排名，是 $O(n ^ 3)$ 的，但是容易发现枚举的排名都是 $O(sz)$ 的。考虑每一对点对 $(x, y)$，他们都只会在 $lca$ 处枚举到，而他的代价和 $O(sz)$ 枚举的代价相同，于是原问题也是 $O(n ^ 2)$ 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
void dfs(int x, int fa = 0)
{
	sz[x] = 1, dp[x][0][1] = dp[x][1][1] = 1;
	for (int v : g[x])
	{
		if (v == fa) continue;
		dfs(v, x);
		static int tmp[N], sum[N];
		for (int i = 1; i <= sz[x] + sz[v]; ++ i) tmp[i] = 0;
		for (int i = 1; i <= sz[v] + 1; ++ i) sum[i] = 0;
		for (int i = sz[v]; i; -- i) adj(sum[i] = sum[i + 1] + dp[v][1][i] - Mod);
		for (int i = 1; i <= sz[x]; ++ i) // sz[x] - i
			for (int j = 0; j < sz[v]; ++ j) // sz[v] - j
				tmp[i + j] = (tmp[i + j] + (LL) dp[x][0][i] * sum[j + 1] % Mod * C(i + j - 1, i - 1)
					% Mod * C(sz[x] + sz[v] - i - j, sz[x] - i)) % Mod;
		for (int i = 1; i <= sz[x] + sz[v]; ++ i) dp[x][0][i] = tmp[i];
		
		for (int i = 1; i <= sz[x] + sz[v]; ++ i) tmp[i] = 0;
		for (int i = 1; i <= sz[v]; ++ i) sum[i] = 0;
		for (int i = 1; i <= sz[v]; ++ i)
			adj(sum[i] = sum[i - 1] + dp[v][0][i] - Mod);
		for (int i = 1; i <= sz[x]; ++ i)
			for (int j = 1; j <= sz[v]; ++ j)
				tmp[i + j] = (tmp[i + j] + (LL) dp[x][1][i] * sum[j] % Mod * C(i + j - 1, i - 1)
					% Mod * C(sz[x] + sz[v] - i - j, sz[x] - i)) % Mod;
		for (int i = 1; i <= sz[x] + sz[v]; ++ i) dp[x][1][i] = tmp[i];
		
		sz[x] += sz[v];
	}
}

int main()
{
	init();
	std::cin >> n;
	for (int i = 1, u, v; i < n; ++ i)
	{
		scanf("%d %d", &u, &v);
		g[u].push_back(v), g[v].push_back(u);
	}
	dfs(1);
	int res = 0;
	for (int i = 1; i <= n; ++ i) adj(res += dp[1][0][i] - Mod);
	for (int i = 1; i <= n; ++ i) adj(res += dp[1][1][i] - Mod);
	std::cout << res << std::endl;
	return 0;
}

E

题意：对一个正整数序列 $A$ 操作 $k$ 次，单次操作为把一个最小值 +1。最后得到一个长度为 $k$ 的序列 $id$，为每次 +1 的数的位置。现已知 $id$，求是否存在一个 $A$ 满足能得到 $id$，如果存在输出字典序最小的 $A$。$n, k\leq 3\times 10 ^ 5$。

和官方题解做法似乎不同，来自 jiangly 的代码。

首先有一个关键的性质：

结论：答案序列 $A$ 在操作过程中一定出现了一次所有数都相同的时候。

证明：首先考虑至少出现了一次的数。当操作完之后，所有数一定都满足任意数差都不超过 1，因为一旦出现这种情况，小的那个数一定会在大的那个数操作第一次前就和他靠近距离，最后一定差不超过 1。而最后几次操作一定是对着 $val + 1$ 去的（设最小值为 $val$），那么消完所有的 $val + 1$ 后，都是 $val$ 了。另外，对于没有操作的数，他们至少是 $val$，否则会被操作一次；另外 $> val$ 就不优了，因为 $=val$ 可以满足条件。

容易发现如果我们找到这个时候和这个时候所有数的权值，原序列很容易求出了。

尝试对原操作序列进行分段，使得每一段操作的数的最小值相同。容易发现一段一定不包含任何重复的数字，并且区间长度等于右端点前面出现不同数字的总和。那么可以得到结论中提到的位置就是倒数第二段的右端点，而权值就是前面段数 +1（减掉段数次后还得是正整数）。

考虑逐个计算以 $i$ 结尾的段数。维护一个 $mx$ 表示倒序扫描扫到第一个重复数字的位置。容易发现最后一段划分位置不能在 $mx$ 之前。另外，转移的时候肯定是从 $i - cnt$ 划分（如果合法）。

然后从最后的 $mx$ 向后扫描，看能否找到一个合法划分的，如果能的话，找一个段数最小的，段数相同肯定位置较大的更优。找到之后模拟即可。时间复杂度线性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main()
{
	std::cin >> n >> m;
	for (int i = 1; i <= m; ++ i) scanf("%d", id + i);
	for (int i = 1; i <= n; ++ i) cur[i] = -1;
	for (int i = 1; i <= m; ++ i)
		ls[i] = cur[id[i]], cur[id[i]] = i;
	
	int mx = 0;
	for (int i = 1, cnt = 0; i <= m; ++ i)
	{
		chkmax(mx, ls[i]), cnt += !~ls[i];
		if (mx + cnt > i) cov[i] = INF;
		else cov[i] = cov[i - cnt] + 1;
	}
	int fin = INF, pos = -1;
	for (int i = mx; i < m; ++ i)
		if (chkmin(fin, cov[i]), fin == cov[i]) pos = i;
	if (fin > INF / 2) return puts("-1"), 0;
	for (int i = 1; i <= n; ++ i) a[i] = fin + 1;
	for (int i = pos; i; -- i) -- a[id[i]];
	for (int i = 1; i <= n; ++ i) printf("%d ", a[i]);
	return 0;
}

F

题意：给出一个序列，令 $j = \dfrac{i + k}2$，可以把 $a_j\leftarrow \lfloor \dfrac{a_i + a_k}{2} \rfloor$，求任意操作之后得到的 $\sum a$ 的最小值。$n\leq 3\times 10 ^ 5, n\leq 10 ^ {12}$。

其实感觉很神秘的一个题目，其实似乎没有 E 难？

容易发现如果 $a_j > \dfrac{a_i + a_k}{2}$，我们操作一波之后其实变成了这样：

这样操作相当于把下凸的部分砍掉了，那么剩下的部分其实就是一个 $(i, a_i)$ 的上凸包不会被消灭。

如果是实数的话，这个题就做完了，直接计算新的这个点会落在那两个关键点之间，然后用斜率算算即可。求凸包可以直接单调栈做到线性。

问题就在于还有一个神秘的下取整。容易发现不同段之间其实还是没有影响，因为不可能把原来的关键点给弄没了的。主要就在于把区间内部的搞好。

大概目前看到的最简洁的做法是把区间内按照原来构造直接下取整的数组构造出来，差分后直接排序，再放回去前缀和。容易发现这个还是不影响段间的情况。

其实这么做的原因是由于负数除法的时候会向 0 取整，出一些锅，好像只有正数（相邻两个关键点变化量为正）时没有问题吧。没验证过，还不太清楚。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct Point {
	LL x, y;
	Point operator -(Point t) const { return {x - t.x, y - t.y}; }
	LL operator *(Point t) const { return x * t.y - y * t.x; }
} p[N];
int n, stk[N];
LL a[N], b[N], del[N];
 
int main()
{
	std::cin >> n;
	for (int i = 1; i <= n; ++ i) std::cin >> a[i];
	for (int i = 1; i <= n; ++ i) p[i] = {i, a[i]};
	int top = 0;
	for (int i = 1; i <= n; ++ i)
	{
		while (top > 1 && (p[stk[top]] - p[stk[top - 1]]) * (p[i] - p[stk[top - 1]]) <= 0)
			top --;
		stk[++ top] = i;
	}
	b[1] = a[1];
	for (int i = 1; i < top; ++ i)
		for (int j = stk[i] + 1; j <= stk[i + 1]; ++ j)
			b[j] = a[stk[i]] + (a[stk[i + 1]] - a[stk[i]]) * (j - stk[i]) / (stk[i + 1] - stk[i]);
	for (int i = 1; i < n; ++ i) del[i] = b[i + 1] - b[i];
	std::sort(del + 1, del + n);
	b[1] = a[1];
	for (int i = 1; i <= n; ++ i) b[i + 1] = b[i] + del[i];
	LL res = 0;
	for (int i = 1; i <= n; ++ i) res += b[i];
	std::cout << res << '\n';
	return 0;
}