首页 > 代码库 > 急训 Day 1 (2)
急训 Day 1 (2)
Mushroom的区间
【题目描述】
Mushroom有一行数,初始时全部是0。现在Mushroom有m个区间[L,R],他希望用以下操作得到新的序列。
从m个给定区间中选择一个区间[s,t],把区间中的数对应元素全部翻转。(0变1,1变0)
请告诉Mushroom他能得到多少区间。(模10^9+7)
【输入格式】
第一行包含两个整数n,m。表示n个数和m个区间。
接下来m行是所表示的区间。
【输出格式】
一个整数,表示能得到的区间数。
【样例输入】
3 3
1 1
2 2
3 3
【样例输出】
8
【数据范围】
对于30%的数据,n,m<=20
对于60%的数据,n,m<=100
对于100%的数据,n,m<=100000
【样例解释】
每个位置都可以单个修改,所以有8种可能。
神奇的解法,思路:去掉一些可以用其他区间覆盖掉他的区间(该区间则视为无效)最后有效区间数则为幂,ans=2^(边数)
如何维护区间是否被覆盖,这里有一个很神奇的并查集做法,因为L可以等于R 所以考虑平移左区间一位(答案不改变)
每次读入判断两端点的father 如果father一样则说明这个区间是可以被之前出现过的区间所覆盖的(一定等效)
#include<iostream>#include<cstring>#include<cstdio>#include<map>#include<vector>#include<algorithm>#include<queue>using namespace std;const int MAX=1000005;const int MOD=1000000000+7;int n,m,ans=1;int fa[MAX];int findfa(int k){ if (fa[k]!=k) return fa[k]=findfa(fa[k]); return fa[k];}int main(){ cin>>n>>m; for (int i=0;i<=n;i++) fa[i]=i; for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); int f1=findfa(x-1); int f2=findfa(y); if (f1!=f2) { fa[f1]=f2; ans=ans*2%MOD; } } cout<<ans;}
急训 Day 1 (2)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。