湖南建设银行官网网站首页,内蒙古优途国际旅行社,网站制作的评价标准,wordpress 默认上传路径Description#xff1a;石头剪刀布是常见的猜拳游戏。石头胜剪刀#xff0c;剪刀胜布#xff0c;布胜石头。如果两个人出拳一样#xff0c;则不分胜负。 一天#xff0c;小A和小B正好在玩石头剪刀布。已知他们的出拳都是有规律的#xff0c;比如#xff1a;“石头-布-石…Description石头剪刀布是常见的猜拳游戏。石头胜剪刀剪刀胜布布胜石头。如果两个人出拳一样则不分胜负。 一天小A和小B正好在玩石头剪刀布。已知他们的出拳都是有规律的比如“石头-布-石头-剪刀-石头-布-石头-剪刀……”就是以“石头-布-石头-剪刀”为周期的。请问小A和小B比了N轮之后谁赢了 Input 输入的第一行包含一个整数K表示K组测试数据。 之后的每组测试数据包含三行。第一行包含三个整数NNANB分别表示比了N轮小A出拳的周期长度小B出拳的周期长度。第二行包含NA个整数表示小A出拳的规律第三行包含NB个整数表示小B出拳的规律。其中0表示“石头”2表示“剪刀”5表示“布”。 对于小数据0 K,N,NA,NB 10;对于大数据0 K,N,NA,NB 100; Output: 对于每组测试数据输出一行。如果小A赢了输出A如果小B赢了输出B如果两人打平输出draw。 Sample Input 2 10 3 4 0 2 5 0 5 0 2 5 3 3 2 0 5 0 2 5 Sample Output A draw Hint 对于第一组测试数据猜拳过程为 A0 2 5 0 2 5 0 2 5 0 B0 5 0 2 0 5 0 2 0 5 所以A赢了4轮B赢了2轮双方打平4轮所以A赢了。 对于第二组测试数据猜拳过程为 A2 0 5 2 0 B0 2 5 0 2 所以A赢了2轮B赢了2轮双方打平1轮所以最终打平了。 思路假设A出拳的周期长度为naB出拳的周期长度为nb对于具体的出拳规律则使用两个数组arrayA[],arrayB[]来保存。 在第i次出拳时判断获胜方的方法比较A出arrayA[i%na]、B出 arrayB[i%nb]的赢家统计n次出拳后A总共赢的次数和B总共赢的次数然后按要求输出即可。 优化方法在以上方法中总是需要比较n次才能算出赢家这样在n比较大时可能存在着周期性的重复比较。如n 40, na 3nb 4时显然n从13到36的比较就很多余了所以考虑优化这些多余的比较——聪明如你肯定想到可以使用na和nb的最小公倍数来进行优化了吧~ 此外思考具体的计算过程是否是将最小公倍数周期内的比较同不满足整个周期第37-40次的比较相加PS之所以将此项单独列出是因为在同学的讨论中确实存在这样的误解所以看仔细了哦~ 试想在前12次比较中B先赢4次然后在5-12次中A、B平局2次、A赢6次然后再第37-40次B赢4次A总共赢6次B总共赢8次最终B取得胜利 也许你会大声的说No在前36次中A共赢18次B共赢12次在全40次的比较中A赢18次B赢16次结果是A赢。 下面上代码 1 #includeiostream2 using namespace std;3 static int winA;4 static int winB;5 //求正整数a和b的最大公约数6 int divisor(int a, int b){7 int n ab ? a:b;8 if(ab) a b;9 else return a;
10 while(n%a !0){
11 b a;
12 a n%a;
13 n b;
14 }
15 return a;
16 }
17
18 //求正整数a和b的最小公倍数
19 int multiple(int a, int b){
20 return a/divisor(a,b)*b;
21 }
22
23 void cmp(int arrayA[],int na, int arrayB[], int nb,const int cal)
24 {
25 for(int i0; ical; i)
26 {
27 int a i % na;
28 int b i % nb;
29 //A赢
30 if((arrayA[a]0 arrayB[b]2)||(arrayA[a]2 arrayB[b]5)||(arrayA[a]5 arrayB[b]0))
31 {
32 winA;
33 }else if(arrayA[a] ! arrayB[b])
34 {//B赢
35 winB;
36 }
37 }
38 }
39
40 int main()
41 {
42 int K, N, NA, NB, cal, i;
43 cinK;
44 while(K0){
45 winA0, winB0;
46 cinNNANB;
47 int* arrayA (int *)malloc((NA1)*sizeof(int));
48 int* arrayB (int *)malloc((NB1)*sizeof(int));
49 for(i0; iNA; i)
50 {
51 cinarrayA[i];
52 }
53 for(i0; iNB; i)
54 {
55 cinarrayB[i];
56 }
57 //通过最小公约数来实现最少的比较次数
58 cal multiple(NA,NB);
59 if(N cal)
60 cmp(arrayA,NA,arrayB,NB,N);
61 else
62 {
63 cmp(arrayA,NA,arrayB,NB,cal);
64 int mod N % cal, mul N / cal;
65 winA * mul;
66 winB * mul;
67 if(mod)
68 cmp(arrayA,NB,arrayB,NB,mod);
69 }
70 //输出计算结果
71 if(winAwinB)
72 coutdrawendl;
73 else if(winAwinB)
74 coutAendl;
75 else
76 coutBendl;
77 //别忘了释放空间
78 free(arrayA);
79 free(arrayB);
80 K--;
81 }
82 return 0;
83 } 转载于:https://www.cnblogs.com/Allie0920/archive/2013/04/05/3001612.html
