题解 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掉了，请告知这个白痴。