2023.8.25 LGJ Round
A
Alice 和 Bob 玩一个游戏，Alice 先手。
有一个长度为偶数的字符串，每次取出该字符串最前或最后的字符并删掉，并把该字符加入自己的字符串末尾。
双方都采取最优策略，问谁的字符串字典序更小，或相同。
区间 dp.
\(dp_{i,j}\) 表示 \([i,j]\) 这个区间先手必胜/必败/平局。
初始 \(dp_{i,i+1}=[s_i=s_{i+1}]\).
枚举先手取哪个，后手取哪个即可。
转移 \(dp_{i,j}\leftarrow dp_{i,j-2}\).
\(dp_{i,j}\leftarrow dp_{i+1,j-1}\).
\(dp_{i,j}\leftarrow dp_{i+2,j}\).
最后 \(dp_{1,n}\).
B
一张地图上 \((n,m\le 10^4)\)，经过一条无向边需要花费一些时间。
有两个内鬼，给定初始位置，内鬼需要抓到所有共 \(k(k\le 8)\) 个目标。
有若干情报，每条情报揭露了 \(p,x,t\)，代表第 \(p\) 个目标在 \(t\) 时刻出现在 \(x\).
若内鬼在 \(t\) 时刻恰好在 \(x\)，那么就可以抓捕目标，这也是仅有的抓捕方式。
求抓到所有目标的最小时间。
首先枚举两个内鬼分别抓哪些人。
分层图，设 \(f_{u,S}\) 表示当前在 \(u\)，抓捕了 \(S\) 集合的所有人，需要多少时间。
转移即可。
C
有一个序列，\(a_i\le m\)，\(n,m\le 10^5\).
对于 \(i=1\sim m\)，问最短的区间，使得 \([1,i]\) 都出现了。
处理类似 \(\text{mex}\) 的一类题目，套路是从小到大顺序加入 \(1\sim m\).
我们加入的时候，顺便处理一个数组 \(f_{i,L}\) 表示：
当前加到 \(i\)，左端点为 \(L\) 的区间满足出现 \([1,i]\) 的最小右端点。
对于加入的 \(i\)，设其出现位置是 \(p_1,p_2...p_k\).
对于在 \([p_{j}+1,p_{j+1}]\) 这里的所有 \(L\)，\(f_{i,L}\leftarrow\max(f_{i-1,L},p_{j+1})\)
我们还发现 \(f_{i-1,L}\) 是单调的，我们只需二分出 \(f_{i-1,j}\le p_{j+1}\) 的区间将其全部赋值成 \(p_{j+1}\) 即可。
对于 \(i\) 的答案就是求最小的 \(f_{i,L}-L+1\).
用线段树，实现区间查询第一个大于某数的位置（线段树上二分），区间赋值，区间求 \(\min\).
D
要求支持区间向区间建边，边权是 \(a\times 2^b\) 类型。求最短路。
强行拼题。
关于 \(a\times 2^b\)，是 CF464E The Classic Problem
大概是线段树维护高精加，再把线段树可持久化一下。
关于两棵线段树大小，线段树上二分 Hash 值找出第一位不一样的即可。
区间向区间建边，正常做法是线段树优化建图，（然而这题好像不是）。