# 70 条题解

• @ 2017-01-06 17:08:24

var x:array[0..200]of real;
a:array[0..200,0..201]of real;
n:longint;
procedure initial;
var i,j:longint;
begin
for i:=1 to n do begin
end;
procedure gause;
var maxi,ii,i,j:longint;
max,t:real;
begin
for ii:=1 to n-1 do
begin
max:=abs(a[ii,ii]);maxi:=ii;
for i:=ii+1 to n do if abs(a[i,ii])>max then begin maxi:=i;max:=abs(a[i,ii]);end;
for i:=1 to n+1 do
begin t:=a[ii,i];a[ii,i]:=a[maxi,i];a[maxi,i]:=t;end;
for i:=ii+1 to n do
begin
t:=a[i,ii]/a[ii,ii];
for j:=ii+1 to n+1 do
a[i,j]:=a[i,j]-a[ii,j]*t;
end;
end;
x[n]:=a[n,n+1]/a[n,n];
for i:=n-1 downto 1 do
begin
for j:=n downto i+1 do a[i,n+1]:=a[i,n+1]-a[i,j]*x[j];
x[i]:=a[i,n+1]/a[i,i];
end;
for i:=1 to n-1 do write(round(x[i]),' ');
writeln(round(x[n]));
end;
begin
initial;
gause;
end.

• @ 2018-07-20 11:52:12

c++ AC代码
#1 Accepted 3ms 256.0 KiB
#2 Accepted 4ms 380.0 KiB
#3 Accepted 4ms 380.0 KiB
#4 Accepted 5ms 256.0 KiB
#5 Accepted 2ms 384.0 KiB
#6 Accepted 4ms 372.0 KiB
#7 Accepted 6ms 380.0 KiB
#8 Accepted 6ms 364.0 KiB
#9 Accepted 4ms 472.0 KiB
#10 Accepted 3ms 512.0 KiB
代码
#include<bits/stdc++.h>
#define maxn 105
using namespace std;
typedef double matrix[maxn][maxn];
matrix a;
double x[maxn];
int n;
void gaos(matrix a,double *x,int n,int m){
int i=1,j=1,r;
while(i<=n&&j<=m){
int maxx=0;
for(int k=i;k<=n;k++){
if(fabs(a[k][j])>maxx) maxx=fabs(a[k][j]),r=k;
}
if(maxx>0){
for(int k=1;k<=m;k++) swap(a[i][k],a[r][k]);//这个必须交换全排
for(int k=i+1;k<=n;k++){
if(fabs(a[k][j])>0){
double f=a[k][j]/a[i][j];
for(int p=1;p<=m;p++){
a[k][p]-=f*a[i][p];//f用处:简便正负判断
}
}
}
i++;
}
j++;//注意这里i++和j++的精妙区别，只有定下一行后才会i++，若都为0则j++
}
for(int k=n;k>=1;k--){
for(int p=m-1;p>=k+1;p--){
a[k][m]-=a[k][p]*x[p];
}
x[k]=a[k][m]/a[k][k];
}
}
void init(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n+1;j++) scanf("%lf",&a[i][j]);
}

gaos(a,x,n,n+1);//最后多了一个答案 增广矩阵

for(int i=1;i<=n;i++) printf("%d ",(int)(x[i]+0.5));
}
int main(){
init();

return 0;
}

• @ 2016-08-28 14:38:17

样例有毒.......
减号居然是全角的......

• @ 2015-12-15 22:00:18

水题有毒！！！
记录信息
评测状态 Accepted
题目 P1052 贾老二算算术
递交时间 2015-12-15 21:57:35
代码语言 C++
评测机 VijosEx
消耗时间 22 ms
消耗内存 372 KiB
评测时间 2015-12-15 21:57:37
评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 368 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 368 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 372 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 372 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 372 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 368 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 372 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 372 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 368 KiB, score = 10

测试数据 #9: Accepted, time = 7 ms, mem = 372 KiB, score = 10

Accepted, time = 22 ms, mem = 372 KiB, score = 100
代码

