HDU5755 Gambler Bo

2019-04-14 21:01发布

站内文章 / 模拟电子
15855 0 1300
题目链接：点击打开链接 题目大意：有一n*m(1 分析：由题意可知，所有的操作也是模3 域下的，也就是说如果有解的话，除去无效操作，操作总数一定<=2*m*n。 只需要解一个模3的线性方程组即可，未知量数为n*m个，表示从全为0的状态变为当前状态该位置进行了几次操作。 注意，可能存在无穷组解，只需要任意确定自由元即可得到一个解。 对得到的解求其模3的补即是答案。

#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int mod = 1000000003; const double eps = 1e-6; const int inf = 0x3f3f3f3f; const ll INF = 100000000000000000ll; int mat[40][40],n,m; const int MAXN=1805; int a[MAXN][MAXN];//增广矩阵 int x[MAXN];//解集 bool free_x[MAXN];//标记是否是不确定的变元 inline int gcd(int a,int b) { int t; while(b!=0) { t=b; b=a%b; a=t; } return a; } inline int lcm(int a,int b) { return a/gcd(a,b)*b;//先除后乘防溢出 } // 高斯消元法解方程组(Gauss-Jordan elimination).(-2表示有浮点数解，但无整数解， //-1表示无解，0表示唯一解，大于0表示无穷解，并返回自由变元的个数) //有equ个方程，var个变元。增广矩阵行数为equ,分别为0到equ-1,列数为var+1,分别为0到var. int Gauss(int equ,int var) { int i,j,k; int max_r;// 当前这列绝对值最大的行. int col;//当前处理的列 int ta,tb; int LCM; int temp; int free_x_num; int free_index; for(int i=0;i<=var;i++) { x[i]=0; free_x[i]=true; } //转换为阶梯阵. col=0; // 当前处理的列 for(k = 0;k < equ && col < var;k++,col++) {// 枚举当前处理的行. // 找到该col列元素绝对值最大的那行与第k行交换.(为了在除法时减小误差) max_r=k; for(i=k+1;iabs(a[max_r][col])) max_r=i; } if(max_r!=k) {// 与第k行交换. for(j=k;j= 0; i--) { // 第i行一定不会是(0, 0, ..., 0)的情况，因为这样的行是在第k行到第equ行. // 同样，第i行一定不会是(0, 0, ..., a), a != 0的情况，这样的无解的. free_x_num = 0; // 用于判断该行中的不确定的变元的个数，如果超过1个，则无法求解，它们仍然为不确定的变元. for (j = 0; j < var; j++) { if (a[i][j] != 0 && free_x[j]) free_x_num++, free_index = j; } if (free_x_num > 1) continue; // 无法求解出确定的变元. // 说明就只有一个不确定的变元free_index，那么可以求解出该变元，且该变元是确定的. temp = a[i][var]; for (j = 0; j < var; j++) { if (a[i][j] != 0 && j != free_index) temp -= a[i][j] * x[j]%3; temp=(temp%3+3)%3; } x[free_index] = (temp / a[i][free_index])%3; // 求出该变元. free_x[free_index] = 0; // 该变元是确定的. } return var - k; // 自由变元有var - k个. } // 3. 唯一解的情况: 在var * (var + 1)的增广阵中形成严格的上三角阵. // 计算出Xn-1, Xn-2 ... X0. for (i = var - 1; i >= 0; i--) { temp = a[i][var]; for (j = i + 1; j < var; j++) { if (a[i][j] != 0) temp -= a[i][j] * x[j]; temp=(temp%3+3)%3; } while (temp % a[i][i] != 0) temp+=3; x[i] =( temp / a[i][i])%3 ; } return 0; } int judge(int c,int d){ int i,j,i1,j1; i = c/m; j = c%m; i1 = d/m; j1 = d%m; if(abs(i1-i)+abs(j1-j)==1){ return 1; } return 0; } vector ans; int main() { int T; cin>>T; while(T--){ ans.clear(); scanf("%d%d",&n,&m); int nn = n*m; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ scanf("%d",&mat[i][j]); } } for(int i = 0;i < nn;i++){ for(int j = 0;j < nn;j++){ if(i == j){ a[i][j] = 2; } else{ if(judge(i,j)){ a[i][j] = 1; } else a[i][j] = 0; } } } for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ a[i*m+j][nn] = mat[i][j]; } } int res = 0; int free = Gauss(nn,nn); if(free>0){ for(int i = 0;i < free;i++){ for(int j = 0;j < nn;j++){ if(j == nn-free+i) a[nn-free+i][j] = 1; } } int aa = Gauss(nn,nn); } for(int i = 0;i < nn;i++){ int k = (3-x[i])%3; for(int j = 0;j < k;j++){ res++; ans.push_back(i); } } printf("%d ",res); for(int i = 0;i < ans.size();i++){ int k = ans[i]; printf("%d %d ",k/m+1,k%m+1); } } return 0; }

热门文章