题解 | 2023年天梯赛省赛模拟赛
L1-1 嫑废话上代码
题目
Linux 之父 Linus Torvalds 的名言是：“Talk is cheap. Show me the code.”（嫑废话，上代码）。本题就请你直接在屏幕上输出这句话。
输入格式：
本题没有输入。
输出格式：
在一行中输出 Talk is cheap. Show me the code.。
输入样例：
无
输出样例：
Talk is cheap. Show me the code.
思路
直接输出即可
参考代码(c++)
#include <bits/stdc++.h>
using namespace std;
int main() {
cout<<"Talk is cheap. Show me the code.";
}
L1-2 九牛一毛
题目
这是一道脑筋急转弯题：猪肉一斤 15 元，鸡肉一斤 20 元，那么一毛钱能买多少头牛？
答案是：9 —— 因为“九牛一毛”。
本题就请你按照这个逻辑，计算一下 N 块钱能买多少斤猪肉、多少斤鸡肉、多少头牛。
输入格式：
输入在一行中给出一个不超过 1000 的正整数 N，即以“元”为单位的货币量。
输出格式：
在一行中顺序输出 N 块钱能买多少斤猪肉、多少斤鸡肉、多少头牛。三个数字都只取整数部分，其间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
18
输出样例：
1 0 1620
思路
猪肉和鸡肉除价格，牛肉乘90就行
参考代码(c++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
cout<<n/15<<" "<<n/20<<" "<<n*90;
}
L1-3 小孩子才做选择，大人全都要
题目
阿汪面前有两只盲盒，每只盒子打开都有两种可能：或者装了 X 克狗粮，或者是一只容量为 Y 克的狗粮储蓄盒。如果是狗粮，阿汪可以快乐地吃掉；如果是空储蓄盒，那就倒霉了，阿汪必须想办法找到狗粮把这只储蓄盒装满，自己还吃不到。
正当阿汪发愁不知道该怎么选的时候，铲屎官大手一挥：“小孩子才做选择，大人全都要！”但全都要的结果，却不一定是赚了还是亏了……
我们假设聪明的阿汪总是能嗅出狗粮最多的盒子，并且绝不会选任何储蓄盒。而铲屎官没有这样的鼻子，他一定是全都要。铲屎官如果打开了有储蓄盒的盒子，就必须想办法把储蓄盒装满，他会优先用另一只盒子里的狗粮装（如果另外一只盒子里有狗粮），不够了还得自己去买新的狗粮，这样阿汪可就亏啦，什么都吃不到了。本题就请你判断阿汪到底是赚了还是亏了。
输入格式：
输入在一行中给出两个整数，绝对值都不超过 100，中间用一个空格分开，分别代表两只盒子里的东西。如果是正数就表示是狗粮的份量，如果是负数就表示绝对值是空盆的容量。两个数都肯定不是 0，因为保证没有空盒子。
输出格式：
第一行输出两个结果：如果让阿汪选能吃到的狗粮 A，和如果铲屎官全都要能吃到的狗粮 B。两个数字间用一个空格分开。如果铲屎官的决定让阿汪赚到了，就在第二行输出一个笑脸 ^_^，否则输出一个哭脸 T_T。但如果反正什么都吃不到（两个盒子里都没有狗粮），就输出一张躺平脸 -_-。
输入样例 1：
12 18
输出样例 1：
18 30
^_^
输入样例 2：
12 -18
输出样例 2：
12 0
T_T
思路
这题属于阅读理解题，看懂了其实非常好做。
换种方式来解释题目：
你妈给你两个包裹，里面可能是红包或欠费单
你一眼就能看出哪个里面是大钱包，但是你妈非让你选两个
那你自己判断一下，你只拿一个和两个都拿两种的情况
你妈让你拿两个，那相比较自己拿的那一个，究竟是赚钱了还是亏钱了
结果：
-
两个都是钱包，血赚啊！
输出：大钱包的钱 两个钱包的钱 ^_^ -
两个都是欠费单，不论拿一个还是两个到手都没有钱，躺平了！
输出：0 0 -_- -
一个是钱包，一个是欠费单，但是钱包钱多一点，两个都拿 比 只拿钱包 少了好多钱，所以亏了，但是到手还有一丢丢
输出：钱包的钱 钱包付完欠费单剩下的钱 T_T -
一个是钱包，一个是欠费单，但是欠费单钱多一点，两个都拿 比 只拿钱包 少了好多钱，所以亏了，没有到手的钱了
输出：钱包的钱 0 T_T
参考代码(c++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m;
cin>>n>>m;
int t=n;
if(n<m) t=m;
if(n>0&&m>0){
cout<<t<<" "<<n+m<<endl<<"^_^";
}else if(n<0&&m<0){
cout<<"0 0"<<endl<<"-_-";
}else if(n+m>0){
cout<<t<<" "<<n+m<<endl<<"T_T";
}else{
cout<<t<<" 0"<<endl<<"T_T";
}
}
L1-4 拯救外星人
题目
你的外星人朋友不认得地球上的加减乘除符号，但是会算阶乘 —— 正整数 N 的阶乘记为 “N!”，是从 1 到 N 的连乘积。所以当他不知道“5+7”等于多少时，如果你告诉他等于“12!”，他就写出了“479001600”这个答案。
本题就请你写程序模仿外星人的行为。
输入格式：
输入在一行中给出两个正整数 A 和 B。
输出格式：
在一行中输出 (A+B) 的阶乘。题目保证 (A+B) 的值小于 12。
输入样例：
3 6
输出样例：
362880
思路
ab相加，循环从1累乘到a+b就行
参考代码(c++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int a,b,res=1;
cin >> a >> b;
a+=b;
for (int i = 1; i <= a; i++) {
res*=i;
}
cout<<res;
}
L1-5 试试手气
题目
我们知道一个骰子有 6 个面，分别刻了 1 到 6 个点。下面给你 6 个骰子的初始状态，即它们朝上一面的点数，让你一把抓起摇出另一套结果。假设你摇骰子的手段特别精妙，每次摇出的结果都满足以下两个条件：
1、每个骰子摇出的点数都跟它之前任何一次出现的点数不同；
2、在满足条件 1 的前提下，每次都能让每个骰子得到可能得到的最大点数。
那么你应该可以预知自己第 n 次（1≤n≤5）摇出的结果。
输入格式：
输入第一行给出 6 个骰子的初始点数，即 [1,6] 之间的整数，数字间以空格分隔；第二行给出摇的次数 n（1≤n≤5）。
输出格式：
在一行中顺序列出第 n 次摇出的每个骰子的点数。数字间必须以 1 个空格分隔，行首位不得有多余空格。
输入样例：
3 6 5 4 1 4
3
输出样例：
4 3 3 3 4 3
样例解释：
这 3 次摇出的结果依次为：
6 5 6 6 6 6
5 4 4 5 5 5
4 3 3 3 4 3
思路
判断从6到6-n时会不会碰到初始点数。未碰到，则输出；碰到了，就跳过，再输出结果。
参考代码(c++)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,a[7]={0};
for (int i = 0; i < 6; i++) cin>>a[i];
cin>>n;
for(int i = 0; i < 6; i++){
if(a[i]>6-n){
cout<<6-n;
}else{
cout<<6-n+1;
}
if(i!=6){
cout<<" ";
}
}
}
L1-6 打PTA
题目
传说这是集美大学的学生对话。本题要求你做一个简单的自动问答机，对任何一个问句，只要其中包含 PTA 就回答 Yes!，其他一概回答 No.。
输入格式：
输入第一行给出一个整型范围内的正整数 N，随后 N 行，每行给出一个长度不超过 80 的字符串，为用户输入的句子，由英文字母、数字、空格和标点符号组成，以回车结束。
输出格式：
对每一行句子，如果其结尾字符为问号 ? 则判断此句中有无 PTA？如果有则在一行中输出 Yes!，否则输出 No.。如果不是问号结尾，则敷衍地回答 enen。
输入样例：
5
Hello!
Do you still play WZRY?
Chi Ji?
you play PTA ah?
how about pta site?
输出样例：
enen
No.
No.
Yes!
No.
思路
用字符串取值，使用getline可以取一行的值（包括空格），再判断最后一个字符是否是问号，然后使用find()函数判断有无 PTA 字符串。
PS：如若使用size()函数需注意其返回的是无符号数值，可能会对最终结果有影响，建议强转或赋值int类型使用。
参考代码(c++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s, c = "PTA";
cin >> n;
getchar();
for (int i = 0; i < n; i++) {
getline(cin, s);
if (s[s.size() - 1] == '?') {
if (s.find(c) != -1) {
cout << "Yes!" << endl;
} else {
cout << "No." << endl;
}
} else {
cout << "enen" << endl;
}
}
}
L1-7 机工士姆斯塔迪奥
题目
在 MMORPG《最终幻想14》的副本“乐欲之所瓯博讷修道院”里，BOSS 机工士姆斯塔迪奥将会接受玩家的挑战。
你需要处理这个副本其中的一个机制：N×M 大小的地图被拆分为了 N×M 个 1×1 的格子，BOSS 会选择若干行或/及若干列释放技能，玩家不能站在释放技能的方格上，否则就会被击中而失败。
给定 BOSS 所有释放技能的行或列信息，请你计算出最后有多少个格子是安全的。
输入格式:
输入第一行是三个整数 N,M,Q (1≤N×M≤10^5 ，0≤Q≤1000)，表示地图为 N 行 M 列大小以及选择的行/列数量。
接下来 Q 行，每行两个数 T i ,C i ，其中 T i =0 表示 BOSS 选择的是一整行，T i =1 表示选择的是一整列，C i 为选择的行号/列号。行和列的编号均从 1 开始。
输出格式:
输出一个数，表示安全格子的数量。
输入样例:
5 5 3
0 2
0 4
1 3
输出样例:
12
思路
去掉受攻击的行和列，剩下的行列相乘就是结果。
可以使用set集合处理，自动去重（代码更少）。
参考代码(c++) set集合写法
#include<bits/stdc++.h>
using namespace std;
set<int>a,b;
int main(){
int n,m,q,t,c;
cin>>n>>m>>q;
while(q--){
cin>>t>>c;
if(t==0){
a.insert(c);
}else{
b.insert(c);
}
}
cout<<(n-a.size())*(m-b.size());
}
参考代码(c++) 数组写法
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int n,m,q,t,c;
cin>>n>>m>>q;
int row[n+1]={0},column[m+1]={0};
while (q--) {
cin>>t>>c;
if(t==0){
if(row[c]==0){
row[c]=1;
n--;
}
}else{
if(column[c]==0){
column[c]=1;
m--;
}
}
}
cout<<n*m;
return 0;
}
L1-8 随机输一次
题目
大家应该都会玩“锤子剪刀布”的游戏：两人同时给出手势，胜负规则如图所示：
现要求你编写一个控制赢面的程序，根据对方的出招，给出对应的赢招。但是！为了不让对方意识到你在控制结果，你需要隔 K 次输一次，其中 K 是系统设定的随机数。
输入格式：
输入首先在第一行给出正整数 N（≤10），随后给出 N 个系统产生的不超过 10 的正随机数 { K 1 ,K 2 ,⋯,K N }，数字间以空格分隔。这意味着第 i（i=0,1,⋯,N−1）次输局之后应该隔 K i+1次再让下一个输局。如果对方出招太多，则随机数按顺序循环使用。例如在样例中，系统产生了 3 个随机数 {2, 4, 1}，则你需要：赢 2 次，输 1 次；赢 4 次，输 1 次；赢 1 次，输 1 次；然后再次回到第 1 个随机数，赢 2 次，输 1 次。
之后每行给出对方的一次出招：“ChuiZi”代表“锤子”、“JianDao”代表“剪刀”、“Bu”代表“布”。“End”代表输入结束，这一行不要作为出招处理。输入保证对方至少出了一招。
输出格式：
对每一个输入的出招，按要求输出赢或输局的招式。每招占一行。
输入样例：
3 2 4 1
ChuiZi
JianDao
Bu
JianDao
Bu
ChuiZi
ChuiZi
ChuiZi
JianDao
Bu
JianDao
Bu
ChuiZi
End
输出样例：
Bu
ChuiZi
ChuiZi
ChuiZi
JianDao
Bu
Bu
JianDao
ChuiZi
ChuiZi
ChuiZi
JianDao
JianDao
思路
可以提前用新的数组计算好间隔（比如1为赢，0为故意输）
在循环里根据新数组的值进行出招
参考代码(c++)
#include<bits/stdc++.h>
using namespace std;
int main()
{
string ss,s[4]={"JianDao","ChuiZi","Bu"};
int n;
cin>>n;
int a[n],b[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
b[0]=a[0]+1;
for(int i=1;i<n;i++){
b[i]=b[i-1]+a[i]+1;
}
int i=0,m=0;
while(1){
i++;
cin>>ss;
if(ss=="End"){
break;
}
if(i!=b[m]){
if(ss==s[0]){
cout<<s[1];
}else if(ss==s[1]){
cout<<s[2];
}else{
cout<<s[0];
}
}else{
if(ss==s[0]){
cout<<s[2];
}else if(ss==s[1]){
cout<<s[0];
}else{
cout<<s[1];
}
m++;
if(m>=n){
m=0;
i=0;
}
}
cout<<endl;
}
}
L2-1 插松枝
题目
人造松枝加工场的工人需要将各种尺寸的塑料松针插到松枝干上，做成大大小小的松枝。他们的工作流程（并不）是这样的：
每人手边有一只小盒子，初始状态为空。
每人面前有用不完的松枝干和一个推送器，每次推送一片随机型号的松针片。
工人首先捡起一根空的松枝干，从小盒子里摸出最上面的一片松针 —— 如果小盒子是空的，就从推送器上取一片松针。将这片松针插到枝干的最下面。
工人在插后面的松针时，需要保证，每一步插到一根非空松枝干上的松针片，不能比前一步插上的松针片大。如果小盒子中最上面的松针满足要求，就取之插好；否则去推送器上取一片。如果推送器上拿到的仍然不满足要求，就把拿到的这片堆放到小盒子里，继续去推送器上取下一片。注意这里假设小盒子里的松针片是按放入的顺序堆叠起来的，工人每次只能取出最上面（即最后放入）的一片。
当下列三种情况之一发生时，工人会结束手里的松枝制作，开始做下一个：
（1）小盒子已经满了，但推送器上取到的松针仍然不满足要求。此时将手中的松枝放到成品篮里，推送器上取到的松针压回推送器，开始下一根松枝的制作。
（2）小盒子中最上面的松针不满足要求，但推送器上已经没有松针了。此时将手中的松枝放到成品篮里，开始下一根松枝的制作。
（3）手中的松枝干上已经插满了松针，将之放到成品篮里，开始下一根松枝的制作。
现在给定推送器上顺序传过来的 N 片松针的大小，以及小盒子和松枝的容量，请你编写程序自动列出每根成品松枝的信息。
输入格式：
输入在第一行中给出 3 个正整数：N（≤10^3 ），为推送器上松针片的数量；M（≤20）为小盒子能存放的松针片的最大数量；K（≤5）为一根松枝干上能插的松针片的最大数量。
随后一行给出 N 个不超过 100 的正整数，为推送器上顺序推出的松针片的大小。
输出格式：
每支松枝成品的信息占一行，顺序给出自底向上每片松针的大小。数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
8 3 4
20 25 15 18 20 18 8 5
输出样例：
20 15
20 18 18 8
25 5
思路
使用队列queue存储推送器；栈stack存储盒子；容器vector存储松枝。
注意考虑多种情况。
参考代码(c++) 大佬写法
感谢南昌航空大学的编程大佬 @小小白？提供的代码和思路
// 算法标签：栈、列
// 思路：用栈、队列模拟插松针的过程
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
stack<int>s; // 小盒子
queue<int>q; // 推送器
vector<int>v[N]; // 松枝
int main() {
int n, m, k, songzhen, l = 0;
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
cin >> songzhen;
q.push(songzhen); // 将所有松枝放入推送器
}
while (!q.empty() || !s.empty()) { // 当推送器和小盒子中还有松针时继续插松针
while (v[l].size() < k) { // 松枝上松针数量少于k时
if (v[l].size() == 0) { // 松枝上没有松针时
if (!s.empty()) { // 小盒子不为空时，此时应从小盒子拿松针插入松枝
v[l].push_back(s.top());
s.pop();
} else { // 小盒子为空时，此时应从推送器拿松针插入松枝
v[l].push_back(q.front());
q.pop();
}
} else { // 松枝上有松针时
if (!s.empty() && s.top() <= v[l].back()) { // 小盒子不为空，且顶部松针不大于松枝上最后的松针时，从小盒子拿松针插入松枝
v[l].push_back(s.top());
s.pop();
} else { // 不能从小盒子拿松针放入松枝，就判断是否能够从推送器拿松针
if (!q.empty()
&& q.front() <= v[l].back()) { // 推送器不为空，且前部松针不大于松枝上最后的松针时，从推送器拿松针插入松枝
v[l].push_back(q.front());
q.pop();
} else { // 不能从推送器拿松针放入松枝，就判断是否能放入小盒子
while (!q.empty() && q.front() > v[l].back()
&& s.size() < m) { // 推送器不为空，前部松针大于松枝上最后的松针，且小盒子未满时，可以将推送器的松针放入小盒子
s.push(q.front()); // 将推送器的松针放入小盒子
q.pop();
}
if (s.size() == m && q.front() > v[l].back()) { // 小盒子已满，且推送器前部松针大于松枝上最后的松针
break; // 当前松枝结束，开始下一根松枝制作
}
if (q.empty()) { // 推送器的松针用完了
break; // 当前松枝结束，开始下一根松枝制作
}
// 此时推送器不为空，且前部松针不大于松枝上最后的松针，可以从推送器拿松针插入松枝
v[l].push_back(q.front());
q.pop();
}
}
}
}
l++; // 当前松枝结束，开始下一根松枝制作
}
for (int i = 0; i < l; i++) {
for (int j = 0; j < v[i].size(); j++) {
cout << v[i][j];
if (j != v[i].size() - 1) {
cout << " ";
}
}
cout << endl;
}
}
L2-2 老板的作息表
题目
新浪微博上有人发了某老板的作息时间表，表示其每天 4:30 就起床了。但立刻有眼尖的网友问：这时间表不完整啊，早上九点到下午一点干啥了？
本题就请你编写程序，检查任意一张时间表，找出其中没写出来的时间段。
输入格式：
输入第一行给出一个正整数 N，为作息表上列出的时间段的个数。随后 N 行，每行给出一个时间段，格式为：
hh:mm:ss - hh:mm:ss
其中 hh、mm、ss 分别是两位数表示的小时、分钟、秒。第一个时间是开始时间，第二个是结束时间。题目保证所有时间都在一天之内（即从 00:00:00 到 23:59:59）；每个区间间隔至少 1 秒；并且任意两个给出的时间区间最多只在一个端点有重合，没有区间重叠的情况。
输出格式：
按照时间顺序列出时间表中没有出现的区间，每个区间占一行，格式与输入相同。题目保证至少存在一个区间需要输出。
输入样例：
8
13:00:00 - 18:00:00
00:00:00 - 01:00:05
08:00:00 - 09:00:00
07:10:59 - 08:00:00
01:00:05 - 04:30:00
06:30:00 - 07:10:58
05:30:00 - 06:30:00
18:00:00 - 19:00:00
输出样例：
04:30:00 - 05:30:00
07:10:58 - 07:10:59
09:00:00 - 13:00:00
19:00:00 - 23:59:59
思路
将一天的开始时间记为"00:00:00";结束时间记为"23:59:59"。
把每段的开始时间和结束时间放入结构体，对结构体进行排序。
对比上一段的结束时间是否等于当前的开始时间。如果是，则时间连续；反之，时间不连续，输出上一段的结束时间和当前的开始时间。
参考代码(c++)
#include<bits/stdc++.h>
using namespace std;
struct node{
string begin,end;
}no[100001];
bool cmp(node a,node b){
return b.begin>a.begin;
}
int main()
{
string b="00:00:00",e="23:59:59";
char c;
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>no[i].begin>>c>>no[i].end;
}
sort(no,no+n,cmp);
if(no[0].begin!=b){
cout<<b<<" - "<<no[0].begin<<endl;
}
for(int i=1;i<n;i++){
if(no[i].begin!=no[i-1].end){
cout<<no[i-1].end<<" - "<<no[i].begin<<endl;
}
}
if(no[n-1].end!=e){
cout<<no[n-1].end<<" - "<<e<<endl;
}
}
L2-3 智能护理中心统计
题目
智能护理中心系统将辖下的护理点分属若干个大区，例如华东区、华北区等；每个大区又分若干个省来进行管理；省又分市，等等。我们将所有这些有管理或护理功能的单位称为“管理结点”。现在已知每位老人由唯一的一个管理结点负责，每个管理结点属于唯一的上级管理结点管辖。你需要实现一个功能，来统计任何一个管理结点所负责照看的老人的数量。
注意这是一个动态问题，即随时可能有老人加入某个管理结点，并且老人是有可能从一个管理结点换到另一个管理结点去的。
输入格式：
输入在第一行中给出 2 个正整数：N（≤10^4 ）是老人的总数量，即老人们从 1 到 N 编号；M（≤10^5 ）是归属关系的总数。
接下来是 M 行，每行给出一对归属关系，格式为：
A B
表示 A 归属于 B。A 或 B 如果是某个管理结点，则用不超过 4 个大写英文字母表示其名称；如果是某位老人，则用老人的编号表示。这里每个 A 保证只有唯一的上级归属 B，且只有这个中心系统本身是没有上级归属的。此外，输入保证没有老人自己承担管理结点的角色，即 B 一定是一个管理结点，不可能是老人的编号。但一个管理结点既可以管辖下级结点，也可以直接护理一部分老人。
随后每行给出一个指令，格式为：
指令 内容
如果 指令 为 T，则表示有老人要入院或转院，内容 是某老人的编号和要去的管理结点的名称，以空格分隔；如果 指令 为 Q，则 内容 是一个管理结点的名称，意思是统计这个结点所负责照看的老人的数量；如果 指令 为 E，则表示输入结束。题目保证指令总数不会超过 100 个。
输出格式：
对每个 T 指令，将对应的老人转存到对应的管理结点名下；对每个 Q 指令，在一行中输出对应管理结点所负责照看的老人的数量。读到 E 指令就结束程序。
输入样例：
10 23
EAST CNTR
ZJ EAST
SD EAST
WEST CNTR
SX WEST
HZ ZJ
JN SD
2 JN
8 JTH
6 XAHP
4 ZDYH
5 ZDYH
ZDYH HZ
HUZ ZJ
JX ZJ
1 JX
3 JN
WZ ZJ
XAHP XIAN
XIAN SX
YL SX
JTH XIAN
7 XAHP
Q EAST
T 1 YL
Q EAST
Q SX
T 8 ZDYH
Q HZ
Q HUZ
T 10 XAHP
Q CNTR
E
输出样例：
5
4
4
3
0
9
思路
使用map处理结点。
参考代码(c++) 网上写法
//老人为叶子节点，考虑到每次只有叶子节点的变化
//所以只需要贪心计算叶子节点对对应的这条链的贡献即可
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
map<string, int> mp;
vector<int> G[maxn]; // 用二维vector存储管理结点之间的关系
int Index = 1, N, M; // c++中使用index变量报错，要么换index变量名，要么不用万能头
int peo[maxn]; // peo[i] 记入i 管理节点 老人的数量
int fa[maxn];// 老人所在的管理节点
int get(string s) { // 将字符串对应为数字
if (mp[s]) { // 当前字符串已经在map里，直接返回
return mp[s];
} else { // 当前字符串不在map里，开map的下一个空间进行存储 字符串 和 对应Index值
mp[s] = Index++;
return mp[s];
}
}
int dfs(int pos) {
int res = peo[pos];
// 使用深搜来计算结点下所有子节点之和
for (auto u : G[pos]) {
res += dfs(u);
}
return res;
}
int main() {
cin >> N >> M;
while (M--) {
string a, b;
cin >> a >> b;
int x = get(a); // 调用自定义函数get()使用map将字符串对应为数字
int y = get(b); // 同上
// cout << "x: " << x << " y: " << y << endl;
if (a[0] >= '0' && a[0] <= '9') { // 判断输入的是否为数字，是的话则为老人
peo[y]++; // 老人所在结点 负责照看的老人的数量++
fa[x] = y; // 指定老人的 父结点
} else {
G[y].push_back(x); // 用二维vector存储管理结点之间的关系
}
}
char opt;
while (cin >> opt) {
if (opt == 'E')
break;
string w, des;
if (opt == 'Q') { // 统计这个结点所负责照看的老人的数量
cin >> w;
int res = dfs(get(w));
cout << res << "\n";
} else if (opt == 'T') {
cin >> w >> des; // 老人的编号和要去的管理结点的名称
int id = get(w);
int dd = get(des);
peo[fa[id]]--; // 转出 老人所在原结点 负责照看的老人的数量--
fa[id] = dd; // 指定老人的 父结点
peo[dd]++; // 转入
}
}
}
参考代码(c++) 大佬解法
#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
using namespace std;
unordered_map<string, string>father; //老人的父管理结点
unordered_map<string, vector<string> >mp; //管理结点下的所有子节点
unordered_map<string, int>num; //当前结点的管理老人数量
int n, m;
int bfs(string s) {
queue<string>q;
q.push(s);
//sum用来存储管理结点s的管理老人数量
int sum = 0;
//只要队列中还有结点就继续
while (q.size()) {
string s1 = q.front(); //获取当前管理结点
q.pop();
sum += num[s1]; //加上当前结点的管理老人数量
//搜索当前管理结点的子节点
for (int i = 0; i < mp[s1].size(); i++) {
q.push(mp[s1][i]);
}
}
//返回管理结点s的管理老人数量
return sum;
}
int main() {
cin >> n >> m;
while (m--) {
string a, b;
cin >> a >> b;
//如果a是管理结点
if (a[0] >= 'A' && a[0] <= 'Z') {
//将a加入管理结点b中去
mp[b].push_back(a);
} else {
//如果a是老人
//将老人的父节点设为管理节点b
father[a] = b;
//将管理结点b的管理老人数量加1
num[b]++;
}
}
char c;
while (cin >> c) {
if (c == 'E')
break;
string a, b;
if (c == 'T') {
//如果老人要转院或入院
cin >> a >> b;
//如果老人有父节点，将父节点的管理老人数量减1
if (father[a] != "")
num[father[a]]--;
//将老人的父节点设置为b
father[a] = b;
//将管理节点b的管理老人数量加1
num[b]++;
} else if (c == 'Q') {
//如果要统计管理结点管理老人数量
cin >> a;
cout << bfs(a) << endl;
}
}
return 0;
}
参考代码(c++) 队友解法
#include <bits/stdc++.h>
using namespace std;
const int MAX = 5e5;
//v[i]：哈希索引为i的下级管理节点列表
vector<int> v[MAX];
//cnt[i]：哈希索引为i的管理节点所管理的老人数
//belong[i]：编号为i的老人所属管理节点的哈希值
int cnt[MAX], belong[MAX];
int N, M, Ahashcode, Bhashcode, Anum, judge, conhashcode, res, orma, oldnum;
string A, B, ins, con;
//isdigit(c)：将字符c转数字
int isdigit(char c) {
return c >= 48 && c <= 57;
}
//toHashcode(s)：将字符串映射成一个哈希值
int toHashCode(string s) {
int code = 0;
int len = s.length();
for (int i = 0; i < len; i++) {
code = code + (s[i] - 'A' + 1) * pow(26, len - i - 1);
}
return code;
}
//tonum(s)：将字符串s转为数字
int tonum(string s) {
int num = 0;
int len = s.length();
for (int i = 0; i < len; i++) {
num = num + (s[i] - '0') * pow(10, len - i - 1);
}
return num;
}
//初始化操作
void initial() {
// 将每个老人的从属节点都初始化为-1，表示没有从属节点
for (int i = 0; i < MAX; i++) {
belong[i] = -1;
}
//初始化v、belong和cnt
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> A >> B;
Bhashcode = toHashCode(B);
judge = isdigit(A[0]);
//如果输入内容是老人-管理节点
if (judge == 1) {
Anum = tonum(A);
belong[Anum] = Bhashcode;
cnt[Bhashcode]++;
} else {
Ahashcode = toHashCode(A);
v[Bhashcode].push_back(Ahashcode);
}
}
}
//跑一遍dfs得到总的管理老人数
//可以这么理解，dfs(code)：哈希值为code的节点所管理的老人数
//一个管理节点的老人数 = 其直接管理的老人数 + 下级管理节点管理老人数之和（间接管理老人数），写成dfs的形式就是：dfs(code) = cnt[code] + dfs(其下级列表所有节点)，（txt不好写逻辑表达式，凑合着看吧）
int dfs(int code) {
int total = 0;
for (int i = 0; i < v[code].size(); i++) {
total = total + dfs(v[code][i]);
}
total = total + cnt[code];
return total;
}
//处理指令函数
void solve() {
cin >> ins;
while (ins != "E") {
//查询指令跑一遍dfs，T指令迁移老人等价于更新belong和cnt
if (ins == "Q") {
cin >> con;
conhashcode = toHashCode(con);
res = dfs(conhashcode);
cout << res << endl;
} else {
cin >> oldnum >> con;
conhashcode = toHashCode(con);
orma = belong[oldnum];
if (orma != -1) {
cnt[orma]--;
}
belong[oldnum] = conhashcode;
cnt[conhashcode]++;
}
cin >> ins;
}
}
signed main(void) {
initial();
solve();
}
L2-4 大众情人
题目
人与人之间总有一点距离感。我们假定两个人之间的亲密程度跟他们之间的距离感成反比，并且距离感是单向的。例如小蓝对小红患了单相思，从小蓝的眼中看去，他和小红之间的距离为 1，只差一层窗户纸；但在小红的眼里，她和小蓝之间的距离为 108000，差了十万八千里…… 另外，我们进一步假定，距离感在认识的人之间是可传递的。例如小绿觉得自己跟小蓝之间的距离为 2，则即使小绿并不直接认识小红，我们也默认小绿早晚会认识小红，并且因为跟小蓝很亲近的关系，小绿会觉得自己跟小红之间的距离为 1+2=3。当然这带来一个问题，如果小绿本来也认识小红，或者他通过其他人也能认识小红，但通过不同渠道推导出来的距离感不一样，该怎么算呢？我们在这里做个简单定义，就将小绿对小红的距离感定义为所有推导出来的距离感的最小值。
一个人的异性缘不是由最喜欢他/她的那个异性决定的，而是由对他/她最无感的那个异性决定的。我们记一个人 i 在一个异性 j 眼中的距离感为 D ij ；将 i 的“异性缘”定义为 1/max j∈S(i) {D ij }，其中 S(i) 是相对于 i 的所有异性的集合。那么“大众情人”就是异性缘最好（值最大）的那个人。
本题就请你从给定的一批人与人之间的距离感中分别找出两个性别中的“大众情人”。
输入格式：
输入在第一行中给出一个正整数 N（≤500），为总人数。于是我们默认所有人从 1 到 N 编号。
随后 N 行，第 i 行描述了编号为 i 的人与其他人的关系，格式为：
性别 K 朋友1:距离1 朋友2:距离2 …… 朋友K:距离K
其中 性别 是这个人的性别，F 表示女性，M 表示男性；K（<N 的非负整数）为这个人直接认识的朋友数；随后给出的是这 K 个朋友的编号、以及这个人对该朋友的距离感。距离感是不超过 10^6 的正整数。
题目保证给出的关系中一定两种性别的人都有，不会出现重复给出的关系，并且每个人的朋友中都不包含自己。
输出格式：
第一行给出自身为女性的“大众情人”的编号，第二行给出自身为男性的“大众情人”的编号。如果存在并列，则按编号递增的顺序输出所有。数字间以一个空格分隔，行首尾不得有多余空格。
输入样例：
6
F 1 4:1
F 2 1:3 4:10
F 2 4:2 2:2
M 2 5:1 3:2
M 2 2:2 6:2
M 2 3:1 2:5
输出样例：
2 3
4
思路
使用floyd处理数据（涉及到计算距离，多源最短路径）
找出每个人所有异性到他的最大距离并记录
再找所有最大距离的 最小值
为什么是从最大中找最小呢？
因为 i 的“异性缘”定义为 1/max j∈S(i) {D ij } ，要使异性缘最大，则只需要max j∈S(i) {D ij }最小
参考代码(c++) 大佬解法
感谢南昌航空大学的编程大佬 @小小白？提供的代码和思路
#include<iostream>
#include<vector>
using namespace std;
const int N = 510;
int g[N][N],sex[N],d[N];
int main()
{
int n;
scanf("%d",&n);
//floyd初始化
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j) g[i][j]=0;
else g[i][j]=1e9;
for(int i=1;i<=n;i++){
char op;
int k;
scanf(" %c %d",&op,&k);
if(op=='F') sex[i]=1;//女生
else sex[i]=2;//男生
for(int j=1;j<=k;j++){
int a,b;
scanf("%d:%d",&a,&b);
g[i][a]=b;
}
}
//求每个人到其他人的最短距离 floyd
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
//如果是异性才统计
if(sex[i]!=sex[j])
//找到最大距离
d[i]=max(d[i],g[j][i]); //这里是g[j][i]，因为是对方到自己的距离
int d1=1e9,d2=1e9;//d1,表示女 d2,表示男
for(int i=1;i<=n;i++){
if(sex[i]==2) d1=min(d1,d[i]);//找男对女的最小距离 ,即男性的"大众情人"
else d2=min(d2,d[i]);//找女对男的最小距离 ,即女性的 "大众情人"
}
vector<int> a,b;
for(int i=1;i<=n;i++){
if(sex[i]==2){//男性的"大众情人"
if(d[i]==d1)
b.push_back(i);
}else{//女性的"大众情人"
if(d[i]==d2)
a.push_back(i);
}
}
printf("%d",a[0]);
for(int i=1;i<(int)a.size();i++)
printf(" %d",a[i]);
puts("");
printf("%d",b[0]);
for(int i=1;i<(int)b.size();i++)
printf(" %d",b[i]);
return 0;
}
查看9道真题和解析
联想公司氛围 558人发布