poj1753 (高斯消元法求异或方程组)
2024-10-06 14:45:36
题目链接:http://poj.org/problem?id=1753
题意:经典开关问题,和poj1222一样,进行两次高斯消元即可,只用初始化的时候改一下初始状态。可能存在无解或多解的情况,多解要枚举自由变元的所有状态。
AC代码:
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std; const int maxn=;
const int inf=0x3f3f3f3f;
int mp[][],a[maxn][maxn],x[maxn],equ,var,free_x[maxn];
char s[]; void init(int p){
memset(a,,sizeof(a));
for(int i=;i<;++i){
for(int j=;j<;++j){
int t=i*+j;
a[t][]=p^mp[i][j];
a[t][t]=;
if(i>) a[t][(i-)*+j]=;
if(i<) a[t][(i+)*+j]=;
if(j>) a[t][i*+j-]=;
if(j<) a[t][i*+j+]=;
}
}
} int Gauss(){
int r=,cnt=;
for(int c=;r<equ&&c<var;++r,++c){
int Maxr=r;
for(int i=r+;i<equ;++i){
if(abs(a[i][c])>abs(a[Maxr][c]))
Maxr=i;
}
if(Maxr!=r){
for(int i=c;i<var+;++i)
swap(a[r][i],a[Maxr][i]);
}
if(!a[r][c]){
--r;
free_x[cnt++]=c;
continue;
}
for(int i=r+;i<equ;++i){
if(!a[i][c]) continue;
for(int j=c;j<var+;++j)
a[i][j]^=a[r][j];
}
}
for(int i=r;i<equ;++i)
if(a[i][var])
return -;
return var-r;
} int solve(int t){
int ret=inf;
for(int i=;i<(<<t);++i){
int cnt=;
memset(x,,sizeof(x));
for(int j=;j<t;++j){
if((i>>j)&){
++cnt;
x[free_x[j]]=;
}
}
for(int j=var-t-;j>=;--j){
int tmp=a[j][var],tp,ok=;
for(int k=j;k<var;++k){
if(!a[j][k]) continue;
if(ok){
ok=;
tp=k;
}
else{
tmp^=x[k];
}
}
x[tp]=tmp;
cnt+=x[tp];
}
ret=min(ret,cnt);
}
return ret;
} int main(){
equ=var=;
for(int i=;i<;++i){
scanf("%s",s);
for(int j=;j<;++j)
if(s[j]=='b') mp[i][j]=;
else mp[i][j]=;
}
init();
int t1,t2,t3,t4;
t1=Gauss();
if(t1!=-) t2=solve(t1);
init();
t3=Gauss();
if(t3!=-) t4=solve(t3);
if(t1==-&&t3==-)
printf("Impossible\n");
else
printf("%d\n",min(t2,t4));
return ;
}
最新文章
- C#操作剪贴板
- LeetCode:Text Justification
- Codeforces Round #373 (Div. 1)
- 【C#4.0图解教程】笔记(第19章~第25章)
- 如何在安卓/data(而不是/data/data)目录下进行文件的读写操作
- 3DShader之移位贴图(Displacement Mapping)
- 《Programming WPF》翻译 第5章 6.触发器
- artdialog关闭弹出窗口
- cv2.cornerHarris()详解 python+OpenCV 中的 Harris 角点检测
- 使用Java面向对象单词必备
- Android——媒体库 相关知识总结贴
- jfinal集成cas单点认证实践
- Haskell语言练习
- 第三次spring冲刺2
- async 和 await的前世今生 (转载)
- Nuget~打包时添加powershell初始化脚本
- liunx less 命令
- 对于";第一次创业者";应该给什么样的建议
- yii2:oracle date类型字段的写入或查询
- Python之virtualenv沙盒环境