Bakser's Blog

我是逗比。

几道高斯消元+小结

| Comments

话说本来是准备从前往后一道一道切bzoj的,然后发现了1013是道高斯消元。
突然发现还不会高斯消元,真是丧失,果然我还是半吊子水平。。。
抓紧时间补,看看今天能做几道。
upd 2014.5.4 9:00
bzoj1013
题解遍地是,为了秀公式编辑器我还是写两句吧。
设球心坐标为x[1,2...n]

用a[k]的方程减去a[k+1]的方程得。

就变成了一个n元一次方程组,高斯消元求解。

bzoj1013
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 30
typedef long double LD;
template <class T>
T abs(T a)
{
    return a<0?-a:a;
}
LD a[N][N],x[N][N];
int n;
inline void gauss()
{
    for(int i(0);i<n;i++)
    {
        int r(i);
        for(int j(i+1);j<n;j++)
            if(abs(x[j][i])>abs(x[r][i]))
                r=j;
        if(r!=i)
            for(int j(0);j<=n;j++)
                swap(x[i][j],x[r][j]);
        for(int j(n);j>=i;j--)
            for(int k(i+1);k<n;k++)
                x[k][j]-=x[k][i]/x[i][i]*x[i][j];
    }
    for(int i(n-1);i>=0;i--)
    {
        for(int j(i+1);j<n;j++)
            x[i][n]-=x[j][n]*x[i][j];
        x[i][n]/=x[i][i];
    }
    for(int i=0;i<n-1;i++)  
        printf("%.3lf ",(double)x[i][n]);
    printf("%.3lf",(double)x[n-1][n]);  
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<=n;i++)
        for(int j=0;j<n;j++)
            {
                double hh;
                scanf("%lf",&hh);
                a[i][j]=hh;
            }
    for(int i=0;i<n;i++)
    {
        LD hh=0;
        for(int j=0;j<n;j++)
        {
            x[i][j]=2*(a[i][j]-a[i+1][j]);
            hh+=(a[i][j]*a[i][j]-a[i+1][j]*a[i+1][j]);
        }
        x[i][n]=hh;
    }
    gauss();
    return 0;
}

2014.5.4 10:49
bzoj2466
解异或方程组的题。
膜拜了dzy大爷的简短题解。
就是每个点建一个n元方程,每个元代表该点的状态,系数就是这两点是否有边相连,等式右边常数当然是1.
然后正常向gauss消元,注意会有不定元,又要求输出最小的解。。。。。
所以暴搜。
从后往前做,可以解出来的点根据已确定的点消元解。
不定元枚举T_T

bzoj2466
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 120
int n,a[N][N],res[N],ans;
inline void dfs(int x,int sum)
{
    if(sum>=ans)return;
    if(!x)
    {
        if(sum<ans)ans=sum;
        return;
    }
    if(a[x][x])
    {
        int t(a[x][n+1]);
        for(int i=x+1;i<=n;i++)
            if(a[x][i])
                t^=res[i];
        res[x]=t;
        dfs(x-1,sum+res[x]);
    }
    else
    {
        res[x]=0;
        dfs(x-1,sum);
        res[x]=1;
        dfs(x-1,sum+1);
        res[x]=0;
    }
}
inline void gauss()
{
    for(int i=1;i<=n;i++)
    {
        bool flag(false);
        for(int j(i);!flag&&j<=n;j++)
        if(a[j][i])
        {
            for(int k=1;k<=n+1;k++)
                swap(a[i][k],a[j][k]);
            flag=1;
        }
        if(!flag)continue;
        for(int j(i+1);j<=n;j++)
        if(a[j][i])
            for(int k=1;k<=n+1;k++)
                a[j][k]^=a[i][k];
    }
    ans=0x7f7f7f7f;
    dfs(n,0);
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
        memset(a,0,sizeof(a));
        memset(res,0,sizeof(res));
        for(int i=1,u,v;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            a[u][v]=a[v][u]=1;
        }
        for(int i=1;i<=n;i++)
            a[i][i]=a[i][n+1]=1;
        gauss();
        printf("%d\n",ans);
    }
    return 0;
}

