[数据结构与算法]Codeforces Round #760 (Div. 3) 题解 完整A~G

A. Polycarp and Sums of Subsequences

题意

有数组$a$，由3个正整数组成。对于$a$的每个非空子序列，求子序列中的元素和，并按非递减的顺序存入数组$b$，显然$b$由7个正整数组成。现给定数组$b$，求数组$a$。

思路

不妨令$a=[x,y,z],x\le y\le z$，则 b = { x , y , z , x + y , y + z , z + x , x + y + z } b=\{x,y,z,x+y,y+z,z+x,x+y+z\} b={x,y,z,x+y,y+z,z+x,x+y+z}（并排序）。由于$x,y,z$都是正整数，我们不难想到$x,y\le z,x+y,y+z,z+x\le x+y+z$。因此$b$中前两项必然是$x,y$，最后一项必然是$x+y+z$。

时间复杂度

$$O(1)$$

AC代码

#include <bits/stdc++.h>

using namespace std;

int a[100];

void solve() {
	for (int i = 0; i < 7; ++i) {
		cin >> a[i];
	}
	cout << a[0] << ' ' << a[1] << ' ' << a[6] - a[0] - a[1] << '\n';
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);					//关同步，下同
	cout.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

B. Missing Bigram

题意

有一长为$n$字符串，由小写字母’a’和’b’组成，现在依次将相邻的字母（第1个和第2个，第2个和第3个，依次类推）组成字母对，并删掉其中一对字母对，其余的字母对按顺序给出，求可能的原字符串。（任意输出一种答案）

思路

假如不考虑删掉的那一对字母对，我们不难发现相邻字母对之间存在关系：前一字母对的后一个字母与后一字母对的前一个字母是相同的。因此，对于满足条件的相邻字母对，我们直接将其合并即可，否则，在这个位置一定删除了一个字母对，将其补上即可。如果整个字母对序列都处理完后仍没发现缺失，则我们可以在两端补上a或b中的任何一个字母（因为题目要求输出任何一种可行解），目的是为了补足字符串长度。

时间复杂度

$$O(n)$$

AC代码

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;		//第一对直接加上即可
	for (int i = 1; i < n - 2; ++i) {
		string ss;
		cin >> ss;
		if (s.back() == ss[0]) s += ss[1];	//没删除，连上后者即可
		else s += ss;				//删除了一对字母，都加上
	}
	if (s.length() != n) s += 'a';		//长度不足时补足
	cout << s << '\n';
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

C. Paint the Array

题意

现有一长度为$n$的正整数数组$a$，需要对其涂色。任选一正整数$d$，并将$a$中整除$d$的数涂成红色，否则涂成蓝色。问是否存在一个正整数$d$，使得涂色后数组中的相邻元素的颜色不相同。若存在，输出任一可行的$d$，若不存在，输出0。

思路

对题意作进一步的转化，我们会发现，题目要求我们选择一个正整数$d$，使得$a$中的奇数位置的元素都整除$d$，而偶数位置的元素都不被$d$整除（以下叙述建立在上述情况的假设之下），或是与之相反。

关于如何选择$d$：由于奇数位置都能整除$d$，那么$d$一定是奇数位置元素的公约数，而$d$中因子越多，越不容易被偶数位置的数整除，因此我们选择奇数位置元素的最大公约数。

由于$d$已经确定，我们只需对偶数位置逐一验证是否被$d$整除即可，若能满足条件则输出答案，若两种情况都不满足，说明无解，输出0。

时间复杂度

$$O(n{\log }_2{a}_i)$$

AC代码

#include <bits/stdc++.h>

using namespace std;

long long a[10000];

