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下面的第一个点,直接逼死。)

Submission #109888377 - Codeforces
Codeforces. Programming competitions and contests, programming community