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

· · 题解

看到各位大佬的高斯消元都那么厉害，而我只会高斯模板，我很慌啊

但还是交了一个高斯消元模板，然后只有80

各种改，最高改到90，但更多是10,20

经过我一番思考 （刷光谈论区）后，我意识到一个问题：

高斯消元的顺序可能会影响到最终的答案，主要是0与-1的情况

（当然，你只要像各位大佬一样，高斯消元打的够好，或者优化的好，完全可以无视它）

那么，怎么办？

既然高斯消元的顺序会影响最终结果，那么我们就把乱改的思路贯彻到底

——采用随机化算法

既然我把顺序打乱了，那么各种卡顺序的数据也就GG了

上面是随机化思想优化的引入，下面稍微讲一下这道题（反正前人之述备矣）

首先，你要会高斯消元，如果你不懂，请转P3389

其次，为防止各种hack数据，请随机打乱矩阵的行

最后，你高斯消元完了之后，你去计算每一行的a[i][n+1]/a[i][i] (常数/系数)

若a[i][i]不等于0，直接输出商

否则

{

    如果a[i][n+1]==0 那么就是 0
    否则 就是 -1

}

以上是小学数学书上的解释，不懂回去重造

上代码

（已做防抄袭处理，不要和，自己写）

#include <bits/stdc++.h>
#define random(a,b) ((a)+rand()%((b)-(a)+1))
using namespace std;
int n,b[111],fg;
double a[111][111],f[111];
int main() 
{
　　srand(time(NULL));//随机化预处理 
　　cin>>n;
//　　for(int i=1;i<=n;i++) b[i]=1;
　　for(int i=1;i<=n;i++)
　　{
　　　　for(int j=1;j<=n+1;j++)   
　　　　{
　　　　　　scanf("%lf",&a[i][j]); //输入 
　　　　}
　　}　　 
　　for(int i=1;i<=n;i++) //进行随机化交换任意两行 
　　{
　　　　for(int j=i+1;j<=n;j++)
　　　　{
　　　　　　int x=random(1,1000);
　　//　　　　printf("%d ",x);
　　　　　　if(x&1)
　　　　　　{
　　　　　　　　for(int k=1;k<=n+1;k++)
　　　　　　　　{
　　　　　　　　　　swap(a[i][k],a[j][k]);
　　　　　　　　}
　　　　　　}
　　　　}
　　}
　　/* 
　　puts("");
　　for(int i=1;i<=n;i++)
　　{
　　　　for(int j=1;j<=n+1;j++)
　　　　{
　　　　　　printf("%lf ",a[i][j]);
　　　　}
　　　　puts("");
　　}
　　*/
　　for(int i=1;i<=n;i++) //高斯消元 
　　{
　　　　int mx=i;
　　　　for(int j=i+1;j<=n;j++) //约旦算法，查abs最大的先做（由于已经过随机化算法，这个做法也不易被卡） 
　　　　{
　　　　　　if(fabs(a[j][i])>fabs(a[mx][i]))
　　　　　　{
　　　　　　　　mx=j;
　　　　　　}
　　　　}
　　//　　printf("#%d %lf %d\n",mx,a[mx][i],a[mx][i]==0);
　　/*
　　　　if(a[mx][i]==0)
　　　　{
　　//　　　　printf("@%d %lf\n",mx,a[mx][n+1]);
　　　　　　if(!a[mx][n+1]) 
　　　　　　{
　　　　　　　　puts("0");
　　　　　　　　return 0;
　　　　　　//　　puts("0");
　　　　　　//　　return 0;
　　　　　　}
　　　　　　else 
　　　　　　{
　　　　　　　　fg=1;　　
　　　　　　　　continue;
　　　　　　}
　　　　}
　　*/
　　　　if(!a[mx][i]) continue;//a[mx][i]==0就continue掉，不然除0会爆nan的！！！ 
　　　　for(int j=1;j<=n+1;j++)
　　　　{
　　　　　　swap(a[i][j],a[mx][j]);
　　　　}
　　　　for(int j=1;j<=n;j++)
　　　　{
　　　　　　if(j!=i)
　　　　　　{
　　　　　　　　double t=a[j][i]/a[i][i]; //加减消元 
　　　　　　　　for(int k=1;k<=n+1;k++)
　　　　　　　　{
　　　　　　　　　　a[j][k]-=a[i][k]*t;
　　　　　　　　}
　　　　　　}
　　　　}
　　}
　　/*
　　for(int i=1;i<=n;i++)
　　{
　　　　for(int j=1;j<=n+1;j++)
　　　　{
　　　　　　printf("%lf ",a[i][j]);
　　　　}
　　　　puts("");
　　}
　　*/
　　for(int i=1;i<=n;i++) //用f[i]存结果 
　　{
　　//　　if(b[i]>0)
　　
　　　　if(a[i][i]==0) //判断有无解，只要一个无解，那么就算其他有无数解，也算无解 
　　　　{
　　　　　　if(a[i][n+1])
　　　　　　{
　　　　　　　　puts("-1");
　　　　　　　　return 0; //所以无解优先 
　　　　　　}
　　　　　　else fg=1;
　　　　　　continue;
　　　　}
　　
　　//　　printf("%lf %lf\n",a[i][n+1],a[i][i]);
　　　　f[i]=a[i][n+1]/a[i][i];
　　　　if(!f[i]) f[i]=0.00; //防止-0.00这种狗屎情况 
　　//　　else printf("%d\n",b[i]);
　　}
　　if(fg)
　　{
　　　　puts("0");
　　　　return 0;
　　}
　　for(int i=1;i<=n;i++)
　　{
　　　　printf("x%d=%.2f\n",i,f[i]);//输出 
　　}
　　return 0; 
}　　　  　　

