Codeforces Round 1099 (Div. 2) 构造|贪心|图论|还原数组

Maxwell_Newton

94人浏览 · 2026-05-22 18:46:51

Maxwell_Newton · 2026-05-22 18:46:51 发布

A

构造

使用 $[1 ， 2 n]$ 的元素构成一个长度 $n$ 的数组，，然后求相邻元素和，得到一个长度 $n - 1$ 的数组，接到原数组后面。要求操作后数组不含重复元素

一个比较巧妙的构造是，注意到如果我们等差数列构造，等差数列是很容易出现相邻两项和等于后面的项的，所以考虑插空，在奇偶位置分别插入两个等差数列。

这个的一个构造方案是，奇数位 $a_i=i$ ，偶数位 $a_i=n+i$ ，这样相邻元素和是一个 $n + 3, n + 5..$ 的等差数列，而我们插入的是 $1, 3, 5...$ 和 $n + 2, n + 4, n + 6...$ 的两个等差数列，刚好错开了。

void solve() {
	int n;
	cin >> n;

	rep(i, 1, n) {
		if (i % 2) {
			cout << i << ' ';
		} else {
			cout << n + i << ' ';
		}
	}
	cout << '\n';
}

但这其实做麻烦了，这是 $a$ 题，大道至简，不该有太复杂的做法。注意到限制使用的元素不超过 $2 n$ ，但是相邻元素和可以超过 $2 n$ ，那么我们让相邻元素和都大于 $2 n$ ，不就肯定和原始序列不重复了吗？想让相邻元素和都大于 $2 n$ ，那么每个元素都至少是 $n + 1$ ，还要不重复，那么就 $[n + 1, 2 n]$ 填进去就好，正好 $n$ 个

void solve() {
	int n;
	cin >> n;
	for (int i = 2 * n; i > n; i--) {
		cout << i << ' ';
	}
	cout << '\n';

}

B

贪心/dp

在一个序列中选择一个子序列，全部加上一个正整数 $k$ ，问能否把序列变成非降序？

首先是应该加多少？至少要加 $max(a_i-a_{i+1})$ ，也就是最大的下降跨度。这样才能在每一个局部下降的地方改成非降序。但这就够了吗？

可以大胆猜想，这就够了。因为，这个 $k$ ，已经够每个下降的位置变成平的了，如果还有下降，说明 $ai>ai+1a_i\gt a_{i+1}$ 这样的位置， $a_i,a_{i+1}$ 都被选入增加的子序列了，都加了 $k$ ，那此时不论 $k$ 多大都没用的，两个位置同步加，永远保持降序关系。

所以可以认为加的值就是 $k=\max(a_i-a_{i+1})$ 。操作固定了，问能否升序，显然可以直接贪心，这是常见思路，需要增加的地方（也就是降序的地方）就加，如果增加了，还是降序的，肯定就不能排序了，直接退出。

void solve() {
	int n;
	cin >> n;
	vi a(n + 1);
	rep(i, 1, n) {
		cin >> a[i];
	}

	int k = 0;
	rep(i, 1, n - 1) {
		k = max(k, a[i] - a[i + 1]);
	}

	if (k == 0) {
		cout << "yes\n";
		return;
	}

	int f = 0;
	rep(i, 2, n) {
		if (a[i] < a[i - 1]) {
			a[i] += k;
		}
		if (a[i] < a[i - 1]) {
			cout << "no\n";
			return;
		}
	}

	cout << "yes\n";

}

前面是直接在原数组上操作的思路，也可以不在原数组上直接操作，而是记录前面的位置是否增加了，然后同样也是看，这个位置增加后能否超过前一位。

如果前一位 $a_{i-1}$ 比原始比当前 $a_i$ 大，也就是存在降序，且 $a_{i-1}$ 已经被选中要加了，那么肯定就无解了，因为 $a_i$ 即使也加，也还是小于 $a_{i-1}$
如果 $a_i$ 比 $a_{i-1}$ 至少大 $k$ ，不论前一位有没有加，都还是升序的，那么此时 $a_i$ 加不加都行，贪心的想，类似 $L I S$ 为例让后面更可能升序，结尾应该尽量小，所以这里选择不加。

