高斯消元
HJWJBSR
posted @ 2015年6月02日 17:27
in 专题
, 425 阅读
Orzei了hzwer的代码，还算是学了高斯消元吧。。。然后开始水了几道题。感觉高斯消元的题目有的思路还是很屌的。。。
BZOJ1013球形空间产生器：直接根据每个点到球心的距离相等列方程，然后直接Gauss()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #include <iostream>#include <cmath>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define N 105#define eps 1e-6#define INF 0x7f7f7f7fdouble a[N][N],f[N];int n;inline double sqr(double x) { return x*x; }void Gauss() { int now=1,i,j,k;double t; for (i=1;i<=n;i++) { j=now;while (fabs(a[j][i])<eps&&j<=n) j++; if (j>n) continue; for (k=i;k<=n+1;k++) swap(a[now][k],a[j][k]); for (k=i+1;k<=n+1;k++) a[now][k]/=a[now][i]; a[now][i]=1; for (j=1;j<=n;j++) if (j!=i) { t=a[j][i]; for (k=1;k<=n+1;k++) a[j][k]-=t*a[now][k]; } now++; } return; }int main() { int i,j,q,w,e;double k,l; freopen("input.txt","r",stdin); memset(f,0,sizeof(f));memset(a,0,sizeof(a)); scanf("%d",&n); for (i=1;i<=n;i++) scanf("%lf",&f[i]); for (i=1;i<=n;i++) for (j=1;j<=n;j++) { scanf("%lf",&k); a[i][j]=2*(k-f[j]);a[i][n+1]+=sqr(k)-sqr(f[j]); } Gauss(); for (i=1;i<=n-1;i++) printf("%.3lf ",a[i][n+1]); printf("%.3lf\n",a[n][n+1]); return 0; } |
BZOJ1923外星千足虫：取模高斯消元，感觉很吊，而且新技能get了bitset。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <iostream>#include <cmath>#include <cstdio>#include <cstring>#include <algorithm>#include <bitset>using namespace std;#define N 2050#define INF 0x7f7f7f7ftypedef bitset<N> M[N];M a;int n,m,ans=0;void Gauss() { int i,j,k,l; for (i=1;i<=n;i++) { j=i;while (!a[j][i]&&j<=m) j++; if (j>m) {ans=-1;return;}else ans=max(ans,j); swap(a[j],a[i]); for (k=1;k<=m;k++) if (k!=i&&a[k][i]) a[k]^=a[i]; } return; }int main() { int i,j,k,l,q,w,e; char b[N],c[N]; scanf("%d%d",&n,&m); for (i=1;i<=m;i++) { scanf("%s%s",b,c);a[i][n+1]=c[0]-'0'; for (j=0;j<n;j++) a[i][j+1]=b[j]-'0'; } Gauss(); if (ans==-1) { printf("Cannot Determine\n"); return 0; } printf("%d\n",ans); for (i=1;i<=n;i++) if (a[i][n+1]) printf("?y7M#\n");else printf("Earth\n"); return 0; } |
BZOJ2115XOR：感觉十分屌，可以将图转化为一条从1到n的路径及若干环，环有O(M)个，然后二进制按位看可不可以取，验证就用高斯消元。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | #include <iostream>#include <cmath>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define N 250050#define ll long long#define INF 0x7f7f7f7fint ss=0,n,m,fi[N],c[N][2],tot=1,cir=0;ll v[N],a2[N],s[N],ans=0,h[N];bool vis[N];inline ll Read() { ll x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; }inline void Line(int x,int y,ll z) { c[++ss][0]=y;c[ss][1]=fi[x];s[ss]=z;fi[x]=ss; c[++ss][0]=x;c[ss][1]=fi[y];s[ss]=z;fi[y]=ss; return; }void DFS(int x) { vis[x]=1; for (int i=fi[x];i;i=c[i][1]) if (!vis[c[i][0]]) { h[c[i][0]]=h[x]^s[i];DFS(c[i][0]); }else v[++cir]=h[c[i][0]]^h[x]^s[i]; return; }void Gauss() { int i,j,k,l;ll q,w,e; for (q=a2[60];q;q >>= 1) { j=tot;while (j<=cir&&!(v[j]&q)) j++; if (j>cir) continue; swap(v[j],v[tot]); for (i=1;i<=cir;i++) if (i!=tot&&v[i]&q) v[i]^=v[tot]; tot++; } return; }int main() { int i,j,k,l;ll q,w,e; memset(s,0,sizeof(s));memset(h,0,sizeof(h)); memset(v,0,sizeof(v));memset(c,0,sizeof(c)); memset(a2,0,sizeof(a2));memset(fi,0,sizeof(fi)); memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); for (i=1,a2[0]=1;i<=60;i++) a2[i]=a2[i-1] << 1; for (i=1;i<=m;i++) k=Read(),l=Read(),q=Read(),Line(k,l,q); DFS(1);Gauss(); ans=h[n]; for (i=1;i<tot;i++) ans=max(ans,ans^v[i]); cout <<ans<<endl; return 0; } |
BZOJ2466树：据说只要高斯消元后暴力枚举未确定点DFS，总感觉dzy的代码很高能，现在还是不懂原理。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #include <iostream>#include <cmath>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;#define N 110#define INF 0x7f7f7f7fint a[N][N];int n,m,ans,t[N];void Gauss() { int i,j,k,l; for (i=1;i<=n;i++) { j=i;while (!a[j][i]&&j<=n) j++; if (j>n) continue; swap(a[j],a[i]); for (j=1;j<=n;j++) if (j!=i&&a[j][i]) for (k=1;k<=n+1;k++) a[j][k]^=a[i][k]; } return; }inline void DFS(int x,int y) { if (y>=ans) return; if (!x) {ans=min(ans,y);return;} if (a[x][x]) { t[x]=a[x][n+1]; for (int i=x+1;i<=n;i++) t[x]^=(t[i]&a[x][i]); DFS(x-1,y+t[x]); }else DFS(x-1,y+(t[x]=0)),DFS(x-1,y+(t[x]=1)); return; }int main() { int i,j,k,l,q,w,e; while (scanf("%d",&n),n) { ans=INF; memset(a,0,sizeof(a));memset(t,0,sizeof(t)); for (i=1;i<=n;i++) a[i][i]=a[i][n+1]=1; for (i=1;i<n;i++) scanf("%d%d",&k,&l),a[k][l]=a[l][k]=1; Gauss();DFS(n,0); printf("%d\n",ans); } return 0; } |
BZOJ2337XOR和路径：之前一直在想怎么设从1到i的二进制位为1的概率写方程，其实还好，但是被样例卡了很久没想出来1怎么处理= =结果应该是设从i到n的二进制位为1的概率（好像确实没区别），并且a[n]设为0。然后按位跑高斯消元求出a[1]，然后带权求和即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #include <iostream>#include <cmath>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;#define N 105#define M 20050#define INF 0x7f7f7f7fint fi[N],c[M][3],n,m,ss=1,d[N];double a[N][N],ans=0;long long s=0;inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; }inline void Line(int x,int y,int z) { c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss; c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss; return; }void Gauss() { int i,j,k;double l; for (i=1;i<n;i++) { j=i;while (!a[j][i]) j++; swap(a[j],a[i]); for (j=i+1;j<=n;j++) a[i][j]/=a[i][i]; a[i][i]=1; for (j=1;j<n;j++) if (a[j][i]&&j!=i) { l=a[j][i]; for (k=1;k<=n;k++) a[j][k]-=a[i][k]*l; } } return; }inline void Set_up(int x) { int i,j,k,l;double q,w,e; for (i=1;i<n;i++) { q=1.0/d[i];a[i][i]=-1; for (j=fi[i];j;j=c[j][1]) if (j%2&&c[j][0]==i) continue;else if (c[j][0]==n) a[i][n]-=c[j][2]&x?q:0;else if (c[j][2]&x) a[i][c[j][0]]-=q,a[i][n]-=q;else a[i][c[j][0]]+=q; } return; }int main() { int i,j,k,l,q,w,e; memset(a,0,sizeof(a));memset(c,0,sizeof(c)); memset(fi,0,sizeof(fi));memset(d,0,sizeof(d)); scanf("%d%d",&n,&m); for (i=1;i<=m;i++) { k=Read(),l=Read(),Line(k,l,Read()); d[k]++;if (k!=l) d[l]++; } for (s=1;s<=1073741824;s <<= 1) { Set_up(int(s));Gauss(); ans+=(int)(s)*a[1][n]; memset(a,0,sizeof(a)); } printf("%.3lf\n",ans); return 0; } |
BZOJ3143游走：直接设每个点走过次数的期望列方程，注意边界是an=1以及a1的方程里面要加上1。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 | #include <iostream>#include <cmath>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define N 1050#define M 1000050#define INF 0x7f7f7f7fstruct Edge { int u,v;double t; } b[M];double a[N][N],ans=0;int n,m,c[M][2],fi[N],ss=1,d[N];inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; }inline void Line (int x,int y) { c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss; c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss; return; }void Gauss() { int i,j,k;double l; for (i=1;i<n;i++) { j=i;while (!a[j][i]) j++; swap(a[i],a[j]); for (j=i+1;j<=n;j++) a[i][j]/=a[i][i]; a[i][i]=1; for (k=1;k<n;k++) if (k!=i&&a[k][i]) { l=a[k][i]; for (j=1;j<=n;j++) a[k][j]-=l*a[i][j]; } } return; }void Set_up() { int i,j,k,l;double q,w,e; for (i=1;i<n;i++) { a[i][i]=-1; for (j=fi[i];j;j=c[j][1]) if (c[j][0]!=n) a[i][c[j][0]]=1.0/d[c[j][0]]; } a[1][n]=-1; return; }inline bool cmp(Edge x,Edge y) { return x.t>y.t; }int main() { int i,j,k,l,q,w,e; memset(c,0,sizeof(c));memset(a,0,sizeof(a)); memset(fi,0,sizeof(fi));memset(d,0,sizeof(d)); scanf("%d%d",&n,&m); for (i=1;i<=m;i++) { Line(b[i].u=k=Read(),b[i].v=l=Read()),d[k]++,d[l]++; if (k==n) swap(b[i].u,b[i].v); } Set_up();Gauss(); for (i=1;i<=m;i++) b[i].t=a[b[i].u][n]/d[b[i].u]+a[b[i].v][n]/d[b[i].v]; sort(b+1,b+m+1,cmp); for (i=1;i<=m;i++) ans+=b[i].t*i; printf("%.3lf\n",ans); return 0; } |
BZOJ3503和谐矩阵：由于元素数量过多，不能直接列方程，但是可以推出每个格子是哪些第一行元素的异或和，然后就直接列异或方程。但是最后求可行解的部分好像加了特技= =（其实是人太naive一开始还写什么DFS之类的什么找可行解）具体部分看代码吧。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | #include <iostream>#include <cmath>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define N 105#define M 10050#define ll long long#define INF 0x7f7f7f7fint a[N][N],n,m,c[N][N],ss;ll b[N][N];void Gauss() { int i,j,k,l; for (i=1;i<=m;i++) { j=i;while (j<=m&&!a[j][i]) j++; if (j>m) continue; swap(a[i],a[j]); for (j=1;j<=m;j++) if (j!=i&&a[j][i]) for (k=1;k<=m;k++) a[j][k]^=a[i][k]; } for (i=m;i>=1;i--) { if (!a[i][i]) {c[1][i]=1;continue;} for (j=i+1;j<=m;j++) c[1][i]^=a[i][j]&c[1][j]; } return; }int main() { int i,j,k,l,q,w,e; memset(a,0,sizeof(a));memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); scanf("%d%d",&n,&m); b[1][1]=1;for (i=2;i<=m;i++) b[1][i]=b[1][i-1] << 1; for (i=2;i<=n+1;i++) for (j=1;j<=m;j++) b[i][j]=b[i-1][j-1]^b[i-1][j]^b[i-1][j+1]^b[i-2][j]; for (i=1;i<=m;i++) for (j=1;b[n+1][i];j++) a[i][j]=b[n+1][i]%2,b[n+1][i]/=2; Gauss();ss=0; for (i=2;i<=n;i++) for (j=1;j<=m;j++) c[i][j]=c[i-1][j-1]^c[i-1][j]^c[i-1][j+1]^c[i-2][j]; for (i=1;i<=n;i++) { for (j=1;j<=m;j++) printf("%d ",c[i][j]); printf("\n"); } return 0; } |
先更到这里吧，感觉再多题目我也还是做不出来= =先提高自身姿势再来填坑吧。。。
评论 (0)
