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

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Codeforces Round #739 (Div. 3) 题解完整A~F -> 正文阅读

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

Codeforces Round #739 (Div. 3) 题解

A. Dislike of Threes

题意

求所有不能被 $3$ 整除且个位不为 $3$ 的正整数中，第 $k$ 大的是多少。（关注数据范围， $1\le k\le 1000$ ）

思路

题目限定 $k\le1000$ ，那么不妨直接预处理打表，样例里面有第 $1000$ 个符合题意的数是 $1666$ ，那么只需处理至 $1666$ 即可。本题使用纯暴力，每次都求一遍也可以通过。

时间复杂度

$预处理 O (n) ，求值 O (1)$

AC代码

Problem	Lang	Verdict	Time	Memory
A - Dislike of Threes	GNU C++17	Accepted	31 ms	3700 KB

#include <bits/stdc++.h>

using namespace std;

vector<int> v;

void solve() {
	int n;
	scanf("%d", &n);
	printf("%d\n", v[n - 1]);				//我是从下标0开始存储的，需要减1
}

int main() {
//	freopen("in.txt", "r", stdin);
	for (int i = 1; i <= 1666; ++i) {		//预处理
		if (i % 10 != 3 && i % 3) v.push_back(i);
	}
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}

B. Who’s Opposite?

题意

给定一个由偶数个点组成的环，点在环上均匀分布，按顺时针依次从 $1$ 开始编号。完成编号后，每个点关于圆心对称处必定存在另一个点，例如： $6$ 个点组成的环中， $1$ 与 $4$ 相对， $2$ 与 $5$ 相对， $3$ 与 $6$ 相对。现给定 $3$ 个互不相同的正整数 $a, b, c$ ，并已知编号为 $a$ 的点与编号为 $b$ 的点相对，问与 $c$ 相对的点编号是多少，如果这样的环不存在，输出 $? 1$ 。

思路

给出了 $a$ 和 $b$ ，我们就可以求出这个环上有多少个点，记环上有 $2 n$ 个点，那么就有 $n = ∣ a ? b ∣$ 。于是就有了 $3$ 个限制条件，也就是： $a, b, c$ 都必须在环上，换句话说， $1\le a,b,c\le n$ 。若条件满足，则能够求出 $c$ 对面的点，其编号是 $c + n$ 和 $c ? n$ 中符合条件的一个。细致来说， $c\le n$ 时为 $c + n$ ， $c > n$ 时为 $c ? n$ 。

时间复杂度

$O (1)$

AC代码

Problem	Lang	Verdict	Time	Memory
B - Who’s Opposite?	GNU C++17	Accepted	31 ms	3600 KB

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	if (a > b) swap(a, b);
	int n = b - a;
	if (a > n * 2 || b > n * 2 || c > n * 2) {	//不合法情形
		printf("-1\n");
		return;
	}
	if (c - n > 0) printf("%d\n", c - n);
	else printf("%d\n", c + n);
}

int main() {
//	freopen("in.txt", "r", stdin);
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}

C. Infinity Table

题意

现有一个无限大的空表格，在 $(1, 1)$ 位置填入 $1$ ，然后按照以下规则填表：

在第一行找到最靠左的空白格，填入下一个正整数（此时填入的是 $2$ ），然后检查左侧是否是空白格；
若左侧是空白格，则向左侧填入下一个正整数；
否则，向下方填入下一个正整数；
若左侧没有格子了，则重新回到第一行，再次寻找最左侧空白格，开始新的一轮。（具体如下表所示）

$\begin{matrix}{} 1 & 2 & 5 & 10\\ 4 & 3 & 6 & \ \vdots\\ 9 & 8 & 7 & \ \vdots \end{matrix}$

问：正整数 $k$ 在这个表格中，位于什么位置，用行号和列号表示。

思路

观察表格，不难发现填入 $(1,2)\to(2,2)\to(2,1)$ 区域的数，值域为 $1^2,2^2]$ ，填入 $(1,3)\to(3,3)\to(3,1)$ 区域的数，值域为 $2^2,3^2]$ ，进一步推广可以发现，填入 $(1,n)\to(n,n)\to(n,1)$ 区域的数，值域为 $n-1)^2,n^2]$ ，且前 $n$ 个数按列从上到下排布，后 $n ? 1$ 个数按行从右到左排布。然后只需将 $k$ 减去 $n-1)^2$ ，按上述规则简单求值即可。

时间复杂度

$O (1)$

AC代码

Problem	Lang	Verdict	Time	Memory
C - Infinity Table	GNU C++17	Accepted	31 ms	3700 KB

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	scanf("%d", &n);
	int s;
	s = floor(sqrt(n - 1));	//由于我们要减掉的是严格小于n的最大完全平方数，所以需要先减1再开根，向下取整
	n -= s * s;
	if (n <= s) printf("%d %d\n", n, s + 1);
	else printf("%d %d\n", s + 1, 2 * s + 2 - n);
}

int main() {
//	freopen("in.txt", "r", stdin);
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}

D. Make a Power of Two

题意

给定一个正整数 $n$ ，每次在十进制下可以去掉该数的某一位（若去掉某一位后，导致该数有前导0，则前导0不消失），或者在数的末尾增加一位任意数字。求至少多少次操作后，该数变为 $2$ 的整数次幂。

思路

关注 $n$ 的数据范围， $n$ 不超过 $10^9$ ，那么也就是说，最多 $9$ 次操作后，我们一定能得到一个 $2$ 的整数次幂：去掉这个数的所有位（最多操作 $8$ 次），在末尾增加一个 $1$ 。因此，最终的结果，一定不超过 $10^{18}$ （也就是不断在末尾添加数，加 $9$ 次）。众所周知，long long范围内 $2$ 的整数次幂的个数极其有限，因此暴力枚举结果即可。

对于每一种可能的结果，采用双指针匹配来求出需要多少次操作。我们记 $x$ 为目标的数， $y$ 为给定的数，记 $x_i$ 为 $x$ 的第 $i$ 位， $y_j$ 为 $y$ 的第 $j$ 位，根据贪心思想，如果当前匹配至 $x_i$ 和 $y_j$ 位置，若 $x_i=y_j$ ，则将这两个位置匹配， $i, j$ 指针同时后移，否则 $i$ 指针不动， $j$ 指针后移，由于这一位没能匹配上，原先 $j$ 位置的数需要删除，操作数需要加 $1$ 。全部匹配完后，多余的部分也需要加入到操作数中，也即为 $x$ 补全缺失的数位，为 $y$ 删去多余的数位。

由于要将整数按十进制位拆分，常用的方法是将整数转化为字符串，sprintf是非常好用的函数，当然用其他任何一种合理的方式实现都可以。

时间复杂度

$O (62) (具体复杂度不好算，但肯定很快，是常数级的复杂度)$

AC代码

Problem	Lang	Verdict	Time	Memory
D - Make a Power of Two	GNU C++17	Accepted	61 ms	3700 KB

#include <bits/stdc++.h>

using namespace std;

char s[80][40];
char k[40];

void solve() {
	scanf("%s", k);		//直接当作字符串读入，免去数位拆分工作
	int ans = 1000;		//初始化一个比较大的值，1000足够大了
	for (int i = 0; i < 63; ++i) {
		int cur = 0, p1 = 0, p2 = 0;	//cur保存的是当前枚举的答案下至少需要多少次操作
		while (s[i][p1] != '\0' && k[p2] != '\0') {
			if (s[i][p1] == k[p2]) ++p1, ++p2;
			else ++cur, ++p2;
		}
		while (s[i][p1] != '\0') ++cur, ++p1;
		while (k[p2] != '\0') ++cur, ++p2;
		ans = min(ans, cur);
	}
	printf("%d\n", ans);
}