#include <iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n;
double A[110][110];
double ABS(double x)
{return x>0?x:-x;}
void print()
{
printf("~~~~~~~~~~~~\n");
for(int i=1;i<n;i++){
for(int j=1;j<=n;j++)
printf("%d ",(int)A[i][j]);
printf("\n");
}
printf("~~~~~~~~~~~~\n");
}
int main()
{
scanf("%d",&n);n++;
for(int i=1;i<n;i++)
for(int j=1;j<=n;j++)
scanf("%lf",&A[i][j]);
for(int i=1;i<n;i++)
{
int np=i;
for(int j=i+1;j<n;j++)if(ABS(A[np][i])<ABS(A[j][i]))np=j;
if(np!=i)swap(A[np],A[i]);
//print();
double GD=A[i][i];
for(int j=1;j<=n;j++)A[i][j]/=GD;
for(int j=1;j<n;j++)
if(j!=i){
GD=A[j][i];
for(int k=1;k<=n;k++)
A[j][k]-=GD*A[i][k];
}
}
//print();
for(int i=1;i<n;i++)
printf("%d ",(int)(round)(A[i][n]));
return 0;
}

• @ 2015-12-15 22:00:02

此题有毒，其实无毒。。打好搞笑（高消），AC可待！下附渣渣代码。。：(ACM大牛说double用%f输出会更保险）
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,a,b;
const int maxn=200+15;
float A[maxn][maxn];
double EPS=1e8;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<=n;j++) scanf("%f",&A[i][j]);
for(int i=0;i<n;i++)
{
int now=i;
for(int j=i;j<n;j++) if(fabs(A[now][i])<fabs(A[j][i])) now=j;
if(now!=i) swap(A[now],A[i]);
for(int j=i+1;j<=n;j++) A[i][j]/=A[i][i];
for(int j=0;j<n;j++)
if(i!=j)
{
for(int k=i+1;k<=n;k++) A[j][k]-=A[j][i]*A[i][k];
}
}
for(int i=0;i<n;i++)
{
printf("%d ",(int)(A[i][n]+0.5));
}
return 0;
}

• @ 2015-08-09 19:56:39

#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN = 100+10;

float num[MAXN][MAXN];
int n;
float ans[MAXN];

void think(int x){
if(x > n)
return;
int f;
for(int i=1; i<=n; i++)
if(num[i][0] == 0 && num[i][x] != 0){

for(int j=1; j<=n; j++)
if(num[j][0] == 0 && j != i){
float bri = num[j][x]/num[i][x];
for(int u=x; u<=n+1; u++){
num[j][u] -= num[i][u] * bri;
}
}
num[i][0] = 1;
f = i;
break;

}
think(x+1);
ans[x] = num[f][n+1] / num[f][x];
num[f][0] = 0;
for(int i=1; i<=n; i++)
if(num[i][0] == 1)
num[i][n+1] -= num[i][x] * ans[x];
}

int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++){
for(int j=1; j<=n+1; j++)
scanf("%f", &num[i][j]);
num[i][0] = 0;
}
think(1);
for(int i=1; i<=n; i++)
printf("%d ", (int)round(ans[i]));
return 0;
}
有点麻烦的方法~~求指点

• @ 2015-05-26 15:42:14

输出的时候要round一下。

``````#include <stack>
#include <cstdio>
#include <list>
#include <cassert>
#include <set>
#include <fstream>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <cmath>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define LL long long
#define ULL unsigned long long
#define SZ(x) (int)x.size()
#define Lowbit(x) ((x) & (-x))
#define MP(a, b) make_pair(a, b)
#define MS(arr, num) memset(arr, num, sizeof(arr))
#define PB push_back
#define X first
#define Y second
#define ROP freopen("input.txt", "r", stdin);
#define MID(a, b) (a + ((b - a) >> 1))
#define LC rt << 1, l, mid
#define RC rt << 1|1, mid + 1, r
#define LRT rt << 1
#define RRT rt << 1|1
#define FOR(i, a, b) for (int i=(a); (i) < (b); (i)++)
#define FOOR(i, a, b) for (int i = (a); (i)<=(b); (i)++)
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const double eps = 1e-4;
const int MAXN = 1e2+10;
const int MOD = 1e9+7;
const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
const int seed = 131;
int cases = 0;
typedef pair<int, int> pii;

int n;
double A[MAXN][MAXN];
void Gauss()
{
int i, j, k, r;
for (i = 0; i < n; i++)
{
r = i;
for (j = i+1; j < n; j++)
if (fabs(A[j][i]) > fabs(A[r][i])) r = j;
if (r != i) for (j = 0; j <= n; j++) swap(A[r][j], A[i][j]);
for (k = i+1; k < n; k++)
{
double f = A[k][i] / A[i][i];
for (j = i; j <= n; j++) A[k][j] -= f * A[i][j];
}
}
for (i = n-1; i >= 0; i--)
{
for (j = i+1; j < n; j++)
A[i][n] -= A[j][n] * A[i][j];
A[i][n] /= A[i][i];
}
}

