C/C++教程
Codeforces Round #739 (Div. 3) 题解
本文主要是介绍Codeforces Round #739 (Div. 3) 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
旅行传送门
A. Dislike of Threes
题意：求这样一个序列：序列中不包含 \(3\) 的倍数和以 \(3\) 结尾的整数，输出这个序列中的第 \(k\) 个数。
题目分析：打表，过
AC代码：
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
const int maxn = 2005;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf; // 或者用fread更难调的快读
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int t, k, a[maxn];
void init()
{
rep(i, 1, 2000) if (!(i % 3) || (i % 10 == 3))
a[i] = 1;
}
int main(int argc, char const *argv[])
{
init();
t = read();
while (t--)
{
k = read();
int ans = 0;
while (k)
if (!a[++ans])
--k;
printf("%d\n", ans);
}
return 0;
}
B. Who's Opposite?
题意：若干个数按顺时针排列成圆，且关于圆心一一对称，告诉你其中对称的一组数 \(a\) 、 \(b\) ，求与 \(c\) 对称的数。
题目分析：不妨设 \(a\) > \(b\) ， \(a、b\) 是对称数，两者间的差值 \(tmp\) 即为每一对对称数间的差值，那么总人数即为 \(2 \times tmp\) ，由于编号从 \(1\) 开始，所以总人数小于 \(a、b、c\) 其中一个都无解，若有解，即为 \(c \pm tmp\)
AC代码：
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf; // 或者用fread更难调的快读
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int main(int argc, char const *argv[])
{
int T = read();
while (T--)
{
int a = read(), b = read(), c = read();
if (a < b)
std::swap(a, b);
int tmp = a - b;
int sum = 2 * (tmp - 1) + 2;
if (sum < a || sum < b || sum < c)
{
puts("-1");
continue;
}
printf("%d\n", c > (sum / 2) ? c - tmp : c + tmp);
}
return 0;
}
C. Infinity Table
题意：给你个矩阵，这个矩阵以某种方式填充数，问你第 \(k\) 个数的坐标是多少？
题目分析：不难发现行首的数均为平方数，两行首之差即为一次循环 ← ↓ 所填充的数，设当前行为 \(i\) ，这个差值为 \(tmp = a[i][1] - a[i-1][1]\) ，则 < \(\frac{tmp}{2}\) 的都在第 \(i\) 列， > \(\frac{tmp}{2}\) 的都在第 \(i\) 行，再推一下 \(k\) 与两行首的大小关系就能得到坐标了。
代码写得有些乱，见谅。
AC代码：
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf; // 或者用fread更难调的快读
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int vis[32000];
int main(int argc, char const *argv[])
{
rep(i, 1, 32000) vis[i] = i * i;
int T = read();
while (T--)
{
int k = read(), pos = 0;
rep(i, 1, 32000) if (k < vis[i])
{
pos = i;
break;
}
if (k == vis[pos - 1])
{
printf("%d %d\n", pos - 1, 1);
continue;
}
if (k == vis[pos - 1] + 1)
{
printf("%d %d\n", 1, pos);
continue;
}
int tmp = vis[pos] - vis[pos - 1];
if (k - vis[pos - 1] == tmp / 2 + 1)
{
printf("%d %d\n", pos, pos);
continue;
}
if (k - vis[pos - 1] > tmp / 2)
{
int cha = vis[pos] - k;
printf("%d %d\n", pos, cha + 1);
}
else if (k - vis[pos - 1] <= tmp / 2)
{
int cha = k - vis[pos - 1];
printf("%d %d\n", cha, pos);
}
}
}
D. Make a Power of Two
题意：给你一个整数 \(n\) ，你可以任意次进行下列操作之一:
- 移除数 \(n\) 的任意一位
- 给 \(n\) 的末尾加上一个数
问至少要经过几次操作，才能使得 \(n\) 成为 \(2\) 的幂。
题目分析：提前记下 \(2\) 的所有幂次，开两个指针去逐个顺序匹配，匹配结果分三种情况：
- 数 \(n\) 本就是 \(2\) 的幂次，这种情况无需再进行任何操作
- 如果该幂次的每一位数 \(n\) 中都包含，则答案为擦除其它位数所需的次数
- 否则，操作所需最少次数为第二种情况的答案加上未匹配位数的数目
说人话，假如 \(n\) 为 \(1052\) ，与 \(1024\) 匹配有 \(3\) 位匹配，那么对于当前次幂来说最少次数为擦除 \(5\) 的一次加上末尾添上 \(4\) 的一次。
遍历 \(2\) 的所有幂次，不断更新迭代，即可找到最优解。
AC代码：
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
const int inf = 0x3f3f3f3f;
char num[20];
char s[55][20] = {"1", "2", "4", "8", "16", "32", "64", "128", "256", "512", "1024", "2048", "4096", "8192", "16384", "32768", "65536", "131072", "262144", "524288", "1048576", "2097152", "4194304", "8388608", "16777216", "33554432", "67108864", "134217728", "268435456", "536870912", "1073741824", "2147483648", "4294967296", "8589934592", "17179869184", "34359738368", "68719476736", "137438953472", "274877906944", "549755813888", "1099511627776", "2199023255552", "4398046511104", "8796093022208", "17592186044416", "35184372088832", "70368744177664", "140737488355328", "281474976710656", "562949953421312", "1125899906842624", "2251799813685248", "4503599627370496", "9007199254740992", "18014398509481984"};
int main(int argc, char const *argv[])
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%s", num);
int ans = inf;
rep(i, 0, 54)
{
int match = 0;
int p1 = 0, p2 = 0;
while (num[p2])
{
if (num[p2] == s[i][p1])
++p1, ++match;
++p2;
}
int len1 = strlen(s[i]), len2 = strlen(num);
int dif = len2 - match;
if (match ^ len1)
ans = std::min(ans, dif + len1 - match);
else
ans = std::min(ans, dif);
}
printf("%d\n", ans);
}
return 0;
}
E. Polycarp and String Transformation
题意：假设有这样一个字符串 \(s\) 和一个空字符串 \(t\) ， 字符串 \(s\) 可以执行下列操作直至其为空：
- 先令 \(t = t + s\)
- 再移除 \(s\) 中所有的某字母
现在给你一个 \(t\) 串，问你能否倒推出 \(s\) 串和字母的删除顺序。
题目分析：
-
怎么确定删除顺序呢？字母的位置越靠后，说明它“存活”得越久，那么我们只需记录下每个字母最后出现位置的先后顺序，即可确定删除顺序。
-
怎么确定原串 \(s\) 呢？我们可以这样想，若 \(s\) 串最终可以拼出 \(t\) 串，那么虽然 \(s\) 每次删去的字母不同，但在某字母被删去前，其在 \(s\) 中出现的次数是固定的，假设第 \(i\) 次操作删去了字母 \(a\) ，那么 \(a\) 在 \(t\) 中的出现次数一定为 \(i\) 的倍数。否则就不存在能拼出当前 \(t\) 串的 \(s\) 串。
-
记录下字母 \(a\) 的出现次数 \(cnta\) ，即 \(a\) 在原串中的出现次数为 \(numa = cnta / i\) ，所有字母的 \(num\) 之和即为原串 \(s\) 的长度，那 \(s\) 也就可以随之确定了
-
吗？答案是否定的，我们还要再模拟上述操作用目前得到的 \(s\) 串试着能不能拼出 \(t\) ，只有正推逆推都没问题，答案才合法。
AC代码：
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
#define full(x, y) memset(x, y, sizeof(x))
using namespace std;
int flag, cnt[26], pos[26];
string ori, tmp, s, t, order;
struct node
{
int ch, pos;
} lst[26];
void init()
{
flag = 0;
s.clear(), order.clear();
rep(i, 0, 25) lst[i].ch = i, lst[i].pos = 0;
full(cnt, 0), full(pos, 0);
}
inline bool cmp(node a, node b) { return a.pos < b.pos; }
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--)
{
init();
cin >> t;
int len = t.length() - 1;
rep(i, 0, len)
{
int c = t[i] - 'a';
++cnt[c];
lst[c].pos = i + 1;
}
sort(lst, lst + 26, cmp);
rep(i, 0, 25) if (lst[i].pos) order += lst[i].ch + 'a';
len = order.length() - 1;
rep(i, 0, len)
{
int c = order[i] - 'a';
pos[c] = i + 1;
}
int sum = 0;
rep(i, 0, 25)
{
if (!cnt[i])
continue;
if (cnt[i] % pos[i])
{
flag = 1;
break;
}
sum += cnt[i] / pos[i];
}
if (!flag)
{
ori = t.substr(0, sum);
tmp = ori;
rep(i, 0, len)
{
s += tmp;
tmp.erase(remove(tmp.begin(), tmp.end(), order[i]), tmp.end());
}
if (s.compare(t))
flag = 1;
}
if (flag)
{
cout << "-1" << endl;
continue;
}
cout << ori << " " << order << endl;
}
return 0;
}
题外话：前两天打HDU多校还在骂STL来着，今天string用起来又真香了。
F1. Nearest Beautiful Number (easy version)
题意：给你一个数 \(n\) ，如果 \(n\) 中不同的数 \(\leq k\) ，我们就称其为“美数”（我没在玩谐音梗），求 \(\geq n\) 的最小的“美数” \(x\) 。
一些闲话：分类讨论讨论得想死。。修锅修了一晚上。。分类情况写了删删了加。。提前体会以后上班写 \(sh*t\) 山代码的感觉了。。。
题目分析：具体可以去看这位dalao的题解 → 旅行传送门 ，原谅我偷懒不想码字了( -'`-)
嘛，细节有亿点多，像各种情况的处理顺序啊、各种找位置啊啥的，注意下就好。。
分类讨论不过是邪门歪道。。想看正解请移步 F2 Hard Version。
AC代码：
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
using namespace std;
int vis[10];
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--)
{
int k;
string s, ans;
cin >> s >> k;
memset(vis, 0, sizeof(vis));
int len = s.length() - 1;
int dif = 0;
rep(i, 0, len) if (!vis[s[i] - '0']) vis[s[i] - '0'] = 1, ++dif;
if (dif <= k)
cout << s << endl;
else if (k == 1)
{
int flag = 0, pos = 0;
rep(i, 1, len) if (s[i] != s[i - 1])
{
pos = i;
break;
}
if (s[0] < s[pos])
flag = 1;
char c = flag ? s[0] + 1 : s[0];
rep(i, 0, len) ans += c;
cout << ans << endl;
}
else
{
int pos1 = 0, pos2 = 0;
int num1 = s[0] - '0', num2 = 0;
ans += s[0];
rep(i, 1, len)
{
if (s[i] != s[pos1])
{
pos2 = i;
num2 = s[i] - '0';
break;
}
ans += s[i];
}
int mx = std::max(num1, num2), mi = std::min(num1, num2);
int pos3, num3;
ans += s[pos2];
rep(i, pos2 + 1, len)
{
if (s[i] != s[pos1] && s[i] != s[pos2])
{
pos3 = i;
num3 = s[i] - '0';
break;
}
ans += s[i];
}
if (num3 < mi)
rep(i, pos3, len) ans += mi + '0';
else if (num3 < mx)
{
ans += mx + '0';
rep(i, pos3 + 1, len) ans += mi + '0';
}
else
{
string tmp1 = ans, tmp2 = ans;
ans = "999999999";
int pos_min = 0;
rep(i, 0, len) if (s[i] - '0' == mi && i < pos3) pos_min = std::max(pos_min, i);
tmp2[pos_min] = mx + '0';
rep(i, pos_min + 1, len) tmp2[i] = mi + '0';
while (tmp2.length() <= len)
tmp2 += mi + '0';
if (tmp2 > s)
if (ans > tmp2)
ans = tmp2;
++num2;
mi = std::min(num1, num2);
tmp2 = tmp1;
tmp2[pos2] = num2 + '0';
rep(i, pos2 + 1, len)
tmp2[i] = mi + '0';
while (tmp2.length() <= len)
tmp2 += mi + '0';
if (tmp2 > s)
if (ans > tmp2)
ans = tmp2;
if (num1 == num2)
{
tmp2 = tmp1;
tmp2[pos2] = num2 + '0';
rep(i, pos2 + 1, len) tmp2[i] = '0';
while (tmp2.length() <= len)
tmp2 += '0';
if (tmp2 > s)
if (ans > tmp2)
ans = tmp2;
}
}
cout << ans << endl;
}
}
return 0;
}
F2. Nearest Beautiful Number (hard version)
还是一些闲话：
队友钻研这题钻研了一天，摸索出了个DFS的写法，经不住我的再三要求，写下了本题题解，代码很简单，思路也很容易看懂，强烈建议阅读！！！
友情链接：无人问津的小羊圈
题目分析：
假设我们已经取得k个不同的、可以用于构造答案的数字，现在考虑如何使用这些数字来构造一个最小的、大于等于所给数字n的答案。
从最高位开始构造数字，我们可以得到以下两个贪心策略：
- 如果该位可以使用一个更小的数字来满足大于等于n上相同位数字的条件，则使用更大的数字不会更优。
- 如果所构造答案的某一位严格大于n上相同位的数字，则该位之后的每一位可以任意使用k个数字的其中一个。显然，选择k个数中最小的那个最优。
于是我们可以得出以下构造方式：
- 从最高位开始向低位构造数字。
- 对于每一位，从小到大依次尝试使用这k个数，直到某个数大于等于n上相同位的数字，将该数字填入该位。如果k个数都小于n上相同位的数字，则构造失败（这k个数无法构造出答案）。
- 如果选取的数字严格大于n上相同位的数字，则使用k个数中最小的数字填入该位之后的所有位。否则，对下一位重复执行第2个步骤。
这个构造方法可以通过对每一位进行递归实现。
接下来，我们考虑如何选取这k个数。当k=2时（Easy version），我们可以枚举所有的取值情况，记录每一种取值情况的合法解，最后选取其中最小的解作为答案即可。
然而事实上，我们并不需要在递归求解之前就得到这k个数的取值，而是在对每一位递归的过程中逐渐取得这k个数。
让我们从最高位开始考虑，此时我们选中的数字个数为0，这意味着我们可以选择一个当前最优的数字加入k数字集合，然后直接使用该数字填入该位。当前最优的数字是什么？显然是n相同位上的数字，这是能满足大于等于n上相同位数字条件的最小值；如果通过递归求解发现填入该数字后无法构造出答案，那其加一后的值就是当前位最优的数字（满足大于相同位数字的条件，一定能够确保构造出答案）。
让我们将该取数方法扩展到其他位，当处理到第i位，此时选中的数字个数m小于k时，选择n相同位上的数字填入该位，并将该数加入k（注意去重），继续递归求解下一位；若递归求解下一位无法构造出答案，则将该数加一后填入该位，并将该数加入k（注意去重），然后递归求解下一位，此时能够保证构造出最优解。
AC代码：
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int t, k, dignum;
bool vis[10]; // 用于标记某个数是否已被加入k数集合
char n[15], ans[15];
// ind: 当前构造的位数
// num: 已选择的k数数组
// len: 已选择的k数数量
// isok: 该位之前是否已经存在某一位严格大于n相同位的数字
bool dfs(int ind, int *num, int len, bool isok)
{
if (ind == dignum)
return true;
// 已选择的k数个数小于k
if (len < k)
{
int new_num[k] = {0}, new_num_len = len;
for (int i = 0; i < len; i++)
new_num[i] = num[i];
// 如果k集合中没有该数，便加入该数并标记
if (!vis[n[ind] - '0'])
new_num[new_num_len++] = n[ind] - '0', vis[n[ind] - '0'] = true;
ans[ind] = n[ind];
// 递归求解，如果可以构造，则必为最优解
if (dfs(ind + 1, new_num, new_num_len, isok))
return true;
// 从k集合中移除该数
if (new_num_len != len)
vis[n[ind] - '0'] = false;
for (int i = 0; i < len; i++)
new_num[i] = num[i];
// 注意，如果加一后的值已经在集合中了，这意味着在集合未填满的情况下，我们获得了任意填写之后所有位的权利
// 此时，当后续所有位填0时最优，因此，我们需要将0加入k集合。
if (vis[n[ind] - '0' + 1])
new_num[len] = 0;
else
new_num[len] = n[ind] - '0' + 1;
ans[ind] = n[ind] + 1;
// 若上述情况无法构造，则加一后填入必能构造出最优解
return dfs(ind + 1, new_num, len + 1, true);
}
sort(num, num + len);
// 先前已有某一位严格大于n相同位上的数字
if (isok)
{
ans[ind] = num[0] + '0';
return dfs(ind + 1, num, len, isok);
}
for (int i = 0; i < len; i++)
{
// 满足条件
if (num[i] >= n[ind] - '0')
{
ans[ind] = num[i] + '0';
// 递归求解下一位
if (dfs(ind + 1, num, len, num[i] > n[ind] - '0'))
return true;
}
}
// 若该位无法继续构造答案，返回false表示构造失败
return false;
}
int main()
{
cin >> t;
while (t--)
{
memset(vis, 0, sizeof(vis));
cin >> n >> k;
dignum = strlen(n);
// 答案必为dignum位
ans[dignum] = '\0';
int num[k] = {0};
dfs(0, num, 0, false);
cout << atoll(ans) << endl;
}
return 0;
}
这篇关于Codeforces Round #739 (Div. 3) 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
增量更新怎么做？-icode9专业技术文章分享11-23
-
压缩包加密方案有哪些？-icode9专业技术文章分享11-23
-
用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享11-23
-
webman可以同步自己的仓库吗？-icode9专业技术文章分享11-23
-
在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享11-23
-
如何重置new Swiper?-icode9专业技术文章分享11-23
-
oss直传有什么好处？-icode9专业技术文章分享11-23
-
如何将oss直传封装成一个组件在其他页面调用时都可以使用？-icode9专业技术文章分享11-23
-
怎么使用laravel 11在代码里获取路由列表？-icode9专业技术文章分享11-23
-
怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享11-22
-
ansible 的archive 参数是什么意思？-icode9专业技术文章分享11-22
-
ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享11-22
-
exclude_path参数是什么作用？-icode9专业技术文章分享11-22
-
微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享11-22
-
uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享11-22
栏目导航
