Codeforces Round #706 Let's Go Hiking 博弈

题意

_{此题意有对原题意添油加醋，以便理解。如产生反效果，请自己读题。}

p是一个数组表示山的高度。qingshan总是走下坡路，Daniel总是走上坡路。两个人每次都只能往左或往右走一格，且同一时间两人不能在同一个格子上。

qingshan先选起点，Daniel后选起点。两个人按回合轮流走，qingshan先手。先走到不能走的人算输。

假设双方都是最优策略，问qingshan有多少种起点选择可以让他必胜。

题解

感觉就是水题。只是要考虑严密。勉强能归到博弈里面。

首先做出以下定义：

1. 山峰，山谷。山峰是指，往左往右都是单调递减的，山谷是指往左往右都是单增的。
2. 对称山峰，对称山谷。就是往左往右单增或单减的长度是一样的。
3. 对称山峰的长度。就是单增/单减的长度。
4. 斜坡与斜坡的长度。斜坡就是一条单增或单减的路。斜坡长度就是单调的长度。显然，山峰的两侧是两个斜坡。

结论：
假设所有斜坡的长度的最大值为max。
再有且仅有两个斜坡的长度为max，而且这两个斜坡构成了一个山峰的时候。这个山峰的山顶时唯一的必胜解。（显然此时这个山峰是对称山峰）

场景：

1. 假设qingshan选择的不是最长斜坡，那Dainel选择一条最长斜坡就完事了。
2. 假如有多于两条的最长斜坡，或者两条最长斜坡不是在同一个山峰，或者甚至又多个对称最长山峰。那么Daniel只需要选择和qingshan不同的斜坡就行了。因此这个情况输出0就完事。
3. 假如是最长的山谷。那么Daniel只需要从谷底出发，选择和qingshan不同的方向就可以了。因此这种情况也是输出0就完事。
4. 如果不是对称最长山峰，但山峰的一边为最长斜坡。那么Daniel只需要在最长斜坡一侧选择一个距离山顶为偶数，且距离长于或等于另一次斜坡的长度就行了。显然这样的点一定存在。输出0就完事。
5. 如果是对称最长山峰，但是山峰的长度是偶数。因为qingshan只能选择Dainel那一边（否则会被耗死），而两人又不能同时在一个格子上。因此也是必败。输出0就完事。
6. 当且仅当是对称最长山峰，且长度为奇数。面对面走，正好获胜。此时输出1。

代码

唉。没有考虑到#4种情况。天真的以为Dainel永远都会从山地出发和他硬刚。结果就挂了。（其实对于一直单增的情况，Dainel只需要选择qingshan下面的第一个点，直接逼死。）