2021 TPC 腾讯程序设计竞赛 热身赛
作者: | 更新日期:
热身赛都这么难，希望。
本文首发于公众号：天空的代码世界，微信号：tiankonguse
零、背景
2021 年 TPC 腾讯程序设计竞赛 又开始了。
热身赛已经结束，分享下热身赛的题解。
一、Future of Tencent
题意：签到题
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
if (n) {
printf("You are the future of Tencent!\n");
} else {
printf("Good luck and Enjoy TPC!\n");
}
}
return 0;
}
二、Wondrous Tails
题意：给一个 4*4的矩阵和 9 个披萨，问怎么调整披萨的位置，可以使 9 个披萨组成三条线。
如下图，左图只有两条线，右图有三条线。
思路：由于只有 9 个披萨，可以发现，必须是横竖斜三条直线才能组成三条线。
所以可以通过O(4*4*2)的复杂度，预处理计算出所有的满足要求的三线矩阵，有 24 个。
然后对于每个输入，与 24 个三线矩阵对比，找到最小调整数即可。
int main() {
init();
// printf("num=%d\n", num);
int t;
scanf("%d", &t);
while (t--) {
char str[5][5];
for (int i = 0; i < 4; i++) {
scanf("%s", str[i]);
}
int ans = 9;
for (int k = 0; k < num; k++) {
int tmpAns = 9;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (base[k][i][j] == str[i][j]) {
tmpAns--;
}
}
}
ans = min(ans, tmpAns);
}
printf("%d\n", ans);
}
return 0;
}
三、BFS Sequence
题意：对于一个多叉树，给出两个 BFS 序列，求构造出多叉树。
由于可能存在多个答案，求输出树高最高的多叉树。
思路：由于是 BFS，对于同一层的节点，组成的集合应该是完全相同的。
所以对两个序列进行集合划分即可，每个集合就是树的一层。
关于每层节点的父节点，我们发现可以指向同一个父亲，所以指向上一层的第一个节点即可。
vector<int> one(100011, 0);
vector<int> two(100011, 0);
vector<int> pre(100011, 0);
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &one[i]);
}
for (int i = 0; i < n; i++) {
scanf("%d", &two[i]);
}
if (one[0] != two[0]) {
printf("No\n");
continue;
}
int root = 0;
int onePos = 0;
int twoPos = 0;
unordered_set<int> oneSet;
unordered_set<int> twoSet;
for (int i = 0; i < n;) {
onePos = twoPos = i;
int tmpRoot = one[onePos];
oneSet.clear();
twoSet.clear();
do {
// printf("%d %d\n", onePos, twoPos);
int tmpVal = one[onePos];
pre[tmpVal] = root;
oneSet.insert(tmpVal);
if (twoSet.count(tmpVal)) {
onePos++;
continue;
}
while (twoPos < n && two[twoPos] != tmpVal) {
twoSet.insert(two[twoPos]);
twoPos++;
}
if (twoPos < n && two[twoPos] == tmpVal) {
twoSet.insert(two[twoPos]);
twoPos++;
}
} while (oneSet.size() != twoSet.size());
i = twoPos;
root = tmpRoot;
// printf("root=%d\n", root);
}
printf("Yes\n");
for (int i = 1; i <= n; i++) {
printf("%d%c", pre[i], i < n ? ' ' : '\n');
}
}
return 0;
}
四、Persistent String
题意：给一个字符串 s，有三个操作。
1）+ p t，在位置 p 之后插入字符串 t。
2）! a b c p，将字符串子串 s[a,b] 在位置 p 之后重复插入 c 次。
3）? p 询问位置 p 的字符。
思路：对于这种字符串插入拼接的问题，需要倒着处理。
如果有询问，先缓存起来。
如果有操作1，则计算缓存的所有询问是否在插入字符串的范围内，在了则找到答案，否则更新偏移量。
如果有操作2，则根据位置关系，更新所有询问的偏移量。
这样到达第一个输入字符串时，就可以找到所有答案了。
map<int, pair<LL, char>> ans;
int main() {
int t, q;
scanf("%d", &t);
while (t--) {
input(q);
ans.clear();
for (int i = q; i >= 0; i--) {
Op* p = ops + i;
LL pos = p->pos;
if (p->op[0] == '?') {
ans[i].first = pos - 1;
continue;
}
LL len = 0;
if (p->op[0] == '+') {
len = strlen(p->pt);
} else {
len = (p->b - p->a + 1) * p->c;
}
for (auto& kv : ans) {
auto& pp = kv.second;
if (pp.first == -1 || pp.first < pos) {
// do nothing
} else if (pos <= pp.first && pp.first < pos + len) {
if (p->op[0] == '+') {
pp.second = p->pt[pp.first - pos];
pp.first = -1;
} else {
pp.first = p->a - 1 + (pp.first - pos) % (p->b - p->a + 1);
}
} else {
pp.first -= len;
}
}
}
for (auto& kv : ans) {
printf("%c\n", kv.second.second);
}
}
return 0;
}
五、Minimum Spanning Tree
题意：给一个图，边的权重是a + b * x。
问 x 分别取值 [l, r]时，所有图中最小生成树边和的最小值。
思路：什么是最小生成树？所有的树里面边和最小的树，假设有 k 个树。
这里 x 可以取值 [l, r]，树的个数就是 (r-l+1)*k 个。
所有树的边和都是关于 x 的方程，即A + B * x 线段，且有 k 条。
图上画出线段，可以发现对于[l,r]得到的最小生成树的值是上凸包。
既然是凸包，那最优值就是在两个端点。
所以只需要求 x 为 l 和 r 时的最小生成树即可。
六、最后
这个热身赛的题除了前三题，其他的都有一定难度。
第二题是枚举题，第三题是随便搞题，第四题是经典的字符串题，第五题是图论题。
做完这次的热身赛，发现两个问题。
第一是比赛是英文的，对理解题意有很大的挑战。
第二是比赛会有几何题和图论题，我擅长的是比如线段树、动态规划、搜索等。
如果比赛遇到几何题和图论题，我就只好看过的人了，不多就不看题了。
思考题：字符串题的做法你见过吗？
加油，算法人。
《完》
-EOF-
本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code
本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。
