hdu 5755（GAuss 消元）

时间：2016-09-11 23:05:42 收藏：0 阅读：332

Gambler Bo

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1152 Accepted Submission(s): 471
Special Judge

Problem Description

Gambler Bo is very proficient in a matrix game.

You have a

Input

First line, an integer

Output

For each test, first line contains an integer

Sample Input

2 2 3 2 1 2 0 2 0 3 3 1 0 1 0 1 0 1 0 1

Sample Output

1 1 2 5 1 1 1 3 2 2 3 1 3 3

Author

绍兴一中

Source

2016 Multi-University Training Contest 3

Recommend

wange2014

gauss消元的mod 3 版本，把n*m个格子上的操作全部变成列向量，共n*m个，每个列向量有n*m个元素，做一遍gauss消元就能解出。

另：优化后因为第i行的状态可以由i+1行确定，所以能建立m个方程，每个方程 M 个变量进行高斯消元，解出解后代回去得到每个元素应该被操作的次数。详见

http://www.cnblogs.com/naturepengchen/articles/5711133.html

我的裸gauss消元代码如下：

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 #define clr(x) memset(x,0,sizeof(x))
  7 #define clrdown(x) memset(x,-1,sizeof(x))
  8 #define maxn 910
  9 using namespace std;
 10 int A[maxn][maxn];
 11 int free_x[maxn];
 12 int x[maxn];
 13 int mov[4][2]={0,1,0,-1,1,0,-1,0};
 14 void init(int n,int m);
 15 void gauss(int n,int m);
 16 void print(int n,int m);
 17 int exgcd(int a,int b,int &x,int &y);
 18 int lcm(int a,int b);
 19 int gcd(int a,int b);
 20 int main()
 21 {
 22     int T,p,num,n,m;
 23     scanf("%d",&T);
 24     while(T--)
 25     {
 26         scanf("%d%d",&n,&m);
 27         init(n,m);
 28         gauss(n*m,n*m);
 29         print(n,m);
 30     }
 31     return 0;
 32 }
 33 void print(int n,int m)
 34 {
 35     int sum=0;
 36     for(int i=0;i<n*m;i++)
 37         sum+=x[i];
 38     printf("%d\n",sum);
 39     for(int i=0;i<n;i++)
 40         for(int j=0;j<m;j++)
 41             while(x[i*m+j]>0)
 42             {
 43                 printf("%d %d\n",i+1,j+1);
 44                 x[i*m+j]--;
 45             }
 46     return ;
 47 }
 48 void init(int n,int m)
 49 {
 50     int t;
 51     clr(A);
 52     for(int i=0;i<n;i++)
 53         for(int j=0;j<m;j++)
 54         {
 55             t=i*m+j;
 56             A[t][t]=2;
 57             for(int k=0;k<4;k++)
 58                 if(i+mov[k][0]>=0 && i+mov[k][0]<n && j+mov[k][1]>=0 && j+mov[k][1]<m)
 59                     A[(i+mov[k][0])*m+j+mov[k][1]][t]=1;
 60         }
 61     t=n*m;
 62     for(int i=0;i<n;i++)
 63         for(int j=0;j<m;j++)
 64         {
 65             scanf("%d",&A[i*m+j][t]);
 66             A[i*m+j][t]=(3-A[i*m+j][t])%3;
 67         }
 68     clrdown(x);
 69     clr(free_x);
 70 }
 71 void gauss(int n,int m)
 72 {
 73 //    for(int i=0;i<n;i++)
 74 //    {
 75 //       for(int j=0;j<=m;j++)
 76 //           printf("%d ",A[i][j]);
 77 //       printf("\n");
 78 //    }
 79     int k,col,num=0,max_r,dou,max_x,LCM,ta,tb;
 80     for(k=0,col=0;k<n && col<m;k++,col++)
 81     {
 82         max_r=k;
 83         max_x=abs(A[k][col]);
 84         for(int i=k+1;i<n;i++)
 85             if(max_x<abs(A[i][col]))
 86             {
 87                 max_x=abs(A[i][col]);
 88                 max_r=i;
 89             }
 90         if(max_r!=k)
 91         {
 92             for(int j=col;j<=m;j++)
 93                 swap(A[k][j],A[max_r][j]);
 94         }
 95         if(A[k][col]==0)
 96         {
 97             k--;
 98             free_x[num++]=col;
 99             continue;
100         }
101         for(int i=k+1;i<n;i++)
102         if(A[i][col])
103         {
104             LCM=lcm(A[k][col],A[i][col]);
105             ta=LCM/A[i][col];
106             tb=LCM/A[k][col];
107             for(int j=col;j<=m;j++)
108             {
109                     A[i][j]=((A[i][j]*ta-A[k][j]*tb)%3+3)%3;
110             }
111         }
112     }
113     int temp;
114     for(int i=0;i<num;i++)
115         x[free_x[i]]=0;
116     int  xi,yi;
117     for(int i=k-1,c=m-1;i>=0;c=m-1,i--)
118     {
119         temp=A[i][m];
120         while(x[c]!=-1)
121         {
122             if(A[i][c])
123                 temp=((temp-(x[c]*A[i][c])%3)%3+3)%3;
124             c--;
125         }
126         exgcd(A[i][c],3,xi,yi);
127         xi=(xi%3+3)%3;
128         x[c]=(temp*xi%3+3)%3;
129     }
130 //    for(int i=0;i<n;i++)
131 //    {
132 //        for(int j=0;j<=m;j++)
133 //            printf("%d ",A[i][j]);
134 //        printf("\n");
135 //    }
136 //    for(int i=0;i<m;i++)
137 //        printf("%d ",x[i]);
138     return ;
139 }
140 int exgcd(int a,int b,int &x,int &y)
141 {
142     if(b==0)
143     {
144         x=1;
145         y=0;
146         return a;
147     }
148     else
149     {
150         int r=exgcd(b,a%b,y,x);
151         y-=x*(a/b);
152         return r;
153     }
154 }
155 int gcd(int a,int b)
156 {
157     int c;
158     while(b!=0)
159     {
160         c=a%b;
161         a=b;
162         b=c;
163     }
164     return a;
165 }
166 int lcm(int a,int b)
167 {
168     return a/gcd(a,b)*b;
169 }

原文：http://www.cnblogs.com/wujiechao/p/5862935.html