为什么不搞\(T2\)？？？
因为我太菜了，那题我是真的搞不出来
题目描述
链接：https://ac.nowcoder.com/acm/contest/1100/C
来源：牛客网
小\(w\)喜欢打牌，某天小\(w\)与\(dogenya\)在一起玩扑克牌，这种扑克牌的面值都在\(1\)到\(n\)，原本扑克牌只有一面，而小\(w\)手中的扑克牌是双面的魔术扑克（正反两面均有数字，可以随时进行切换），小\(w\)这个人就准备用它来出老千作弊。小\(w\)想要打出一些顺子，我们定义打出一个\(l\)到\(r\)的顺子需要面值为从\(l\)到\(r\)的卡牌各一张。小\(w\)想问问你，他能否利用手中的魔术卡牌打出这些顺子呢？
输入描述:
首先输入一行2个正整数\(n\)，\(k\)，表示牌面为\(1\)~\(n\)，小\(w\)手中有\(k\)张魔术扑克牌。
然后输入\(k\)行，每行两个数字，表示卡牌的正面和反面的面值。
接下来输入一行一个正整数\(q\)，表示\(q\)组查询，然后每组占一行查询输入两个整数\(l\),\(r\)。表示查询小\(w\)能否打出这么一个\(l\)到\(r\)的顺子。
输出描述:
对于输出"\(Yes\)"表示可以，"\(No\)"表示不可以。（不含引号）
每个查询都是独立的，查询之间互不影响。
题解
我在考试的时候看出来这是个图了，也想过正反面连边了，但是一些操作没想到，这题还是没能搞出来……
首先我们可以考虑一个事儿，就是我们不判自环重边的时候，有几张牌，就会连几条边
那一个数字可以使用的要求是什么呢，就是它的出度不为零（无向图
因为我们每张牌的正反面都要互相连边，假如说某个数字的出度为零，那么就说明这个数字没有在任意一张牌上出现过
那么我们就可以想到连完边以后，看一下图中各个连通块里有多少条边，就可以知道包含这个连通块里的某数字的牌一共有几张
举个栗子：
我们有三张牌，第一张两面是\(1,2\)，第二张是\(2,3\)，第三张是\(4,4\)
我们先找\(1\)所在连通块有几条边几个点，发现有两条边三个点，那么就说明只有两张牌包含这三个数字，这三个数字就一定不能同时出现
此时如果我们再加一张\(1,3\)的牌，就可以了
那么我们就可以发现，如果一个连通块是一棵树，那么它包含的数字一定不可能同时出现
我们就可以判一下有几个连通块是树
我们再考虑一个事儿，树上的数字一定不能被使用吗？
不是，只要我们不同时选用树上的所有点就可以使用
那么我们就可以记录一下每个树里的最大值和最小值，如果有一个顺子包含最小值，那么它不能包含最大值，否则它一定包含整棵树
如果一个顺子不包含最小值，那么这个连通块里的数字我们随便用
所以我们可以设一个数组\(r[i]\)，记录以\(i\)为最小值的树的最大值是多少
从头到尾扫一遍每个查询区间，看有没有出现\(r[i]\)小于等于右端点的情况
我最后还特判了一下是不是每张牌的正反面都相等，不然找连通块会炸
可能是我的代码常数太大？？？反正别人做法跟我一样但是不用特判
话说考场上这题默认正反面相同写个暴力能拿50分……
宁康康代码：
#include<bits/stdc++.h>
using namespace std;
#define rint register int
int n, q, k, cnt, tag, b, minn, maxn, num, nump;
int head[100010], r[100010], vis[100010], t[100010], add[100010];
struct edge{
int nxt, to;
}a[200010];
inline void addedge( int x, int y ){
a[++cnt].nxt = head[x];
a[cnt].to = y;
head[x] = cnt;
}
inline int read( void ){
int re = 0, f = 1; char ch = getchar();
while( ch > '9' || ch < '0' ){
if( ch == '-' ) f = -1;
ch = getchar();
}
while( ch >= '0' && ch <= '9' ){
re = re * 10 + ch - '0';
ch = getchar();
}
return re * f;
}
inline void dfs( int now, int fa ){
maxn = max( maxn, now );
minn = min( minn, now );
vis[now] = 1;
nump++;
for( rint i = head[now]; i; i = a[i].nxt ){
int v = a[i].to; num++;
if( v == fa || vis[v] ) continue ;
dfs( v, now );
}
}
int main( void ){
n = read(); k = read();
for( rint i = 1; i <= k; i++ ){
int u, v; u = read(); v = read();
addedge( u, v ); addedge( v, u );
t[u] = 1; t[v] = 1;
if( u != v ) b = 1;
}
memset( r, 0x3f, sizeof( r ) );
if( !b ){
for( rint i = 1; i <= n; i++ ) add[i] = add[i - 1] + t[i];
q = read();
for( rint i = 1; i <= q; i++ ){
int u, v; u = read(); v = read();
if( add[v] - add[u] == v - u ) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
for( rint i = 1; i <= n; i++ ){
if( !vis[i] ){
maxn = 0, minn = 0x3f3f3f3f;
num = 0; nump = 0;
dfs( i, i );
if( num / 2 < nump ){
r[minn] = maxn;
}
}
}
q = read();
//for( rint i = 1; i <= n; i++ ) cout << r[i] << ' ';
for( rint i = 1; i <= q; i++ ){
tag = 0;
int u, v; u = read(); v = read();
for( rint j = u; j <= v; j++ ){
if( r[j] <= v ){
cout << "No" << endl;
tag = 1; break;
}
}
if( !tag ) cout << "Yes" << endl;
}
return 0;
}