题目描述
《英雄联盟》（简称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最有可能玩的角色，角色表示方法见注意事项，每个输出单独占一行
样例输入
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
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
样例输出
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
float d[][];
int i,j,m,n,T;
freopen("in.txt","r",stdin) ;
scanf("%d",&T); //数据组数
while(T>)
{
scanf("%d",&n); //求第n次
for(i=;i<=;i++)
{
for(j=;j<=;j++)
{
scanf("%f",&d[i][j]); //存概率
}
}
scanf("%d",&m); //第一次m
int k=,term2;
float term1,term;
term1=d[][m];
term2=m;
while(k<n)
{
for(i=;i<=;i++)
{
term=d[i][m];
if(term>term1)
{
term1=term;
term2=i;
}
}
m=term2;
k++;
}
printf("%d\n",term2);
T--;
}
return ;
}
借鉴了大神的算法才A了这道题：
# 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]+= a.mat[i][k]*b.mat[k][j];
}
}
return c;
} Matrix pow(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=k/;
}
return ans;
} int main ()
{
int T;
cin>>T ;
while(T--)
{
int n,m;
scanf("%d",&n);
int i,j;
Matrix t ;
for (i =;i<;i++)
for (j=;j<;j++)
scanf("%lf",&t.mat[i][j]);
scanf("%d",&m);
if (n==)
{
cout<<m<<endl;
continue;
}
n=n-;
m=m-;
double MAX = ;
int id ;
Matrix ans=pow(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 ;
}
/**************************************************************
Problem: 1208
User: 2014217052
Language: C++
Result: 正确
Time:7 ms
Memory:1504 kb
****************************************************************/