个人网站找谁建设好,东莞市品牌网站建设价格,洛阳网站建设多少钱,提供佛山顺德网站设计正题
题目链接:https://ac.nowcoder.com/acm/contest/1100/C 题目大意 nnn个数字mmm张扑克牌#xff0c;每张两面有各有一个数字#xff0c;可以选择一些扑克牌使用正面的数字#xff0c;一些使用反面的#xff0c;qqq次询问能否凑出l∼rl\sim rl∼r。 1≤n,m,q≤1051\leq…正题
题目链接:https://ac.nowcoder.com/acm/contest/1100/C 题目大意
nnn个数字mmm张扑克牌每张两面有各有一个数字可以选择一些扑克牌使用正面的数字一些使用反面的qqq次询问能否凑出l∼rl\sim rl∼r。
1≤n,m,q≤1051\leq n,m,q\leq 10^51≤n,m,q≤105 解题思路
每张牌看成连接两个点的一条边那么显然如果一个大小为kkk的连通块有kkk条或以上的边那么肯定能抽出整个联通块。
而如果是k−1k-1k−1条边那么这棵树最多有一个数字无法被抽出所以包括整棵树的区间不合法并查集处理出这些区间判断即可。
时间复杂度O(nα(n))O(n\alpha (n))O(nα(n)) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510;
int n,m,fa[N],w[N],siz[N],l[N],r[N],mx[N];
int find(int x)
{return (fa[x]x)?x:(fa[x]find(fa[x]));}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)fa[i]i,siz[i]1;for(int i1,x,y;im;i){scanf(%d%d,x,y);xfind(x),yfind(y);if(xy){w[x];continue;}fa[x]y;w[y]w[x]1;siz[y]siz[x];}memset(l,0x3f,sizeof(l));for(int i1;in;i){int xfind(i);l[x]min(l[x],i);r[x]max(r[x],i);}for(int i1;in;i){if(find(i)i){if(w[i]!siz[i]-1)continue;mx[r[i]]max(mx[r[i]],l[i]);}}for(int i1;in;i)mx[i]max(mx[i-1],mx[i]);scanf(%d,m);while(m--){int l,r;scanf(%d%d,l,r);if(lmx[r])puts(Yes);else puts(No);}return 0;
}