upd2014.5.4 15:53
bzoj2115
此题好神
YM了ydc神犇的题解.
本质就是求一条从1到n的简单路径+一坨环的最大值。
简单路径随便dfs即可。
同时dfs时记录树上横叉边所构成的环,可以证明所有环都是从这些“树环”异或来的。
然后就是好多数中任选几个与定值异或后最大值了。
按位建立方程,然后从高位到低位枚举常数看是否能解出来1,能就解出来(贪心),到这其实已经不是gauss消元了,用类似的方式求解。
此题还有一种神级做法叫线性基。。。下道做bzoj2115,用这种方法做吧。

bzoj2115
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef unsigned long long LL;
#define N 51000
#define M 301000
#define size 60
template <class T>
T read(T &x)
{
    x=0;char c=0;
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())(x*=10)+=c-'0';
    return x;
}
struct hh
{
    int v,next;
    LL w;
}edges[M];
int n,m,point[N],tot(0),a[80][M];
LL val[N],circle[M];
bool vis[N];
inline void addedge(int u,int v,LL w)
{
    static int en(0);
    edges[++en].v=v;edges[en].next=point[u];point[u]=en;edges[en].w=w;
    edges[++en].v=u;edges[en].next=point[v];point[v]=en;edges[en].w=w;
}
inline void dfs(int x)
{
    vis[x]=1;
    for(int i=point[x];i;i=edges[i].next)
        if(!vis[edges[i].v])val[edges[i].v]=val[x]^edges[i].w,dfs(edges[i].v);
        else circle[++tot]=val[x]^val[edges[i].v]^edges[i].w;
}
inline LL solve()
{
    LL ans(0);
    int k;
    for(int i=size;i>=0;i--)
    {
        ans<<=1;
        for(k=1;k<=tot;k++)
            if(a[i][k])break;
        if(k<=tot)
        {
            ans|=1;
            for(int j=i-1;j>=0;j--)
                if(a[j][k])
                    for(int l=0;l<=tot;l++)
                        a[j][l]^=a[i][l];
        }
        else if(!a[i][0])ans|=1;
    }
    return ans;
}
int main()
{
    read(n);read(m);
    int u,v;LL w;
    for(int i=0;i<m;i++)
    {
        read(u);read(v);read(w);
        addedge(u,v,w);
    }
    dfs(1);
    sort(circle+1,circle+tot+1);
    tot=unique(circle+1,circle+tot+1)-circle-1;
    for(int i=0;i<=size;i++)
    {
        a[i][0]=~val[n]>>i&1;
        for(int j=1;j<=tot;j++)
            a[i][j]=circle[j]>>i&1;
    }
    printf("%lld\n",solve());
    return 0;
}

upd2014.5.4 20:47
颓了半天啊啊啊啊,不过集体颓mc确实很带感。
言出必行,用线性gay做的。
就是把各个环按照线性无关分解开。
首先离线做,把删边变成加边。
若加入边形成环就判断能否形成新的基底。
基底更新后再对边去重(分解式一样的算同一个)。
若未形成环就正常将树扩展加入新的链。