int main() {
//	freopen("in.txt", "r", stdin);
	for (int i = 0; i < 63; ++i) {		//2的幂，按位拆分，预处理一下就行了
		sprintf(s[i], "%lld", 1ll << i);
	}
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}

E. Polycarp and String Transformation

题意

现有字符串 $t$ 和 $s$ ，其中 $t$ 初始为空串， $s$ 初始非空，并按以下规则进行操作：

在 $t$ 的末尾增加 $s$ ，也即 $t = t + s$
选择任意一个在 $s$ 中出现过的字母，并将 $s$ 中所有该字母都删去

以上操作必须按顺序执行，并不断重复操作，直到 $s$ 变为空串。

现给定完成了所有操作后的字符串 $t$ ，求原先的字符串 $s$ ，并求出字母的删除顺序。

如果不存在相应的答案，输出 $? 1$ 。

思路

注意：本人认为，我的做法可能不是最优解法，虽然理解并不困难，但如果有更优的做法，读者可以择优学习。如有不足，欢迎指出！

首先，我们假定我们知道 $s$ 的内容，设 $s$ 中一共有 $k$ 个不同的字母，并设删除顺序为 $d_1,d_2,\dots,d_k$ ，这些字母分别出现了 $c_1,c_2,\dots,c_k$ 次，那么在字符串 $t$ 中， $d_1$ 出现了 $1\times c_1$ 次， $d_2$ 出现了 $2\times c_2$ 次， $d_k$ 出现了 $k\times c_k$ 次~~（我觉得这应该比较容易理解，不需要证明了）~~。

利用上述性质，我们根据得到的 $t$ ，从后往前逆推答案。最后一个出现的字母，一定是 $d_k$ （这毫无疑问），除去 $d_k$ 之外，最后一个出现的字母是 $d_{k-1}$ 。于是，字母的删除顺序就可以求出来了。根据上一段中说明的，每个字母在 $t$ 中出现次数的结论，我们在统计了 $i\times c_i$ 之后，很容易可以求出 $c_i$ 。如果 $d_i$ 在 $t$ 中的出现次数不能被 $i$ 整除，那么显然答案不存在，输出 $? 1$ 即可。

由于 $t$ 中，最开始时一定会加入一段完整的 $s$ ，那么我们对前若干个字母进行统计，直到各字母的出现次数与预期的 $c_i$ 相等。这里不建议每次都将 $26$ 个字母的出现次数一一比较，这样效率太低。假定答案存在，那么 $s$ 的长度就等于 $\sum c_i$ 。如果在这一段中，各字母的出现次数与预期不符，则答案不存在。

最后，还需要进行最后一次确认。现在我们已经得到了 $s$ 和 $d_i$ ，我们只需要根据操作规则，完整模拟字符串 $t$ 的生成过程，将生成的字符串与给定的比较，如果完全一致，则可以输出答案了，否则答案不存在。

这一段比较长，可能不容易理解，总体思路是模拟，只需要根据答案，再现生成过程即可。

时间复杂度

$O (n) (n 是字符串 t 的长度)$

AC代码

Problem	Lang	Verdict	Time	Memory
E - Polycarp and String Transformation	GNU C++17	Accepted	31 ms	4600 KB

#include <bits/stdc++.h>

using namespace std;
					//代码中的变量名和题目中不太一样
char s[500005];		//s相当于题目中的t
char ss[500005];	//ss用于模拟生成t
char k[100];		//k是反向存储的删除顺序
int num[100], vis[100];

