2023.11.14 信息学日志

1. CF1600E The Treasure of The Segments

题目描述

https://www.luogu.com.cn/problem/CF1600E

题目概况

来源：Codeforces

洛谷难度：$蓝题$

CF难度：$1900$

标签：递归 数学 博弈论

思路点拨

题面回忆：这道题的突破点在只能移动数组最右边或最左边的数，并保证新数列单调递增。
这种博弈论题目先模拟一下试一试。
不妨设 $a_1\le a_n$
对于先手来说第一步可以分为 $3$ 种情况

1. $a_1=a_n$ ，取哪个都一样，反正后手都输，结束
2. 取 $a_n$, 以后数列只能从最右边取了，因为 $a_1\le a_n$ ,最终计算出谁胜利需要 $\mathrm{O}(n)$ 的时间复杂度
3. 取$a_1$ ，问题转变为后手取 2 或 3 情况 ，时间复杂度仍在 $\mathrm{O}(n)$ 级别

对于单步来说。
若先手取。

• 1 情况成立 或 2 ，3 情况其一满足先手胜利，则先手胜。
• 否则先手败
  若后收取
• 1 情况成立 或 2，3 情况都满足先手失败，则先手败
• 否则先手胜利

时间复杂度： $\mathrm{O}(n)$

AC。

2. CF82C

题目描述

https://www.luogu.com.cn/problem/CF82C

题目概况

来源：Codeforces

洛谷难度：$绿题$

CF难度：$2000$

标签：图论 数 优先队列

思路点拨

• 首先原图是一棵树，所以每个军队到达原点的路径唯一
• 排队所消耗时长和树的高度成反比
• 每过一个时间让每个军队跳到父节点，将从一个节点出发的军队扔进相应的优先队列，取当前路径要求的代价的军队进阶至父节点
• 均摊时间复杂度：$\mathrm{O}(n^2\cdot log2(n))$
  AC。