void solve() {
	int n;
	cin >> n;
	vi a(n + 1);
	rep(i, 1, n) {
		cin >> a[i];
	}

	int k = 0;
	rep(i, 1, n - 1) {
		k = max(k, a[i] - a[i + 1]);
	}

	if (k == 0) {
		cout << "yes\n";
		return;
	}

	int f = 0;
	//f记录之前的结尾，在最好情况下是否 +k
	rep(i, 2, n) {
		if (a[i] < a[i - 1]) {
			if (f) {
				cout << "no\n";
				return;
			} else {
				f = 1;
			}
		} else if (f && a[i] >= a[i - 1] + k) {
			f = 0;
		}
	}

	cout << "yes\n";

}

能贪，其实也能 $d p$ ，只是对于 $d i v 2 b$ 来说有点大炮打蚊子了。

第二种贪心的时候，需要考虑前一个位置是否加 $k$ 了，根据贪心策略规定，在能不加 $k$ 的情况下都不加。如果想不到这点，可以用一个状态机 $d p$ ， $f (i, 0/1)$ 表示前缀 $[1, i]$ 升序，且最后一个位置 $i$ 是否加 $k$ ，的方案是否存在。

转移类似，如果 $ai−1>aia_{i-1}\gt a_i$ ，必须是 $i - 1$ 不加， $i$ 加。如果 $ai−1<aia_{i-1}\lt a_i$ ，但相差不到 $k$ ，如果 $i - 1$ 加了， $i$ 就不能加。如果 $i - 1$ 没加， $i$ 加不加都行。如果升序，且相差超过 $k$ ，不论前一个加不加，当前加不加都可以。

void solve() {
	int n;
	cin >> n;
	vi a(n + 1);
	rep(i, 1, n) {
		cin >> a[i];
	}

	int k = 0;
	rep(i, 1, n - 1) {
		k = max(k, a[i] - a[i + 1]);
	}

	if (k == 0) {
		cout << "YES\n";
		return;
	}

	vvi f(n + 1, vi(2));
	//f(i,0/1)表示能否前i个有序，且第i个是/否被选中
	f[1][0] = f[1][1] = 1;
	rep(i, 2, n) {
		if (a[i - 1] > a[i]) {
			f[i][1] = f[i - 1][0];
		} else {
			if (a[i] - a[i - 1] < k) {
				f[i][1] = f[i - 1][0] | f[i - 1][1];
				f[i][0] = f[i - 1][0];
			} else {
				f[i][1] = f[i][0] = f[i - 1][0] | f[i - 1][1];
			}
		}
	}

	if (f[n][1] || f[n][0]) {
		cout << "YES\n";
	} else {
		cout << "NO\n";
	}
}

C

图论结论模拟

一个序列，每次可以选一个位置，如果是奇数，加一，如果是偶数，除二。问至少操作多少次，把整个序列变成全都相同？

一个比较显然的结论是，每个数在整个操作下，最终会变成 $1$ ，并且在变成 $1$ 之前，执行的操作次数是 $O(log⁡V)O(\log V)$ 的，最多大约60次。

并且这里不存在随机性，每个数一直操作，产生的序列是完全确定的，这个序列最后会进入 $2, 1, 2, 1...$ 的循环。

这样，可以把数看成点，这个序列看成图上的一条链，最后进入 $2, 1$ 构成的环，多个数，构成的是一个 $2, 1$ 为中心的基环树。问的这个树上选一个点，其他所有点到这个点距离最短是多少？

由于 $2, 1$ 都在环上，可以相互转换，所以最后都变成 $1, 2$ 都可以，不妨设都变成 $1$ ，那么把每个元素，一直操作，直到变成 $1$ ，得到的所有序列，计算最长公共后缀，这个后缀开头元素，就是想让操作次数最少，应该变成的元素，每个序列长度 $O(log⁡V)O(\log V)$ ， $n$ 个序列一块求最长公共后缀，暴力做复杂度也只有 $O(nlog⁡V)O(n\log V)$ 。

