2023 hdu 多校第一场

A - Hide-And-Seek Game

题意：有两个人在一棵树上游走，每个人的速度均为 $1$ 条边每秒，每个人都在两个固定的点之间循环，求两个人相遇的位置（两个人只能在点上相遇，不能在边上相遇）

对于一个人而言，其到一个点的所有时间点可以被分成两个等差数列，考虑对每个人求出在每个点对应的等差数列，则两个人在一个点相遇可以等价为四个等差数列任选两个相等得到的最小的 $t$ 是所有点中最小的一个。等差数列相等可以转化为 ax-by=c 的形式，用 exgcd 求解即可得到最小的非负整数解，所有可能性取 min 即可，复杂度 $O(mn\log n)$，可以通过

B - City Upgrading

题意：给出一棵树，求树点集的一个子集，要求每个点相邻的点中至少有一个点在该子集中（包括其自身），并且子集内点的点权和最小，求该点权和

典型的树形 dp，定义 $dp_{i,0/1,0/1}$ 表示考虑第 $i$ 个点及其子树中的所有点，要求该点必选/非必选，该点的直接子节点是/否有点被选，转移即可，复杂度 $O(n)$

C - Mr. Liang play Card Game

题意：给出一排数，每次可以合并两个相邻的 level $k$ 的数得到一个 level $k+1$ 的相同的数，或者可以去掉一个数得到 $P^{k-1}V_i$ 的收入，其中 $k$ 为数的 level，$i$ 为数的大小，求最终能够得到的最大收入

考虑 dp，定义 $dp_{l,r,x,y}$ 求最后区间 $[l,r]$ 剩下一张 level $x$ 的数 $y$ 时的最大收入，枚举分界点转移即可，复杂度 $O(n^3mR)$（$m$ 为值域的范围，$R$ 为 level 的范围）

可惜的是考场上我想出来这种方法了，但是被 $R$ 的大数据范围骗了导致放弃了这种方法，实际上 $R$ 的范围只有 $\log n$，所以真正的复杂度应该是 $O(n^3m\log n)$，可以通过

D - Amazing spacecraft

E - Cyclically Isomorphic

题意：给出 $n$ 个字符串，每次给出一对 $x,y$，询问第 $x$ 个字符串和第 $y$ 个字符串是否循环相等

看到循环相等可以想到最小表示法，然后就是板子了，复杂度 $O(\sum\limits_{i=1}^n len_i)$

F - Escape The Maze

题意：有一个带边权的树，每次在树上一个路径行动的代价为 $(s-L)^2$，$s$ 为路径的长度，$L$ 是一个常数，给定起点，求到任意一个叶子的最小代价

首先有一个很简单的 dp：$dp_u=\sum\limits_{u \in subtree(v)} dp_v+(dep_u-dep_v-L)^2$，其中 $dep$ 为加权深度。将二次项展开后就是一个很板子的斜率优化 dp 了，由于 $x$ 不单调所以要用李超树（线段树维护凸包），再加上是树上 dp 所以需要可持久化李超树，最后可能还需要卡卡常，复杂度 $O(n\log n)$

另外今天知道了一件事，原来在代码里的 O2 优化是 G++ 才能用的，找个小本本记下来。。。

G - Travel

H - Umamusume

题意：有一个游戏，分成 $n$ 轮进行，每轮有三种选择： 1. TP += 50 2. TP -= 50 $\sf\ and\ $ sp += 15 3. TP -= 50 $\sf\ and\ $ money+=100G

其中 money 可以用来在商店买物品，商店中物品的列表如下： | item name | price | function | | -----------: | -----------: | -----------: | |TP Medicine(L)| 100G | add 100 TP | |TP Medicine(M)| 50G | add 50 TP | |TP Medicine(S)| 25G | add 25 TP | |Magic Book(L) | 100G | add 15 speed points| |Magic Book(M) | 50G | add 7 speed points | |Magic Book(S) | 25G | add 3 speed points | | Horn | 100G | next training speed points will become 2x | | Weight | 200G | next training speed points will spend 100 TP but become 3x |

