BZOJ1013 + BZOJ1923 + POJ1830 (高斯消元)

三个题放在一起写了 主要是搞搞模板 在这里简述一下怎么写高斯消元

就和代数里学的加减消元学的一样 把矩阵化为上三角形形式 然后进行回代

同时枚举当前要消元的未知数和当前化简到哪一行了

然后从这一行往后 找这一列的一个不为0的系数

如果这一列以后的每一行都是0了 那么就说明当前这个未知数可以作为一个自由元 就是有无数解的意思

然后继续枚举下一个未知数

如果找到一个不为0的 和当前这一行的所有元素swap一下 然后除了这一行外 把其他所有行在这一列的系数消为0

最后答案存在每一行的第n + 1个位置

如果化简完了 如果存在后面的某一行 他的n + 1的值不等于0 那么就是无解

bzoj1013

#include <stdio.h>

#include <algorithm>

#include <cmath>

#include <iostream>

#include <string.h>

using namespace std;

double eps = 1e-;

int n;

double a[][];

double zb[][];

void gauss()

{

    int now = , to;

    for(int i = ; i <= n; i++)

    {

        for(to = now; to <= n; to++) if(fabs(a[to][i]) > eps) break;

        if(to > n) continue;

        if(to != now)

            for(int j = ; j <= n + ; j++) swap(a[to][j], a[now][j]);

        double tmp = a[now][i];

        for(int j = ; j <= n + ; j++) a[now][j] /= tmp;

        for(int j = ; j <= n; j++)

            if(j != now)

            {

                tmp = a[j][i];

                for(int k = ; k <= n + ; k++) a[j][k] -= tmp * a[now][k];

            }

        now++;

    }

}

int main()

{

    cin>>n;

    for(int i = ; i <= n + ; i++)

    {

        for(int j = ; j <= n; j++) scanf("%lf", &zb[i][j]);

        if(i > )

        for(int j = ; j <= n; j++) a[i - ][j] = 2.0 * (zb[i][j] - zb[][j]), a[i - ][n + ] += zb[i][j] * zb[i][j] - zb[][j] * zb[][j];

    }

    gauss();

    for(int i = ; i <= n - ; i++) printf("%.3lf ", a[i][n + ]);

    printf("%.3lf\n", a[n][n + ]);

    return ;

}

bzoj1923   高斯消元的时间复杂度是n三方的 然后这个题数据是1000 10s居然水过去了 听说有用bitset优化的方法 (以后再学吧

#include <stdio.h>

#include <algorithm>

#include <iostream>

#include <string.h>

using namespace std;

int n, m, x, ans;

int a[][];

void gauss1()

{

    int now = , to;

    for(int i = ; i <= n; i++)

    {

        for(to = now; to <= m; to++) if(a[to][i]) break;

        if(to > m)

        {

            ans = -;

            return;

        }

        ans = max(ans, to);

        if(to != now)

            for(int j = ; j <= n + ; j++) swap(a[to][j], a[now][j]);

        for(int j = ; j <= m; j++)

            if(j != now && a[j][i])

                for(int k = ; k <= n + ; k++) a[j][k] ^= a[now][k];

        now++;

    }

}

int main()

{

    cin>>n>>m;

    for(int i = ; i <= m; i++)

    {

        char s[];

        scanf("%s %d", s, &x);

        int len = strlen(s);

        for(int j = ; j < len; j++) a[i][j + ] = s[j] - '';

        a[i][len + ] = x;

    }

    gauss1();

    if(ans == -) puts("Cannot Determine");

    else

    {

        printf("%d\n", ans);

        for(int i = ; i <= n; i++)

        {

            if(a[i][n + ]) puts("?y7M#");

            else puts("Earth");

        }

    }

    return ;

}

POJ1830 入门题

#include <stdio.h>

#include <algorithm>

#include <iostream>

#include <string.h>

using namespace std;

int ans;

int q[];

int w[];

int a[][];

void gauss(int n, int m)

{

    ans = ;

    int now = , to;

    for(int i = ; i <= n; i++)

    {

        for(to = now; to <= m; to++) if(a[to][i]) break;

        if(to > m)

        {

            ans++;

            continue;

        }

        if(to != now)

            for(int j = ; j <= n + ; j++) swap(a[to][j], a[now][j]);

        for(int j = ; j <= m; j++)

            if(j != now && a[j][i])

                for(int k = ; k <= n + ; k++) a[j][k] ^= a[now][k];

        now++;

    }

    for(int i = now; i <= m; i++)

        if(a[i][n + ])

        {

            ans = -;

            return;

        }

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        memset(a, , sizeof(a));

        int n; scanf("%d", &n);

        for(int i = ; i <= n; i++) scanf("%d", &q[i]);

        for(int i = ; i <= n; i++) scanf("%d", &w[i]), w[i] ^= q[i], a[i][n + ] = w[i];

        for(int i = ; i <= n; i++) a[i][i] = ;

        int u, v;

        while(~scanf("%d%d", &u, &v) && u + v) a[v][u] = ;

        gauss(n, n);

        if(ans == -) puts("Oh,it's impossible~!!");

        else printf("%d\n",  << ans);

    }

    return ;

}