bzoj2322
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<set>
using namespace std;
#define N 6000
#define M 50000
#define Q 20100
#define size 63
typedef unsigned long long LL;
template <class T>
T read(T &x)
{
    x=0;char c=0;
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())(x*=10)+=c-'0';
    return x;
}
struct hh
{
    int v,next;
    LL w;
}edges[M];
int n,m,q,point[N],u[M],v[M],deal[Q];
int ctot,nctot,ltot,nltot,len;
LL w[M],base[100],dis[N],list[N],ans[Q],temp[N],top;
bool del[M],vis[N];
set<LL> hash;
inline void addedge(int u,int v,LL w)
{
    static int en(0);
    edges[++en].next=point[u];edges[en].v=v;edges[en].w=w;point[u]=en;
    edges[++en].next=point[v];edges[en].v=u;edges[en].w=w;point[v]=en;
}
inline void add_list(LL x)
{
    list[++len]=x;nltot++;
}
inline void add_circle(LL x)
{
    for(int i=size;i>=0;i--)
        if(base[i]&&(x>>i&1))
            x^=base[i];
    for(int i=size;i>=0;i--)
        if(x>>i&1)
            {
                base[i]=x;
                nctot++;
                ctot++;
                break;
            }
}
inline bool check(LL x)
{
    for(int i=size;i>=0;i--)
        if(base[i]&&(x>>i&1))
            x^=base[i];
    if(x&&!hash.count(x))
    {
        hash.insert(x);
        return true;
    }
    return false;
}
inline LL calc(int now)
{
    ltot=0;
    if(!nctot)
    {
        int tmp(len);len-=nltot;
        for(int i(tmp-nltot+1);i<=tmp;i++)
            if(check(list[i]))
                ltot++,list[++len]=list[i];
        ans[now]=ans[now+1]+ltot*(1LL<<ctot);
    }
    else
    {
        hash.clear();
        top=0;nctot=0;
        for(int i=1;i<=len;i++)
        if(check(list[i]))
            ltot++,temp[++top]=list[i];
        len=top;
        for(int i=1;i<=top;i++)list[i]=temp[i];
        ans[now]=(ltot+1)*(1LL<<ctot)-1;
    }
    nltot=0;
}
inline void dfs(int x)
{
    vis[x]=1;
    for(int i=point[x];i;i=edges[i].next)
    if(!vis[edges[i].v])dis[edges[i].v]=dis[x]^edges[i].w,add_list(dis[edges[i].v]),dfs(edges[i].v);
    else add_circle(dis[x]^dis[edges[i].v]^edges[i].w);
}
int main()
{
    read(n);read(m);read(q);
    for(int i=1;i<=m;i++)
        read(u[i]),read(v[i]),read(w[i]);
    for(int i=1,x;i<=q;i++)
        del[read(deal[i])]=1;
    for(int i=1;i<=m;i++)
        if(!del[i])
            addedge(u[i],v[i],w[i]);
    dfs(1);
    calc(q+1);
    for(int i=q,x,y;i>=1;i--)
    {
        x=u[deal[i]];y=v[deal[i]];
        addedge(x,y,w[deal[i]]);
        if(vis[x]&&vis[y])add_circle(dis[x]^dis[y]^w[deal[i]]);
        else if(vis[x])dfs(x);
        else if(vis[y])dfs(y);
        calc(i);
    }
    for(int i=1;i<=q+1;i++)
        printf("%lld\n",ans[i]);
    return 0;
}

upd 2014.5.5 8:39
bzoj2844
思路跟前几道题大体一致,也是按照线性无关分解给出的n个数,然后枚举询问的数的分解方式,同时统计有多少个分解式比他小。
已知总共有2^n个可能产生的数,设有k个线性基,则总共有2^k种不同的数,那么每个数出现了2^(n-k)次,所以就可以统计。
妈蛋没注意位运算优先级wa了好多发,最后把代码改的和wyl君一样了才发现是左移优先级比小于号还低。哭瞎QAQ.

bzoj2844
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100100
#define MOD 10086
#define size 30
int n,a[N],m;
inline int gauss()
{
    int j(0),k;
    for(int i(size);i>=0;i--)
    {
        for(k=j;k<n&&(!((a[k]>>i)&1));k++);
        if(k>=n)continue;
        swap(a[j],a[k]);
        for(k=0;k<n;k++)
            if(j!=k&&((a[k]>>i)&1))
                a[k]^=a[j];
        j++;
    }
    return j;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",a+i);
    int k(gauss());
    scanf("%d",&m);
    int now(0),rank(0);
    for(int i(0);i<k&&now!=m;i++)
    if((now^a[i])<=m)
        rank+=(1<<(k-i-1)),now^=a[i];
    for(int i=0;i<n-k;i++)
        (rank<<=1)%=MOD;
    (rank+=1)%=MOD;
    printf("%d\n",rank);
    return 0;
}

