WC2011 Xor
对拍全正确，OJ上却4sWA了，只得了50分
d记录生成树数上s到每个点路径上xor和
a记录每个简单环的xor和(树边xor和^非树边)
cnt记录简单环(非树边)的个数
LL d[N],a[N],cnt=0,ans;
bool v[N];
void dfs(int x)
{
v[x]=true;
R(i,x){
int y=e[i].go;
if(!v[y]){
d[y]=d[x]^e[i].w;
dfs(y);
}
else a[++cnt]=d[x]^d[y]^e[i].w;
}
}
可用线性基做
int gauss_lb()
//高斯消元计算"线性基",即主元的个数--返回值
{
int k=1;//记录当前主元所在行
D(i,64,1){
int t=0;//(记录当前列主元所在行的最大值)
F(j,k,cnt) if((a[j]>>i-1)&1) t=j;
if(!t) continue;//如果该列不存在主元则找下一列
swap(a[k],a[t]);//(如果t==k则相当于不交换)
F(j,k+1,cnt) if((a[j]>>i-1)&1) a[j]^=a[k];//消元成阶梯形矩阵
k++;
}
return --k;//最后多算了一次,减去
}
#include<bits/stdc++.h>
#define mec(a,x) memset(a,x,sizeof(a))
#define F(i,s,t) for(int i=(s);i<=(t);i++)
#define D(i,s,t) for(int i=(s);i>=(t);i--)
#define R(i,x) for(int i=head[x];i;i=e[i].nxt)
using namespace std;
const int inf=1<<30;
const int M=(int)1e5+10,N=50000+10;
typedef long long LL;
int n,m;
int head[N],tot=0;
struct edge{int fro,go,nxt;LL w;}e[M<<1];
void addedge(int x,int y,LL z)//无向图双向边
{
e[++tot]=(edge){x,y,head[x],z};head[x]=tot;
e[++tot]=(edge){y,x,head[y],z};head[y]=tot;
}
/*****************************************/
LL d[N],a[N],cnt=0,ans;
bool v[N];
void dfs(int x)
{
v[x]=true;
R(i,x){
int y=e[i].go;
if(!v[y]){
d[y]=d[x]^e[i].w;
dfs(y);
}
else a[++cnt]=d[x]^d[y]^e[i].w;
}
}
int gauss_lb()
{
int k=1;
D(i,64,1){
int t=0;
F(j,k,cnt) if((a[j]>>i-1)&1) t=j;
if(!t) continue;
swap(a[k],a[t]);
F(j,k+1,cnt) if((a[j]>>i-1)&1) a[j]^=a[k];
k++;
}
return --k;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("xor.in", "r", stdin);
// freopen("bzoj2115.txt", "w", stdout);
#endif
scanf("%d%d",&n,&m);
F(i,1,m){
int x,y;LL z;
scanf("%d%d",&x,&y);
scanf("%lld",&z);
addedge(x,y,z);
}
dfs(1);
ans=d[n];//d不参与消元
int num=gauss_lb();
F(i,1,num) ans=max(ans,ans^a[i]);//该数(环)选or不选
printf("%lld\n",ans);
return 0;
}
CQOI2013 新Nim游戏
在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。
第二回合也一样，第二个游戏者也有这样一次机会。从第三个回合（又轮到第一个游戏者）开始，规则和Nim游戏一样。
问先手是否有必胜策略，如果可以获胜的话，要让第一回合拿的火柴总数尽量小。
50%:
关键：先手一定有必胜策略。（极端情况：拿走n-1堆）==>输出-1是坑nc的,我就nc了
对n<=10的数据，用二进制表示状态
直接暴力枚举每种第一轮A拿了过后的状态，再暴力枚举第一轮B拿了过后的状态，
判断合法后，对剩下的进行普通的Nim游戏，取所有合法状态拿走的最小总数即可
int n,tmp[N],a[N];
LL ans;
void work(int co)
{
int tot=0;
LL sum=0;//记录拿的总数
for(int i=1;i<=n;i++)
if(!(co&(1<<(i-1)))) tmp[++tot]=a[i];//剩余的状态
else sum+=1ll*a[i];
if(sum>ans) return;
//枚举B拿的状态 1表示未拿,0表示拿
for(int i=1;i<=(1<<tot)-1;i++){
int t=0;
for(int j=1;j<=tot;j++)
if(i&(1<<(j-1))) t^=tmp[j];
if(t==0) return;//不合法的情况!
}
ans=min(ans,sum);
return;
}
/***main***/
if(n<=10){//用二进制数枚举A拿的状态:1表示拿了,0表示没拿
ans=inf;
for(int co=0;co<=(1<<n)-1;co++) work(co);
printf("%lld\n",ans);
}
100%:
第一次拿完后，要使剩下的火柴中不存在异或和为0的子集，且让子集和最大
求解极大线性无关组，即高斯消元求主元堆的火柴棒个数之和res，ans=sum-res
b[]记录每列的主元:b[3]=a[2]表示matrix[3][2]为该列主元
找到则break
高斯消元(矩阵初等xor变换)后求线性基(主元)
附带线性基(主元)求和
注：不需要化为化简阶梯矩阵,即最后答案不一定有序,但
消元前排一下序方便些
LL gauss_lb()
{
sort(a+1,a+n+1);
D(i,n,1){
int t=a[i];
D(j,31,0) if(a[i]>>j&1){
if(b[j]) a[i]^=b[j];//xor变换
else{b[j]=a[i];break;}
}
if(a[i]) res+=(LL)t;//该行没有被消为0==>存在主元
}
return res;
}
CQOI2014 和谐矩阵matrix
我们称一个由0和1组成的矩阵是和谐的，当且仅当每个元素都有偶数个相邻的1。一个元素相邻的元素包括它本
身，及他上下左右的4个元素（如果存在）。
给定矩阵的行数和列数，请计算并输出一个和谐的矩阵。注意：所有元素为0的矩阵是不允许的。
题解（%regina8023）
高斯消元解异或方程组（具体做法见【POJ 1222】）。
有两种做法：
①速度较慢的方法：
对于矩阵中的每一个元素都可以列出一个方程，m∗n个未知数，m∗n个方程(f[i][j]表示第i个对第j个有影响)：
a[k]+f[1][k]∗a[1]+f[2][k]∗a[2]+...f[tot][k]∗a[tot]=0(mod2)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
int a[2000][2000],ans[2000],d[10][5],id[50][50],n,m;
void Gauss(int n,int m)
{
for (int i=1;i<=n;i++)
{
int j;
for (j=i;j<=m&&!a[j][i];j++);
if (j>n) continue;
if (j!=i)
for (int k=i;k<=m;k++)
swap(a[i][k],a[j][k]);
for (int j=i+1;j<=n;j++)
if (a[j][i])
for (int k=i;k<=m;k++)
a[j][k]^=a[i][k];
}
for (int i=n;i;i--)
{
if (!a[i][i])
{
ans[i]=1;
continue;
}
for (int j=i+1;j<=n;j++)
a[i][m]^=(ans[j]*a[i][j]);
ans[i]=a[i][m];
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
d[0][1]=d[0][2]=0;
d[1][1]=d[2][1]=0,d[1][2]=1,d[2][2]=-1;
d[3][2]=d[4][2]=0,d[3][1]=1,d[4][1]=-1;
int cnt=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
id[i][j]=++cnt;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
for (int k=0;k<=4;k++)
{
int p=id[i+d[k][1]][j+d[k][2]];
if (p) a[id[i][j]][p]=1;
}
Gauss(cnt,cnt+1);
cnt=0;
for (int i=1;i<=n;i++)
{
printf("%d",ans[++cnt]);
for (int j=2;j<=m;j++)
printf(" %d",ans[++cnt]);
printf("\n");
}
return 0;
}
②速度快的办法：
如果第一行的数知道了，我们就可以推出其他行的数。
那么如何判断第一行的数的一种填法是否合法呢?很简单，我们递推出m+1行的数，当且仅当这一行都是0时满足题意。
那么，我们就有了一种想法。
直接把m+1行的每个数用x[1..n]表示出来，这一定是个系数只为0/1的式子。然后让这个异或值=0，就可以解异或方程组了。
系数怎么推呢？
for1(i,n)b[1][i]=(ll)1<<i-1;
for2(i,2,m+1)
for1(j,n)
b[i][j]=b[i-1][j]^b[i-1][j-1]^b[i-1][j+1]^b[i-2][j];
然后解方程就可以了。
代码（贴上别人跑得快的）
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define drp(i,x,y) for(int i=x;i>=y;i--)
typedef long long LL;
const int N=52;
int n,m;
LL a[N]={0},b[N][N]={0};
bool c[N][N]={0};
void Gauss() {
rep(i,1,m) {
int j=i;
while (j<=m&&!(a[j]>>i-1&1)) j++;
if (j>m) continue;
swap(a[i],a[j]);
rep(k,i+1,m) if (a[k]>>i-1&1)
a[k]^=a[i];
}
drp(i,m,1) {
c[1][i]=a[i]>>m&1;
if (!(a[i]>>i-1&1)) {c[1][i]=1;continue;}
rep(j,i+1,m) if (a[i]>>j-1&1)
c[1][i]^=c[1][j];
}
}
int main() {
// freopen("test.out","w",stdout);
scanf("%d%d",&n,&m);
rep(i,1,m) b[1][i]=(LL)1<<i-1;
rep(i,2,n+1) rep(j,1,m)
b[i][j]=b[i-1][j]^b[i-2][j]^b[i-1][j-1]^b[i-1][j+1];
rep(i,1,m) a[i]=b[n+1][i];
Gauss();
rep(i,2,n) rep(j,1,m)
c[i][j]=c[i-1][j]^c[i-2][j]^c[i-1][j-1]^c[i-1][j+1];
rep(i,1,n) {rep(j,1,m) printf("%d ",c[i][j]);printf("\n");}
return 0;
}
评论 (0)