int main()
{
//ROP;
scanf("%d", &n);
for (int i = 0; i < n; i++)
for (int j = 0; j <= n; j++) scanf("%lf", &A[i][j]);
Gauss();
printf("%d", (int)round(A[0][n]));
for (int i = 1; i < n; i++) printf(" %d", (int)round(A[i][n]));
puts("");
return 0;
}
``````
• @ 2015-05-21 13:08:10

最最最最基础的高斯消元搞定

• @ 2014-08-02 16:59:39

var
n,i,j:integer;
jie:array[1..101]of double;
a:array[1..101,1..101]of double;
procedure exc(i:integer);
var
j:integer;
c:array[1..101] of double;
begin
for j:=i+1 to n do
if a[j,i]<> 0 then
break;
c:=a[i];
a[i]:=a[j];
a[j]:=c;
end;
procedure fu(p:double);
var
i,j,k:integer;
begin
for k:=1 to n-1 do
for i:=k+1 to n do
begin
if a[k,k]=0 then
exc(k);
for j:=n+1 downto k do
a[i,j]:=a[i,j]-a[k,j]*(a[i,k]/a[k,k]);
end;
jie[n]:=a[n,n+1]/a[n,n];
for i:= n-1 downto 1 do
begin
for j:=i+1 to n do
a[i,n+1]:=a[i,n+1]-a[i,j]*jie[j];
jie[i]:=a[i,n+1]/a[i,i];
end;
for i:= 1 to n do
write(round(jie[i]):6);
end;
begin
for i:=1 to n do
for j:=1 to n+1 do
fu(n);
end.

• @ 2014-08-02 09:19:46

program p1052;
var
a:array[1..100,1..101] of double;
n:longint;
procedure init;
var
i,j:longint;
begin
for i:=1 to n do
for j:=1 to n+1 do
end;
procedure change(x:longint);
var
i:longint;
f:array[1..101] of double;
begin
for i:=x to n do
if a[i,x]<>0 then
begin
f:=a[i];
a[i]:=a[x];
a[x]:=f;
break;
end;
end;
procedure solve;
var
i,j,k:longint;
l,sum:double;
begin
for i:=1 to n-1 do
begin
if a[i,i]=0 then change(i);
for j:=i+1 to n do
begin
l:=a[j,i]/a[i,i];
for k:=i to n+1 do
a[j,k]:=a[j,k]-a[i,k]*l;
end;
end;
for i:=n-1 downto 1 do
begin
sum:=0;
for j:=i+1 to n do
sum:=a[i,n+1]-sum;
end;
end;
procedure shuchu;
var
i:longint;
begin
for i:=1 to n do
end;
begin
init;
solve;
shuchu;
end.

• @ 2014-08-01 17:07:56

楼下的是傻帽，都别信他！！！

• @ 2014-08-01 17:09:56

盗取我的智力成果，，哎，脸皮啊

• @ 2014-08-01 17:06:58

大概就是个模拟，和平时解方程的过程、方法是一样的program ttdd8;var matrix:array[1..100,1..101] of double; temp:array[1..101] of double; x:array[1..100] of double; i,j,k,n:integer; m:double;beginreadln(n);{一共有n个式子}for i:=1 to n do begin for j:=1 to n+1 do read(matrix[i,j]);{依次读入每个式子x1,x2…的系数及常数项} readln; end;for i:=1 to n-1 do{需要消元n-1次} begin for j:=i to n do{寻找主元，即当前要消去元素系数最大的一个式子} if matrix[j,i]>matrix[i,i] then begin temp:=matrix[i]; matrix[i]:=matrix[j]; matrix[j]:=temp; end; for j:=i+1 to n do begin m:=matrix[j,i]/matrix[i,i]; matrix[j,i]:=0; for k:=i+1 to n+1 do matrix[j,k]:=matrix[i,k]*m-matrix[j,k]; end; end;x[n]:=matrix[n,n+1]/matrix[n,n];{回代过程}for i:=n-1 downto 1 do begin m:=0; for j:=i+1 to n do m:=m+matrix[i,j]*x[j]; x[i]:=(matrix[i,n+1]-m)/matrix[i,i]; end;for i:=1 to n do writeln(x[i]:0:2);end.

• @ 2014-08-02 08:52:33

你俩好猥琐···

• @ 2014-08-01 17:05:08

