问题描述
小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 hereint 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;
}
