题解：P12748 [POI 2017 R2] 体育比赛 Sports competition
Ymy1201
·
·
题解
吐槽：我竟然是第一个过的入。
P12748 [POI 2017 R2] 体育比赛 Sports competition
题目大意
有 n 个国家的选手进行体育比赛，需要根据记者的报道求出唯一的比赛排名或可能的排名数量对 1000000007 取模的结果。
分析
如果 x 国的排名是 1，y 国的记者报道是他们排名可能是 1 或者是 2，真的可能是 1 吗？不可能啊！x 国的排名都是 1 了，y 国怎么可能是啊。所以 y 国的排名是 2。
我们就可以按照这个方法递归下去，如果递归完了还有国家的排名不确定，那我们就可以输出不确定的国家的排名能形成多少个环，就有多少个 2 相乘。
举个例子：
$y$ 国的排名可能是 $2$，$3$。
$z$ 国的排名可能是 $3$，$1$。
是不是就行成了一个 $1\to2\to3\to1$ 的环，一个环就有一个 $2$ 相乘，答案就是 $2$。
以为就完了吗？不，不，不。
如果有某个排名都没有出现的数据，直接输出 `NIE 0` 就行了。
那我们就可以写出这份代码：
```cpp
#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$ 这两个排名只出现了一次！
那我们就可以再递推一次了。
### 上代码！
```cpp
#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。~~