线性基系列
线性基是一个基于线性代数和矩阵的东西。
首先是简易安装版传送门。
构造线性基还是看上面的构造法。
然后开始刷题啦~。
BZOJ 2460
2460: [BeiJing2011]元素
Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 1580 Solved: 826
[Submit][Status][Discuss]
Description
相传,在远古时期,位于西方大陆的 Magic Land 上,人们已经掌握了用魔
法矿石炼制法杖的技术。那时人们就认识到,一个法杖的法力取决于使用的矿石。
一般地,矿石越多则法力越强,但物极必反:有时,人们为了获取更强的法力而
使用了很多矿石,却在炼制过程中发现魔法矿石全部消失了,从而无法炼制
出法杖,这个现象被称为“魔法抵消” 。特别地,如果在炼制过程中使用超过
一块同一种矿石,那么一定会发生“魔法抵消”。
后来,随着人们认知水平的提高,这个现象得到了很好的解释。经过了大量
的实验后,著名法师 Dmitri 发现:如果给现在发现的每一种矿石进行合理的编
号(编号为正整数,称为该矿石的元素序号),那么,一个矿石组合会产生“魔
法抵消”当且仅当存在一个非空子集,那些矿石的元素序号按位异或起来
为零。 (如果你不清楚什么是异或,请参见下一页的名词解释。 )例如,使用两
个同样的矿石必将发生“魔法抵消”,因为这两种矿石的元素序号相同,异或起
来为零。
并且人们有了测定魔力的有效途径,已经知道了:合成出来的法杖的魔力
等于每一种矿石的法力之和。人们已经测定了现今发现的所有矿石的法力值,
并且通过实验推算出每一种矿石的元素序号。
现在,给定你以上的矿石信息,请你来计算一下当时可以炼制出的法杖最多
有多大的魔力。
Input
第一行包含一个正整数N,表示矿石的种类数。
接下来 N行,每行两个正整数Numberi 和 Magici,表示这种矿石的元素序号
和魔力值。
Output
仅包一行,一个整数:最大的魔力值
Sample Input
1 10
2 20
3 30
Sample Output
HINT
由于有“魔法抵消”这一事实,每一种矿石最多使用一块。
如果使用全部三种矿石,由于三者的元素序号异或起来:1 xor 2 xor 3 = 0 ,
则会发生魔法抵消,得不到法杖。
可以发现,最佳方案是选择后两种矿石,法力为 20+30=50。
对于全部的数据:N ≤ 1000,Numberi ≤ 10^18
,Magici ≤ 10^4
线性基+贪心。
要选取n个数他们异或以后不为0,并且权值最大。
那么贪心想肯定是从权值最大往最小选啦,能选上就选上,这样获得的权值最大。
那么怎么选呢?我们把他们从大到小插入线性基中。如果能插入,那么说明他是可选的就选上。不能插入就是不可选的。
排序的话只需要第一关键字为权值就行。而不用考虑第二关键字为序号。因为在权值相同的情况下如果有k个物品,这k个物品无论按照什么顺序选取的数量都固定(从线性相关想想为什么?)。于是第一关键字排序完从大到小把能插入线性基的插入就好啦~。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1.sizeof(x)) 4 #define LL long long 5 #define mod 1000000007 6 using namespace std; 7 const int N=1e5+10; 8 int num; 9 struct Node 10 { 11 LL val,num; 12 }good[N]; 13 int n; 14 LL ans; 15 LL liner[65],p; 16 bool cmp(Node a,Node b) 17 { 18 return a.val>b.val; 19 } 20 int main() 21 { 22 scanf("%d",&n); 23 for(int i=1;i<=n;i++) 24 { 25 scanf("%lld%lld",&good[i].num,&good[i].val); 26 } 27 sort(good+1,good+n+1,cmp); 28 ans=0; 29 clr(liner); 30 for(int i=1;i<=n;i++) 31 { 32 p=good[i].num; 33 for(int j=62;j>=0;j--) 34 { 35 if(p>>j) 36 { 37 if(liner[j]) p^=liner[j]; 38 else 39 { 40 liner[j]=p; 41 break; 42 } 43 } 44 } 45 if(p) 46 { 47 ans+=good[i].val; 48 } 49 } 50 printf("%lld\n",ans); 51 return 0; 52 }
hdu 3949
XOR
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3241 Accepted Submission(s): 1117
For each test case, the first line is an integer N(1<=N<=10000), the number of numbers below. The second line contains N integers (each number is between 1 and 10^18). The third line is a number Q(1<=Q<=10000), the number of queries. The fourth line contains Q numbers(each number is between 1 and 10^18) K1,K2,......KQ.
第k小的异或和,这个学习资料里有讲解。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define mod 1000000007 5 #define LL long long 6 using namespace std; 7 const int N=1e4+10; 8 LL a[N]; 9 LL liner[65],per[65]; 10 int n,m,k,q; 11 bool flag; 12 LL p,qy,tag,ans; 13 int main() 14 { 15 int T; 16 scanf("%d",&T); 17 for(int kase=1;kase<=T;kase++) 18 { 19 scanf("%d",&n); 20 for(int i=1;i<=n;i++) 21 scanf("%lld",&a[i]); 22 clr(liner); 23 flag=0; 24 for(int i=1;i<=n;i++) 25 { 26 p=a[i]; 27 for(int j=62;j>=0;j--) 28 { 29 if(p>>j) 30 { 31 if(liner[j]) p^=liner[j]; 32 else 33 { 34 liner[j]=p; 35 break; 36 } 37 } 38 } 39 } 40 for(int i=62;i>=0;i--) 41 { 42 for(int j=i-1;j>=0;j--) 43 if((liner[i]>>j)&1) 44 liner[i]^=liner[j]; 45 } 46 k=0; 47 for(int i=0;i<=62;i++) 48 if(liner[i]) 49 per[++k]=liner[i]; 50 if(k!=n) 51 flag=1; 52 scanf("%d",&q); 53 tag=(1LL<<k); 54 printf("Case #%d:\n",kase); 55 for(int i=1;i<=q;i++) 56 { 57 scanf("%lld",&qy); 58 if(flag) qy--; 59 if(qy>=tag) 60 printf("-1\n"); 61 else 62 { 63 ans=0; 64 for(int j=1;j<=k;j++) 65 if((qy>>(j-1))&1) 66 ans^=per[j]; 67 printf("%lld\n",ans); 68 } 69 } 70 } 71 return 0; 72 }
BZOJ 2115
2115: [Wc2011] Xor
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 3749 Solved: 1571
[Submit][Status][Discuss]
Description
Input
第一行包含两个整数N和 M, 表示该无向图中点的数目与边的数目。 接下来M 行描述 M 条边,每行三个整数Si,Ti ,Di,表示 Si 与Ti之间存在 一条权值为 Di的无向边。 图中可能有重边或自环。
Output
仅包含一个整数,表示最大的XOR和(十进制结果),注意输出后加换行回车。
Sample Input
1 2 2
1 3 2
2 4 1
2 5 1
4 5 3
5 3 4
4 3 2
Sample Output
HINT
Source
那两个博客也有讲这一题。
具体做法是我们找一条1~n的路径,在dfs找路径的过程中记录下所有的环(要注意有重边,要更改下常用的链式前向星结构)的xor值。然后找到的1~n路径的xor值作为初始答案ans。接下来就是在这些环中选择一定的环使xor最大了。对这些环的xor求个线性基。然后从大到小和ans^,若能使ans变大则为有效的,ans^=liner[i]。
为什么呢?第一个问题:我们选取的这条无环路径一定是答案中的无环路径吗?很显然,不一定是。但是由于用我们选取的这条路径到达答案中的无环路径,相当于在选取路径中走多个环(答案路径和选取路径不同部分肯定构成环),因此我们选不选得到答案路径都无所谓,只要最后选取正确的环就行了。
第二个问题:环如果不是在选取路径上,那么能选取吗?我们注意到,我们如果走到一个非路径上的环,该路径到达该环的这条路由于我们要走回来,异或后为0,那么就相当于不用走过这条路。也就相当于凭空走过一个环。因此只要选择正确的环就行了。
那么这两个问题都归结于选取正确的环,所以我们只需要在一条随意选取的路径上,再加上一堆环的xor使该路径xor最大就行了。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define LL long long 5 #define mod 1000000007 6 using namespace std; 7 const int N=2e5+10; 8 int num; 9 LL ans; 10 LL liner[65]; 11 LL a[N],_xor[N]; 12 struct Edge 13 { 14 int next,to; 15 LL val; 16 int rev; 17 }edge[N*2]; 18 int head[N],ecnt; 19 int pre[N]; 20 void addedge(int u,int v,LL d) 21 { 22 edge[++ecnt]=(Edge){head[u],v,d}; 23 head[u]=ecnt; 24 edge[++ecnt]=(Edge){head[v],u,d}; 25 head[v]=ecnt; 26 edge[head[u]].rev=head[v]; 27 edge[head[v]].rev=head[u]; 28 return ; 29 } 30 int n,m,T,t,u,v,cnt; 31 LL p; 32 void init() 33 { 34 clr(pre); 35 clr_1(head); 36 ecnt=0; 37 cnt=0; 38 clr(liner); 39 return ; 40 } 41 void dfs(int u,int fa) 42 { 43 for(int i=head[u];i!=-1;i=edge[i].next) 44 { 45 int t=edge[i].to; 46 if(edge[i].rev!=fa) 47 { 48 if(!pre[t]) 49 { 50 pre[t]=u; 51 _xor[t]=_xor[u]^edge[i].val; 52 dfs(t,i); 53 } 54 else 55 { 56 a[++cnt]=_xor[u]^edge[i].val^_xor[t]; 57 } 58 } 59 } 60 return ; 61 } 62 int main() 63 { 64 scanf("%d%d",&n,&m); 65 init(); 66 for(int i=1;i<=m;i++) 67 { 68 scanf("%d%d%lld",&u,&v,&p); 69 addedge(u,v,p); 70 } 71 pre[1]=1; 72 _xor[1]=0; 73 dfs(1,0); 74 for(int i=1;i<=cnt;i++) 75 { 76 p=a[i]; 77 for(int j=62;j>=0;j--) 78 { 79 if(p>>j) 80 { 81 if(liner[j]) p^=liner[j]; 82 else 83 { 84 liner[j]=p; 85 break; 86 } 87 } 88 } 89 } 90 for(int i=62;i>=0;i--) 91 { 92 for(int j=i-1;j>=0;j--) 93 if((liner[i]>>j)&1) liner[i]^=liner[j]; 94 } 95 ans=_xor[n]; 96 for(int i=62;i>=0;i--) 97 { 98 ans=max(ans,liner[i]^ans); 99 } 100 printf("%lld\n",ans); 101 return 0; 102 }
2844: albus就是要第一个出场
Time Limit: 6 Sec Memory Limit: 128 MBSubmit: 1583 Solved: 657
[Submit][Status][Discuss]
Description
Input
第一行一个数n, 为序列A的长度。接下来一行n个数, 为序列A, 用空格隔开。最后一个数Q, 为给定的数.
Output
Sample Input
1 2 3
1
Sample Output
样例解释:
N = 3, A = [1 2 3]
S = {1, 2, 3}
2^S = {空, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
f(空) = 0
f({1}) = 1
f({2}) = 2
f({3}) = 3
f({1, 2}) = 1 xor 2 = 3
f({1, 3}) = 1 xor 3 = 2
f({2, 3}) = 2 xor 3 = 1
f({1, 2, 3}) = 0
所以
B = [0, 0, 1, 1, 2, 2, 3, 3]
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define mod 10086 5 #define LL long long 6 using namespace std; 7 const int N=1e5+10; 8 LL a[N]; 9 LL liner[65],per[65]; 10 int n,m,k,q; 11 LL p,qy,tag,ans; 12 LL quick_pow(LL n,LL x) 13 { 14 x=(x%mod+mod)%mod; 15 LL res=1; 16 while(n) 17 { 18 if(n&1) res=(res*x)%mod; 19 n>>=1; 20 x=(x*x)%mod; 21 } 22 return res; 23 } 24 int main() 25 { 26 scanf("%d",&n); 27 for(int i=1;i<=n;i++) 28 scanf("%lld",&a[i]); 29 clr(liner); 30 for(int i=1;i<=n;i++) 31 { 32 p=a[i]; 33 for(int j=62;j>=0;j--) 34 { 35 if(p>>j) 36 { 37 if(liner[j]) p^=liner[j]; 38 else 39 { 40 liner[j]=p; 41 break; 42 } 43 } 44 } 45 } 46 for(int i=62;i>=0;i--) 47 { 48 for(int j=i-1;j>=0;j--) 49 if((liner[i]>>j)&1) 50 liner[i]^=liner[j]; 51 } 52 k=0; 53 for(int i=62;i>=0;i--) 54 if(liner[i]) 55 per[++k]=liner[i]; 56 scanf("%lld",&p); 57 ans=0; 58 for(int i=1;i<=k;i++) 59 { 60 ans<<=1; 61 if((p^per[i])<p) 62 { 63 ans|=1; 64 p^=per[i]; 65 } 66 // cout<<i<<" "<<ans<<" "<<p<<endl; 67 } 68 // cout<<n<<" "<<k<<" "<<ans<<endl; 69 printf("%lld\n",(ans%mod*quick_pow((LL)(n-k),2)%mod+1)%mod); 70 return 0; 71 }
bzoj 3811:玛里苟斯