首页 > 代码库 > 【BZOJ3563/3569】DZY Loves Chinese II 线性基神题
【BZOJ3563/3569】DZY Loves Chinese II 线性基神题
【BZOJ3563/3569】DZY Loves Chinese II
Description
神校XJ之学霸兮,Dzy皇考曰JC。
摄提贞于孟陬兮,惟庚寅Dzy以降。
纷Dzy既有此内美兮,又重之以修能。
遂降临于OI界,欲以神力而凌♂辱众生。
今Dzy有一魞歄图,其上有N座祭坛,又有M条膴蠁边。
时而Dzy狂WA而怒发冲冠,神力外溢,遂有K条膴蠁边灰飞烟灭。
而后俟其日A50题则又令其复原。(可视为立即复原)
然若有祭坛无法相互到达,Dzy之神力便会大减,于是欲知其是否连通。
Input
第一行N,M
接下来M行x,y:表示M条膴蠁边,依次编号
接下来一行Q
接下来Q行:
每行第一个数K而后K个编号c1~cK:表示K条边,编号为c1~cK
为了体现在线,c1~cK均需异或之前回答为连通的个数
Output
对于每个询问输出:连通则为‘Connected’,不连通则为‘Disconnected’
(不加引号)
Sample Input
5 10
2 1
3 2
4 2
5 1
5 3
4 1
4 3
5 2
3 1
5 4
5
1 1
3 7 0 3
4 0 7 4 6
2 2 7
4 5 0 2 13
2 1
3 2
4 2
5 1
5 3
4 1
4 3
5 2
3 1
5 4
5
1 1
3 7 0 3
4 0 7 4 6
2 2 7
4 5 0 2 13
Sample Output
Connected
Connected
Connected
Connected
Disconnected
Connected
Connected
Connected
Disconnected
HINT
N≤100000 M≤500000 Q≤50000 1≤K≤15
数据保证没有重边与自环
题解:BZ3563真的是一道doubi题啊~~~
但是BZ3569页真是够神的,看了题解——还有这种操作?
好吧我从做题人的角度来分析一下这道题。
我们依旧是利用DFS树的优秀性质,先求出DFS树,然后整棵树不联通当且仅当存在一条树边,使得它和所有覆盖它的非树边都被切掉(覆盖一条边:指的是将这条树边切掉、整棵树形成两个部分后,跨越这两个部分的非树边)。
那么我们强行往线性基上去构造,我们的目的就是使得:一旦存在某条树边和所有覆盖它的非树边都被切掉,那么得到的异或和就是0,否则异或和是1。
然后就容易去构造了,直接给每条非树边都赋一个随机权值,然后每条树边的权值就是所有覆盖它的非树边的权值的异或和。但我们怎样才能求出这个异或和呢?其实打一个标记,再DFS一次就行了,自己yy一下?
#include <cstdio>#include <cstring>#include <iostream>#include <cstdlib>using namespace std;int n,m,q,cnt,tot,ans;int to[1000010],next[1000010],head[100010],val[500010],tag[100010],vis[100010],v[20];int rd(){ int ret=0,f=1; char gc=getchar(); while(gc<‘0‘||gc>‘9‘) {if(gc==‘-‘)f=-f; gc=getchar();} while(gc>=‘0‘&&gc<=‘9‘) ret=ret*10+gc-‘0‘,gc=getchar(); return ret*f;}void dfs1(int x,int fa){ vis[x]=1; for(int i=head[x];i!=-1;i=next[i]) { if(to[i]==fa||val[i>>1]) continue; if(vis[to[i]]!=1) dfs1(to[i],x); else val[i>>1]=rand()*rand(),tag[to[i]]^=val[i>>1],tag[x]^=val[i>>1]; }}void dfs2(int x,int fa){ vis[x]=2; for(int i=head[x];i!=-1;i=next[i]) { if(to[i]==fa) continue; if(vis[to[i]]!=2) dfs2(to[i],x),val[i>>1]=tag[to[i]],tag[x]^=tag[to[i]]; }}int gauss(){ int i,j; tot=0; for(i=1<<30;i;i>>=1) { for(j=++tot;j<=v[0];j++) if(v[j]&i) { swap(v[j],v[tot]); break; } if(!(v[tot]&i)) { tot--; continue; } for(j=1;j<=v[0];j++) if(j!=tot&&(v[j]&i)) v[j]^=v[tot]; } if(tot==v[0]) { printf("Connected\n"); return 1; } else { printf("Disconnected\n"); return 0; }}void add(int a,int b){ to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;}int main(){ srand(2333666); n=rd(),m=rd(); int i,j,a,b; memset(head,-1,sizeof(head)); for(i=1;i<=m;i++) a=rd(),b=rd(),add(a,b),add(b,a); dfs1(1,0),dfs2(1,0); q=rd(); for(i=1;i<=q;i++) { memset(v,0,sizeof(v)); v[0]=rd(); for(j=1;j<=v[0];j++) v[j]=val[(rd()^ans)-1]; ans+=gauss(); } return 0;}
【BZOJ3563/3569】DZY Loves Chinese II 线性基神题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。