2023年团体程序设计天梯赛（含部分题解）
目录
个人总结
今年的天梯赛相比于去年确实是简单了，但依旧未能保住175的国三个奖（弱校勿喷），最终因为L2-2题干意思看的过于粗略导致代码敲完后发现不太对劲从而浪费了不少时间，最终还是没能A掉L2-2以150+结束今年的天梯赛，发现天梯赛的题好像就是有点在玩文字游戏，光读题就耗费了不少时间，不同于其他平台的OJ，也有可能是我个人对题意的理解有偏差吧，总之感觉天梯赛的题目就是又臭又长还难理解，明年应该还会参加天梯赛，希望那时候能拿个个人国奖
L1-1 最好的文档（模拟）
有一位软件工程师说过一句很有道理的话：“Good code is its own best documentation.”（好代码本身就是最好的文档）。本题就请你直接在屏幕上输出这句话。
输入格式：
本题没有输入。
输出格式：
在一行中输出 Good code is its own best documentation.。
输入样例：
无
输出样例：
Good code is its own best documentation.
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
cout << "Good code is its own best documentation." << endl;
system("pause");
return 0;
}L1-2 什么是机器学习（模拟）
什么是机器学习？上图展示了一段面试官与“机器学习程序”的对话：
面试官：9 + 10 等于多少？
答：3
面试官：差远了，是19。
答：16
面试官：错了，是19。
答：18
面试官：不，是19。
答：19
本题就请你模仿这个“机器学习程序”的行为。
输入格式：
输入在一行中给出两个整数，绝对值都不超过 100，中间用一个空格分开，分别表示面试官给出的两个数字 A 和 B。
输出格式：
要求你输出 4 行，每行一个数字。第 1 行比正确结果少 16，第 2 行少 3，第 3 行少 1，最后一行才输出 A+B 的正确结果。
输入样例：
9 10
输出样例：
3
16
18
19
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a, b, sum;
cin >> a >> b;
sum = a + b;
cout << sum - 16 << endl;
cout << sum - 3 << endl;
cout << sum - 1 << endl;
cout << sum << endl;
system("pause");
return 0;
}L1-3 程序员买包子（模拟）
这是一条检测真正程序员的段子：假如你被家人要求下班顺路买十只包子，如果看到卖西瓜的，买一只。那么你会在什么情况下只买一只包子回家？
本题要求你考虑这个段子的通用版：假如你被要求下班顺路买 N 只包子，如果看到卖 X 的，买 M 只。那么如果你最后买了 K 只包子回家，说明你看到卖 X 的没有呢？
输入格式：
输入在一行中顺序给出题面中的 N、X、M、K，以空格分隔。其中 N、M 和 K 为不超过 1000 的正整数，X 是一个长度不超过 10 的、仅由小写英文字母组成的字符串。题目保证 N != M。
输出格式：
在一行中输出结论，格式为：
- 如果 K=N，输出
mei you mai X de； - 如果 K=M，输出
kan dao le mai X de； - 否则输出
wang le zhao mai X de.
其中X是输入中给定的字符串 X。
输入样例1：
10 xigua 1 10
输出样例1：
mei you mai xigua de
输入样例2：
10 huanggua 1 1
输出样例2：
kan dao le mai huanggua de
输入样例3：
10 shagua 1 250
输出样例3：
wang le zhao mai shagua de
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, m, k;
string x;
cin >> n >> x >> m >> k;
if (k == n) cout << "mei you mai " << x << " de" << endl;
else if (k == m) cout << "kan dao le mai " << x << " de" << endl;
else cout << "wang le zhao mai " << x << " de" << endl;
system("pause");
return 0;
}L1-4 进化论（模拟）
在“一年一度喜剧大赛”上有一部作品《进化论》，讲的是动物园两只猩猩进化的故事。猩猩吕严说自己已经进化了 9 年了，因为“三年又三年”。猩猩土豆指出“三年又三年是六年呐”……
本题给定两个数字，以及用这两个数字计算的结果，要求你根据结果判断，这是吕严算出来的，还是土豆算出来的。
输入格式：
输入第一行给出一个正整数 N，随后 N 行，每行给出三个正整数 A、B 和 C。其中 C 不超过 10000，其他三个数字都不超过 100。
输出格式：
对每一行给出的三个数，如果 C 是 A×B，就在一行中输出 Lv Yan；如果是 A+B，就在一行中输出 Tu Dou；如果都不是，就在一行中输出 zhe du shi sha ya!。
输入样例：
3
3 3 9
3 3 6
3 3 12
输出样例：
Lv Yan
Tu Dou
zhe du shi sha ya!
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i, n;
vector<string>res;
string item1 = "Lv Yan", item2 = "Tu Dou", item3 = "zhe du shi sha ya!";
cin >> n;
for (i = 0; i < n; i++) {
int a, b, c;
cin >> a >> b >> c;
if (a * b == c) res.push_back(item1);
else if (a + b == c) res.push_back(item2);
else res.push_back(item3);
}
for (i = 0; i < res.size(); i++) {
cout << res[i] << endl;
}
system("pause");
return 0;
}L1-5 猜帽子游戏（模拟）
宝宝们在一起玩一个猜帽子游戏。每人头上被扣了一顶帽子，有的是黑色的，有的是黄色的。每个人可以看到别人头上的帽子，但是看不到自己的。游戏开始后，每个人可以猜自己头上的帽子是什么颜色，或者可以弃权不猜。如果没有一个人猜错、并且至少有一个人猜对了，那么所有的宝宝共同获得一个大奖。如果所有人都不猜，或者只要有一个人猜错了，所有宝宝就都没有奖。
下面顺序给出一排帽子的颜色，假设每一群宝宝来玩的时候，都是按照这个顺序发帽子的。然后给出每一群宝宝们猜的结果，请你判断他们能不能得大奖。
输入格式：
输入首先在一行中给出一个正整数 N（2<N≤100），是帽子的个数。第二行给出 N 顶帽子的颜色，数字 1 表示黑色，2 表示黄色。
再下面给出一个正整数 K（≤10），随后 K 行，每行给出一群宝宝们猜的结果，除了仍然用数字 1 表示黑色、2 表示黄色之外，0 表示这个宝宝弃权不猜。
同一行中的数字用空格分隔。
输出格式：
对于每一群玩游戏的宝宝，如果他们能获得大奖，就在一行中输出 Da Jiang!!!，否则输出 Ai Ya。
输入样例：
5
1 1 2 1 2
3
0 1 2 0 0
0 0 0 0 0
1 2 2 0 2
输出样例：
Da Jiang!!!
Ai Ya
Ai Ya
思路： 可以定义一个bool型变量flag用来记录是否有答错的，count记录总弃权人数，最终综合判断即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i, j, k, n;
cin >> n;
vector<int>nums(n, 0);
vector<string>res;
for (i = 0; i < n; i++) {
cin >> nums[i];
}
cin >> k;
for (i = 0; i < k; i++) {
bool flag = true;
int count = 0;
for (j = 0; j < n; j++) {
int x;
cin >> x;
if (x == 0) {
count++;
continue;
}
if (x != nums[j]) flag = false;
}
if (count < n && flag) res.push_back("Da Jiang!!!");
else res.push_back("Ai Ya");
}
for (i = 0; i < res.size(); i++) {
cout << res[i] << endl;
}
system("pause");
return 0;
}L1-6 剪切粘贴（模拟）
使用计算机进行文本编辑时常见的功能是剪切功能（快捷键：Ctrl + X）。请实现一个简单的具有剪切和粘贴功能的文本编辑工具。
工具需要完成一系列剪切后粘贴的操作，每次操作分为两步：
- 剪切：给定需操作的起始位置和结束位置，将当前字符串中起始位置到结束位置部分的字符串放入剪贴板中，并删除当前字符串对应位置的内容。例如，当前字符串为
abcdefg，起始位置为 3，结束位置为 5，则剪贴操作后， 剪贴板内容为cde，操作后字符串变为abfg。字符串位置从 1 开始编号。 - 粘贴：给定插入位置的前后字符串，寻找到插入位置，将剪贴板内容插入到位置中，并清除剪贴板内容。例如，对于上面操作后的结果，给定插入位置前为
bf，插入位置后为g，则插入后变为abfcdeg。如找不到应该插入的位置，则直接将插入位置设置为字符串最后，仍然完成插入操作。查找字符串时区分大小写。
每次操作后的字符串即为新的当前字符串。在若干次操作后，请给出最后的编辑结果。
输入格式：
输入第一行是一个长度小于等于 200 的字符串 S，表示原始字符串。字符串只包含所有可见 ASCII 字符，不包含回车与空格。
第二行是一个正整数 N (1≤N≤100)，表示要进行的操作次数。
接下来的 N 行，每行是两个数字和两个长度不大于 5 的不包含空格的非空字符串，前两个数字表示需要剪切的位置，后两个字符串表示插入位置前和后的字符串，用一个空格隔开。如果有多个可插入的位置，选择最靠近当前操作字符串开头的一个。
剪切的位置保证总是合法的。
输出格式：
输出一行，表示操作后的字符串。
输入样例：
AcrosstheGreatWall,wecanreacheverycornerintheworld
5
10 18 ery cor
32 40 , we
1 6 tW all
14 18 rnerr eache
1 1 e r
输出样例：
he,allcornetrrwecaneacheveryGreatWintheworldAcross
思路：利用C++STL的string容器内的string::substr()取子串操作和string::find()查找子串操作以及string::insert()插入操作即可轻松解决，这里需要注意一下的是在插入的过程中我们需要将插入字符串的前后字符串综合到一块来考虑，在插入的时候下标加上对应前置子串的长度即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i, j, k, n;
string s;
cin >> s >> n;
for (i = 0; i < n; i++) {
int a, b;
string s1, s2;
cin >> a >> b >> s1 >> s2;
string item = s.substr(a - 1, b - a + 1);
s = s.substr(0, a - 1) + s.substr(b, s.length() - b);
string s3 = s1 + s2;
int index = s.find(s3);
if (index == -1) s += item;
else {
s.insert(index + s1.length(), item);
}
}
cout << s << endl;
system("pause");
return 0;
}L1-7 分寝室（模拟）
学校新建了宿舍楼，共有 n 间寝室。等待分配的学生中，有女生 n0 位、男生 n1 位。所有待分配的学生都必须分到一间寝室。所有的寝室都要分出去，最后不能有寝室留空。
现请你写程序完成寝室的自动分配。分配规则如下：
- 男女生不能混住；
- 不允许单人住一间寝室；
- 对每种性别的学生，每间寝室入住的人数都必须相同；例如不能出现一部分寝室住 2 位女生，一部分寝室住 3 位女生的情况。但女生寝室都是 2 人一间，男生寝室都是 3 人一间，则是允许的；
- 在有多种分配方案满足前面三项要求的情况下，要求两种性别每间寝室入住的人数差最小。
输入格式：
输入在一行中给出 3 个正整数 n0、n1、n，分别对应女生人数、男生人数、寝室数。数字间以空格分隔，均不超过 105。
输出格式：
在一行中顺序输出女生和男生被分配的寝室数量，其间以 1 个空格分隔。行首尾不得有多余空格。
如果有解，题目保证解是唯一的。如果无解，则在一行中输出 No Solution。
输入样例1：
24 60 10
输出样例1：
4 6
注意：输出的方案对应女生都是 24/4=6 人间、男生都是 60/6=10 人间，人数差为 4。满足前三项要求的分配方案还有两种，即女生 6 间（都是 4 人间）、男生 4 间（都是 15 人间）；或女生 8 间（都是 3 人间）、男生 2 间（都是 30 人间）。但因为人数差都大于 4 而不被采用。
输入样例2：
29 30 10
输出样例2：
No Solution
思路：对每个寝室数量进行枚举模拟判断即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i, j, k;
int n0, n1, n;
cin >> n0 >> n1 >> n;
int res_a = 0, res_b = 0, minn = INT_MAX;
for (i = 1; i < n; i++) {
if (n0 % i == 0 && n1 % (n - i) == 0 && n0 != i && n1 != (n - i)) {
int item1 = n0 / i;
int item2 = n1 / (n - 1);
if (abs(item1 - item2) < minn) {
minn = abs(item1 - item2);
res_a = i, res_b = n - i;
}
}
}
if (res_a == 0 && res_b == 0) cout << "No Solution" << endl;
else cout << res_a << " " << res_b << endl;
system("pause");
return 0;
}L1-8 谁管谁叫爹（模拟）
《咱俩谁管谁叫爹》是网上一首搞笑饶舌歌曲，来源于东北酒桌上的助兴游戏。现在我们把这个游戏的难度拔高一点，多耗一些智商。
不妨设游戏中的两个人为 A 和 B。游戏开始后，两人同时报出两个整数 NA 和 NB。判断谁是爹的标准如下：
- 将两个整数的各位数字分别相加，得到两个和 SA 和 SB。如果 NA 正好是 SB 的整数倍，则 A 是爹；如果 NB 正好是 SA 的整数倍，则 B 是爹；
- 如果两人同时满足、或同时不满足上述判定条件，则原始数字大的那个是爹。
本题就请你写一个自动裁判程序，判定谁是爹。
输入格式：
输入第一行给出一个正整数 N（≤100），为游戏的次数。以下 N 行，每行给出一对不超过 9 位数的正整数，对应 A 和 B 给出的原始数字。题目保证两个数字不相等。
输出格式：
对每一轮游戏，在一行中给出赢得“爹”称号的玩家（A 或 B）。
输入样例：
4
999999999 891
78250 3859
267537 52654299
6666 120
输出样例：
B
A
B
A
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i, j, k, n;
cin >> n;
vector<char>res;
for (i = 0; i < n; i++) {
int a, b, sum_a = 0, sum_b = 0, num_a, num_b;
cin >> a >> b;
num_a = a, num_b = b;
while (a) {
sum_a += a % 10;
a /= 10;
}
while (b) {
sum_b += b % 10;
b /= 10;
}
if (num_a % sum_b == 0 && num_b % sum_a == 0 || num_a % sum_b != 0 && num_b % sum_a != 0) {
if (num_a > num_b) res.push_back('A');
else res.push_back('B');
} else {
if (num_a % sum_b == 0) res.push_back('A');
else res.push_back('B');
}
}
for (i = 0; i < res.size(); i++) {
cout << res[i] << endl;
}
system("pause");
return 0;
}L2-1 堆宝塔（栈）
堆宝塔游戏是让小朋友根据抓到的彩虹圈的直径大小，按照从大到小的顺序堆起宝塔。但彩虹圈不一定是按照直径的大小顺序抓到的。聪明宝宝采取的策略如下：
- 首先准备两根柱子，一根 A 柱串宝塔，一根 B 柱用于临时叠放。
- 把第 1 块彩虹圈作为第 1 座宝塔的基座，在 A 柱放好。
- 将抓到的下一块彩虹圈 C 跟当前 A 柱宝塔最上面的彩虹圈比一下，如果比最上面的小，就直接放上去；否则把 C 跟 B 柱最上面的彩虹圈比一下：
-
- 如果 B 柱是空的、或者 C 大，就在 B 柱上放好；
-
- 否则把 A 柱上串好的宝塔取下来作为一件成品；然后把 B 柱上所有比 C 大的彩虹圈逐一取下放到 A 柱上，最后把 C 也放到 A 柱上。
重复此步骤，直到所有的彩虹圈都被抓完。最后 A 柱上剩下的宝塔作为一件成品，B 柱上剩下的彩虹圈被逐一取下，堆成另一座宝塔。问：宝宝一共堆出了几个宝塔？最高的宝塔有多少层？
输入格式：
输入第一行给出一个正整数 N（≤103），为彩虹圈的个数。第二行按照宝宝抓取的顺序给出 N 个不超过 100 的正整数，对应每个彩虹圈的直径。
输出格式：
在一行中输出宝宝堆出的宝塔个数，和最高的宝塔的层数。数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
11
10 8 9 5 12 11 4 3 1 9 15
输出样例：
4 5
样例解释：
宝宝堆成的宝塔顺次为：
- 10、8、5
- 12、11、4、3、1
- 9
- 15、9
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i, j, k, n, count = 0;
cin >> n;
vector<int>nums(n, 0);
for (i = 0; i < n; i++) {
cin >> nums[i];
}
int maxx = INT_MIN;
stack<int>st1, st2;
for (i = 0; i < n; i++) {
if (st1.empty() || st1.top() > nums[i]) st1.push(nums[i]);
else {
if (st2.empty() || st2.top() < nums[i]) st2.push(nums[i]);
else {
int ans = 0;
while (!st1.empty()) {
ans++;
st1.pop();
}
count++;
maxx = max(maxx, ans);
while (!st2.empty() && st2.top() > nums[i]) {
st1.push(st2.top());
st2.pop();
}
st1.push(nums[i]);
}
}
}
if (!st1.empty()) count++;
if (!st2.empty()) count++;
int ans = 0;
while (!st1.empty()) {
ans++;
st1.pop();
}
maxx = max(maxx, ans);
ans = 0;
while (!st2.empty()) {
ans++;
st2.pop();
}
maxx = max(maxx, ans);
cout << count << " " << maxx << endl;
system("pause");
return 0;
}L2-2 天梯赛的赛场安排（堆）
天梯赛使用 OMS 监考系统，需要将参赛队员安排到系统中的虚拟赛场里，并为每个赛场分配一位监考老师。每位监考老师需要联系自己赛场内队员对应的教练们，以便发放比赛账号。为了尽可能减少教练和监考的沟通负担，我们要求赛场的安排满足以下条件：
- 每位监考老师负责的赛场里，队员人数不得超过赛场规定容量 C；
- 每位教练需要联系的监考人数尽可能少 —— 这里假设每所参赛学校只有一位负责联系的教练，且每个赛场的监考老师都不相同。
为此我们设计了多轮次排座算法，按照尚未安排赛场的队员人数从大到小的顺序，每一轮对当前未安排的人数最多的学校进行处理。记当前待处理的学校未安排人数为 n：
- 如果 n≥C，则新开一个赛场，将 C 位队员安排进去。剩下的人继续按人数规模排队，等待下一轮处理；
- 如果 n<C，则寻找剩余空位数大于等于 n 的编号最小的赛场，将队员安排进去；
- 如果 n<C，且找不到任何非空的、剩余空位数大于等于 n 的赛场了，则新开一个赛场，将队员安排进去。
由于近年来天梯赛的参赛人数快速增长，2023年超过了 480 所学校 1.6 万人，所以我们必须写个程序来处理赛场安排问题。
输入格式：
输入第一行给出两个正整数 N 和 C，分别为参赛学校数量和每个赛场的规定容量，其中 0<N≤5000，10≤C≤50。随后 N 行，每行给出一个学校的缩写（为长度不超过 6 的非空小写英文字母串）和该校参赛人数（不超过 500 的正整数），其间以空格分隔。题目保证每所学校只有一条记录。
输出格式：
按照输入的顺序，对每一所参赛高校，在一行中输出学校缩写和该校需要联系的监考人数，其间以 1 空格分隔。
最后在一行中输出系统中应该开设多少个赛场。
输入样例：
10 30
zju 30
hdu 93
pku 39
hbu 42
sjtu 21
abdu 10
xjtu 36
nnu 15
hnu 168
hsnu 20
输出样例：
zju 1
hdu 4
pku 2
hbu 2
sjtu 1
abdu 1
xjtu 2
nnu 1
hnu 6
hsnu 1
16
思路：可以利用优先队列（最大堆）依次存放每个学校的参赛队员，依次对其进行判断，如果堆顶的人数小于赛场规定容量C，我们则将堆中的所有小于C的参赛队员存储到vector容器中依次进行遍历（双指针），将剩余人数进行凑齐，最终判断vector中无法凑齐的队员有几个赛场，对其进行额外分配即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i, j, k, n, c, ans = 0;
cin >> n >> c;
map<string, int>mp;
map<int, string>mp1;
vector<int>nums(n, 0);
vector<int>res(n, 0);
priority_queue<pair<int, string>>Q;
for (i = 0; i < n; i++) {
string s;
int x;
cin >> s >> x;
nums[i] = x;
mp[s] = i;
mp1[i] = s;
Q.push({x, s});
}
while (!Q.empty()) {
auto t = Q.top();
int N = t.first;
string name = t.second;
if (N >= c) {
N -= c;
res[mp[name]]++;
ans++;
Q.push({N, name});
} else break;
Q.pop();
}
vector<pair<int, string>>item;
while (!Q.empty()) {
auto t = Q.top();
if (t.first != 0)
item.push_back({t.first, t.second});
Q.pop();
}
for (i = 0, j = item.size() - 1; i < j; i++) {
bool flag = false;
while (i < j && item[i].first + item[j].first <= c) {
flag = true;
item[i].first += item[j].first;
item[j].first = 0;
res[mp[item[j].second]]++;
j--;
}
if (flag) {
item[i].first = 0;
res[mp[item[i].second]]++;
ans++;
}
}
for (i = 0; i < item.size(); i++) {
if (item[i].first != 0) {
res[mp[item[i].second]]++;
ans++;
}
}
for (i = 0; i < res.size(); i++) {
cout << mp1[i] << " " << res[i] << endl;
}
cout << ans << endl;
system("pause");
return 0;
}L2-3 锦标赛
有 2k 名选手将要参加一场锦标赛。锦标赛共有 k 轮，其中第 i 轮的比赛共有 2k−i 场，每场比赛恰有两名选手参加并从中产生一名胜者。每场比赛的安排如下：
- 对于第 1 轮的第 j 场比赛，由第 (2j−1) 名选手对抗第 2j 名选手。
- 对于第 i 轮的第 j 场比赛（i>1），由第 (i−1) 轮第 (2j−1) 场比赛的胜者对抗第 (i−1) 轮第 2j 场比赛的胜者。
第 k 轮唯一一场比赛的胜者就是整个锦标赛的最终胜者。
举个例子，假如共有 8 名选手参加锦标赛，则比赛的安排如下：
- 第 1 轮共 4 场比赛：选手 1 vs 选手 2，选手 3 vs 选手 4，选手 5 vs 选手 6，选手 7 vs 选手 8。
- 第 2 轮共 2 场比赛：第 1 轮第 1 场的胜者 vs 第 1 轮第 2 场的胜者，第 1 轮第 3 场的胜者 vs 第 1 轮第 4 场的胜者。
- 第 3 轮共 1 场比赛：第 2 轮第 1 场的胜者 vs 第 2 轮第 2 场的胜者。
已知每一名选手都有一个能力值，其中第 i 名选手的能力值为 ai。在一场比赛中，若两名选手的能力值不同，则能力值较大的选手一定会打败能力值较小的选手；若两名选手的能力值相同，则两名选手都有可能成为胜者。
令 li,j 表示第 i 轮第 j 场比赛 败者 的能力值，令 w 表示整个锦标赛最终胜者的能力值。给定所有满足 1≤i≤k 且 1≤j≤2k−i 的 li,j 以及 w，请还原出 a1,a2,⋯,an。
输入格式：
第一行输入一个整数 k（1≤k≤18）表示锦标赛的轮数。
对于接下来 k 行，第 i 行输入 2k−i 个整数 li,1,li,2,⋯,li,2k−i（1≤li,j≤109），其中 li,j 表示第 i 轮第 j 场比赛 败者 的能力值。
接下来一行输入一个整数 w（1≤w≤109）表示锦标赛最终胜者的能力值。
输出格式：
输出一行 n 个由单个空格分隔的整数 a1,a2,⋯,an，其中 ai 表示第 i 名选手的能力值。如果有多种合法答案，请输出任意一种。如果无法还原出能够满足输入数据的答案，输出一行 No Solution。
请勿在行末输出多余空格。
输入样例1：
3
4 5 8 5
7 6
8
9
输出样例1：
7 4 8 5 9 8 6 5
输入样例2：
2
5 8
3
9
输出样例2：
No Solution
提示：
本题返回结果若为格式错误均可视为答案错误。
（代码待补充）
L2-4 寻宝图（BFS+连通块）
给定一幅地图，其中有水域，有陆地。被水域完全环绕的陆地是岛屿。有些岛屿上埋藏有宝藏，这些有宝藏的点也被标记出来了。本题就请你统计一下，给定的地图上一共有多少岛屿，其中有多少是有宝藏的岛屿。
输入格式：
输入第一行给出 2 个正整数 N 和 M（1<N×M≤10^5），是地图的尺寸，表示地图由 N 行 M 列格子构成。随后 N 行，每行给出 M 位个位数，其中 0 表示水域，1 表示陆地，2-9 表示宝藏。
注意：两个格子共享一条边时，才是“相邻”的。宝藏都埋在陆地上。默认地图外围全是水域。
输出格式：
在一行中输出 2 个整数，分别是岛屿的总数量和有宝藏的岛屿的数量。
输入样例：
10 11
01000000151
11000000111
00110000811
00110100010
00000000000
00000111000
00114111000
00110010000
00019000010
00120000001
输出样例：
7 2
思路：迷宫问题板子题，具体板子详见，对迷宫依次进行遍历求连通块即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
vector<string>G;
vector<vector<bool>>visit;
typedef struct {
int x, y;
}point;
vector<pair<int, int>>dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int n, m;
bool bfs(int start_x, int start_y) {
bool flag = false;
visit[start_x][start_y] = true;
point start;
start.x = start_x;
start.y = start_y;
queue<point>Q;
Q.push(start);
while (!Q.empty()) {
auto t = Q.front();
int x = t.x, y = t.y;
int new_x, new_y;
for (auto & dir : dirs) {
new_x = x + dir.first;
new_y = y + dir.second;
if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < m) {
if (!visit[new_x][new_y] && G[new_x][new_y] != '0') {
if (G[new_x][new_y] != '1') flag = true;
visit[new_x][new_y] = true;
point p;
p.x = new_x;
p.y = new_y;
Q.push(p);
}
}
}
Q.pop();
}
return flag;
}
int main()
{
int i, j, k, count = 0, ans = 0;
cin >> n >> m;
G.resize(n, "");
visit.resize(n, vector<bool>(m, false));
for (i = 0; i < n; i++) {
cin >> G[i];
}
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
if (!visit[i][j] && G[i][j] != '0') {
bool flag1 = bfs(i, j);
bool flag2 = G[i][j] == '1' ? false : true;
if (flag1 || flag2) ans++;
count++;
}
}
}
cout << count << " " << ans << endl;
system("pause");
return 0;
}L3-1 超能力者大赛
知乎上有这样一个话题：“全世界范围内突然出现 666 个超能力者，击败对手就能获得对手的超能力，最终获胜者将如何自处？”
现在让我们来将这个超能力者大赛的规则具体化：给定 N 位超能力者（超能力者从 0 到 N−1 编号，你的编号为 0），分布在全世界 M 座城市中（城市从 0 到 M−1 编号），比赛从第 1 天开始，到第 D 天结束。每位超能力者有一个能力值 Ei（i=0,⋯,N−1）。
如果你的能力值大于等于对手的能力值，就可以将其击败，并且对方的能力值立刻直接累加到你的能力值上。但是，当你每次到达一座城市，击败一位对手后，就会惊动这座城市中所有剩下的超能力者（包括联盟）。这座城市中剩下的所有个体能力值小于等于你的超能力者就会立刻团结起来形成联盟，联盟的能力值等于所有联盟成员能力值的总和。联盟将从此作为一个整体进攻或防御你，你可将联盟等价地理解为一个超能力者，它还可能在后续的战斗中继续与其它弱小的同城选手或联盟合并。第二天，这个城市中任何能力值大于你的对手就会找上门来，而你为了自保，就只能赶紧离开这个城市……
此外，还有如下补充规定：
- 你每天只能进行 1 场战斗，击败一个超能力者（包括联盟），或者被一个能力值大于你的超能力者（包括联盟）击败。
- 比赛中间没有一天可以休息，你或者在战斗，或者在去往另一个城市的路上。
- 当你到达一个城市时，会在到达的第二天进行战斗。
- 当你结束战斗要离开这个城市时，是第二天开始出发。
下面我们为你设计一套贪心算法，就请你验证一下，这个算法能否让你得到这个大赛的冠军。算法步骤很简单：
- 第 1 步：从所有超能力者（包括联盟）中找出一个与自己能力值最接近、同时自己能够击败的对手，用最短时间去到对方的城市，在到达后第二天击败之；
- 第 2 步：如果该城市中没有能力值大于你的超能力者（包括联盟），按照规则逐一击败之；如果该城市中已经没有超能力者、或你第二天没有必胜把握，则回到第 1 步。
重复上述步骤，直到你：
- 击败了所有超能力者；或
- 你已经无路可逃（即剩下的所有超能力者的能力值都大于你）；或
- 比赛终止时间到。
第 1 步中有可能遇到多个符合条件的对手，并列情况下优先选最近的；距离也并列的情况下选途径城市最少的；再有并列就选城市编号最小的。
输入格式：
输入在第一行中给出 4 个正整数：N（≤10^5），为参加比赛的超能力者人数；M（≤200），为比赛涉及的城市数量；Me 为城市间直达通路的数量；D（≤1000）为比赛时长（以“天”为单位）。
随后 N 行，第 i 行（i=0,⋯,N−1）给出第 i 位参赛者的信息，格式为：
所在城市编号 能力值
其中能力值是不超过 1000 的正整数。
接下来是城市通路信息，分 Me 行，每行给出一对城市间的双向直接通路信息，格式为：
城市1 城市2 通行时间
其中通行时间为不超过 D/2 的正整数，以“天”为单位。题目保证每条道路的信息只出现一次，没有重复。
输出格式：
顺次输出你每一步的活动，每个活动占一行，格式为：
Get e at city on day d.
表示第 d 天在编号为 city 的城市击败了一个能力值为 e 的对手。
Move from city1 to city2.
表示从编号为 city1 的城市到达了编号为 city2 的城市。
WIN on day d with e!
表示在第 d 天成为唯一的赢家，此时你的能力值是 e
Lose on day d with e.
表示在第 d 天走投无路成为输家，此时你的能力值是 e。
Game over with e.
表示比赛结束你没能成为唯一赢家，此时你的能力值是 e。注意：比赛最后一天是先判断输赢，才判断结束的。即：如果最后一天剩下所有人都比你厉害，是判你输，而不是 Game over。
输入样例1：
17 8 14 40
1 10
2 22
0 3
5 18
6 10
1 5
3 106
7 18
5 10
0 27
4 18
7 10
4 10
0 5
3 85
4 8
3 9
5 6 1
5 2 1
5 0 5
5 3 6
6 2 8
6 3 3
6 0 2
2 0 2
2 3 1
0 3 4
1 0 1
1 3 1
1 4 3
1 7 3
输出样例1：
Move from 1 to 4.
Get 10 at 4 on day 4.
Move from 4 to 7.
Get 18 at 7 on day 11.
Get 10 at 7 on day 12.
Move from 7 to 0.
Get 27 at 0 on day 17.
Get 8 at 0 on day 18.
Move from 0 to 4.
Get 26 at 4 on day 23.
Move from 4 to 3.
Get 106 at 3 on day 28.
Get 94 at 3 on day 29.
Move from 3 to 2.
Get 22 at 2 on day 31.
Move from 2 to 5.
Get 18 at 5 on day 33.
Get 10 at 5 on day 34.
Move from 5 to 6.
Get 10 at 6 on day 36.
Move from 6 to 1.
Get 5 at 1 on day 40.
WIN on day 40 with 374!
样例1说明：
样例 1 描述了这样的战斗场景：
你作为 0 号选手，初始能力值为 10，位于 1 号城市。
与你能力值最接近的有 4 位选手，能力值都是 10，分别位于 4、5、6、7 号城市。他们距离你都是 3 天，其中途径城市最少的是 4、7 号城市，并列时选城市编号小的，所以选 4 号城市。于是你的第一个动作是 Move from 1 to 4.，在第 3 天到达了 4 号城市。
第 4 天你击败了 12 号选手，于是 Get 10 at 4 on day 4.，能力值增长为 20。此时 4 号城市中剩下的两人都打不过你，但他们组成能力值为 26 的联盟后，你就不行了，所以从第 5 天开始你要逃走。
下一个目标是与你最接近的能力值为 18 的两个选手，分别在 5、7 号城市。距离相等时选择中途只经过一个城市的 7 号城市，于是 Move from 4 to 7.，在第 10 天到达 7 号城市。
第 11 天你击败了 7 号选手，于是 Get 18 at 7 on day 11.，能力值增长为 38。此时该城市中剩下的 11 号选手打不过你，所以你在第 12 天击败这个人，Get 10 at 7 on day 12. 后能力值增长为 48。这时 7 号城市已经被你清空。
下一个目标是 0 号城市能力值为 27 的 9 号选手。你在第 16 天到达，然后 Get 27 at 0 on day 17.，同时该城市中剩下的两人组成联盟，但能力值一共只有 8，于是在第二天的战斗中被你消灭，Get 8 at 0 on day 18.。至此 0 号城市也被你清空，你的能力值达到了 83。
这时 4 号城市那个能力值为 26 的联盟成为你的下一个目标，你花了 4 天时间回到 4 号城市，Get 26 at 4 on day 23.，能力值涨到了 109。
以此类推，可得到剩余的结果。最终在比赛的最后一天 —— 第 40 天将 1 号城市清空，赢得了比赛。
输入样例2：
7 4 5 30
2 10
2 10
1 9
1 25
1 25
0 40
3 30
0 1 1
1 2 2
2 3 3
3 0 2
1 3 3
输出样例2：
Get 10 at 2 on day 1.
Move from 2 to 1.
Get 9 at 1 on day 4.
Lose on day 5 with 29.
输入样例3：
7 4 5 7
2 20
2 9
1 9
1 25
1 25
0 40
3 30
0 1 1
1 2 2
2 3 3
3 0 2
1 3 3
输出样例3：
Get 9 at 2 on day 1.
Move from 2 to 1.
Get 25 at 1 on day 4.
Get 34 at 1 on day 5.
Move from 1 to 0.
Get 40 at 0 on day 7.
Game over with 128.
（代码待补充）
L3-2 完美树
给定一棵有 N 个结点的树（树中结点从 1 到 N 编号，根结点编号为 1）。每个结点有一种颜色，或为黑，或为白。
称以结点 u 为根的子树是 好的，若子树中黑色结点与白色结点的数量之差的绝对值不超过 1。称整棵树是 完美树，若对于所有 1 ≤ i ≤ N，以结点 i 为根的子树都是好的。
你需要将整棵树变成完美树，为此你可以进行以下操作任意次（包括零次）：选择任意一个结点 i (1 ≤ i ≤ N)，改变结点 i 的颜色（若结点 i 目前是黑色则将其改为白色，若结点 i 目前是白色则将其改为黑色）。这次操作的代价为 Pi。
求将给定的树变为完美树的最小代价。
注：以结点 i 为根的子树，由结点 i 以及结点 i 的所有后代结点组成。
输入格式：
输入第一行为一个数 N (1≤N≤105)，表示树的结点个数。
接下来的 N 行，第 i 行的前三个数为 Ci,Pi,Ki (1≤Pi≤104,0≤Ki≤N)，分别表示树上编号为 i 的结点的初始颜色（0 为白色，1 为黑色）、变换颜色的代价及孩子结点的数量。紧跟着有 Ki 个数，为孩子结点的编号。数字均用一个空格隔开，所有的编号保证在 1 到 N 里，且不会有环。
数据中只包含一棵树。
输出格式：
输出一行一个数，表示将树 T 变为完美树的最小代价。
输入样例：
10
1 100 3 2 3 4
0 20 1 7
0 5 2 5 6
0 8 1 10
0 7 0
0 2 0
1 1 2 8 9
0 15 0
0 13 0
1 8 0
输出样例：
15
提示：
样例中最佳的方案是：将 9 号点和 6 号点从白色变为黑色，此时代价为 13 + 2 = 15。
（代码待补充）
L3-3 血染钟楼
九条可怜最近非常沉迷血染钟楼 —— 一款类狼人杀的身份推理类的游戏。在一局血染钟楼的游戏中，玩家们之间隐藏着一名"恶魔"，而所有善良玩家的目标就是将抽到恶魔身份的玩家绳之以法。
今天，九条可怜和她的小伙伴们开了一局 n+1 名玩家参与的游戏，可怜的编号是 0，其他玩家编号从 1 到 n。
可怜抽到的身份是占卜师，其技能如下（注意这儿和标准钟楼规则有出入）：
- 每个夜晚，你可以选择任意名玩家，并得知被选择的玩家中是否有恶魔。
- 有一名除你以外善良玩家始终被你的能力视为恶魔。
换句话说，在剩下的 n 名玩家中，存在着两名未知的玩家，如果这两名玩家均未被可怜选中，可怜就会得到信息 0，否则就会得到信息 1。
在抽到身份的时候，可怜就对游戏开始的前 m 个夜晚进行了规划：她打算在第 i 个夜晚选中编号在区间 [li,ri] 内的所有玩家。
因为血染钟楼的第一个夜晚通常比较漫长，所以可怜在百无聊赖之际开始了头脑风暴。如果一切顺利，在 m 晚之后，她将能得到 m 个 0 或 1 的信息，共有 2m 种不同的可能性。可怜想要知道在这些可能性中，有多少种结果是可能发生的且可以让她唯一确定被她技能识别的两名玩家。
输入格式：
第一行输入一个整数 t(1≤t≤10^3)，表示数据组数。
第二行输入两个整数 n,m(1≤n,m≤10^5)，表示可怜以外的玩家数量以及可怜规划的夜晚数量。
接下来 m 行每行两个整数 li,ri(1≤li≤ri≤n)，表示可怜的计划中在第 i 晚会被选中的玩家编号区间。
输入保证所有数据中满足 n>10^3 或 m>10^3 的数据不超过 5 组。
输出格式：
对于每组数据，输出一行一个整数，表示满足条件的可能性数量。答案可能很大，你只需要输出对 998244353 取模后的结果。
输入样例：
3
4 1
2 3
5 4
2 5
1 3
5 5
2 4
10 10
1 2
6 6
3 7
3 6
1 8
9 10
1 6
4 4
8 8
5 8
输出样例：
1
2
7
样例解释：
在第一组数据中，可怜得到的信息共有两种可能性：
- 得到的信息为 0，表明两名目标的玩家均不在区间 [2,3] 中，因此可以唯一确定他们的编号为 (1,4)。
- 得到的信息为 1，表明至少有一名目标的玩家在区间 [2,3] 中，此时共有四种可能性 (1,2),(1,3),(2,4),(3,4)，因此不能唯一确定。
在第二组数据中，满足要求的两种可能性如下所示： - 四天得到的信息依次为 1110，此时目标玩家的编号一定为 (1,5)。
- 四天得到的信息依次为 1011，此时目标玩家的编号一定为 (4,5)。
容易验证其他 14 种可能性均不满足条件。
（代码待补充）
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
38
0- 0
已为社区贡献2条内容
所有评论(0)