如果你觉得他太长，还有短的

压行前130多，压行后30多，无语

#include <bits/stdc++.h>
#define random(a,b) ((a)+rand()%((b)-(a)+1))
using namespace std;
int n,b[111],fg;
double a[111][111],f【111】;
int main() {
　　srand(time(NULL));  #随机化预处理 
　　cin>>n； 
　　for(int i=1;i<=n;i++)
　　　　for(int j=1;j<=n+1;j++)   
　　　　　　scanf("%lf",&a[i][j]); //输入 
　　for(int i=1;i<=n;i++) \\进行随机化交换任意两行 
　　　　for(int j=i+1;j<=n;j++){
　　　　　　int x=random(1,1000);
　　　　　　if(x&1)　　for(int k=1;k<=n+1;k++)　swap(a[i][k],a[j][k]);
　　　　}
　　for(int i=1;i<=n;i++){ 、、高斯消元 
　　　　int mx=i;
　　　　for(int j=i+1;j<=n;j++)  　　if(fabs(a[j][i])>fabs(a[mx][i]))　　mx=j;//约旦算法，查abs最大的先做（由于已经过随机化算法，这个做法也不易被卡）
　　　　if(!a[mx][i]) continue; ！！！a[mx][i]==0就continue掉，不然除0会爆nan的！！！ 
　　　　for(int j=1;j<=n+1;j++)　　swap(a[i][j],a[mx][j]);
　　　　for(int j=1;j<=n;j++) if(j!=i){
　　　　　　　　double t=a[j][i]/a[i][i]; //加减消元 
　　　　　　　　for(int k=1;k<=n+1;k++) a[j][k]-=a[i][k]*t;
　　　　　　}
　　}
　　for(int i=1;i<=n;i++){ //用f[i]存结果 
　　　　if(a[i][i]==0){ //判断有无解，只要一个无解，那么就算其他有无数解，也算无解 
　　　　　　if(a[i][n+1]) return puts("-1"),0;  ！！！所以无解优先^__^ 
　　　　　　else fg=1;
　　　　　　continue;
　　　　}
　　　　f[i]=a[i][n+1]/a[i][i]； 
　　　　if(!f[i]) f[i]=0.00; //防止-0.00这种狗屎情况 
　　}
　　if(fg) return puts（"0"）,0； 
　　for(int i=1;i<=n;i++)　　printf("x%d=%.2f\n",i,f[i]);//输出 
}《《————你猜猜这大括号中文英文　　　  　　

总之，随机化算法可以避免你常规算法的各种问题，是一种不错的算法 （就是还得看脸）, 其他就是正常的高斯消元，对0，与-1的情况多加留意就是，此外还有些细节，好好处理，耐心点就好 调料一个晚上

最后，祝大家 AK NOIP 2019