void solve() {
	scanf("%s", s);
	int n = strlen(s);
	int tot = 0, cnt = 0;
	memset(num, 0, sizeof num);
	for (int i = 0; i < n; ++i) {		//统计每个字母出现了几次
		if (!num[s[i] - 'a']) ++tot;
		++num[s[i] - 'a'];
	}
	memset(vis, 0, sizeof vis);
	for (int i = n - 1; i >= 0; --i) {		//反向推出删除的顺序
		if (!vis[s[i] - 'a']) {
			if (num[s[i] - 'a'] % tot) {	//不能整除，不合法
				printf("-1\n");
				return;
			}
			k[cnt++] = s[i];	//注意这里k的存储是反向的，输出的时候要倒过来
			num[s[i] - 'a'] /= tot--;
			vis[s[i] - 'a'] = 1;
		}
	}
	int pos = 0, sum = 0;
	for (int i = 0; i < 26; ++i) sum += num[i];	//求出s的长度
	while (sum) {		//模拟生成字符串s
		if (!num[s[pos] - 'a']) {	//某个字母数量过多，多于预期，不合法
			printf("-1\n");		//不必判少于预期的情况，因为有偏少的就一定有偏多的
			return;
		}
		--num[s[pos++] - 'a'];
		--sum;
	}
	int p = 0;
	memset(vis, 0, sizeof vis);
	for (int i = cnt; i >= 0; --i) {	//模拟生成字符串t
		if (i < cnt) vis[k[i] - 'a'] = 1;
		for (int j = 0; j < pos; ++j) {
			if (!vis[s[j] - 'a']) ss[p++] = s[j];
			if (p > n) {		//生成的t过长了，需要及时剪掉，以防RE
				printf("-1\n");
				return;
			}
		}
	}
	ss[p] = '\0';
	if (strcmp(s, ss) != 0) {	//生成的t与给定的不同，不合法
		printf("-1\n");
		return;
	}
	s[pos] = '\0';		//在原字符串上修改，相应位置设置成结束符即可
	printf("%s ", s);
	for (int i = cnt - 1; i >= 0; --i) {	//反向输出删除序列
		putchar(k[i]);
	}
	putchar('\n');
}

int main() {
//	freopen("in.txt", "r", stdin);
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}

F1/F2. Nearest Beautiful Number

这两道题的方法是完全一样的，这里直接讲F2的解题方法。

题意

定义一个正整数为k-beautiful：该正整数中出现过的不同数字的数量不超过 $k$ 。

给定正整数 $n$ 和 $k$ ，求不小于 $n$ 的最小k-beautiful数。

F1与F2的区别是数据范围不同：F1: $k\le2$ ，F2: $k\le10$ 。

思路

这其实是一个暴力搜索+分类讨论+剪枝的题目。我们对一个数按十进制位展开，一位一位的分析。

虽然是状态的转移，但其实和DP没多大关系，简简单单的搜索罢了

设状态 $(p, k, n, f)$ ：

$p$ 是当前枚举到第 $p$ 位，假如这个数有 $l e n$ 位，那么 $p$ 将从 $0$ （最高位）枚举至 $l e n ? 1$ （最低位），当 $p = l e n$ 的时候，说明枚举结束了，这是一个合法的答案。
$k$ 是当前状态下，还能有多少个新的数字出现。无论什么情况，只要 $k < 0$ ，就说明这种情况不合法。
$n$ 是枚举到当前状态时，前 $p$ 位连起来，生成的数，用于计算。
$f$ 是当前状态的数是否已经大于给定的限制， $f = 1$ 表示已经大于给定限制，换句话说，此后的所有数，不论取几，都能满足题目要求的“不小于”的条件。

接下来是状态的转移以及剪枝：（式中 $d_i$ 表示给定的数的第 $i$ 位，下标从 $0$ 开始）