如果以 $2$ 作为序列结尾，也同理，但答案可能不同，分别求一下取最值

void solve() {
	int n;
	cin >> n;
	vi a(n + 1);
	rep(i, 1, n) {
		cin >> a[i];
	}

	auto cal = [&](int v)->int{
		int tot = 0;
		vvi b(n + 1);
		rep(i, 1, n) {
			vi t;
			int x = a[i];
			while (x != v) {
				t.push_back(x);
				if (x % 2)x++;
				else x >>= 1;
			}
			t.push_back(x);
			tot += t.size();

			ranges::reverse(t);
			b[i] = t;
		}

		rep(i, 1, 100) {
			set<int>s;
			bool f = 0;
			rep(j, 1, n) {
				if (b[j].size() < i) {
					f = 1;
					break;
				} else {
					s.insert(b[j][i - 1]);
				}
			}
			if (f || s.size() > 1) {
				break;
			}
			tot -= n;
		}
		return tot;
	};

	cout << min(cal(1), cal(2)) << '\n';
}

另一个更暴力的做法是，考虑我们前面的图论转化，问题等价于，求每个点，到所有初始元素的距离之和的最值。那么可以在计算每个初始元素的序列时，维护它到每个点的距离。

这样计算完所有序列，每个点作为终点的答案也算好了。这样做的话，由于值域很大，需要用 $ma p$ 存每个点的答案， $ma p$ 里一共 $O(nlog⁡V)O(n\log V)$ 个点，每次插入复杂度 $O(log⁡(nlog⁡V))O(\log(n\log V))$ ，一共插入 $O(nlog⁡n)O(n\log n)$ 次。复杂度还是很大的，需要卡常才能过，比如换成哈希表。

这个方法实现时，需要注意，即使一个元素初始就是 $1$ 了，它也可以移动到 $2$ ，需要更新它到 $2$ 的距离。并且，一个点，只有全部 $n$ 个点都能到达，才能作为候选答案，所以不止需要统计每个点到初始元素距离和，还要统计这个点有多少个初始元素可以到达。

void solve() {
	int n;
	cin >> n;
	vi a(n + 1);
	rep(i, 1, n) {
		cin >> a[i];
	}

	unordered_map<int, pii>mp;

	rep(i, 1, n) {
		int x = a[i];
		if (x == 1) {
			mp[2].fi++;
			mp[2].se++;

			mp[1].fi++;
		} else {
			int d = 0;
			while (x != 1) {
				mp[x].fi++;
				mp[x].se += d++;
				if (x % 2)x++;
				else x >>= 1;
			}
			mp[x].fi++;
			mp[x].se += d;
		}
	}

	int ans = inf;
	for (auto &[k, v] : mp) {
		if (v.fi == n) {
			ans = min(ans, v.se);
		}
	}

	cout << ans << '\n';


}

上述做法，有一个优化点：既然每个点只有全部 $n$ 个点都能到，才能作为候选答案，那么任选一个元素，操作形成的序列，终点肯定也在这些点中，所以只用随机选一个序列，统计序列上的点，到达所有初始元素的距离，这样就把统计的点数降低到了 $O(log⁡V)O(\log V)$ ，这很小，用哈希表的话，基本没有哈希碰撞，可以视为 $O (1)$ 插入，查询。那么再算上操作次数，整体复杂度也只有 $O(nlog⁡V)O(n\log V)$ ，跑得很快。

实测比前一个 $O(nlog⁡V)O(n\log V)$ 个点快十倍左右，这个才是正解，不需要担心卡常。
在这里插入图片描述
比前面的求最长公共后缀也快一倍左右快

