首页 > 代码库 > bzoj1013题解

bzoj1013题解

2024-09-05 15:10:48   214人阅读

【解题思路】

　　初看以为是二次方程组，但这些方程有相同的右值r2，于是可以化为一次方程组，高斯消元即可。复杂度O(n3)。

　　化简过程：

假设第i个方程和第j个方程联立，得：

　　 ∑(a[i,k]-a[0,k])2=∑(a[j,k]-a[0,k])2

<=>∑(a[i,k]2+a[0,k]2-2*a[i,k]*a[0,k])=∑(a[j,k]2+a[0,k]2-2*a[j,k]*a[0,k])

<=>∑(a[i,k]2-a[j,k]2)=2*∑(a[0,k]*(a[i,k]-a[j,k]))

<=>∑(a[i,k]-a[j,k])a[0,k]=∑(a[i,k]2-a[j,k]2)/2

选取n个线性无关的区间(i,j)联立方程组（我选的是i和i+1），a[0]即是答案向量。

【参考代码】

 1 #include <iomanip> 2 #include <iostream> 3 #define REP(I,start,end) for(int I=start;I<=end;I++) 4 #define PER(I,start,end) for(int I=start;I>=end;I--) 5 #define REPs(I,start,end,step) for(int I=start;I<=end;I+=step) 6 #define PERs(I,start,end,step) for(int I=start;I>=end;I-=step) 7 using namespace std; 8 template<typename T> T sqr(T n) 9 {10     return n*n;11 }12 int n;13 long double a[20][20],A[20][20];14 int main()15 {16     ios::sync_with_stdio(false);17     cin>>n;18     REP(i,1,n+1)19         REP(j,1,n)20             cin>>a[i][j];21     REP(i,1,n)22         REP(j,1,n)23         {24             A[i][j]=2*(a[i+1][j]-a[i][j]);25             A[i][0]+=sqr(a[i+1][j])-sqr(a[i][j]);26         }27     REP(i,1,n-1)28         REP(j,i+1,n)29         {30             long double _i=A[i][i],_j=A[j][i];31             REP(k,0,n)32                 A[j][k]=A[j][k]*_i/_j-A[i][k];33         }34     PER(i,n,1)35         REP(j,1,i-1)36         {37             long double _i=A[i][i],_j=A[j][i];38             REP(k,0,i)39                 A[j][k]=A[j][k]*_i/_j-A[i][k];40         }41     REP(i,1,n-1)42         cout<<setiosflags(ios::fixed)<<setprecision(3)<<A[i][0]/A[i][i]<<‘ ‘;43     cout<<setiosflags(ios::fixed)<<setprecision(3)<<A[n][0]/A[n][n]<<endl;44     return 0;45 }

 

bzoj1013题解


联系
我们