打卡信奥刷题（3491）用C++实现信奥题 P10734 [NOISG 2019 Prelim] Experimental Charges

P10734 [NOISG 2019 Prelim] Experimental Charges

题目背景

翻译自 NOISG2019 Prelim C.Experimental Charges。

题目描述

现有

N

N

N 个带电粒子，带正电子的粒子会和带负电子的粒子相互吸引，而带同一种电子的粒子会相互排斥。

有

Q

Q

Q 次操作，每次操作表示为

T

i

,

A

i

,

B

i

T_i,A_i,B_i

Ti​,Ai​,Bi​，可根据

T

i

T_i

Ti​ 的不同分为三种类型：

• A 操作代表 $A_i,B_i$
• R 操作代表 $A_i,B_i$
• Q 操作询问按照目前已知的信息，如果 $A_i,B_i$

对于每个 Q 操作，如果互相吸引，输出 A；如果互相排斥，输出 R；如果无法确定，输出 ?。

保证至少有一种可能使得所有操作不冲突。

输入格式

第一行两个整数

N

,

Q

N,Q

N,Q。

接下来的

Q

Q

Q 行，每行一个字符

T

i

T_i

Ti​ 与两个整数

A

i

,

B

i

A_i,B_i

Ai​,Bi​，表示一种操作。

输出格式

若干行，每行表示一次 Q 操作的回答。

输入输出样例 #1

输入 #1

2 3
Q 1 2
R 1 2
Q 1 2

输出 #1

?
R

输入输出样例 #2

输入 #2

4 5
R 1 2
A 2 3
A 1 4
Q 2 4
Q 1 3

输出 #2

A
A

说明/提示

【样例 #1 解释】

对于第一次询问，并不能确定

1

,

2

1,2

1,2 之间的关系，输出 ?。

对于第二次询问，可以确定

1

,

2

1,2

1,2 相斥，输出 R。

【数据范围】

对于

100

%

100\\%

100% 的数据：

• $1\le N,Q\le 10^5$
• $1\le A_i\ne B_i\le N$
• $T_i$

C++实现

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int n,m,f[N];
int gf(int x){return x==f[x]?f[x]:f[x]=gf(f[x]);}
void link(int x,int y){
int u=gf(x),v=gf(y);
f[u]=v;
}
int main(){
for(int i=1;i<N;++i)f[i]=i;
cin>>n>>m;
while(m—){
char op;int a,b;
cin>>op>>a>>b;
if(op=='A')
link(a,b+n),link(a+n,b);
else if(op=='R')
link(a,b),link(a+n,b+n);
else{
int fl=0;
if(gf(a)==gf(b)||gf(a+n)==gf(b+n))
cout<<'R';
else if(gf(a+n)==gf(b)||gf(a)==gf(b+n))
cout<<'A';
else
cout<<'?';
cout<<"\\n";
}
}
return 0;
}

后续

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