D 矩阵快速幂

Description

《英雄联盟》（简称LOL）是由美国Riot Games开发，腾讯游戏运营的英雄对战网游。《英雄联盟》除了即时战略、团队作战外，还拥有特色的英雄、自动匹配的战网平台，包括天赋树、召唤师系统、符文等元素。简单来说，LOL是一个10人组的对战游戏，一个队伍(5个人)对抗另一个队伍(5个人)，主要目的是拆掉对面的建筑物，一个每个队伍的英雄都扮演着不同的角色，分别为“上单”，“打野”，“中单”，“辅助”，“ADC”，通常的情况是各自队伍的“上单”VS“上单”，“打野”VS“打野”，“中单”VS“中单”，“辅助”VS“辅助”，“ADC”VS“ADC”。上单在LOL中一直是一个很吃香的角色，一般小学生进入匹配以后都会强调一句“锐雯上单不给就送”作为联络暗号。zz_1215和devtang经常玩这个游戏，zz_1215是devtang的宿敌，devtang很想知道zz_1215玩的什么角色，然后他就选同样的角色和zz_1215决斗(solo)。经过观察devtang发现zz_1215选择什么角色是有规律的，那就是取决于他上一次玩的什么角色。现用一个5*5的矩阵来表示，a(i,j)表示上一次如果zz_1215玩的是第j个角色，那么他这一次玩第i个角色的概率为a(i,j)(0<=a(i,j)<=1))，另外有a(1,j)+a(2,j)+a(3,j)+a(4,j)+a(5,j)=1。现在知道zz_1215第一次玩的是什么角色，devtang想知道在第n次游戏中，zz_1215最有可能玩的是什么角色。

Input

首先是一个正整数T，表示有T组数据
每组数据包括
第一行是一个数字n(1<=n<=10^8)，表示devtang想知道第n次游戏中zz_1215最可能玩的角色
接下来会给出5*5的矩阵表示概率关系
最后一行给出整数m(1<=m<=5)表示zz_1215第一次游戏玩的角色，角色表示方法见注意事项

Output

输出第n次游戏中，zz_1215最有可能玩的角色，角色表示方法见注意事项，每个输出单独占一行

a ij 上一次玩j 这一次就会玩i
概率相同时选数字小的

Sample Input

2 //T
1
0 0.1 0.2 0.3 0.4
0.4 0 0.1 0.2 0.3
0.3 0.4 0 0.1 0.2
0.2 0.3 0.4 0 0.1
0.1 0.2 0.3 0.4 0
3
2 //第2次玩什么
0 0.1 0.2 0.3 0.4
0.4 0 0.1 0.2 0.3
0.3 0.4 0 0.1 0.2
0.2 0.3 0.4 0 0.1 //看第3列 0.4最大所以下一次玩4
0.1 0.2 0.3 0.4 0
3 //第一次玩3

Sample Output

3
4

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 # include <algorithm>

 # include <cmath>

 using namespace std ;

 struct Matrix

 {

     double mat[][];

 };

 Matrix mul(Matrix a,Matrix b) //矩阵乘法

 {

     Matrix c;

     for(int i=;i<;i++)

         for(int j=;j<;j++)

         {

             c.mat[i][j]=;

             for(int k=;k<;k++)

             {

                 c.mat[i][j]=(c.mat[i][j] + a.mat[i][k]*b.mat[k][j]);

             }

         }

     return c;

 }

 Matrix pow_M(Matrix a,int k)  //矩阵快速幂

 {

     Matrix ans;

     memset(ans.mat,,sizeof(ans.mat));

     for (int i=;i<;i++)

         ans.mat[i][i]=;

     Matrix temp=a;

     while(k)

     {

         if(k&)ans=mul(ans,temp);

         temp=mul(temp,temp);

         k>>=;

     }

     return ans;

 }

 int main ()

 {

     //freopen("in.txt","r",stdin) ;

     int T;

     cin>>T ;

     while(T--)

     {

         int n , m;

         cin>>n ;

         int i , j ;

         Matrix t ;

         for (i =  ; i <  ; i++)

             for (j =  ; j <  ; j++)

                 cin>>t.mat[i][j] ;

         cin>>m ;

         if (n == )

         {

             cout<<m<<endl ;

             continue ;

         }

         n-= ;

         m-= ;

         double MAX =  ;

         int id ;

         Matrix ans = pow_M(t,n) ;

         for (i =  ; i >=  ; i--)

         {

             if (ans.mat[i][m] > MAX || abs(ans.mat[i][m] - MAX) < 1e-)

             {

                 MAX = ans.mat[i][m] ;

                 id = i ;

             }

         }

         cout<<id+<<endl ;

     }

     return  ;

 }

巴特西

D 矩阵快速幂

最新文章

热门文章