[HDOJ6418] Rikka with Stone-Paper-Scissors (纳什均衡)

链接:http://acm.hdu.edu.cn/showproblem.php?pid=6418

A和B玩剪子石头布,每个人要出$n$步,现在给你它们剪子、石头、布分别出的次数,每赢一次,获胜方得一分。已知A会随机出,现在求B的分数的最大期望。

一共玩$n$局,每一次出不同的手势,得分的概率和对方守中对应手势的数目有关系,直接把能赢和能输的概率加加减减就OK。证明涉及纳什均衡,JLS直播讲的也没太听懂orz。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;

using LL = long long;
LL a,b,c,a1,b1,c1;

signed main() {
// freopen("in", "r", stdin);
int T;
scanf("%d", &T);
while(T--) {
scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&a1,&b1,&c1);
LL n = a + b + c;
LL m = -a*c1-b*a1-c*b1+a1*c+b1*a+c1*b;
if(m % n == 0) {
printf("%lld\n", m / n);
}
else {
printf("%lld/%lld\n", m/__gcd((LL)abs(m),n), n/__gcd((LL)abs(m),n));
}
}
return 0;
}