void solve() {
	int n;
	cin >> n;
	vi a(n + 1);
	rep(i, 1, n) {
		cin >> a[i];
	}

	unordered_map<int, pii>mp;

	int x = a[1];
	if (x == 1) {
		mp[2].fi++;
		mp[2].se++;

		mp[1].fi++;
	} else {
		int d = 0;
		while (x != 1) {
			mp[x].fi++;
			mp[x].se += d++;
			if (x % 2)x++;
			else x >>= 1;
		}
		mp[x].fi++;
		mp[x].se += d;
	}

	rep(i, 2, n) {
		int x = a[i];
		if (x == 1) {
			mp[2].fi++;
			mp[2].se++;

			mp[1].fi++;
		} else {
			int d = 0;
			while (x != 1) {
				if (mp.count(x)) {
					mp[x].fi++;
					mp[x].se += d;
				}
				d++;
				if (x % 2)x++;
				else x >>= 1;
			}
			mp[x].fi++;
			mp[x].se += d;
		}
	}

	int ans = inf;
	for (auto &[k, v] : mp) {
		if (v.fi == n) {
			ans = min(ans, v.se);
		}
	}

	cout << ans << '\n';


}

D

思维维护合法区间

一个初始数组 $a$ ， $b$ 是 $a$ 的前缀和， $c$ 是 $b$ 的前缀 $max⁡\max$ ,现在给出 $c$ ，和部分缺失的 $a$ 。问能否还原出一个合法的 $a$ ？

这种给出前缀和，前缀 $max⁡\max$ ，还原原始数组的问题，一个经典做法是，维护每个位置的可能值域，如果每个位置的值域最终都没有矛盾，则可以在区间内任取，然后推出整个原始数组。

具体就是：

如果 $c_i=c_{i-1}$ ， $b_i$ 的取值限制是只要不超过 $b_i$ 就行
如果 $ci>ci−1c_i\gt c_{i-1}$ ， $b_i$ 就是前缀最大， $b_i=c_i$ ，值域直接缩到一个点。
另外，如果 $s_i=1$ ，也就是 $a_i$ 这个位置的值是准确的，那么 $b_i$ 的取值区间，至少是 $b_{i-1}$ 的区间整体加 $a_i$ 。
第三点和前两点的约束要同时生效，也就是把区间取交集。
$c_1=b_1=a_1$ 一定成立，递推初始状态可以直接确定。

这样可以推出每个位置的取值范围，检查无矛盾，则有解。

具体构造方案，考虑递推计算， $b_n$ 的值可以直接在区间内任选，中间的值，假设 $b_{i+1}$ 已经确定， $b_i$ 的值要在 $l_i,r_i]$ 内取，并且如果 $s_{i+1}=1$ ，也就是 $a_{i+1}$ 是确定的，那么 $b_i=b_{i+1}-a_{i+1}$ 一定成立，没有选择余地，必须是这个值。如果没有这个严格约束，可以在 $l_i,r_i]$ 任取，直接取 $r_i$ 即可。

还原出 $b$ 后差分即可得到 $a$

void solve() {
	int n;
	cin >> n;

	string s;
	cin >> s;
	vi a(n + 1), c(n + 1);
	rep(i, 1, n) {
		cin >> a[i];
	}

	rep(i, 1, n) {
		cin >> c[i];
	}

	vector<pii>lim(n + 1);

	rep(i, 2, n) {
		if (c[i] < c[i - 1]) {
			cout << "no\n";
			return;
		}
	}

	if (s[0] == '1' && a[1] != c[1]) {
		cout << "no\n";
		return;
	}

	lim[1].fi = lim[1].se = c[1];

	rep(i, 2, n) {
		int l, r;
		if (c[i] == c[i - 1]) {
			l = -inf;
			r = c[i];
		} else {
			l = r = c[i];
		}

		if (s[i - 1] == '1') {
			lim[i].fi = max(lim[i - 1].fi + a[i], l);
			lim[i].se = min(lim[i - 1].se + a[i], r);
		} else {
			lim[i].fi = l;
			lim[i].se = r;
		}
	}

	vi b(n + 1);
	b[n] = lim[n].se;
	rep1(i, n, 1) {
		if (lim[i].fi > lim[i].se) {
			cout << "no\n";
			return;
		} else {
			if (s[i - 1] == '1') {
				b[i - 1] = b[i] - a[i];
			} else {
				b[i - 1] = lim[i - 1].se;
			}
		}
	}

	vi ans(n + 1);
	rep(i, 1, n) {
		ans[i] = b[i] - b[i - 1];
	}
	cout << "yes\n";
	rep(i, 1, n) {
		cout << ans[i] << ' ';
	}
	cout << '\n';

}