void solve() {
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	long long g[2] = {0, 0};
	for (int i = 0; i < n; ++i) {
		g[i & 1] = gcd(g[i & 1], a[i]);		//求奇偶位置的最大公约数
	}
	for (int i = 0; i < 2; ++i) {		//逐一验证可行性
		bool ok = true;
		for (int j = i ^ 1; j < n; j += 2) {
			if (a[j] % g[i] == 0) {
				ok = false;
				break;
			}
		}
		if (ok) {		//满足条件就输出
			cout << g[i] << '\n';
			return;
		}
	}
	cout << 0 << '\n';		//无解
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

D. Array and Operations

题意

现有一长度为$n$的正整数数组$a$，要求你进行恰好$k$次操作，每次操作可以选择$a$中任意两个元素$a_i$和$a_j$，并将$?\frac{a_i}{a_j}?$加入你的得分，然后删除这两个元素。完成$k$次操作之后，将剩余元素也加入你的得分，求你的最小得分。

思路

你的目标是使得分数尽可能的小，因此我们选择$a_i$和$a_j$之后，总有$0\le ?\frac{a_i}{a_j}?\le 1$。其次，我们一定选择最大的$2?k$个元素，因为如果我们放弃较大的某个数，而选择较小的某个数，我们最多能使得$?\frac{a_i}{a_j}?$减小1，而剩余的元素之和至少会增加1，这一定不优于我们刚才的选择。最后我们要尽可能的避免$?\frac{a_i}{a_j}?=1$的出现，也就是说需要把相同的元素尽可能的不组合在一起，将数组从大到小排序后，我们将$a_i$和$a_{i+k}$组成一对，并产生$?\frac{a_{i+k}}{a_i}?$，即是最优解。

时间复杂度

$$O(n{\log }_{2}n)$$

#include <bits/stdc++.h>

using namespace std;

long long a[10000];

void solve() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a, a + n, greater<int>());	//降序排序
	long long ans = 0;
	for (int i = 0; i < k; ++i) {
		ans += a[k + i] / a[i];		//最大的2k个元素相除
	}
	for (int i = k + k; i < n; ++i) {
		ans += a[i];		//其余元素直接加入结果中
	}
	cout << ans << '\n';
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

E. Singers’ Tour

题意

有$n$个城市$(1,2,3,\dots ,n)$按顺序环状排列（即城市$n$的下一个城市是城市1），每个城市有一个歌手，第$i$个城市的歌手会首先在城市$i$开一场时长为$a_i$的音乐会（$a_i$是正整数），然后前往下一个城市，每到一个新的城市他都会开音乐会，时长比上一个城市长$a_i$。所有歌手都开完音乐会之后，第$i$个城市的音乐会总时长为$b_i$。现已知所有$b_i$，求所有的$a_i$，或反馈无解。

思路

第一步，我们可以根据题目意思列方程：对第$i$个城市，$b_i=1?a_i+2?a_{i+1}+?+(n?1)?a_{i?2}+n?a_{i?1}$。

第二步，根据第一步的方程，求和：${\sum }_{i=1}^n{b}_i=({\sum }_{i=1}^{n}i)?({\sum }_{i=1}^n{a}_i)$。等式左边的每一项都已知，而右边的${\sum }_{i=1}^{n}i$，实际上根据等差数列求和公式可以转化为$\frac{n?(n+1)}{2}$。故可以解得${\sum }_{i=1}^n{a}_i=\frac{2{\sum }_{i=1}^n{b}_i}{n?(n+1)}$。

第三步，根据第一步的方程，作差：$b_i?b_{i?1}=a_1+a_2+?+(1?n)a_i+?+a_n=({\sum }_{i=1}^n{a}_i)?n?a_i$。解此方程得$a_i=\frac{\frac{2{\sum }_{i=1}^n{b}_i}{n?(n+1)}?(b_i?b_{i?1})}{n}$。

注意$a_i$是正整数，需要考虑整除问题和0与负数问题。

时间复杂度

$$O(n)$$

AC代码

#include <bits/stdc++.h>

using namespace std;

long long a[100000], b[100000];	//我代码中的变量和题目中的a,b意义恰好相反，需要注意

void solve() {
	int n;
	cin >> n;
	long long sum = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		sum += a[i];		//求和
	}
	if (sum % (n * (n + 1) / 2)) {	//不整除无解
		cout << "NO\n";
		return;
	}
	sum /= n * (n + 1) / 2;
	for (int i = 0; i < n; ++i) {
		long long d = sum - (a[i] - a[(i + n - 1) % n]);
		if (d % n || d <= 0) {	//不整除或答案不是正数无解
			cout << "NO\n";
			return;
		}
		b[i] = d / n;
	}
	cout << "YES\n";
	for (int i = 0; i < n; ++i) {
		cout << b[i] << ' ';
	}
	cout << '\n';
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

F. Reverse

题意

给定一个正整数$x$，允许进行若干次操作：将$x$转化为二进制形式，且不得含有前导零，在其末尾增加一个0或1，然后首尾对称翻转（不是翻转01，是翻转位置），去掉前导零，转化为十进制，替换原来的$x$。问经过若干次（可能0次）操作后，$x$能否变成$y$？

思路

由于翻转之前，二进制的首位一定是1，故翻转后末位一定是1。又由于翻转后去掉所有前导0，故翻转后首位也是1。对于一个首尾都是1的二进制数$x$来说，在其末尾增加一个0，然后翻转，得到的结果是$x$的翻转（记作$\bar{x}$）；如果在其末尾加一个1，然后翻转，则会得到$1\bar{x}$。进而推广可得，经过若干次操作，$x$可以变成$111..1x111..1$或$111..1\bar{x}111..1$，即左右侧会增加任意多个1（也可以是0个），这可以用归纳法证明。

