H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
https://ac.nowcoder.com/acm/contest/1100/C
D
e
s
c
r
i
p
t
i
o
n
Description
Description
给定
n
n
n张双面牌，每张牌的每一面分别写着
a
i
,
b
i
a_i,b_i
ai,bi，给定
m
m
m组询问，问你是否能用这些牌打出
l
i
,
r
i
l_i,r_i
li,ri的顺子
数据范围：
S
o
l
u
t
i
o
n
Solution
Solution
匈牙利+牌相同的特判可以拿到40分。。。代码详见总结
考虑将原题图论化，如果我们让
a
i
−
>
b
i
a_i->b_i
ai−>bi，那么这就构成了一张图，一个顺子合法当且仅当这张图联通且带环
所以我们并查集预处理，处理出对于每个数
x
x
x，他顺子的起点的最小值
l
[
x
]
l[x]
l[x]，就可以
O
(
1
)
O(1)
O(1)判断了
总的时间复杂度：
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
C
o
d
e
Code
Code
#include<cctype>
#include<cstdio>
#include<algorithm>
#define N 100010
#define LL long long
using namespace std
;int f
[N
],mx
,n
,q
,x
,y
,belong
[N
],maxn
,l
[N
];
bool h
[N
];
inline int find(register int x
){return x
==f
[x
]?x
:f
[x
]=find(f
[x
]);}
inline LL
read()
{
char c
;LL d
=1,f
=0;
while(c
=getchar(),!isdigit(c
)) if(c
=='-') d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
signed main()
{
mx
=read();n
=read();
for(register int i
=1;i
<=mx
;i
++) f
[i
]=i
,belong
[i
]=i
;
for(register int i
=1;i
<=n
;i
++)
{
x
=find(read());y
=find(read());
if(x
>y
) x
^=y
,y
=x
^y
,x
^=y
;
if(x
==y
) h
[x
]=true;
else h
[x
]|=h
[y
],f
[y
]=x
,belong
[x
]=max(belong
[x
],belong
[y
]);
}
for(register int i
=1;i
<=mx
;i
++)
{
int x
=find(i
);
if(belong
[x
]==i
&&!h
[x
]) maxn
=max(maxn
,x
);
l
[i
]=maxn
;
}
q
=read();
while(q
--)
{
x
=read();y
=read();
puts(x
>l
[y
]?"Yes":"No");
}
}
