补题记录B. Let's Go Hiking

概述补题记录：B.Let'sGoHiking题意：有两个人对由一个排列组成的数组玩游戏，A先选一个位置x，B后选一个位置y。然后A只能往小的数字走，B只能往大的数字走。并且A和B不能走到一起，不能走超出边界。A先手，问A必胜的策略数。方法：思维首先我们先确定一下A一定会放哪个地方首先排除边界，因为

补题记录：

B. Let's Go Hiking
题意：有两个人对由一个排列组成的数组玩游戏，A先选一个位置x，B后选一个位置y。然后A只能往小的数字走，B只能往大的数字走。并且A和B不能走到一起，不能走超出边界。A先手，问A必胜的策略数。
方法：思维
首先我们先确定一下A一定会放哪个地方
首先排除边界，因为假如A放在1或者n这些地方的时候，我们可以放在2或者n - 1来堵
如果不放在边界，假设A放的地方为x，并且数组p中\(p_x < p_{x + 1}\)，那么B可以放在x - 1处来堵，反之
所以我们得出，A一定会放在x位置，其中x满足\(p_{x - 1} < p_x < p_{x + 1}\)
那么接下来我们记录\(l\)为最长的单调序列的长度，\(c\)为最长单调序列长度的个数
我们很容易得出，当\(c \neq 2\)的时候，A必败
假如\(c > 2\)，当A选择了一个峰占领的时候，我们可以找到另外一条长度为\(l\)的单调序列的底部来爬，最终B是必胜的
假如\(c = 1\)，根据我们之前的分析，堵它隔壁就行
那么当\(c = 2\)的时候，当且仅当形式为\(p_{x - l + 1} < p_{x - l + 2} < ... < p_x < ... < p_{x + l - 2} < p_{x + l - 1}\)A才可能必胜，证明其他形式必败类似于证明\(c > 2\)时候的情景，这里省略
对于我们刚刚得出的序列，我们给出以下方案
当\(l\mod 2 = 0\)时，B必胜，因为B只要放在最下面即可
当\(l\mod2 = 1\)时，A必胜，因为当B放在最下面的时候，我们和B走同一条路，是必胜的；当B不放在最下面的时候，我们就不和B走同一条路，于是B的单调路线没我们的长，所以A必胜。
所以求出\(l, c\)验证即可

#include <bits/stdc++.h>using namespace std;typedef long long LL;typedef pair<int, int> PII;typedef pair<LL,LL> PLL;const int INF = 0x3f3f3f3f, N = 1e5 + 10;inline int lc(int u) {return u << 1;}inline int rc(int u) {return u << 1 | 1;}inline int lowbit(int x) {return x & (-x);}int a[N], st[N];//st[i]表示以i为结尾的最长的单调序列长度为多少inline voID solve() {    int n; cin >> n;    for (int i = 1; i <= n; i ++ ) cin >> a[i];    int ml = 0, c = 0, len = 0;    bool is_up = true, is_down = false;    for (int i = 1; i <= n; i ++ ) {//求出最长的长度        if (a[i] > a[i - 1]) {            if (is_up) len ++ ;            else {                is_up = true;                is_down = false;                ml = max(ml, len);                len = 2;            }        } else {            if (is_down) len ++ ;            else {                is_down = true;                is_up = false;                ml = max(ml, len);                len = 2;            }        }        st[i] = len;    }    ml = max(ml, len);    if (ml & 1) {        vector<int> v;//存最长单调序列的下标        for (int i = 1; i <= n; i ++ ) {            if (ml != st[i]) continue;            v.push_back(i);            c ++ ;        }        if (c != 2) cout << 0 << endl;        else {            if (a[v[0]] > a[v[0] - 1] && a[v[1]] < a[v[1] - 1]) cout << 1 << endl;            else cout << 0 << endl;        }    } else cout << 0 << endl;}int main() {    ios::sync_with_stdio(false), cin.tIE(nullptr);//    int t; cin >> t;//    while (t -- )        solve();    return 0;}

总结

以上是内存溢出为你收集整理的补题记录B. Let's Go Hiking全部内容，希望文章能够帮你解决补题记录B. Let's Go Hiking所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。