注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2466][中山市选2009]树  

2014-09-20 09:37:38|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2466: [中山市选2009]树

高斯消元解xor方程组
因为没有理解看了好长时间代码
按照惯例题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m;
const int N = 100+10;
typedef int Matrix[N][N];
//n = n+1
void gauss(int n,Matrix a){
int i,j,k,s;
for(i=1;i<n;i++){
for(s = i,j = i+1;j<n;j++)
if(abs(a[j][i]) > abs(a[s][i]))s = j;
if(s!=i)for(j=i;j<=n;j++)swap(a[i][j],a[s][j]);
if(!a[i][i])continue;
for(j=i+1;j<n;j++)
if(a[j][i]){//注意条件
//int l = a[j][i] ^ a[i][i];
//for(k=i;k<=n;k++) a[j][k] ^= a[i][k]^l;
for(k=i;k<=n;k++) a[j][k] ^= a[i][k];//和普通的消元不同
}
}
/*
for(i=n-1;i;i--){
for(j=i+1;j<n;j++)a[i][n] ^= a[i][j]^a[j][n];
a[i][n] = a[i][n] ^ a[i][i];
}*/

}
int scan(){int i;scanf("%d",&i);return i;}
Matrix ma;
int ans,list[N];
void dfs(int x,int sum){
if(sum >= ans) return;
if(!x){ ans = min(ans,sum);return; }
if(ma[x][x]){
int p = ma[x][n+1];
for(int i=x+1;i<=n;i++)
if(ma[x][i]) p^= list[i];
list[x] = p;
if(list[x])dfs(x-1,sum+1);
else dfs(x-1,sum);
}else{//解是任意
list[x] = 0;
dfs(x-1,sum);
list[x] = 1;
dfs(x-1,sum+1);
list[x] = 0;
}
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("pp.txt","w",stdout);
int i,j,a,b;
while((n = scan())){
for(i=1;i<=n+1;i++)
for(j=1;j<=n+1;j++)
ma[i][j] = 0;
for(i=1;i<n;i++){
a = scan();b = scan();
ma[a][b] = ma[b][a] = 1;
}
for(i=1;i<=n;i++)ma[i][i] = ma[i][n+1] = 1;
gauss(n+1,ma);
ans = 1e9+7;
dfs(n,0);
printf("%d\n",ans);
}
return 0;
}

题解:
著名的关灯问题树上版本
网格的版本似乎可以状压暴力?
解xor方程组
xi^xj^... =1
第i个方程表示i点
xi,xj表示点i,j是否被按下
j 的取值是所有与i相邻的点
等号右边表示这个点最后是否需要改变状态
因为似乎可以证明最优情况每个点最多被按下一次,所以可以这么列方程(我不知道为啥)

先处理出倒三角(和普通的高斯消元略有不同,具体看代码)
然后带入消元
因为有多解所以对于不确定的项需要暴力
加一个最优剪枝
  评论这张
 
阅读(50)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017