自动搬运

查看原文

来自洛谷，原作者为

	Ymy1201 一只正在摸鱼的蒟蒻||100%回关||忘关私我||暑假后小学六年级||玩火影Q区44439234846（是个小白）阿玛特拉斯

搬运于2025-08-24 23:17:52，当前版本为作者最后更新于2025-08-09 10:49:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

吐槽：我竟然是第一个过的入。

P12748 [POI 2017 R2] 体育比赛 Sports competition

题目大意

有 $n$ 个国家的选手进行体育比赛，需要根据记者的报道求出唯一的比赛排名或可能的排名数量对 $1000000007$ 取模的结果。

分析

如果 $x$ 国的排名是 $1$，$y$ 国的记者报道是他们排名可能是 $1$ 或者是 $2$，真的可能是 $1$ 吗？不可能啊！$x$ 国的排名都是 $1$ 了，$y$ 国怎么可能是啊。所以 $y$ 国的排名是 $2$。

我们就可以按照这个方法递归下去，如果递归完了还有国家的排名不确定，那我们就可以输出不确定的国家的排名能形成多少个环，就有多少个 $2$ 相乘。

举个例子：
$x$ 国的排名可能是 $1$，$2$。
$y$ 国的排名可能是 $2$，$3$。
$z$ 国的排名可能是 $3$，$1$。
是不是就行成了一个 $1\to2\to3\to1$ 的环，一个环就有一个 $2$ 相乘，答案就是 $2$。

以为就完了吗？不，不，不。
如果有某个排名都没有出现的数据，直接输出 NIE 0 就行了。
那我们就可以写出这份代码：

#include<bits/stdc++.h>
using namespace std;
int n;
bool vis[1000001],vis2[1000001],vis3[1000001];
unordered_map<int,int>ans,ans2;
unordered_map<int,pair<int,int> >m;
vector<int>e[1000001];
queue<int>q;
int pow2(int x) {
	long long sum=1,y=2;
	while(x) {
		if(x&1)sum=sum*y%1000000007;
		x>>=1;
		y=y*y%1000000007;
	}
	return sum%1000000007;
}
void dfs(int x,int y) {
	vis[x]=1;
	int z=0;
	for(int i:e[y])
		if(i!=x&&vis[i]==0) {
			z=i;
			break;
		}
	if(z==0) {
		return ;
	}
	if(m[z].first==y)dfs(z,m[z].second);
	else dfs(z,m[z].first);
	return;
}
int main() {
//	freopen("a.in","r",stdin);
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		char c;
		scanf(" %c",&c);
		if(c=='N') {
			scanf(" %d%d",&m[i].first,&m[i].second);
			vis2[m[i].first]=vis2[m[i].second]=1;
			e[m[i].first].push_back(i);
			e[m[i].second].push_back(i);
		} else {
			int x;
			scanf(" %d",&x);
			vis2[x]=1;
			ans[i]=x;
			ans2[x]=i;
			vis[i]=1;
			q.push(x);
		}
	}
	while(!q.empty()) {
		int x=q.front();
		q.pop();
		for(int i:e[x])
			if(vis[i]==0) {
				int y=(m[i].first==x?m[i].second:m[i].first);
				if(ans2.find(y)!=ans2.end())return puts("NIE\n0"),0;
				ans[i]=y;
				ans2[y]=i;
				q.push(ans[i]);
				vis[i]=1;
			}
	}
	bool b=1;
	for(int i=1; i<=n; i++)
		if(ans.find(i)==ans.end()) {
			b=0;
			break;
		}
	if(b) {
		puts("TAK");
		for(int i=1; i<=n; i++)printf("%d\n",ans[i]);
	} else {
		puts("NIE");
		long long sum=0;
		for(int i=1; i<=n; i++)if(!vis2[i])return puts("0"),0;
		for(int i=1; i<=n; i++)
			if(!vis[i]) {
				dfs(i,m[i].first);
				sum++;
			}
		printf("%d",pow2(sum));
	}
	return 0;
}

咦？怎么 WA 了，下载数据一看：

10
N 6 4
N 2 3  
N 8 6  
N 3 4  
N 4 5  
N 5 1  
N 1 2  
N 9 7  
N 10 3  
N 7 8  

发现什么特殊的排名没有？对！$9$ 和 $10$ 这两个排名只出现了一次！
那我们就可以再递推一次了。

上代码！

#include<bits/stdc++.h>
using namespace std;
int n;
bool vis[1000001],vis2[1000001],vis3[1000001];
unordered_map<int,int>ans,ans2;
unordered_map<int,pair<int,int> >m;
vector<int>e[1000001];
queue<int>q;
int pow2(int x) {
	long long sum=1,y=2;
	while(x) {
		if(x&1)sum=sum*y%1000000007;
		x>>=1;
		y=y*y%1000000007;
	}
	return sum%1000000007;
}
void dfs(int x,int y) {
	vis[x]=1;
	int z=0;
	for(int i:e[y])
		if(i!=x&&vis[i]==0) {
			z=i;
			break;
		}
	if(z==0) {
		return ;
	}
	if(m[z].first==y)dfs(z,m[z].second);
	else dfs(z,m[z].first);
	return;
}
int main() {
//	freopen("a.in","r",stdin);
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		char c;
		scanf(" %c",&c);
		if(c=='N') {
			scanf(" %d%d",&m[i].first,&m[i].second);
			vis2[m[i].first]=vis2[m[i].second]=1;
			e[m[i].first].push_back(i);
			e[m[i].second].push_back(i);
		} else {
			int x;
			scanf(" %d",&x);
			vis2[x]=1;
			ans[i]=x;
			ans2[x]=i;
			vis[i]=1;
			q.push(x);
		}
	}
	while(!q.empty()) {
		int x=q.front();
		q.pop();
		for(int i:e[x])
			if(vis[i]==0) {
				int y=(m[i].first==x?m[i].second:m[i].first);
				if(ans2.find(y)!=ans2.end())return puts("NIE\n0"),0;
				ans[i]=y;
				ans2[y]=i;
				q.push(ans[i]);
				vis[i]=1;
			}
	}
	bool b=0;
	do {
		b=0;
		for(int i=1; i<=n; i++)
			if(vis3[i]==0&&e[i].size()==1) {
				int x=(m[e[i][0]].first==i?m[e[i][0]].second:m[e[i][0]].first);
				for(int j=0; j<e[x].size(); j++)
					if(e[x][j]==e[i][0]) {
						e[x].erase(e[x].begin()+j);
						break;
					}
				b=1;
				vis3[i]=1;
				vis[e[i][0]]=1;
			}
	} while(b);
	b=1;
	for(int i=1; i<=n; i++)
		if(ans.find(i)==ans.end()) {
			b=0;
			break;
		}
	if(b) {
		puts("TAK");
		for(int i=1; i<=n; i++)printf("%d\n",ans[i]);
	} else {
		puts("NIE");
		int sum=0;
		for(int i=1; i<=n; i++)if(!vis2[i])return puts("0"),0;
		for(int i=1; i<=n; i++)
			if(!vis[i]) {
				dfs(i,m[i].first);
				sum++;
			}
		printf("%d",pow2(sum));
	}
	return 0;
}

看到这了，不点个赞再走？qwp。