cdoj793-A Linear Algebra Problem

http://acm.uestc.edu.cn/#/problem/show/793
 
A Linear Algebra Problem
Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit 
Status
God Kufeng is the God of Math. However, Kufeng is not so skilled with linear algebra, especially when dealing with matrixes.
One day, Captain Chen has a problem with matrix, here is the problem:
Given a n×n matrix A, what is the solution of n×n matrix X for the equation AX+XA=2A?
Captain Chen is a nice Captain, he wants to solve the equation only when A is a diagonal matrix, which means Aij=0 holds for all i≠j .
“That’s easy!” says Kufeng, “the answer is simply X=I, when I is the Identity Matrix.”
“But… is it the only solution for the equation above?” Captain Chen asks.
Kufeng cannot answer this question, can you help him?
Input
The first line of input is a number n, giving the size of matrix A and X. (1≤n≤1000)
Then comes a single line with n numbers, x1,x2,⋯,xn, where xi is the value of Aii. (−10000≤xi≤10000)
Output
If the answer is unique, output  UNIQUE , otherwise output  NOT UNIQUE
Sample input and output
Sample Input
Sample Output

3

1 2 3

UNIQUE

2

1 -1

NOT UNIQUE

Hint
For the second sample input, A=(100−1), there can be more than one possible solutions for X, for example, X=(1001) and X=(1101) both satisfy the equation, so the answer is not unique.
 
标题:行列Aは非主対角線外のすべての要素が0であることを満たし、行列Xがあり、AX+XA=2 Aを満たす.このようなXが唯一かどうかを聞く.
構想:まず,Xは単位行列であり,数式を満たす.次に、最後のマトリクス2 AをマトリクスBとする.i=jの場合、bii=aii*xii+xii*aii=2*aii*xii=2*aiiとなります.すなわち、xiiが唯一、すなわち1である場合、aiiは0ではない.i!=jの場合、bij=aii*xij+xij*ajj=xij*(aii+ajj)=0.つまり、xijが一意である0を望む場合、aii+ajjは0ではないので、Xが一意である場合、マトリクスAの主対角線上の要素は0が存在せず、逆数が存在しないという2つの条件を満たさなければならない.
コード:

 1 #include <fstream>

 2 #include <iostream>

 3 #include <algorithm>

 4 #include <cstdio>

 5 #include <cstring>

 6 #include <cmath>

 7 #include <cstdlib>

 8 #include <queue>

 9 

10 using namespace std;

11 

12 #define PI acos(-1.0)

13 #define EPS 1e-12

14 #define lll __int64

15 #define ll long long

16 #define INF 0x7fffffff

17 

18 int a[1002];

19 bool b;

20 

21 int main(){

22     //freopen("D:\\input.in","r",stdin);

23     //freopen("D:\\output.out","w",stdout);

24     int n;

25     scanf("%d",&n);

26     for(int i=0;i<n;i++){

27         scanf("%d",&a[i]);

28         if(a[i]==0) b=1;

29     }

30     if(!b){

31         sort(a,a+n);

32         for(int i=0;i<n;i++){

33             if(a[i]>0||b)  break;

34             for(int j=n-1;j>i;j--){

35                 if(a[i]+a[j]==0){

36                     b=1;

37                     break;

38                 }else if(a[i]+a[j]<0)

39                     break;

40             }

41         }

42     }

43     if(b)   puts("NOT UNIQUE");

44     else    puts("UNIQUE");

45     return 0;

46 }

View Code