buctoj-2023寒假集训-进阶训练赛（十六）

问题 A: [蓝桥杯2022初赛] 数位排序

题目描述
小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。
当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。
例如，2022 排在 409 前面，因为2022 的数位之和是6，小于 409 的数位之和13。
又如，6 排在 2022 前面，因为它们的数位之和相同，而 6 小于 2022。
给定正整数n，m，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元素是多少？

输入
输入第一行包含一个正整数n。
第二行包含一个正整数m。
30% 的评测用例，1 ≤ m ≤ n ≤ 300。
50% 的评测用例，1 ≤ m ≤ n ≤ 1000。
100%的评测用例，1 ≤ m ≤ n ≤ 10^6。

输出
输出一行包含一个整数，表示答案。

样例输入

13
5

样例输出

3

提示
1到13的排序为：1, 10, 2, 11, 3, 12, 4, 13, 5, 6, 7, 8, 9。第5个数为3。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 1000010;
PII v[N];
int Vei_sum(int n){
	int sum = 0;
	while(n){
		sum += n % 10;
		n /= 10;
	}
	return sum;
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	
	for(int i = 1; i <= n; i ++){
		v[i].first = Vei_sum(i);
		v[i].second = i;
	}
	sort(v + 1, v + n + 1);
	printf("%d", v[m].second);
	return 0;
}

问题 B: [蓝桥杯2018初赛]全球变暖

题目描述
你有一张某海域NxN像素的照片，".“表示海洋、”#"表示陆地，如下所示：

. . . . . . .
. # # . . . .
. # # . . . .
. . . . # # .
. . # # # # .
. . . # # # .
. . . . . . .

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。
具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：

. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . # . .
. . . . . . .
. . . . . . .

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。

输出
一个整数表示答案。

样例输入

7 
.......
.##....
.##....
....##.
..####.
...###.
....... 

样例输出

1

思路：上下左右的都为陆地的陆地不会被淹没，有该种陆地的岛屿不会被完全淹没。对于每块岛屿检查是否有该种陆地，具体看注释

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
queue<PII> q;
//(0,1),(1,0),(0,-1),(-1,0)分别表示 从该点坐标上下左右移动所增加的坐标分量 
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; 
int n, ans;
char g[N][N];
bool us[N][N];

//每次进入BFS会遍历完与该点连通的整个岛屿
int BFS(int a,int b){
	q.push({a, b});//将该点入队并标记用过 
	us[a][b] = 1;
	
	int subm = 1;//该块陆地是否被完全淹没 
	while(q.size()){
		PII t = q.front();
		q.pop();
		
		bool sea = false;//判断一块陆地是否靠海
		//如果上下左右都不靠海则该点不会被淹没，则该块陆地不会被完全淹没 
		int tx = t.first, ty = t.second;
		for(int i = 0; i < 4; i ++){
			int x = tx + dx[i], y = ty + dy[i];
			if(x >= 1 && x <= n && y >= 1 && y <= n && !us[x][y]){
				if(g[x][y] == '#'){
					q.push({x, y});
					us[x][y] = 1;
				}else sea = true;
			}
		}
		if(!sea) subm = 0;
	}
	return subm;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) scanf("%s", g[i] + 1);
	
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= n; j ++) 
			if(g[i][j]=='#' && !us[i][j]) ans += BFS(i, j);
	
	else printf("%d", ans);
	return 0;
}

问题 C: 发工资

题目描述
假如每位老师的工资都知道，最少需要准备多少张人民币，才能在给每位老师发工资的时候都不用老师找零呢？
这里假设老师的工资都是正整数，单位元，人民币一共有100元、50元、10元、5元、2元、1元6种。
输入
输入数据包括多个测试样例，每个测试样例的第一行是一个整数n（n<100），表示老师的人数，然后是n位老师的工资。
n=0表示输入的结束，不做处理。
输出
对于每个测试样例输出一个整数x，表示至少需要准备的人民币张数。每个输出占一行
样例输入

3
1 2 3
0

样例输出

4

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

