P9464 [EGOI 2023] Padel Prize Pursuit / 追梦笼式网球

题目背景

Day 1 Problem B.

题面译自 EGOI2023 ppp。

题目描述

有 $N$ 个编号为 $0$ 到 $N-1$ 的选手参加一场 $M$ 天的笼式网球锦标赛。每天恰好进行一次比赛。在锦标赛中共颁发 $M$ 块奖牌，每场比赛颁发一块新奖牌。在第 $i$ 天的比赛中（$0\le i\le M-1$），两名编号分别为 $x_i$ 和 $y_i$ 的选手参加。比赛中发生如下事件：

• 选手 $x_i$ 打败选手 $y_i$。
• 一个新的奖牌授予给获胜者 $x_i$。
• 失败者所有现有的奖牌都授予给获胜者。

在第 $M$ 天（最后一场比赛结束后一天）举行颁奖典礼。在颁奖典礼上，所有奖牌被收集起来，并授予给持有该奖牌时间最长的选手。具体地，在第 $M$ 天，奖牌 $i$ 授予给持有奖牌 $i$ 最多个晚上的选手（不必须连续持有）。如果两个或更多选手持有一个奖牌同样多晚上，奖牌授予给其中编号最小的选手。

你的任务是求出颁奖典礼中，每位选手被授予多少奖牌。

输入格式

第一行两个整数 $N,M$，表示选手数和比赛数。

接下来 $M$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 天的比赛中，选手 $x_i$ 打败选手 $y_i$。

输出格式

一行 $N$ 个整数，第 $k$ 个整数表示颁奖典礼中，第 $k$ 位选手被授予的奖牌数。

输入输出样例 #1

输入 #1

3 4
0 1
2 1
1 0
2 1

输出 #1

1 1 2

输入输出样例 #2

输入 #2

3 7
0 1
0 2
2 0
0 1
1 0
2 0
0 2

输出 #2

2 2 3

输入输出样例 #3

输入 #3

6 10
2 5
3 0
4 2
0 1
4 3
2 4
0 3
0 2
5 2
5 0

输出 #3

5 0 1 1 1 2

说明/提示

样例 $1$ 解释

下图展示了样例 $1$ 中锦标赛期间奖牌的归属。当选手 $1$ 在第三天被打败时，她的所有奖牌都被授予给选手 $2$。

---

样例 $2$ 解释

如下图。

在颁奖典礼中，选手 $0$ 被授予奖牌 $5$ 和 $6$，选手 $1$ 被授予奖牌 $3$ 和 $4$，选手 $2$ 被授予奖牌 $0,1,2$。

---

数据范围

对于全部数据，$2\le N\le 2\times 10^5$，$1\le M\le 2\times 10^5$，$0\le x_i,y_i\le N-1$ 且 $x_i\ne y_i$。

• 子任务一（$12$ 分）：$N=2$。
• 子任务二（$16$ 分）：$N,M\le 2\times 10^3$。
• 子任务三（$15$ 分）：第 $i$ 场比赛的获胜者参加了第 $i+1$ 场比赛，依赖子任务一。
• 子任务四（$20$ 分）：在第 $i$ 场比赛时，$x_i$ 有至少和 $y_i$ 一样多的奖牌。
• 子任务五（$22$ 分）：一旦一名选手被打败，她永远不会再次参赛。
• 子任务六（$15$ 分）：无特殊限制，依赖子任务二、三、四、五。

C++实现

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+100;
int n,m;
int ans[N],cnt[N],dt[N];
bool vis[N];
struct node{
	int u,st,ed;
};
node a[N];
vector<int> V[N];
void add(int x,int s,int &Mx){
	cnt[x]+=s;
	if(cnt[x]>cnt[Mx])
		Mx=x;
	else if(cnt[x]==cnt[Mx]&&x<Mx)
		Mx=x;
}
void dfs(int u,int Mx){
    if(!u) return ;
	vis[u]=true;
	int s=a[u].ed-a[u].st+1,rMx=Mx;
	add(a[u].u,s,Mx);
	ans[Mx]++;
	for(int v:V[u])
		dfs(v,Mx);
	cnt[a[u].u]-=s;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int x,y; cin>>x>>y;
    	x++,y++;
    	a[i].u=x,a[i].st=i,a[i].ed=m;
    	if(dt[x]) a[dt[x]].ed=i-1,V[i].push_back(dt[x]);
    	if(dt[y]) a[dt[y]].ed=i-1,V[i].push_back(dt[y]);
    	dt[x]=i,dt[y]=0;
    }
    for(int i=1;i<=n;i++){
    	if(dt[i]) dfs(dt[i],0);
    }
    for(int i=1;i<=n;i++)
    	cout<<ans[i]<<" ";
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容