其中每个商品都有 $p$ 的概率在 $6$ 轮中出现一次，购买可以发生在任意时刻，与上述选择不冲突，要求在 $n$ 轮内达到最大的 sp，求在采取最优策略的情况下，最后得到 sp 的期望值

首先主要概率的来源在于那些商品，所以首先可以先研究一下这些物品的效果。很容易发现其实所有的商品都是没有用的（因为与其用 TP 换钱再增加 sp，还不如直接增加 sp，这样增加的 sp 更多），这样最佳的选择就变成了 TP += 50 和 TP -= 50, sp += 15 的循环

偶数只要按照上述策略即可得到最大的 sp，所以偶数轮的结果是确定的，而奇数轮采用上述策略则会剩下一轮没事干，我们可以通过在最开始先进行一次 TP -= 50, money += 100G 并且在之后购买一个 TP Medicine(M) 或两个 TP Medicine(S) 在保持 TP 不变的前提下获得额外的 50G 的初始资金，于是就可以以此购买 Magic Book(M) 和 Magic Book(S) 得到额外的 sp，可能的额外 sp 一共是 0/3/6/7 这四种情况，分类讨论即可，复杂度 $O(T\log n)$

注意还有一些细节：商店是每六轮刷新一次的（因为这个挂了一次。。。）

I - Assertion

题意：给出 $T$ 个断言，每个形如“如果将 $m$ 个物品分成 $n$ 组，每组至少有 $d$ 个物品”，判断其是否正确

一眼鸽巢原理，直接过，复杂度 $O(T)$

J - Easy problem I

题意：维护一个数据结构，支持区间设为 $a_i=|a_i-x|$ 和区间和，满族特殊条件：修改的 $x$ 是递增的

~~论考场上想出正解，结果在写代码的时候自己把自己绕偏后的感受。。。~~ 虽然这么说，但本质上还是忘了只要是双参数的转换方程就得按 kx+b 的形式维护了的过

解法不多说，看到绝对值立刻想到分类讨论，然后用线段树维护，根据特殊性质很容易发现变成 $a_i=x-a_i$ 的 $i$ 不会在后面变回去，于是可以直接暴力转移即可，单次操作均摊复杂度 $O(\log n)$，总复杂度 $O(m\log n+n\log n)$，可以通过

K - Easy problem II

题意：维护一个数据结构，支持区间修改为 $a_i=\begin{cases}x-a_i&,a_i<x\x+a_i&,a_i \geq x\end{cases}$ 和区间求和

~~emmm... 调了一天，最后发现居然是我的 Splay 写挂了~~ 思路其实很简单，很容易发现操作前后不改变操作区间内数的大小关系，所以可以考虑划分区间，每个区间用一个平衡树维护，分段求解。区间的分割方法一般有线段树/分块，这里因为里面还有一层平衡树，所以分块即可，复杂度 $O(n\sqrt n\log\sqrt n)$。但其实分块之后会发现只有整块的单词操作复杂度是 $O(\log n)$，其余均为 $O(1)$，所以可以进一步优化为 $O(n\sqrt{n\log n})$，但由于查询都是 $O(1)$ 的所以复杂度本质上没有那么大，调调块大小一般就过了 P.S. 在 hdu 改题的一些经验： - 不知道为啥 hdu 的快读、scanf 都很慢，一般遇到 TLE 建议先加上神读试试 - hdu 输出在 stderr 的结果也会输出到答案文件里，所以调试注意要删全

L - Play on Tree

结论题，子树的选取是博弈论的经典题型。当根确定时，SG 函数推导公式为 $SG_u=\bigoplus\limits_{v \in son(u)}(SG_v+1)$，要求概率就得求所有点做根时根的 SG 函数值，换根 dp 即可，复杂度 $O(n)$