int main()
{
	int m;
	while(cin >> m){
		if(m == 0) break;
		LL res = 0;
		while(m --){
			int n;
			scanf("%d", &n);
			res += n / 100;
			n %= 100;
			res += n / 50;
			n %= 50;
			res += n / 10;
			n %= 10;
			res += n / 5;
			n %= 5;
			res += n / 2;
			n %= 2;
			res += n;
		}
		printf("%d\n", res);		
	}
	return 0; 
}

问题 D: 看病要排队

题目描述
看病要排队这个是地球人都知道的常识。
不过经过细心的0068的观察，他发现了医院里排队还是有讲究的。0068所去的医院有三个医生（汗，这么少）同时看病。而看病的人病情有轻重，所以不能根据简单的先来先服务的原则。所以医院对每种病情规定了10种不同的优先级。级别为10的优先权最高，级别为1的优先权最低。医生在看病时，则会在他的队伍里面选择一个优先权最高的人进行诊治。如果遇到两个优先权一样的病人的话，则选择最早来排队的病人。
现在就请你帮助医院模拟这个看病过程。

输入
输入数据包含多组测试，请处理到文件结束。
每组数据第一行有一个正整数N(0<N<2000)表示发生事件的数目。
接下来有N行分别表示发生的事件。
一共有两种事件：
1:“IN A B”,表示有一个拥有优先级B的病人要求医生A诊治。(0<A<=3,0<B<=10)
2:“OUT A”,表示医生A进行了一次诊治，诊治完毕后，病人出院。(0<A<=3)

输出
对于每个"OUT A"事件，请在一行里面输出被诊治人的编号ID。如果该事件时无病人需要诊治，则输出"EMPTY"。
诊治人的编号ID的定义为：在一组测试中，"IN A B"事件发生第K次时，进来的病人ID即为K。从1开始编号。

样例输入

7
IN 1 1
IN 1 2
OUT 1
OUT 2
IN 2 1
OUT 2
OUT 1
2
IN 1 1
OUT 1

样例输出

2
EMPTY
3
1
1

思路：优先权从大到小排序，优先权相等的编号从小到大排序

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

bool Sort_idx(PII a,PII b){
	if(a.first == b.first) return a.second > b.second;
	else return a.first < b.first;
}

int main()
{
	int m;
	while(cin >> m){
		int idx = 0;
		vector<PII> v[4];
		while(m --){
			char op[4];
			int a, b;
			scanf("%s", op);
			if(*op == 'I'){
				scanf("%d%d", &a, &b);
				PII t;
				t.second = ++ idx;
				t.first = b;
				v[a].push_back(t);
			}else{
				scanf("%d", &a);
				sort(v[a].begin(), v[a].end());
				sort(v[a].begin(), v[a].end(), Sort_idx);
				if(v[a].empty()) printf("EMPTY\n");
				else{
					PII t = v[a].back();
					v[a].pop_back();
					printf("%d\n", t.second);
				} 
			}
		}		
	}
	return 0; 
}

问题 E: Oil Deposits

题目描述
GeoSurvComp地质调查公司负择探测地下石油矿床。该公司一次处理一个大的矩形区域，并创建一个网格，将土地划分为许多正方形地块。然后，它分别分析每个地块，使用传感设备来确定地块中是否含有石油。一块含有石油的地块叫作油田。如果两块油田相邻，则它们属于同一个油田区。石油储量可能相当大，并可能包含许多油田。你的工作是确定个网格中有多少不同的油田区。
输入
输入包含一个或多个网格。每个网格开始一行是空格分隔的 m和n，它们分别是网格的行 数和列数。 如果m=0，则表示输入结束；否则1≤m≤100, 1≤n≤100。 接下来是m行，每行有n个字符(不包括行尾字符)。每个字符对应一个地块，“ * ” 表示没有油:“ @ ”表示油田。
输出
对于每个网格，输出不同的油田区数量并换行。如果水平、垂直或对角相邻，则两块不同的油田是于一-个油田区。油田区数量不超过100个。
样例输入

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

样例输出

0
1
2
2

思路：处理方法与B一样，比B简单

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 105;
char g[N][N];
int us[N][N];
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int n, m;