赛时没想到这个简洁的做法，用的是另一个略复杂的做法。考虑每一段 $s_i=1$ 的连续段，假设这一段最左侧是 $r oo t$ ，这一段的相对起伏是完全确定的，唯一不确定的只有 $r oo t$ 的取值，随着 $r oo t$ 取值的改变，这一段可以上下平移。

这一段的每个点，都对 $r oo t$ 的取值能产生一个约束，这些约束如果没有矛盾，则可以确定 $r oo t$ 的取值。

一段内的点，对 $r oo t$ 的约束是：

如果 $ci<ci−1c_i\lt c_{i-1}$ ，那么 $c_i=b_i$ 是确定的，加上这一段都是连续的 $s_i=1$ ，也就是 $a_i$ 的值都是确定的，那么从 $r oo t$ 到 $i$ ，这一段的 $a_i$ 的和 $s u m$ 也是确定的，所以 $b_{root}=c_i-sum$ 也是确定的。如果这样唯一确定的 $r oo t$ 值有多个，则必须全都相等，否则矛盾
如果 $c_i=c_{i-1}$ ，那么 $bi≤cib_i \le c_i$ ，对 $r oo t$ 的约束只有 $≤ci−sum\le c_i-sum$ ，确定了一个上界，这些上界应该同时成立，取 $min⁡\min$ ，并且上界不能和前面唯一确定的值冲突

如果没有冲突，则有解。构造时，对于每一个连续的 $s_i=1$ 段，只需要确定 $r oo t$ 即可全部确定具体值， $r oo t$ 如果有唯一确定值，就用这个值，否则只有一个上界，直接取上界。然后根据确定的 $a_i$ ，累加前缀和，计算出其它 $b_i$ 。

void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	s = ' ' + s;

	vi a(n + 1);
	rep(i, 1, n) {
		cin >> a[i];
	}

	vi c(n + 1);
	rep(i, 1, n) {
		cin >> c[i];
	}

	rep(i, 2, n) {
		if (c[i] < c[i - 1]) {
			cout << "no\n";
			return;
		}
	}

	vi rt(n + 1), sum(n + 1);
	rep(i, 1, n) {
		if (s[i] == '1') {
			rt[i] = rt[i - 1];
			sum[i] = sum[i - 1] + a[i];
		} else {
			rt[i] = i;
		}
	}

	vi mx(n + 1, inf);
	vi val(n + 1, inf);
	val[0] = mx[0] = 0;

	rep(i, 1, n) {
		int f = rt[i];
		mx[f] = min(mx[f], c[i] - sum[i]);

		if (i == 1 || c[i] > c[i - 1]) {
			if (val[f] != inf && val[f] != c[i] - sum[i]) {
				cout << "no\n";
				return;
			} else {
				val[f] = c[i] - sum[i];
			}
		}
	}

	vi b(n + 1);
	rep(i, 0, n) {
		if (rt[i] == i) {
			if (val[i] != inf) {
				if (val[i] > mx[i]) {
					cout << "no\n";
					return;
				} else {
					b[i] = val[i];
				}
			} else {
				b[i] = mx[i];
			}
		}
	}

	rep(i, 1, n) {
		b[i] = b[rt[i]] + sum[i];
	}

	vi ans(n + 1);
	rep(i, 1, n) {
		ans[i] = b[i] - b[i - 1];
	}

	cout << "yes\n";
	rep(i, 1, n) {
		cout << ans[i] << ' ';
	}
	cout << '\n';



}