1208: D.锐雯上单不给就送
时间限制: 1 Sec内存限制: 64 MB提交: 39解决: 8
标签提交统计讨论版
题目描述
《英雄联盟》（简称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的矩阵来表示，表示上一次如果zz_1215玩的是第j个角色，那么他这一次玩第i个角色的概率为，另外有。现在知道zz_1215第一次玩的是什么角色，devtang想知道在第n次游戏中，zz_1215最有可能玩的是什么角色。
输入
首先是一个正整数T，表示有T组数据
每组数据包括
第一行是一个数字n，表示devtang想知道第n次游戏中zz_1215最可能玩的角色
接下来会给出5*5的矩阵表示概率关系
最后一行给出整数m()表示zz_1215第一次游戏玩的角色，角色表示方法见注意事项
输出
输出第n次游戏中，zz_1215最有可能玩的角色，角色表示方法见注意事项，每个输出单独占一行
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
提示
1,2,3,4,5分别代表“上单”，“打野”，“中单”，“辅助”，“ADC”这五个角色，如果存在多个角色的概率相同的话，那么就选择下标最小的那个，比如经过计算1，3的概率都是0.5，那么zz_1215会选择1这个角色
1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <algorithm> 5 # include <cmath> 6 using namespace std ; 7 struct Matrix 8 { 9double mat[5][5];10 };11 Matrix mul(Matrix a,Matrix b) //矩阵乘法12 {13Matrix c;14for(int i=0;i<5;i++)15 for(int j=0;j<5;j++)16 {17 c.mat[i][j]=0;18 for(int k=0;k<5;k++)19 {20 c.mat[i][j]=(c.mat[i][j] + a.mat[i][k]*b.mat[k][j]);21 }22 }23return c;24 }25 Matrix pow_M(Matrix a,int k) //矩阵快速幂26 {27Matrix ans;28memset(ans.mat,0,sizeof(ans.mat));29for (int i=0;i<5;i++)30 ans.mat[i][i]=1;31Matrix temp=a;32while(k)33{34 if(k&1)ans=mul(ans,temp);35 temp=mul(temp,temp);36 k>>=1;37}38return ans;39 }40 41 int main ()42 {43freopen("in.txt","r",stdin) ;44int T;45cin>>T ;46while(T--)47{48 int n , m;49 cin>>n ;50 int i , j ;51 Matrix t ;52 for (i = 0 ; i < 5 ; i++)53 for (j = 0 ; j < 5 ; j++)54 cin>>t.mat[i][j] ;55 cin>>m ;56 if (n == 1)57 {58 cout<<m<<endl ;59 continue ;60 }61 n-=1 ;62 m-=1 ;63 double MAX = 0 ;64 int id ;65 Matrix ans = pow_M(t,n) ;66 67 for (i = 4 ; i >= 0 ; i--)68 {69 if (ans.mat[i][m] > MAX || abs(ans.mat[i][m] - MAX) < 1e-6)70 {71 MAX = ans.mat[i][m] ;72 id = i ;73 }74 }75 cout<<id+1<<endl ;76}77return 0 ;78 }