void BFS(int a,int b){
	queue<PII> q;
	q.push({a, b});
	us[a][b] = 1;
	
	while(q.size()){
		PII t = q.front();
		q.pop();
		
		for(int i = 0; i < 8; i ++){
			int x = t.first + dx[i], y = t.second + dy[i];
			if(x >= 1 && x <= n && y >= 1 && y <= m && !us[x][y] && g[x][y] == '@'){
				q.push({x, y});
				us[x][y] = 1;
			}  
		}
	} 
}

int main()
{
	while(cin >> n >> m){
		if(n == 0 && m == 0) break;
		for(int i = 1; i <= n; i ++) cin >> g[i] + 1;
		
		memset(us, 0, sizeof us);
		int res = 0;
		for(int i = 1; i <= n; i ++)
			for(int j = 1; j <= m; j ++)
				if(g[i][j] == '@' && !us[i][j]){
					BFS(i, j);
					res ++;
				}
	
		cout << res << endl;			
	}
	return 0; 
}

问题 F: 免费馅饼

题目描述
都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：
(没有图，大概是一个人在一个0到10的坐标轴上）

为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼）

输入
输入数据有多组。每组数据的第一行为以正整数n(0<n<100000)，表示有n个馅饼掉在这条小径上。在结下来的n行中，每行有两个整数 x,T (0<T<100000),表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。n=0时输入结束。
输出
每一组输入数据对应一行输出。输出一个整数m，表示gameboy最多可能接到m个馅饼。
提示：本题的输入数据量比较大，建议用scanf读入，用cin可能会超时。

样例输入

6
5 1
4 1
6 1
7 2
7 2
8 3
0

样例输出

4

思路：将时间转化成x，坐标转化成y，每组数据转化成一个二维数组，f[x][y]表示在x时间y点掉下馅饼。问题转化成从最后一行走到第0行，每次能走到左斜上方，上方，右斜上方三个位置，求到f[0][5]路径最大值。转化成典型的dp问题。
ssn：不太理解的dp的可以先搜搜数字三角形

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int f[N][11];
int n;

int main()
{
	while(scanf("%d", &n)){
		if(n == 0) break;
		int end = 0;//表示该轮数据最后一个时间点 
		memset(f, 0, sizeof f);		
		while(n --){
			int t, x;
			scanf("%d%d", &x, &t);
			f[t][x] ++;
			end = max(end, t);
		}	
		
		for(int i = end - 1; i >= 0; i -- )
			for(int j = 0; j <= 10; j ++ ){
				if(j == 0) f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
				else if(j == 10) f[i][j] += max(f[i + 1][j - 1], f[i + 1][j]);
				else f[i][j] += max(f[i + 1][j], max(f[i + 1][j - 1], f[i + 1][j + 1])); 
			}
			
		printf("%d\n", f[0][5]);	
	}
	return 0; 
}

问题 G: 打怪兽version-3

题目描述
有N只怪兽的血量为Hi
你现在有2个技能
技能1:选择一个怪兽i,使其血量降低1点
技能2:选择一个怪兽i,使其血量变为0
问你需要使用多少个1技能可以杀死所有怪兽(其血量小于等于0即为死亡)
特别的,技能2只能使用K次
输入
N K

…

1 <= k <= 2e5
1<= N <=2e5
1 <=
<= 1e9
输出
需要使用多少个1技能可以杀死所有怪兽
样例输入

3 1
4 1 5

样例输出

5

思路：血量最多的怪兽用技能2，其他都用技能1

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
int n, k, a[N];
LL sum;

int main()
{
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
	
	sort(a, a + n);
	for(int i = 0; i < n - k; i ++) sum += a[i];
	printf("%lld", sum);
	return 0; 
}

问题 H: 2.4.1 间谍

题目描述
X 国的情报委员受到一份可靠的消息，信息表明 Y 国将派间谍去窃取 X 国的机密文件。X 国指挥官手中有两份名单列表，一份是 Y 国派往 X 国的间谍名单列表，另一份是 X 国以前派往 Y 国的间谍名单。这两份名单列表可能有些重叠。因为间谍可能同时扮演两个角色，称之“双重间谍”。因此，Y 国可以把双重间谍送回 X 国。很明显，这对 X 国是有利的，因为双重间谍可以把 Y 国的机密文件带回，而不必担心在 Y 国边境被拘留。所以指挥官决定抓住由 Y 国派出的间谍，让普通人和双重间谍进入。那么你能确定指挥官需要抓捕的间谍名单吗？
输入
有多组测试数据。
每组数据由四部分组成：
第一部分包含 3 个整数 A、B、C，分别代表进入边境的人数、Y 国将派出的间谍人数，X 国以前派到 Y 国的间谍人数。
第二部分包含 A 个字符串，为进入边境的人员名单。
第三部分包含 B 个字符串，为由 Y 国派出的间谍名单。
第四部分包含 C 个字符串，即双重间谍的名单。
在一份名单中不会有名字重复，如果有重复的名字出现在两份名单中，则表示同一人。
姓名字符串长度不超过 10，
各名单列表最多 500 人。

输出
按照列表 B 的出现顺序输出指挥官要抓捕的间谍名单。
如果不应抓捕任何人，则输出 “No enemy spy”。
样例输入

8 4 3
Zhao  Qian Sun Li Zhou Wu Zheng Wang
Zhao Qian Sun Li
Zhao Zhou Zheng
2 2 2
Zhao Qian
Zhao Qian
Zhao Qian

样例输出

Qian Sun Li
No enemy spy

思路：A $\cap$ B $\cap$ ~C

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n, m, k;
	while(cin >> n >> m >> k){
		vector<string> a, b, c;
		for(int i = 0; i < n; i ++){
			string s;
			cin >> s;
			a.push_back(s);
		}
		for(int i = 0; i < m; i ++){
			string s;
			cin >> s;
			b.push_back(s);
		}
		for(int i = 0; i < k; i ++){
			string s;
			cin >> s;
			c.push_back(s);
		}
		stack<string> S;
		while(b.size()){
			string t = b.back();
			b.pop_back();
			auto it1 = find(a.begin(), a.end(), t);
			auto it2 = find(c.begin(), c.end(), t);
			if(it1 != a.end() && it2 == c.end()) S.push(t);
		}
		if(S.empty()) printf("No enemy spy\n");
		else{
			while(S.size()){
				cout << S.top() << ' ';
				S.pop();
			}
			printf("\n");
		}
	}
	return 0; 
}

