题解：P6989 [NEERC 2014] Epic Win!

a_small_OIer · 2026-10-20 22:38:42 · 题解

P6989 [NEERC 2014] Epic Win!

你说的对，但是确定性算法太难想了。

题意

给定一个 n 状态的有限状态自动机（Finite State Machines，FSM），你需要设计另一台 FSM 与其玩石头剪刀布并在 10^9 场内达到 99\% 胜率。

思路

显然如果我们知道对方的初始状态，那我们一定可以达到 100\% 胜率，把对方的自动机贺上去即可。

那么考虑如何知道对方的初始状态。一个显然的想法是通过一些出拳，根据对方后续的出拳来推测对方的初始状态。但是这个属于信息论范畴了，比较麻烦。

考虑随机化，我们钦定某个状态是对方的初始状态，根据对方的自动机进行预测对方的下一次出拳，如果预测正确，接着预测下下次，直到预测错误。如果预测错误，那么就重新钦定一个状态为当前状况，重复上述过程即可。

证明

显然每次随机猜测猜对的可能性是 \frac{1}{n} 的，只要某次猜测正确，那么后续的胜率就是 100\%，因此输场只可能在这若干次随机猜测的过程。

设猜测错误的次数为 M，那么输场多于 m 的概率为：

在 10^9 场中胜率 99\%，即输掉场次不超过 10^9\times1\%，即 10^7，有：

也就是说你有这么大的概率胜率没有 99\%。

实现

#include<bits/stdc++.h>
#define N 110
#define L 500
using namespace std;
typedef long long LL;
//十年OI一场空，不开long long见祖宗
struct FSM{
    int r , p , s;
}a[N];
int n , nxt[N][N] , out[N];
map<char , int> mp;
int id(int i , int j , int n){
    return j * n + i;
}
int main(){
    //freopen(".in" , "r" , stdin);
    //freopen(".out" , "w" , stdout);
    mt19937 rng(time(0));
    mp['R'] = 0 , mp['P'] = 1 , mp['S'] = 2;
    scanf("%d" , &n);
    for(int i = 1 ; i <= n ; i++){
        char c;
        scanf(" %c" , &c);
        out[i] = mp[c];
        for(int j = 1 ; j <= 3 ; ++j)
            scanf("%d" , &nxt[i][j]);
    }
    printf("%d\n" , L * n);
    for(int i = 0 ; i < L ; ++i){
        for(int j = 1 ; j <= n ; ++j){
            int num = (out[j] + 1) % 3;
            printf("%c" , "RPS"[num]);
            for(int k = 0 ; k < 3 ; ++k){
                int ns;
                if(k == out[j])
                    ns = id(nxt[j][num + 1] , i , n);
                else
                    ns = id(rng() % n + 1 , (i + 1) % L , n);
                printf(" %d" , ns);
            }
            printf("\n");
        }
    }
    return 0;
}