$k = ? 1$ ，不合法情形，直接剪枝。
$p = l e n$ ，合法情形，更新 $a n s w e r$ 即可（取 $m i n$ ），然后剪枝。
$f = 1$ ，不再有数的大小限制，此后所有数位以尽可能小的数来填充，有以下两种情况：
- $k = 0$ ，不能再产生新的数，只能在已经出现过的数中找最小的来填充剩余数位。
- $k > 0$ ，还可以产生新的数，剩下的数位全部用 $0$ 填充。
求出值后更新 $a n s w e r$ ，然后剪枝。
这一位不变，也就是等于原数位 $d_p$ ，状态转移为 $(p,k,n,0)\to(p+1,k',10n+d_p,0)$ ，其中的 $k^{'}$ 是下一步的 $k$ ，其值等于 $k$ 或 $k ? 1$ ，要判断 $d_p$ 在之前的数中是否出现过，再决定是否需要减 $1$ 。
这一位加 $1$ ，状态转移为 $(p,k,n,0)\to(p+1,k',10n+d_p+1,1)$ ，有前提条件 $d_p\not=9$ 。
这一位增加至出现过的最小数字，记大于 $d_p$ 的最小出现数字为 $x$ ，状态转移为 $(p,k,n,0)\to(p+1,k,10n+x,1)$ ，有前提条件 $x$ 存在，注意这里是 $k$ 而不是 $k^{'}$ ，因为保证了 $x$ 是已经出现过的数。

以上的 $a n s w e r$ 需初始化为无穷大，经过更新后，最终求得的 $a n s w e r$ 就是答案了。状态转移只有这 $3$ 种方式，其他方式要么不合法，要么不够优秀。

虽然看起来每一个位置都有 $3$ 类情况，复杂度是指数级别，但实际上有两种情况都会转移到 $f = 1$ 的情形中去，并立刻被剪枝，因此实际上的复杂度是线性的，甚至由于一个数的位数极其有限，算法的复杂度甚至可以认为是常数级复杂度。

时间复杂度

$O (n) (n 极小)$

AC代码

Problem	Lang	Verdict	Time	Memory
F1 - Nearest Beautiful Number (easy version)	GNU C++17	Accepted	30 ms	3700 KB
F2 - Nearest Beautiful Number (hard version)	GNU C++17	Accepted	46 ms	3700 KB

#include <bits/stdc++.h>

using namespace std;

char s[15];
int vis[10];
long long len, ans;

void dfs(int p, int k, long long n, int f) {
	if (k == -1) return;		//不合法，剪枝
	if (p >= len) {				//合法，更新答案，剪枝
		ans = min(ans, n);
		return;
	}
	if (f) {					//合法，尽可能取最小的数填充后更新答案，剪枝
		int minm;
		if (k) minm = 0;
		else {
			for (int i = 0; i < 10; ++i) {
				if (vis[i]) {
					minm = i;
					break;
				}
			}
		}
		for (int i = p; i < len; ++i) n = n * 10 + minm;
		ans = min(ans, n);
		return;
	}
	++vis[s[p] - '0'];		//标记访问痕迹，下同
	dfs(p + 1, k - (vis[s[p] - '0'] == 1), n * 10 + s[p] - '0', 0);
	--vis[s[p] - '0'];		//擦除访问痕迹，下同
	if (s[p] != '9') {
		++vis[s[p] - '0' + 1];
		dfs(p + 1, k - (vis[s[p] - '0' + 1] == 1), n * 10 + s[p] - '0' + 1, 1);
		--vis[s[p] - '0' + 1];
	}
	int fd = 0;
	for (int i = s[p] - '0' + 2; i < 10; ++i) {
		if (vis[i]) {
			fd = i;
			break;
		}
	}
	if (fd) {		//能找到比当前位大的已经出现过的数
		++vis[fd];
		dfs(p + 1, k, n * 10 + fd, 1);
		--vis[fd];
	}
}

void solve() {
	int n, k;
	scanf("%d%d", &n, &k);
	sprintf(s, "%d", n);
	len = strlen(s), ans = 2e9;
	memset(vis, 0, sizeof vis);
	dfs(0, k, 0, 0);
	printf("%lld\n", ans);
}

int main() {
//	freopen("in.txt", "r", stdin);
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}