问题 I: 2.4.2 Web导航

题目描述
标准的 Web 浏览器包含在最近访问过的页面中向后和向前移动的功能。实现这些特性的一种方法是使用两个栈来跟踪前后移动可以到达的页面。支持以下命令。
BACK：将当前页面推到前向栈的顶部。从后向栈的顶部弹出页面，使其成为新的当前页面。如果后向栈为空，则忽略该命令。
FORWARD：将当前页面推到后向栈的顶部。从前向栈顶部弹出页面，使其成为新的当前页面。如果前向栈为空，则忽略该命令。
VISIT：将当前页面推到后向栈的顶部，使得 URL 成为新的当前页面，前向栈清空。
QUIT：退出浏览器。
假设浏览器的最初页面为 URL

***###.acm.org/

(对 “http://” 用 “***” 代替，对 “www” 用 “###” 代替)。
输入
输入是一系列 BACK、FORWARD、VISIT、QUIT 命令。
输出
对于除了 QUIT 外的每个命令，如果不忽略该命令，则在执行该命令后单行输出当前页的 URL，否则输出 “Ignored”。
QUIT 命令没有输出。

样例输入

VISIT ***acm.ashland.edu/
VISIT ***acm.baylor.edu/acmicpc/
BACK
BACK
BACK
FORWARD
VISIT ***###.ibm.com/
BACK
BACK
FORWARD
FORWARD
FORWARD
QUIT

样例输出

***acm.ashland.edu/
***acm.baylor.edu/acmicpc/
***acm.ashland.edu/
***###.acm.org/
Ignored
***acm.ashland.edu/
***###.ibm.com/
***acm.ashland.edu/
***###.acm.org/
***acm.ashland.edu/
***###.ibm.com/
Ignored

提示
URL 没有空白，最多有 70 个字符。
任何时候，在每个栈中都不会超过 100 个元素。
QUIT 命令表示输入结束。

#include<bits/stdc++.h>
using namespace std;
stack<string> F, B;
int main()
{
	char op[10];
	string cur = "***###.acm.org/";
	while(scanf("%s", op)){
		if(*op == 'Q') break;
		else if(*op == 'V'){
			B.push(cur);
			cin >> cur;
			cout << cur << endl;
			while(F.size()) F.pop();
		}else if(*op == 'B'){
			if(B.empty()) printf("Ignored\n");
			else{
				F.push(cur);
				cur = B.top();
				B.pop();
				cout << cur << endl;						
			}
		}else if(*op == 'F'){
			if(F.empty()) printf("Ignored\n");
			else{
				B.push(cur);
				cur = F.top();
				F.pop();
				cout << cur << endl;			
			}
		}
	}
	return 0; 
}

问题 J: 2.4.3 骑士移动

题目描述
写程序，计算象棋中马从一个位置移动到另一个位置所需的最少移动次数。
输入
有多组测试数据。
第一行一个整数 T，代表数据组数。
每组数据包含三行。
第一行表示棋盘的长度 L，棋盘大小为 L×L。
第二行包含两个整数 x, y，表示马的起始位置坐标。
第三行包含两个整数 a, b，表示马的终点位置坐标。
L 最大为 300。
棋盘坐标范围为 [0, …, L-1]。

输出
对于每组数据输出一行，包含一个数字，即最少移动次数。
若起点终点相同，则移动次数为 0。
样例输入

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

样例输出

5
28
0

提示
马走日！！！
数据保证可以到终点，不用额外判断无法走到终点的情况。
思路：bfs求最短路。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 300;
//建议找个网格纸画画算坐标，凭空想很容易就错了 
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1}, dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int n, endx, endy;//把重点设置成全局变量就不用传了 
bool us[N][N];//标记该点是否用过 
int dis[N][N];//dis[i][j]表示从起点到（i,j)的距离 

int bfs(int a,int b){
	queue<PII> q;
	q.push({a, b});
	us[a][b] = 1;
	dis[a][b] = 0;
	
	while(q.size()){
		PII t = q.front();
		q.pop();
		if(t.first == endx && t.second == endy) return dis[t.first][t.second];
		for(int i = 0; i < 8; i ++ ){
			int x = t.first + dx[i], y = t.second + dy[i];
			if(x >= 0 && x < n && y >= 0 && y < n && !us[x][y]){
				q.push({x, y});
				us[x][y] = 1;
				dis[x][y] = dis[t.first][t.second] + 1;
			}
		}
	}
	return 0;
}

int main()
{
	int t;
	cin >> t;
	while(t --){
		cin >> n;
		//多组数据注意初始化问题 
		memset(us, 0, sizeof us);
		memset(dis, 0, sizeof dis);
		int x, y;
		cin >> x >> y >> endx >> endy;
		cout << bfs(x, y) << endl;
	}
	return 0; 
}

问题 K: 衔尾之蚯蚓

题目描述
众所周知，蚯蚓剁成两半之后还能再生，那么重生之后的蚯蚓，它的头和尾是怎么定义的呢？小编也不知道。
现在我们从不大于N的正整数中取出两个数A和B
当A和B以10为基数，并且没有前导零时，A的最后一位数字等于B的第一位，A的第一位数字等于B的最后一位数字。这样就算得上一对合格的蚯蚓（？）
给你一个正整数N，求出这种合格的数对的数量。
输入
N
1≤N≤2×105
输出
符合条件的（A，B）的数量
样例输入
25
样例输出
17
提示
样例说明：
(1,1),(1,11),(2,2),(2,22),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9),(11,1),(11,11),(12,21),(21,12),(22,2),(22,22)
ssn：开始我想的也是n^2的循环怎么去值，看到了一个大佬的绝妙想法

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int res, n;
int a[10][10]; //a[i][j] 表示头为i，尾为j的数有几个 

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ){
		int x = to_string(i)[0] - '0';
		int y = i % 10;
		a[x][y] ++; 
	}
	
	for(int i = 1; i <= 9; i ++ )
		for(int j = 1; j <= 9; j ++ )
			res += a[i][j] * a[j][i];
	
	cout << res;
	return 0; 
}