ACM | Inner PK 1
L1-6 斯德哥尔摩火车上的题
上图是新浪微博上的一则趣闻，是瑞典斯德哥尔摩火车上的一道题，看上去是段伪代码：
s = ''
a = '1112031584'
for (i = 1; i < length(a); i++) {
if (a[i] % 2 == a[i-1] % 2) {
s += max(a[i], a[i-1])
}
}
goto_url('www.multisoft.se/' + s)+
操作是连接两个字符串的意思。所以这道题其实是让大家访问网站
www.multisoft.se/112358（注意：比赛中千万不要访问这个网址！！！）。
当然，能通过上述算法得到 112358 的原始字符串
a
是不唯一的。本题就请你判断，两个给定的原始字符串，能否通过上述算法得到相同的输出？
输入格式：
输入为两行仅由数字组成的非空字符串，长度均不超过
10^4，以回车结束。
输出格式：
对两个字符串分别采用上述斯德哥尔摩火车上的算法进行处理。如果两个结果是一样的，则在一行中输出那个结果；否则分别输出各自对应的处理结果，每个占一行。题目保证输出结果不为空。
输入样例 1：
1112031584
011102315849
输出样例 1：
112358
输入样例 2：
111203158412334
12341112031584
输出样例 2：
1123583
112358
Code:
#include<stdio.h>
#include<string.h>
int main(){
char s1[10005];
char s2[10005];
scanf("%s",s1);
scanf("%s",s2);
char s11[10005];
char s22[10005];
char *cur;
cur=s11;
for(int i=1;i<strlen(s1);i++){
if(s1[i]%2==s1[i-1]%2){
*(cur++)=s1[i]>s1[i-1]?s1[i]:s1[i-1];
}
}
*cur='\0';
cur=s22;
for(int i=1;i<strlen(s2);i++){
if(s2[i]%2==s2[i-1]%2){
*(cur++)=s2[i]>s2[i-1]?s2[i]:s2[i-1];
}
}
*cur='\0';
if(strcmp(s11,s22)==0){
printf("%s\n",s11);
}else{
printf("%s\n%s\n",s11,s22);
}
return 0;
}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 行，每行两个数 Ti,Ci，其中 Ti=0 表示 BOSS 选择的是一整行，Ti=1 表示选择的是一整列，Ci 为选择的行号/列号。行和列的编号均从 1 开始。
输出格式:
输出一个数，表示安全格子的数量。
输入样例:
5 5 3
0 2
0 4
1 3输出样例:
12Code:
#include<stdio.h>
#include<string.h>
int main(){
int N,M,Q;
scanf("%d%d%d",&N,&M,&Q);
int line[100005],count_l=0;
int row[100005],count_r=0;
memset(line,0,sizeof(line));
memset(row,0,sizeof(row));
int temp1,temp2;
for(int i=0;i<Q;i++){
scanf("%d%d",&temp1,&temp2);
if(temp1==0 && temp2>=1){
if(line[temp2]==0 && temp2<=N){
line[temp2]=1;
count_l++;
}
}else if(temp1==1 && temp2>=1){
if(row[temp2]==0 && temp2<=M){
row[temp2]=1;
count_r++;
}
}
}
printf("%d\n",(N-count_l)*(M-count_r));
return 0;
}L1-8 静静的推荐
天梯赛结束后，某企业的人力资源部希望组委会能推荐一批优秀的学生，这个整理推荐名单的任务就由静静姐负责。企业接受推荐的流程是这样的：
只考虑得分不低于 175 分的学生； 一共接受 K
批次的推荐名单； 同一批推荐名单上的学生的成绩原则上应严格递增；
如果有的学生天梯赛成绩虽然与前一个人相同，但其参加过 PAT
考试，且成绩达到了该企业的面试分数线，则也可以接受。
给定全体参赛学生的成绩和他们的 PAT
考试成绩，请你帮静静姐算一算，她最多能向企业推荐多少学生？
输入格式：
输入第一行给出 3
个正整数：N（≤105）为参赛学生人数，K（≤5×103）为企业接受的推荐批次，S（≤100）为该企业的
PAT 面试分数线。
随后 N
行，每行给出两个分数，依次为一位学生的天梯赛分数（最高分 290）和 PAT
分数（最高分 100）。
输出格式：
在一行中输出静静姐最多能向企业推荐的学生人数。
输入样例：
10 2 90
203 0
169 91
175 88
175 0
175 90
189 0
189 0
189 95
189 89
256 100输出样例：
8样例解释：
第一批可以选择 175、189、203、256 这四个分数的学生各一名，此外 175 分 PAT 分数达到 90 分的学生和 189 分 PAT 分数达到 95 分的学生可以额外进入名单。第二批就只剩下 175、189 两个分数的学生各一名可以进入名单了。最终一共 8 人进入推荐名单。
Code未优化
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int stu[100000][3];
int compare_students(const void *a, const void *b) {
// 转换为指向 int 数组的指针
const int (*student_a)[2] = a;
const int (*student_b)[2] = b;
// 首先比较成绩
if ((*student_a)[0] == (*student_b)[0]) {
// 成绩相同，比较第二个标准
return (*student_a)[1] - (*student_b)[1];
} else {
// 成绩不同，按成绩排序
return (*student_a)[0] - (*student_b)[0];
}
}
int compare(const void *a,const void *b){
return (*(int *)a-*(int *)b);
}
void swap(int *a,int *b){
int t=*a;
*a=*b;
*b=t;
}
void swapstu(int j){
int temp;
temp=stu[j][0];
stu[j][0]=stu[j+1][0];
stu[j+1][0]=temp;
temp=stu[j][1];
stu[j][1]=stu[j+1][1];
stu[j+1][1]=temp;
}
int main(){
int N,K,S;
memset(stu,0,sizeof(stu));
scanf("%d%d%d",&N,&K,&S);
for(int i=0;i<N;i++){
scanf("%d%d",stu[i],stu[i]+1);
}
//qsort(stu,N,sizeof(int)*3,compare);
// for(int i=0;i<N;i++){
// for(int j=0;j<N-i-1;j++){
// if(stu[j][0]==stu[j+1][0]){
// if(stu[j][1]>stu[j+1][1]){
// swapstu(j);
// }
// }else if(stu[j][0]>stu[j+1][0]){
// swapstu(j);
// }
// }
// }
qsort(stu,N,sizeof(stu[0]),compare_students);
// for(int i=0;i<N;i++){
// if(stu[i][0]>=175){
// head=i;
// break;
// }
// }
//改为二分查找
int head=0,tail=N-1,m;
while(head<=tail){
m=(head+tail)/2;
if(stu[m][0]>=175){
tail=m-1;
}else if(stu[m][0]<175){
head=m+1;
}
}
//Debug
//printf("%d\n",head);
int ans=0;
int front;
while(K--){
for(int i=head;i<N;i++){
if(stu[i][2]==0){
front=i;
ans++;
stu[i][2]=1;
break;
}
}
for(int i=front+1;i<N;i++){
// if(stu[i][0]>stu[front][0] && stu[i][2]==0){
// ans++;
// stu[i][2]=1;
// front=i;
// }else if(stu[i][0]==stu[front][0] && stu[i][1]>=S && stu[front][1]<S && stu[i][2]==0){
// ans++;
// stu[i][2]=1;
// front=i;
// }
if((stu[i][2]==0 && stu[i][0]==stu[front][0] && stu[i][1]>=S) || (stu[i][2]==0 && stu[i][0]>stu[front][0])){
ans++;
stu[i][2]=1;
front=i;
}
//Debug
// printf("*%d*%d\n",i,ans);
}
//Debug
// for(int i=0;i<N;i++){
// printf("%d %d %d %d\n",K,stu[i][0],stu[i][1],stu[i][2]);
// }
}
printf("%d\n",ans);
return 0;
}Code精简版但超时：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int stu[100000][3];
int compare(const void *a, const void *b) {
const int (*student_a)[2] = a;
const int (*student_b)[2] = b;
if ((*student_a)[0] == (*student_b)[0]) {
return (*student_a)[1] - (*student_b)[1];
} else {
return (*student_a)[0] - (*student_b)[0];
}
}
int main(){
int N,K,S;
scanf("%d%d%d",&N,&K,&S);
memset(stu,0,N*3*sizeof(int));
for(int i=0;i<N;i++){
scanf("%d%d",stu[i],stu[i]+1);
}
qsort(stu,N,sizeof(stu[0]),compare);
int head=0,tail=N-1,m;
while(head<=tail){
m=(head+tail)/2;
if(stu[m][0]>=175){
tail=m-1;
}else if(stu[m][0]<175){
head=m+1;
}
}
int ans=0;
int front;
while(K--){
for(int i=head;i<N;i++){
if(stu[i][2]==0){
front=i;
ans++;
stu[i][2]=1;
break;
}
}
for(int i=front+1;i<N;i++){
if((stu[i][2]==0 && stu[i][0]==stu[front][0] && stu[i][1]>=S) || (stu[i][2]==0 && stu[i][0]>stu[front][0])){
ans++;
stu[i][2]=1;
front=i;
}
}
}
printf("%d\n",ans);
return 0;
}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
Code:
#include<stdio.h>
#include<string.h>
int main(){
int N; //推送器上松针片的数量
int M; //小盒子能存放的松针片的最大数量
int K; //一根松枝干上能插的松针片的最大数量
scanf("%d%d%d",&N,&M,&K);
int leaf[2000]; //推送器上顺序推出的松针片的大小
for(int i=0;i<N;i++){
scanf("%d",leaf+i);
}
int tree[10]; //记录每个tree上的松针
int working_posi=0; //当前处理的tree上的位置
int box[40]; //小盒子的栈
int cur=-1; //栈的cur
int flag=0;
memset(tree,0,sizeof(tree));
memset(box,0,sizeof(box));
for(int i=0;i<N;){
//Debug
// printf("*\n");
if(working_posi==0){ //tree上没有任何叶片
if(cur!=-1){ //从box里拿
tree[working_posi]=box[cur];
box[cur]=0;
cur--;
}else{ //从leaf里拿
tree[working_posi]=leaf[i];
i++;
}
working_posi++;
}else{ //tree上有叶片
if(cur!=-1){ //box里有叶子
if(tree[working_posi-1]>=box[cur]){ //从box里拿
tree[working_posi]=box[cur];
box[cur]=0;
working_posi++;
cur--;
}else{ //从leaf里拿
if(tree[working_posi-1]>=leaf[i]){
tree[working_posi]=leaf[i];
i++;
working_posi++;
}else{ //不符合，把leaf来的放到box里去
if(cur!=M-1){
cur++;
box[cur]=leaf[i];
i++;
}else{
flag=1;
}
}
}
}else{ //box里没有叶子
if(leaf[i]<=tree[working_posi-1]){
tree[working_posi]=leaf[i];
i++;
working_posi++;
}else{ //leaf里的拿到box里去
if(cur!=M-1){
cur++;
box[cur]=leaf[i];
i++;
}else{
flag=1;
}
}
}
}
//Debug
// printf("Box: ");
// for(int j=0;j<M;j++){
// printf("%d ",box[j]);
// }
// printf("\n");
// printf("Tree: ");
// for(int j=0;j<K;j++){
// printf("%d ",tree[j]);
// }
// printf("\n");
//Debug
// printf("posi=%d,flag=%d,\n",working_posi,flag);
if(working_posi==K || flag==1){
printf("%d",tree[0]);
for(int j=1;j<working_posi;j++){
printf(" %d",tree[j]);
}
printf("\n");
memset(tree,0,sizeof(tree));
working_posi=0;
flag=0;
}
}
if(working_posi!=0){ //处理tree上未输出的
printf("%d",tree[0]);
for(int j=1;j<working_posi;j++){
printf(" %d",tree[j]);
}
printf("\n");
memset(tree,0,sizeof(tree));
working_posi=0;
}
while(cur!=-1){ //处理box里多余的
if(working_posi==0){
tree[working_posi++]=box[cur--];
}else{
if(tree[working_posi-1]>=box[cur] && working_posi!=K){
tree[working_posi]=box[cur];
working_posi++;
box[cur]=0;
cur--;
}else{
printf("%d",tree[0]);
for(int j=1;j<working_posi;j++){
printf(" %d",tree[j]);
}
printf("\n");
memset(tree,0,sizeof(tree));
working_posi=0;
}
}
}
if(working_posi!=0){ //处理tree上多余的
printf("%d",tree[0]);
for(int j=1;j<working_posi;j++){
printf(" %d",tree[j]);
}
printf("\n");
memset(tree,0,sizeof(tree));
working_posi=0;
}
return 0;
}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:59Code:
#include<stdio.h>
#include<string.h>
int ttos(int h,int m,int s){
return (((h*60)*60)+(m*60))+s;
}
int stoh(int s){
return s/3600;
}
int stom(int s){
return s/60%60;
}
int stos(int s){
return s%60;
}
int main(){
int ss[24*60*60];
memset(ss,0,sizeof(ss));
int n;
scanf("%d",&n);
int h1,m1,s1,h2,m2,s2;
for(int i=0;i<n;i++){
scanf("%d:%d:%d - %d:%d:%d",&h1,&m1,&s1,&h2,&m2,&s2);
for(int i=ttos(h1,m1,s1);i<ttos(h2,m2,s2);i++){
ss[i]=1;
}
}
int cur=-1; //标记上一个0在哪里
int flag=0;
if(ss[0]==0){
cur=0;
flag=1;
}
for(int i=1;i<24*60*60-1;i++){
if(ss[i]==1 && ss[i-1]==0){
printf("%02d:%02d:%02d - %02d:%02d:%02d\n",stoh(cur),stom(cur),stos(cur),stoh(i),stom(i),stos(i));
flag=0;
}
if(ss[i]==0 && ss[i-1]==1){
cur=i;
flag=1;
}
}
if(flag==1){
printf("%02d:%02d:%02d - %02d:%02d:%02d\n",stoh(cur),stom(cur),stos(cur),stoh(24*60*60-1),stom(24*60*60-1),stos(24*60*60-1));
}
return 0;
}
L2-3 龙龙送外卖
龙龙是“饱了呀”外卖软件的注册骑手，负责送帕特小区的外卖。帕特小区的构造非常特别，都是双向道路且没有构成环 —— 你可以简单地认为小区的路构成了一棵树，根结点是外卖站，树上的结点就是要送餐的地址。
每到中午 12 点，帕特小区就进入了点餐高峰。一开始，只有一两个地方点外卖，龙龙简单就送好了；但随着大数据的分析，龙龙被派了更多的单子，也就送得越来越累……
看着一大堆订单，龙龙想知道，从外卖站出发，访问所有点了外卖的地方至少一次（这样才能把外卖送到）所需的最短路程的距离到底是多少？每次新增一个点外卖的地址，他就想估算一遍整体工作量，这样他就可以搞明白新增一个地址给他带来了多少负担。
输入格式:
输入第一行是两个数 N 和 M
(2≤N≤10^5, 1≤M≤10^5)，分别对应树上节点的个数（包括外卖站），以及新增的送餐地址的个数。
接下来首先是一行 N 个数，第 i 个数表示第
i 个点的双亲节点的编号。节点编号从 1 到
N，外卖站的双亲编号定义为 −1。
接下来有 M 行，每行给出一个新增的送餐地点的编号
Xi。保证送餐地点中不会有外卖站，但地点有可能会重复。
为了方便计算，我们可以假设龙龙一开始一个地址的外卖都不用送，两个相邻的地点之间的路径长度统一设为
1，且从外卖站出发可以访问到所有地点。
注意：所有送餐地址可以按任意顺序访问，且完成送餐后无需返回外卖站。
输出格式:
对于每个新增的地点，在一行内输出题目需要求的最短路程的距离。
输入样例:
7 4
-1 1 1 1 2 2 3
5
6
2
4输出样例:
2
4
4
6
我的Code：
#include<stdio.h>
#include<string.h>
int node[100001]; //记录每个节点的父节点
int stop[100001]; //送餐地址
// int next[100001][1000]; //记录每个节点的子节点
// int next_cur[100001];
// int dfs(int target, int current, int depth){
// printf("%d,%d,%d\n",target,current,depth);
// for(int i=0;i<next_cur[current];i++){
// if(target==next[current][i]){
// return depth+1;
// }else{
// if(dfs(target,next[current][i],depth+1)!=-1)
// return dfs(target,next[current][i],depth+1);
// else{
// continue;
// }
// }
// }
// }
int findsons(int target,int N,int *array,int len){ //查找子节点
int cur=0;
//printf("Findsons:\n");
for(int i=0;i<N;i++){
if(node[i]-1==target){
array[cur]=i;
cur++;
}
//printf("%d,%d",node[i],target);
}
if(cur==0){
return 0; //表示没有查找到
}else{
return 1; //表示查找到了
}
}
int dfs(int target,int current,int N,int depth){
printf("%d,%d\n",target,current);
int array[1000];
memset(array,-1,sizeof(array));
if(findsons(current,N,array,1000)==0){
return -1; //表示到底了，没有子节点
}
int cur=0;
while(array[cur]!=-1){
if(array[cur]==target){
return depth;
}
int temp;
temp=dfs(target,array[cur],N,depth+1);
if(temp==-1){
return -1;
}else{
return temp;
}
// if(target!=array[cur]){
// if(dfs(array[cur],N,depth+1)==-1){
// continue;
// }else{
// return dfs(array[cur],N,depth+1);
// }
// }else{
// return 0;
// }
}
}
int main(){
int N; //树上节点的个数（包括外卖站）
int M; //新增的送餐地址的个数
// memset(next,-1,sizeof(next));
// memset(next_cur,0,sizeof(next_cur));
scanf("%d %d",&N,&M);
for(int i=0;i<N;i++){
scanf("%d",node+i);
}
for(int i=0;i<M;i++){
scanf("%d",stop+i);
// next[stop[i]][next_cur[stop[i]]++]=i;
}
for(int i=0;i<M;i++){
printf("%d\n",dfs(stop[i],0,N,0));
}
return 0;
}
// 0
// 1 2 3
// 4 5 6 7 8 9
// -1 1 1 1
Code：
我思考的方向错误了。应该从子节点的位置去一步步找父节点，从而获得深度。
#include<stdio.h>
#include<stdlib.h>
const int N=200010;
int n,m,sum,max;
int p[N],d[N];
int dfs(int u){
if(p[u]==-1 || d[u]>0) return d[u];
sum++;
d[u]=dfs(p[u])+1;
return d[u];
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&p[i]);
d[i]=0; // 使用 0 初始化 d 数组
}
sum=0;
max=0;
int t;
while(m--){
scanf("%d",&t);
max=(max > dfs(t)) ? max : dfs(t); // 使用三元操作符找出最大值
printf("%d\n",sum*2-max);
}
return 0;
}
L2-4 大众情人
人与人之间总有一点距离感。我们假定两个人之间的亲密程度跟他们之间的距离感成反比，并且距离感是单向的。例如小蓝对小红患了单相思，从小蓝的眼中看去，他和小红之间的距离为 1，只差一层窗户纸；但在小红的眼里，她和小蓝之间的距离为 108000，差了十万八千里…… 另外，我们进一步假定，距离感在认识的人之间是可传递的。例如小绿觉得自己跟小蓝之间的距离为 2，则即使小绿并不直接认识小红，我们也默认小绿早晚会认识小红，并且因为跟小蓝很亲近的关系，小绿会觉得自己跟小红之间的距离为 1+2=3。当然这带来一个问题，如果小绿本来也认识小红，或者他通过其他人也能认识小红，但通过不同渠道推导出来的距离感不一样，该怎么算呢？我们在这里做个简单定义，就将小绿对小红的距离感定义为所有推导出来的距离感的最小值。
一个人的异性缘不是由最喜欢他/她的那个异性决定的，而是由对他/她最无感的那个异性决定的。我们记一个人 \(i\) 在一个异性 \(j\) 眼中的距离感为 \(D_{ij}\)；将 \(i\) 的“异性缘”定义为 \(\frac{1}{\max_{j \in 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
False Code：
#include<stdio.h>
#include<string.h>
int distance[501][501];
int breadth[501][501];
// void bfs(int current, int target, int n, int dis){
// // int route[501];
// // memset(route,-1,sizeof(route));
// printf("%d,%d,%d\n",current,target,dis);
// for(int i=1;i<=n;i++){
// if(distance[current][i]!=-1){
// if(breadth[current][i]>dis+distance[current][i]){
// breadth[current][i]=dis+distance[current][i];
// }
// bfs(i,target,n,breadth[current][i]);
// }
// }
// }
int main(){
int n;
int i,j;
scanf("%d",&n);
memset(distance,-1,sizeof(distance));
//读取
char gender;
int K;
int friend,dis;
for(i=1;i<=n;i++){
scanf(" %c %d",&gender,&K); //%c前面空格以消除缓存区的回车
distance[i][0]=(gender=='F'?0:1);
distance[0][i]=(gender=='F'?0:1);
while(K--){
scanf("%d:%d",&friend,&dis);
distance[i][friend]=dis;
}
}
//Debug
for(i=0;i<=n;i++){
for(j=0;j<=n;j++){
printf("%3d ",distance[i][j]);
}
printf("\n");
}
printf("\n");
//完善图
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(j!=i && distance[i][j]==-1){
memset(breadth,100,sizeof(breadth)); //初始化bfs所需要的图
bfs(i,j,n,0);
distance[i][j]=breadth[i][j];
//用bfs求dis
}
}
}
//Debug
for(i=0;i<=n;i++){
for(j=0;j<=n;j++){
printf("%3d ",distance[i][j]);
}
printf("\n");
}
return 0;
}Code：
这道题真的牛批。我第十行注释掉的初始化方法居然是错误的。 然后后面有一个min变量，初始化1e6+1也是错误的，2e8也错，要INT_MAX才行。
#include<stdio.h>
#include<string.h>
#include<limits.h>
int main(){
int distance[510][510];
int n;
int i,j,k;
scanf("%d",&n);
// for(i=0;i<=n;i++)
// for(j=0;j<=n;j++){
// distance[i][j]=2000000;
// }
memset(distance,0x3f,sizeof(distance));
for(i=0;i<=n;i++)
distance[i][i]=0;
//读取
char gender;
int K;
int friend,dis;
for(i=1;i<=n;i++){
getchar();
scanf("%c %d",&gender,&K); //%c前面空格以消除缓存区的回车
distance[i][0]=(gender=='F'?0:1);
distance[0][i]=(gender=='F'?0:1);
while(K--){
scanf("%d:%d",&friend,&dis);
if(dis<distance[i][friend])
distance[i][friend]=dis;
}
}
//补全图
for(k=1;k<=n;k++){
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if((distance[i][k]+distance[k][j])<distance[i][j]){
distance[i][j]=distance[i][k]+distance[k][j];
}
}
}
}
//计算每个人的异性缘
int popularity[502];
int max;
memset(popularity,0,sizeof(popularity));
for(i=1;i<=n;i++){
max=0;
for(j=1;j<=n;j++){
if(distance[i][0]!=distance[j][0] ){
if(max<distance[j][i]){
max=distance[j][i];
}
}
}
popularity[i]=max;
}
//输出结果
int min;
int t;
for(i=0;i<=1;i++){
min=INT_MAX;
for(j=1;j<=n;j++){
if(distance[j][0]==i && min>popularity[j]){
min=popularity[j];
}
}
t=0;
for(j=1;j<=n;j++){
if(distance[j][0]==i && min==popularity[j]){
if(t!=0) printf(" ");
printf("%d",j);
t++;
}
}
printf("\n");
}
return 0;
}网上提供的C++代码重写C（ChatGPT4.0）:
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define N 510
int min(int a, int b) {
return a < b ? a : b;
}
int max(int a, int b) {
return a > b ? a : b;
}
int n;
int dist[N], sex[N];
int g[N][N];
int main() {
scanf("%d", &n);
memset(g, 0x3f, sizeof (g) );
for (int i = 0; i <= n; i++)
g[i][i] = 0;
for (int i = 1; i <= n; i++) {
char op[2];
scanf("%s", op);
if(op[0] == 'F')
sex[i] = 0;
else
sex[i] = 1;
int k, a, b;
scanf("%d", &k);
for (int j = 0; j < k; j++) {
scanf("%d:%d", &a, &b);
g[i][a] = min(g[i][a], b);
}
}
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])
dist[i] = max(dist[i], g[j][i]);
}
}
for (int k = 0; k <= 1; k++) {
int d = INT_MAX;
for (int i = 1; i <= n; i++) {
if(sex[i] == k)
d = min(d, dist[i]);
}
int f = 0;
for (int i = 1; i <= n; i++) {
if(sex[i] == k && dist[i] == d) {
if(f)
printf(" ");
printf("%d", i);
f++;
}
}
printf("\n");
}
return 0;
}
L3-1 千手观音
人类喜欢用 10 进制，大概是因为人类有一双手 10 根手指用于计数。于是在千手观音的世界里，数字都是 10000 进制的，因为每位观音有 1000 双手 ……
千手观音们的每一根手指都对应一个符号（但是观音世界里的符号太难画了，我们暂且用小写英文字母串来代表），就好像人类用自己的 10 根手指对应 0 到 9 这 10 个数字。同样的，就像人类把这 10 个数字排列起来表示更大的数字一样，ta们也把这些名字排列起来表示更大的数字，并且也遵循左边高位右边低位的规则，相邻名字间用一个点 . 分隔，例如 pat.pta.cn 表示千手观音世界里的一个 3 位数。
人类不知道这些符号代表的数字的大小。不过幸运的是，人类发现了千手观音们留下的一串数字，并且有理由相信，这串数字是从小到大有序的！于是你的任务来了：请你根据这串有序的数字，推导出千手观音每只手代表的符号的相对顺序。
注意：有可能无法根据这串数字得到全部的顺序，你只要尽量推出能得到的结果就好了。当若干根手指之间的相对顺序无法确定时，就暂且按它们的英文字典序升序排列。例如给定下面几个数字：
pat
cn
lao.cn
lao.oms
pta.lao
pta.pat
cn.patpat < cn；根据左边高位的顺序可以推断
lao < pta < cn；再根据高位相等时低位的顺序，可以推断出
cn < oms，lao < pat。综上我们得到两种可能的顺序：lao < pat < pta < cn < oms；或者
lao < pta < pat < cn < oms，即 pat
和 pta 之间的相对顺序无法确定，这时我们按字典序排列，得到
lao < pat < pta < cn < oms。
输入格式：
输入第一行给出一个正整数 \(N
(≤10^5)\)，为千手观音留下的数字的个数。随后 \(N\)
行，每行给出一个千手观音留下的数字，不超过 10 位数，每一位的符号用不超过
3 个小写英文字母表示，相邻两符号之间用 . 分隔。
我们假设给出的数字顺序在千手观音的世界里是严格递增的。题目保证数字是 10^4进制的，即符号的种类肯定不超过 \(10^4\) 种。
输出格式：
在一行中按大小递增序输出符号。当若干根手指之间的相对顺序无法确定时，按它们的英文字典序升序排列。符号间仍然用 . 分隔。
输入样例：
7
pat
cn
lao.cn
lao.oms
pta.lao
pta.pat
cn.pat
输出样例：
lao.pat.pta.cn.oms
L3-2 关于深度优先搜索和逆序对的题应该不会很难吧这件事
背景知识
深度优先搜索与 DFS 序
深度优先搜索算法（DFS）是一种用于遍历或搜索树或图的算法。以下伪代码描述了在树 \(T\) 上进行深度优先搜索的过程：
procedure DFS(T, u, L) // T 是被深度优先搜索的树
// u 是当前搜索的节点
// L 是一个链表，保存了所有节点被第一次访问的顺序
append u to L // 将节点 u 添加到链表 L 的末尾
for v in u.children do // 枚举节点 u 的所有子节点 v
DFS(T, v) // 递归搜索节点 v令 \(r\) 为树 \(T\) 的根，调用 DFS(T, r, L)
即可完成对 \(T\)
的深度优先搜索，保存在链表 \(L\)
中的排列被称为 DFS
序。相信聪明的你已经发现了，如果枚举子节点的顺序不同，最终得到的 DFS
序也会不同。
逆序对
给定一个长度为 \(n\) 的整数序列 \(a_1, a_2, ⋯, a_n\) ，该序列的逆序对数量是同时满足以下条件的有序数对 \((i,j)\) 的数量：
\[ 1 \leq i < j \leq n \] \[ a_i > a_j \]
问题求解
给定一棵 \(n\) 个节点的树，其中节点 \(r\) 为根。求该树所有可能的 DFS 序中逆序对数量之和。
输入格式
第一行输入两个整数 \(n，r（2≤n≤3×10^5，1≤r≤n）\) 表示树的大小与根节点。
对于接下来的 \((n−1)\) 行，第 \(i\) 行输入两个整数 \(u_i\) 与 \(v_i（1≤u_i,v_i≤n）\)，表示树上有一条边连接节点 \(u_i\) 与 \(v_i\) 。
输出格式
输出一行一个整数，表示该树所有可能的 DFS 序中逆序对数量之和。由于答案可能很大，请对 \(10^9+7\) 取模后输出。
样例输入 1
5 3
1 5
2 5
3 5
4 3样例输出 1
24样例输入 2
10 5
10 2
2 5
10 7
7 1
7 9
4 2
3 10
10 8
3 6样例输出 2
516样例解释
下图展示了样例 1 中的树。
sample.png
该树共有 4 种可能的 DFS 序：
{3,4,5,1,2}，有 6 个逆序对； {3,4,5,2,1}，有 7 个逆序对； {3,5,1,2,4}，有 5 个逆序对； {3,5,2,1,4}，有 6 个逆序对。 因此答案为 6+7+5+6=24。
L3-3 教科书般的亵渎
九条可怜最近在玩一款卡牌游戏。在每一局游戏中，可怜都要使用抽到的卡牌来消灭一些敌人。每一名敌人都有一个初始血量，而当血量降低到 \(0\) 及以下的时候，这名敌人就会立即被消灭并从场上消失。
现在，可怜面前有 \(n\) 个敌人，其中第 \(i\) 名敌人的血量是 \(a_i\) ，而可怜手上只有如下两张手牌：
如果场上还有敌人，等概率随机选中一个敌人并对它造成一点伤害（即血量减 \(1\) ），重复 \(K\) 次。
对所有敌人造成一点伤害，重复该效果直到没有新的敌人被消灭。
下面是这两张手牌效果的一些示例：
假设存在两名敌人，他们的血量分别是 \(1\),\(2\) 且 \(K=2\)。那么在可怜打出第一张手牌后，可能会发生如下情况： 第一轮中，两名敌人各有 \(0.5\) 的概率被选中。假设第一名敌人被选中，那么它会被造成一点伤害。这时它的血量变成了 \(0\)，因此它被消灭并消失了。 第二轮中，因为场上只剩下了第二名敌人，所以它一定会被选中并被造成一点伤害。这时它剩下的血量为 \(1\)。 同样假设存在两名敌人且血量分别为 \(1,2\)。那么在可怜打出第二张手牌后，会发生如下情况： 第一轮中，所有敌人被造成了一点伤害。这时第一名敌人被消灭了，因此卡牌效果会被重复一遍。 第二轮中，所有敌人（此时只剩下第二名敌人了）被造成了一点伤害。这时第二名敌人也被消灭了，因此卡牌效果会被再重复一遍。 第三轮中，所有敌人（此时没有敌人剩下了）被造成了一点伤害。因为没有新的敌人被消灭了，所以卡牌效果结束。 如果面对的是四名血量分别为 \(1,2,2,4\) 的敌人，那么在可怜打出第二张手牌后，只有第四名敌人还会存活，且它的剩余血量为 \(1\)。 现在，可怜先打出了第一张手牌，再打出了第二张手牌。她发现，在第一张手牌效果结束后，没有任何一名敌人被消灭，但是在第二张手牌的效果结束后，所有敌人都被消灭了。
可怜想让你计算一下这种情况发生的概率是多少。
输入格式：
第一行输入两个整数 \(n,K(1≤n,K≤50)\)，分别表示敌人的数量以及第一张卡牌效果的发动次数。
第二行输入 \(n\) 个由空格隔开的整数 \(a_i(1≤a_i≤50)\) ，表示每个敌人的初始血量。
输出格式：
在一行中输出一个整数，表示发生概率对 \(998244353\) 取模后的结果。
具体来说，如果概率的最简分数表示为 \(a/b(a≥0,b≥1,gcd(a,b)=1)\)，那么你需要输出
\(a×b^{998244351} mod998244353\)。
输入样例 1：
3 2
2 3 3输出样例 1：
665496236样例解释 1：
在第一张手牌的效果结束后，三名敌人的剩余血量只可能在如下几种中：[1,3,2], [1,2,3], [2,1,3] 和 [2,3,1]。前两种发生的概率是 \(2/9\)，后两种发生的概率是 \(1/9\)。因此答案为 \(2/3\)，输出 \(2×3 ^{998244351} mod998244353=665496236\) 。
输入样例 2：
3 3
2 3 3
输出样例 2：
776412275样例解释 2:
在第一张手牌的效果结束后，三名敌人的剩余血量只可能在如下几种中：[1,2,2]、[2,1,2] 和 [2,2,1]。第一种发生的概率是 \(2/9\) ，后两种发生的概率是 \(1/9\)。因此答案为 \(4/9\)，输出 \(4×9^{998244351} mod998244353=776412275\) 。
输入样例 3： 5 3
1 4 4 2 536735392212 12
1 2 3 4 5 6 7 8 9 10 11 12452061016