此时会有一种个例，也就是第一次操作。由于一开始$x$的末尾可能有0，归纳法失效，需要单独讨论。记初始时$x=x^{\prime }000..0$，其中$x^{\prime }$的首尾都是1。如果在末尾加0，翻转后得到$\overline{x^{\prime }}$；如果在末尾加1，则翻转后会得到$1000..0\overline{x^{\prime }}$，也可以认为是$1\bar{x}$。

综合上述分析，最终可能得到的$y$一定是以下5种可能中的一种：

• $[111..1]x1[111..1]$
• $[111..1]1\bar{x}[111..1]$
• $[111..1]x^{\prime }[111..1]$
• $[111..1]\overline{x^{\prime }}[111..1]$
• $x$（题目说了可以是0次，也只有这种情况下允许$y$是偶数，此类情况很容易漏下，并且测试数据很弱，很多人因此FST了）

对于前4种情况，由于一个数的二进制表示不会超过62位，我们直接暴力匹配即可。

时间复杂度

$$O({\log }_{2}x{\log }_{2}y)$$

AC代码

#include <bits/stdc++.h>

using namespace std;

void solve() {
	long long x, y;
	cin >> x >> y;
	if (x == y) {			//0次的情况不能漏下
		cout << "YES\n";
		return;
	}
	if (y % 2 == 0) {
		cout << "NO\n";
		return;
	}
	string s, t;
	bool ok = false;
	for (int i = 62; i >= 0; --i) {		//转二进制
		if (y >> i & 1) ok = true;
		if (ok) t += '0' + (y >> i & 1);
	}
	cerr << t << '\n';				//cerr是用来调试的，不影响输出结果
	ok = false;
	for (int i = 62; i >= 0; --i) {
		if (x >> i & 1) ok = true;
		if (ok) s += '0' + (x >> i & 1);
	}
	s += '1';
	cerr << s << '\n';
	for (int i = 0; i <= (int) t.length() - (int) s.length(); ++i) {
		if (t[i] == '0') break;
		if (t.substr(i, s.length()) == s) {		//暴力匹配
			bool f = true;
			for (int j = i + s.length(); j < t.length(); ++j) {
				if (t[j] == '0') {
					f = false;
					break;
				}
			}
			if (f) {
				cout << "YES\n";
				return;
			}
		}
	}
	reverse(s.begin(), s.end());		//翻转s，后面都大同小异
	cerr << s << '\n';
	for (int i = 0; i <= (int) t.length() - (int) s.length(); ++i) {
		if (t[i] == '0') break;
		if (t.substr(i, s.length()) == s) {
			bool f = true;
			for (int j = i + s.length(); j < t.length(); ++j) {
				if (t[j] == '0') {
					f = false;
					break;
				}
			}
			if (f) {
				cout << "YES\n";
				return;
			}
		}
	}
	while (x % 2 == 0) x /= 2;
	s.clear();
	ok = false;
	for (int i = 62; i >= 0; --i) {
		if (x >> i & 1) ok = true;
		if (ok) s += '0' + (x >> i & 1);
	}
	cerr << s << '\n';
	for (int i = 0; i <= (int) t.length() - (int) s.length(); ++i) {
		if (t[i] == '0') break;
		if (t.substr(i, s.length()) == s) {
			bool f = true;
			for (int j = i + s.length(); j < t.length(); ++j) {
				if (t[j] == '0') {
					f = false;
					break;
				}
			}
			if (f) {
				cout << "YES\n";
				return;
			}
		}
	}
	reverse(s.begin(), s.end());
	cerr << s << '\n';
	for (int i = 0; i <= (int) t.length() - (int) s.length(); ++i) {
		if (t[i] == '0') break;
		if (t.substr(i, s.length()) == s) {
			bool f = true;
			for (int j = i + s.length(); j < t.length(); ++j) {
				if (t[j] == '0') {
					f = false;
					break;
				}
			}
			if (f) {
				cout << "YES\n";
				return;
			}
		}
	}
	cout << "NO\n";
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

G. Trader Problem

题意

你手里有$n$个物品，第$i$个价值为$a_i$。另有$m$个物品，第$i$个价值为$b_i$。你可以把你手里的价值为$x$的物品与不属于你的价值不超过$x+k$的物品进行交换，交换后原本属于你的物品不再属于你并且可以在新的交换中被换回来，而作为交换，原本不属于你的那个物品现在属于你并且可以被用于新的交换中。现在有$q$次询问，给定$k$，求经过任意次数交换后属于你的物品的价值的最大值。

思路

首先我们考虑一种朴素的做法：

假设$k$已经确定，我们需要求出此情形下最终的最大价值。

将所有物品（包括属于你的和不属于你的）按价值从大到小排序，第$i$个价值为$v_i$，然后依次遍历每一个物品。对于第$i$件物品，如果存在$j\in [i,n+m]$，满足对任意$p\in [i,j?1]$，有$v_p?v_{p+1}\le k$，且第$j$个物品当前属于你，那么经过若干次交换，我们可以间接或直接地用价值为$v_j$的物品交换得到价值为$v_i$的物品。

此方法中，每次询问需要遍历数组$n$次，单次询问时间复杂度是$O(n^2)$，总的时间复杂度达到了$O(q{n}^2)$，这个效率是远远达不到题目要求的。

下一步考虑优化：

显然在上述的过程中，价值差距不超过$k$的相邻物品，我们遍历了很多次，如果我们能够避免这种冗余，效率会大大提高。

于是我们会想到预处理可行区段。对于一个区段$[i,j]$，满足对任意$p\in [i,j?1]$，有$v_p?v_{p+1}\le k$，那么这个区段中价值较低的物品都可以间接或直接地换成区段中价值较高的物品，根据贪心的思想，我们会选择区段中价值最大的那几个，其个数就等于原先在这个区段中属于你的物品数。使用前缀和可以$O(1)$求出每个区段最终的价值之和。

这样，单次询问的时间复杂度下降到了$O(n)$，总的时间复杂度是$O(qn+n{\log }_{2}n)$，有所进步但是还是不够优秀。

继续考虑优化：

上述的方法中，每一次询问都需要处理可行区段，实际上很多的区段是相似乃至相同的，这又导致了冗余。

于是我们考虑离线询问。将询问按$k$值大小从小到大排序，则我们在$k$值变化时只需要进行区段的合并即可，而不必全部重新处理。考虑并查集，同时维护每个并查集中原本属于你的物品数，同样使用前缀和优化查询即可。

于是最终，总的时间复杂度可以下降到$O(q+n{\log }_{2}n)$，达到了题目要求。

这里只讲了总体思路，结合代码看更容易理解。

时间复杂度

$$O(q+n{\log }_{2}n)$$

AC代码

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
const int N = 2e5 + 5;
pii a[N << 1];		//first记录价值，second标记初始是否属于你
int fa[N << 1], w[N << 1];	//fa是并查集父亲节点，w是当前并查集中物品数
map<int, vector<int>> mp;	//记录相邻物品的价值之差，实现方式多样，可以用别的方法代替
long long sum[N << 1];		//前缀和
struct dt {
	int id, k;	//id是询问的次序
	long long ans;
} d[N];		//存储离线询问的结构体

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void solve() {
	int n, m, q;
	cin >> n >> m >> q;
	long long ans = 0;		//需要动态维护的最大价值
	for (int i = 1; i <= n; ++i) {		//读入过程
		cin >> a[i].first;
		a[i].second = 1;
		ans += a[i].first;	//初始认为k=0，所以最大价值就是物品本身的价值
	}
	for (int i = 1; i <= m; ++i) {
		cin >> a[n + i].first;
	}
	sort(a + 1, a + n + m + 1);
	for (int i = 1; i <= n + m; ++i) {		//预处理过程
		fa[i] = i;
		w[i] = a[i].second;
		sum[i] = sum[i - 1] + a[i].first;
		if (i > 1) mp[a[i].first - a[i - 1].first].push_back(i - 1);
	}
	auto it = mp.begin();
	for (int i = 1; i <= q; ++i) {	//读入询问
		cin >> d[i].k;
		d[i].id = i;
	}
	sort(d + 1, d + q + 1, [&](dt &x, dt &y) { return x.k < y.k; });	//离线，按k排序
	for (int i = 1; i <= q; ++i) {
		if (d[i].k == d[i - 1].k) {
			d[i].ans = ans;
			continue;
		}
		while (it != mp.end() && it->first <= d[i].k) {		//区段合并
			for (int j: it->second) {
				int x = find(j), y = find(j + 1);
				ans -= sum[y] - sum[y - w[y]];		//先把原有两个集合产生的价值删去
				ans -= sum[x] - sum[x - w[x]];
				w[y] += w[x];
				fa[x] = y;
				ans += sum[y] - sum[y - w[y]];		//合并后补上新集合产生的价值
			}
			++it;
		}
		d[i].ans = ans;
	}
	sort(d + 1, d + q + 1, [&](dt &x, dt &y) { return x.id < y.id; });	//重新按原顺序排序
	for (int i = 1; i <= q; ++i) cout << d[i].ans << '\n';	//按原询问顺序输出答案
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

后记

千呼万唤始出来，犹抱AK半遮面！

一次AK一次爽，一直AK一直爽