秒过，不解释
var
mid:array[1..101]of double;
f:array[1..100,1..101]of double;
m,n,o,p:longint;
a:array[1..100]of double;
procedure work(i,j:longint);
var
c,d:array[1..101]of double;
k,l:longint;
r:double;
begin
c:=f[i];
d:=f[j];
if d[1]=0
then begin
for k:=1to n-i+1do
f[j,k]:=f[j,k+1];
f[j,n-i+2]:=0;
exit;
end;
r:=-c[1]/d[1];
for k:=1to n-i+1do
d[k]:=d[k+1]*r+c[k+1];
d[n-i+2]:=0;
f[j]:=d;
end;
procedure pri(i:longint);
var
j,k,l:longint;
r:double;
begin
for j:=1to n-i do
f[i,j+1]:=f[i,j+1]*a[i+j];
r:=0;
for j:=2to n-i+1do
r:=r+f[i,j];
r:=(f[i,n-i+2]-r)/f[i,1];
a[i]:=r;
end;
begin
for o:=1to n do
begin
for p:=1to n+1do
end;
for o:=2to n do
if abs(f[o,1])>abs(f[1,1])
then begin
mid:=f[1];
f[1]:=f[o];
f[o]:=mid;
end;
for o:=1to n-1do
begin
for p:=o+1to n do
work(o,p);
for m:=o+2to n do
if abs(f[m,1])>abs(f[o+1,1])
then begin
mid:=f[m];
f[m]:=f[o+1];
f[o+1]:=mid;
end;
end;
for o:=n downto 1do
pri(o);
for o:=1to n-1do
if round(a[o])=-0
then write(0,' ')
else write(round(a[o]),' ');
if round(a[n])=-0
then writeln(0)
else writeln(round(a[n]));
end.

• @ 2014-08-01 17:08:31

抄袭的我的，大笨蛋

• @ 2013-12-19 12:36:47

高斯消元的精度：如果%.0lf 和 round 都WA 的话
这样输出：printf("%d ", int(A[i][n+1]+0.5+1e-6));

• @ 2013-02-16 10:17:14
• @ 2010-03-17 13:34:08

囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

对于线性方程组:

A11*X1+A12*X2+....A1n*Xn=B1

A21*X1+A22*X2+....A2n*Xn=B2

...........................

An1*X1+An2*X2+....Ann*Xn=Bn

要想解它,我们有如下方法:

1.建立增广矩阵,即将Aij和Bi放入矩阵中.

2.消元:

进行第K步消元的时候,选取主元素为Akk,现在我们要将Aik(i>k)全部消掉.怎么消呢?显然将每一行乘一个数,然后再用主行(即Ak)去减就行.具体方法如下:设Mi为第I行要乘的数(i>k),则Mi=Akk/Aik(Aik=0则这行不用乘),然后Aij(i>k且j>k)=Akj-Aij*Mi,Bi(i>k)=Bk-Bi*Mi.要注意到,当Mi的分子很小的时候,会存在很大的精度问题,怎么解决呢?找出Aik(i>k)中绝对值最大的那个(若绝对值最大为0,则主元素变换为Akk+1,继续消元),将它所在行与第K行交换,把它当成新的主行消元即可.

3.找答案:

消元后,增广矩阵会变成如下形状:

A11 A12 ......A1n=B1

A22.......A2n=B2

A33....A3N=B3

.......

Ann=Bn

此时很显然可以看出Xn=Bn/Ann,将其回代上去即可得到解.

上面讨论了对于有且仅有一个解的情况,下面讨论其他情况:

当消元过程中出现无法选出主元素时,观察是否存在行Bi!=0(i>当前行),有则无解,否则无数解.

具体实现时可以递归,然后回家时赋值.

接下来继续讨论如何解决XOR方程.

Xor方程形如这样:

A11*X1xorA12*X2xor....A1n*Xn=B1

A21*X1xorA22*X2xor....A2n*Xn=B2

...........................

An1*X1xorAn2*X2xor....Ann*Xn=Bn

其中aij和bi都为0或1.则答案xi也为0或1.

解法可以参照加法方程,不同的时:进行第K步消元的时候,选取主元素为Akk,现在我们要将Aik(i>k)全部消掉.具体方法如下:对于Aij(i>k且j>k)=Akj xor aij,Bi(i>k)=Bk xor Bi.

返回时利用定理:a xor b=c则a=c xor b;且xor满足结合律.

无解无数解做法同.

输出实数时候输出round(1e-6+a*10^k)/10^k:0:k

• @ 2009-10-30 08:55:10

没注意-0

反正一遍就过了。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

• @ 2009-10-22 18:09:36

高斯消元法

• @ 2009-10-13 12:36:43

经典高斯消元，思路清晰即可

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

• @ 2009-10-12 15:25:53

求最小公倍数总是出现200，还是用大牛提供的double的方法吧

ID
1052

7

(无)

2400

548

23%

5