小Q和小S的游戏 | BFS

问题描述

小Q和小X是很好的朋友，她们正在玩一个游戏。她们拿到了一个数组，游戏开始时小Q随机选择一个元素作为起点。接着，两人轮流行动，小Q先行动。

每次行动时，当前玩家需要选择当前元素左边比它更小的元素，然后移动到该元素，接下来换另一方从这个元素继续移动。如果某一方无法进行合法的移动，则该方输掉游戏。

小Q想知道，在双方都采取最优策略的情况下，她最终获胜的概率是多少？请输出分数的最简形式，即分子和分母互素。如果小Q必胜，则输出 1/1。如果小Q必败，则输出 0/1。

测试样例

样例1：

输入：n = 5,a = [3, 1, 5, 4, 3]
输出：'3/5'

样例2：

输入：n = 6,a = [6, 2, 9, 7, 4, 3]
输出：'2/3'

样例3：

输入：n = 4,a = [8, 5, 6, 3]
输出：'1/4'

题解：

        题目给定一个数组，其中小Q和小S都是按最优解的路走的，所以当小Q每一步如果有获胜的可能性，则直接判定为小Q胜。

        题目的意思简单来说就是选定一个数，两个人轮流在数的左边任意位置挑选比这个数小的数，直到一个人选不了为止。所以使用一个sum来计数，从小Q开始的话，当sum为奇数时则小Q会获胜。

        不能直接使用贪心，因为可能会漏掉情况，所以采用BFS遍历所有情况，在每一次选择好初始的数后，将左边所有小于这个数的全部push进队列。当这些情况中出现了小Q获胜的情况，及判定小Q获胜，ans++。

        最后的通分和转字符串就不再赘述。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long int ll;

int bfs(int i,int sum,vector<int> a){
    int j;
    queue<int> q;
    for(j=i-1;j>=0;j--){
        if(a[j]<a[i]){
            q.push(j);
        }
    }
    while(!q.empty()){
        int t=q.front();
        q.pop();
        if(bfs(t,sum+1,a)==1){
            //ans=1;
            return 1;
        }
    }
    if(sum%2!=0){
        return 1;
    }
    else{
        return 0;
    }
}

string solution(int n, vector<int> a) {
    // write code here
    int i,j,t=0,sum=0,ans=0;
    for(i=0;i<n;i++){
        ans+=bfs(i,0,a);
    }
    //cout << ans << "\n";
    for(i=2;i<=n;i++){
        if(ans%i==0 && n%i==0){
            ans/=i;n/=i;
        }
    }
    string print="";
    print+=to_string(ans);
    print+="/";
    print+=to_string(n);
    //cout << print << "\n";
    return print;
}

int main() {
    cout << (solution(5, {3, 1, 5, 4, 3}) == "3/5") << endl;
    cout << (solution(6, {6, 2, 9, 7, 4, 3}) == "2/3") << endl;
    cout << (solution(4, {8, 5, 6, 3}) == "1/4") << endl;
    return 0;
}