题解 P2455 【[SDOI2006]线性方程组】

狠题。

题意：在高斯消元的基础上，判断是正常的还是“无解”还是“有无数解”。

简述一下高斯消元的思想：让第 i 个式子对应第 i 元，并用第 i 个式子消去其它式子上的第 i 元，最终使方程组呈现出类似一条对角线的样子，即第 i 个式子只在第 i 元和等式右边有值，其余都是0。

一般的高斯消元每次会选择该项系数绝对值最大的来对应第 i 元。这样，如果发现有一元系数为0，就能说明方程没有正常的解了。

那么我们来研究，没有正常的解，究竟是“无解”还是“有无数解”。

一个naive的想法是，在完成消元后枚举每一项，如果发现系数是0则讨论等式右边：如果为0，则有无数解；如果不为0，则无解。其中无解优先级更高，即如果一个方程有一项无解且有一项有无数解，那么判定无解。

交上去喜提90。

存在漏洞：以 hehe_zhou 大佬的hack数据为例：

2
0 2 3
0 0 0

答案显然是0，但是我们的程序会说这是-1。

我们发现，我们可以根据第一个式子来求出第二元，但是程序会用它来算第一元，并且以后算第二元的时候不会再考虑该式，因为我们认为它已经对应第一元了！

也就是说，我们的答案受到消元顺序影响。

题解里部分选手当场召唤玄学势力，把消元顺序随机乱改，大概率能出正解。

这里提供一种新的做法。

注意到，我们的症结在于把还有用的式子放到了用不上它的地方，并且以后也不来看它是否可用。

那么，我们就来看它是否可用。

原本的高斯消元中，我们认为只有 i 之后的式子是可用的，因为我们不用管无解还是无数解，系数为0直接判掉。

但这里，我们有可能会在系数为0之后继续做下去。这就是受到消元顺序影响的原因。

那么，可用的就不仅仅是之后的式子，还有之前系数为0的式子。

于是解决了。

#include <cstdio>

const int maxn=55;const double eps=1e-6;

int n;double a[maxn][maxn];

template<typename T> inline void swap(T &a,T &b){
    T temp=a;a=b;b=temp;
}

template<typename T> inline T abs(T val){
    return val>0?val:-val;
}

void Gauss(){//高斯消元
    for(int i=1;i<=n;i++){
        int maxx=i;
        for(int j=1;j<=n;j++){//把枚举范围从i->n改成了1->n
            if(abs(a[j][j])>eps&&j<i) continue;//若在i前，且的确已对应一项系数，不可用
            if(abs(a[j][i])>abs(a[maxx][i])){
                maxx=j;
            }
        }
        for(int j=1;j<=n+1;j++) swap(a[maxx][j],a[i][j]);
        if(abs(a[i][i])<=eps) continue;
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            double delta=a[j][i]/a[i][i];
            for(int k=i;k<=n+1;k++){
                a[j][k]-=delta*a[i][k];
            }
        }
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n+1;j++){
            scanf("%lf",&a[i][j]);
        }
    }
    Gauss();int key=1;
    for(int i=1;i<=n;i++){
        // for(int j=1;j<=n+1;j++) printf("%.2lf ",a[i][j]);
        // printf("\n");
        if(abs(a[i][i])<=eps){
            if(abs(a[i][n+1])>eps) key=-1;//无解优先级更高
            else if(key!=-1) key=0;
        }
    }
    if(key!=1) printf("%d\n",key);
    else for(int i=1;i<=n;i++) printf("x%d=%.2lf\n",i,abs(a[i][n+1]/a[i][i])<=eps?0:a[i][n+1]/a[i][i]);//防止出现-0.00这种令人郁闷的情况，虽然对于本题数据无所谓
    return 0;
}

如果hack掉了，请告知这个白痴。