2015安徽省赛 D.锐雯上单不给就送

题目描述

《英雄联盟》（简称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最有可能玩的角色，角色表示方法见注意事项，每个输出单独占一行

样例输入

2
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

样例输出

3 4

第一次费了好大劲写了超时的代码，还是掌握的知识还是太少，超时的代码：

 1 #include <iostream>
 2 #include <stdio.h>
 3 using namespace std;
 4 int main()
 5 {
 6     float d[10][10];
 7     int i,j,m,n,T;
 8     freopen("in.txt","r",stdin) ;
 9     scanf("%d",&T);                       //数据组数
10     while(T>0)
11     {
12         scanf("%d",&n);                   //求第n次
13         for(i=1;i<=5;i++)
14         {
15             for(j=1;j<=5;j++)
16             {
17                 scanf("%f",&d[i][j]);     //存概率
18             }
19         }
20         scanf("%d",&m);                   //第一次m
21         int k=1,term2;
22         float term1,term;
23         term1=d[1][m];
24         term2=m;
25         while(k<n)
26         {
27             for(i=1;i<=5;i++)
28             {
29                 term=d[i][m];
30                 if(term>term1)
31                 {
32                     term1=term;
33                     term2=i;
34                 }
35             }
36             m=term2;
37             k++;
38         }
39         printf("%d
",term2);
40         T--;
41     }
42     return 0;
43 }

借鉴了大神的算法才A了这道题：

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 using namespace std ;
 7  
 8 struct Matrix     
 9 {
10     double mat[5][5];
11 };
12  
13 Matrix mul(Matrix a,Matrix b) 
14 {
15     Matrix c;
16     for(int i=0;i<5;i++)
17         for(int j=0;j<5;j++)
18         {
19             c.mat[i][j]=0;
20             for(int k=0;k<5;k++)
21             {
22                 c.mat[i][j]+= a.mat[i][k]*b.mat[k][j];
23             }
24         }
25     return c;
26 }
27  
28 Matrix pow(Matrix a,int k)  
29 {
30     Matrix ans;
31     memset(ans.mat,0,sizeof(ans.mat));
32     for (int i=0;i<5;i++)
33         ans.mat[i][i]=1;
34     Matrix temp=a;
35     while(k)
36     {
37         if(k&1){ans=mul(ans,temp);} 
38         temp=mul(temp,temp);  
39         k=k/2;
40     }
41     return ans;
42 }
43  
44 int main ()
45 {
46     int T;
47     cin>>T ;
48     while(T--)
49     {
50         int n,m;
51         scanf("%d",&n);
52         int i,j;
53         Matrix t ;
54         for (i =0;i<5;i++)
55             for (j=0;j<5;j++)
56                 scanf("%lf",&t.mat[i][j]);
57         scanf("%d",&m);
58         if (n==1)
59         {
60             cout<<m<<endl;
61             continue;
62         }
63         n=n-1;
64         m=m-1;
65         double MAX = 0 ;
66         int id ;
67         Matrix ans=pow(t,n);
68  
69         for (i=4;i>=0;i--)
70         {
71             if(ans.mat[i][m]>MAX||abs(ans.mat[i][m]-MAX)<1e-6)
72             {
73                 MAX=ans.mat[i][m] ;
74                 id=i;
75             }
76         }
77         cout<<id+1<<endl ;
78     }
79     return 0 ;
80 }
81 /**************************************************************
82     Problem: 1208
83     User: 2014217052
84     Language: C++
85     Result: 正确
86     Time:7 ms
87     Memory:1504 kb
88 ****************************************************************/

View Code