题目
传送门 to nowcoder
题目描述 小
w
w
w 有一副魔术扑克——每张扑克既有正面、又有反面。共
k
k
k 张牌。他每一张牌都可以选择某一面打出。现在问是否存在一种方案，能够打出
[
l
,
r
]
[l,r]
[l,r] 的顺子。
输入输出格式 我忘了。
数据范围与约定
1
≤
l
≤
r
≤
n
≤
1
0
5
,
k
≤
1
0
5
1\le l\le r\le n\le 10^5,k\le 10^5
1≤l≤r≤n≤105,k≤105 。
思路壹
将每一个扑克牌两面的数字当做一条边的两个端点。那么每个点都代表一个数字。一条边可以选择“搞定”一个端点。某个点被“搞定”，就是某个数字可以被打出。
首先是这样的：
对于一个联通的图，如果至少有一个点已经被搞定，并且没有用这个图内的边，那么这个图的点都可以被搞定。
原因很简单：
对这个图求一个生成树，将已经被搞定的点作为树根。每条边“搞定”子节点。
所以接下来又有这样的东西：
如果一个
n
n
n 个点的联通图有不小于
n
n
n 条边，那么整个图都可以被搞定。
原因很简单：
图里肯定有环（如果没有环就会是树，就只有
n
−
1
n-1
n−1 条边）。找到这个环。环上的点可以只用环上的边“搞定”（显然）。去掉一些边，让原图变成基环树（环就是找到的这个环）。发现每棵树都是已经有一个点被“搞定”的图。由前面的结论，整个图都会被搞定。
与这个结论是相辅的是：
如果一个
n
n
n 个点的联通图有少于
n
n
n 条边，那么整张图无法全部被搞定。
因为：
n
n
n 个点至少要
n
n
n 条边嘛！（就是说，你要打
[
l
,
r
]
[l,r]
[l,r] 的顺子，你至少得有
r
−
l
+
1
r-l+1
r−l+1 张牌）。
所以直接找边数小于
n
n
n 的联通子图——也就是树。
这个树中一旦某个点不在顺子的考虑范围中，就可以认为它已经被“搞定”。由前面的结论，一定可以搞定整棵树。
所以这棵树中的点无法被“搞定”，当且仅当
[
m
i
n
,
m
a
x
]
∈
[
l
,
r
]
[min,max]\in[l,r]
[min,max]∈[l,r]（也就是整个都包含在顺子的查询区间内）。这等价于
l
≤
m
i
n
∧
m
a
x
≤
r
l\le min\wedge max\le r
l≤min∧max≤r 。
所以将查询排序（右端点递增），本次查询内满足
m
a
x
≤
r
max\le r
max≤r 的只会越来越多。
现在就要
[
l
,
r
]
[l,r]
[l,r] 中没有任何一个
m
i
n
min
min 。因为我们已经满足
m
a
x
≤
r
max\le r
max≤r ，所以不能让
l
≤
m
i
n
l\le min
l≤min 。就是说，
∀
m
i
n
<
l
\forall min<l
∀min<l 。而
m
i
n
≤
m
a
x
≤
r
min\le max\le r
min≤max≤r ，所以等价于
m
i
n
∉
[
l
,
r
]
min\not\in [l,r]
min∈[l,r] 。用树状数组就好了。
代码壹
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std
;
const int MaxN
= 100005;
int n
, k
, q
;
int fa
[MaxN
], cntNode
[MaxN
], cntEdge
[MaxN
];
int minV
[MaxN
], maxV
[MaxN
], cntTree
;
inline int findFa(int a
){
if(fa
[a
] != a
)
fa
[a
] = findFa(fa
[a
]);
return fa
[a
];
}
struct PPL
{
int l
, r
, id
;
bool operator<(const PPL
&that
)const{
return r
< that
.r
;
}
}tree
[MaxN
], query
[MaxN
];
void init(){
scanf("%d %d",&n
,&k
);
for(int i
=1; i
<=n
; ++i
){
fa
[i
] = i
;
cntEdge
[i
] = 0;
cntNode
[i
] = 1;
minV
[i
] = maxV
[i
] = i
;
}
for(int i
=1,x
,y
; i
<=k
; ++i
){
scanf("%d %d",&x
,&y
);
x
= findFa(x
);
y
= findFa(y
);
++ cntEdge
[x
];
if(x
!= y
){
cntEdge
[x
] += cntEdge
[y
];
cntNode
[x
] += cntNode
[y
];
fa
[y
] = x
;
minV
[x
] = min(minV
[x
],minV
[y
]);
maxV
[x
] = max(maxV
[x
],maxV
[y
]);
}
}
cntTree
= 0;
for(int i
=1; i
<=n
; ++i
)
if(fa
[i
] == i
and cntNode
[i
] == cntEdge
[i
]+1){
++ cntTree
;
tree
[cntTree
].l
= minV
[i
];
tree
[cntTree
].r
= maxV
[i
];
}
sort(tree
+1,tree
+cntTree
+1);
scanf("%d",&q
);
for(int i
=1,a
,b
; i
<=q
; ++i
){
scanf("%d %d",&a
,&b
);
query
[i
].l
= a
;
query
[i
].r
= b
;
query
[i
].id
= i
;
}
sort(query
+1,query
+q
+1);
}
int BIT
[MaxN
];
void modifyBIT(int id
,int v
){
for(; id
<=n
; id
+=(id
&-id
))
BIT
[id
] += v
;
}
int queryBIT(int id
){
int sigma
= 0;
for(; id
; id
-=(id
&-id
))
sigma
+= BIT
[id
];
return sigma
;
}
int answer
[MaxN
];
void work(){
int top
= 1;
for(int i
=1; i
<=q
; ++i
){
while(top
<= cntTree
and tree
[top
].r
<= query
[i
].r
)
modifyBIT(tree
[top
++].l
,1);
answer
[query
[i
].id
] = queryBIT(query
[i
].r
)-queryBIT(query
[i
].l
-1);
}
for(int i
=1; i
<=q
; ++i
)
if(not answer
[i
]) puts("Yes");
else puts("No");
}
int main(){
init(); work();
return 0;
}
鸣谢
这位大佬的博客给了我思路。
思路贰
二分图匹配！直接将扑克与数值相连。
匈牙利算法中每次都会确保以前匹配的还是被匹配。
所以将数值作为主体。
代码贰
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std
;
const int MaxN
= 100005;
int n
, k
, q
; vector
<int> g
[MaxN
];
struct Query
{
int l
, r
, id
;
bool operator<(const Query
&that
)const{
if(l
!= that
.l
)
return l
< that
.l
;
return r
< that
.r
;
}
}query
[MaxN
];
int answer
[MaxN
];
void init(){
scanf("%d %d",&n
,&k
);
for(int i
=1,x
,y
; i
<=k
; ++i
){
scanf("%d %d",&x
,&y
);
g
[x
].push_back(i
);
g
[y
].push_back(i
);
}
scanf("%d",&q
);
for(int i
=1; i
<=q
; ++i
){
scanf("%d %d",&query
[i
].l
,&query
[i
].r
);
query
[i
].id
= i
;
}
sort(query
+1,query
+q
+1);
}
bool vis
[MaxN
]; int match
[MaxN
], ppl
[MaxN
];
vector
<int> visited
;
bool XYL(int x
){
vis
[x
] = true;
visited
.push_back(x
);
for(int i
=0,len
=g
[x
].size(); i
<len
; ++i
)
if(not match
[g
[x
][i
]] or (not vis
[match
[g
[x
][i
]]] and XYL(match
[g
[x
][i
]]))){
match
[g
[x
][i
]] = x
;
ppl
[x
] = g
[x
][i
];
return true;
}
return false;
}
void release(int x
){
match
[ppl
[x
]] = 0;
ppl
[x
] = 0;
}
void solve(){
for(int i
=1,nowl
=1,nowr
=0; i
<=q
; ){
while(nowl
< query
[i
].l
and nowl
<= nowr
)
release(nowl
++);
if(nowl
== nowr
+1){
nowl
= query
[i
].l
;
nowr
= query
[i
].l
-1;
}
for(bool f
=XYL(nowr
+1); true; f
=XYL(nowr
+1)){
if(f
) ++ nowr
;
while(not visited
.empty()){
vis
[visited
.back()] = false;
visited
.pop_back();
}
if(not f
) break;
}
for(; i
<=q
and query
[i
].l
==nowl
; ++i
)
answer
[query
[i
].id
] = (query
[i
].r
<= nowr
);
}
for(int i
=1; i
<=q
; ++i
)
puts(answer
[i
]?"Yes":"No");
}
int main(){
init(); solve();
return 0;
}