upd 2014.5.5 11:05
感觉这两天不能颓更多。。。。。
bzoj2337
带环dp转化成高斯消元又是一种新的题型。
具体这题:
首先按位求期望,求出每一位的期望后再加起来就可以了。
关于每一位我们有这样的dp方程(deg表示出度,w(u,v)表示u,v之间的边,等于0或1是指对于正在dp的这一位来言)

但是图有环,所以就完全无法确定dp顺序。
然后我们把每一个点的方程都列出来,发现这就是一个n-1元(f[n]=0是肯定的)一次方程组。移项以后高斯消元即可。
不过要是n再大一些怎么做?缩点搞成DAG?不会。。。。。

bzoj2337
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long double LD;
const LD eps(1e-9);
#define N 110
#define M 31000
#define size 31
template <class T>
T read(T &x)
{
    x=0;char c=0;
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())(x*=10)+=c-'0';
    return x;
}
template <class T>
T abs(T x)
{
    return x>0?x:-x;
}
inline int cmp(LD x)
{
    if(x>eps)return 1;
    if(x<-eps)return -1;
    return 0;
}
struct hh
{
    int next,v,w;
}edges[M];
LD a[N][N];
int point[N],n,m,deg[N];
LD ans(0.0);
inline void addedge(int u,int v,int w)
{
    static int en(0);
    edges[++en].next=point[u];
    deg[u]++;
    edges[en].v=v;
    edges[en].w=w;
    point[u]=en;
}
inline void gauss()
{
    for(int i=1;i<n;i++)
    {
        int r(i);
        for(int j(i+1);j<n;j++)
            if(cmp(abs(a[j][i])-abs(a[r][i]))>0)
                r=j;
        if(r!=i)
            for(int j=1;j<=n+1;j++)
                swap(a[i][j],a[r][j]);
        for(int j(n+1);j>=i;j--)
            for(int k(i+1);k<=n;k++)
                a[k][j]-=a[k][i]/a[i][i]*a[i][j];
    }
    for(int i=n;i>=1;i--)
    {
        for(int j(i+1);j<=n;j++)
            a[i][n+1]-=a[j][n+1]*a[i][j];
        a[i][n+1]/=a[i][i];
    }
}
int main()
{
    read(n);read(m);
    for(int i(0),u,v,w;i<m;i++)
    {
        read(u);read(v);read(w);
        addedge(u,v,w);
        if(u!=v)addedge(v,u,w);
    }
    for(int k=0;k<size;k++)
    {
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)
            a[i][i]=1.0;
        for(int i=1;i<n;i++)
            for(int j(point[i]);j;j=edges[j].next)
                if(edges[j].w>>k&1)a[i][edges[j].v]+=1.0/(LD)deg[i],a[i][n+1]+=1.0/deg[i];
                else a[i][edges[j].v]-=1.0/deg[i];
        gauss();
        ans+=a[1][n+1]*(LD)(1<<k);
    }
    printf("%.3llf\n",ans);
    return 0;
}

小总结
恶补了两天gauss消元,总结一下题型,bzoj上应该还有几道,以后有时间再刷吧。
type1:
正常向解方程组(1013),注意模板不要写错就好。
type2:
解异或方程组(2466,2115,2322),这种题目模型往往隐藏的很深,需要挖掘题目的逗比性质,建立方程就好了。
ps:这种题往往还有求解的个数或最优解或最优解的个数,对自由元枚举就可以了。
type3:
线性分解
gauss消元来求xor下的线性基底,然后用基底来做统计或构造,非常灵活,(2844)
type4:
求数学期望。
列出方程但不好dp情况下可直接解方程。(2337)
分类好像不是很科学。。。。。
------------------------------------------end--------------------------------------------------

Comments

comments powered by Disqus