poj 3735 Training little cats（构造矩阵） - c++编程基础

TOP

poj 3735 Training little cats（构造矩阵）

2015-07-24 06:00:00 来源: 作者: 【大中小】浏览:8次

大致题意：

有n只猫，开始时每只猫有花生0颗，现有一组操作，由下面三个中的k个操作组成：
1. g i 给i只猫一颗花生米
2. e i 让第i只猫吃掉它拥有的所有花生米

3. s i j 将猫i与猫j的拥有的花生米交换

现将上述一组操作循环m次后，问每只猫有多少颗花生？

再一次感受到了矩阵的强大。。。循环m次，且m这么大，很容易想到构造转换矩阵，但如何构造是个问题。尤其是第一种操作，第i只猫增加一个花生。具体构造方法是把矩阵扩大为(n+1)*(n+1)的，初始化为单位矩阵，g i: a.mat[0][i] += 1; e i ：第i列全置为0； s i j: 第i、j列元素互换

这样形成转换矩阵后，循环m次，用矩阵快速幂求得，最后取矩阵第0行的1~n就是答案。

点击打开链接学习了。。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include
       #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #define LL long long #define _LL __int64 #define eps 1e-8 #define PI acos(-1.0) using namespace std; const int maxn = 105; int n,k,m; struct matrix { _LL mat[maxn][maxn]; //初始化为单位矩阵 void init() { memset(mat,0,sizeof(mat)); for(int i = 0; i <= 102; i++) //不知道为什么，102换成maxn就会崩，求解。 mat[i][i] = 1; } }a,res; //矩阵相乘 matrix matrixMul(matrix x, matrix y) { matrix tmp; memset(tmp.mat,0,sizeof(tmp.mat)); for(int i = 0; i <= n; i++) { for(int k = 0; k <= n; k++) { if(x.mat[i][k] == 0) continue; for(int j = 0; j <= n; j++) { tmp.mat[i][j] += x.mat[i][k] * y.mat[k][j]; } } } return tmp; } //矩阵求幂 matrix Mul(matrix x, int k) { matrix tmp; tmp.init(); while(k) { if(k & 1) tmp = matrixMul(tmp,x); x = matrixMul(x,x); k >>= 1; } return tmp; } int main() { char ch[4]; while(~scanf(%d %d %d,&n,&m,&k)) { if(n == 0 && k == 0 && m == 0) break; a.init(); int num1,num2; while(k--) { scanf(%s,ch); if(ch[0] == 'g') { scanf(%d,&num1); a.mat[0][num1] += 1; } else if(ch[0] == 'e') { scanf(%d,&num1); for(int i = 0; i <= n; i++) a.mat[i][num1] = 0; } else { scanf(%d %d,&num1,&num2); for(int i = 0; i <= n; i++) swap(a.mat[i][num1],a.mat[i][num2]); } } if(m == 0) { for(int i = 0; i < n;i++) { if(i == 0)printf(0); else printf( 0); } printf( ); continue ; } res = Mul(a,m); for(int i = 1; i < n; i++) printf(%I64d ,res.mat[0][i]); printf(%I64d ,res.mat[0][n]); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj3411	下一篇：算法5-7：区间搜索

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: