Solutions of Union Training I - Searching and Strings

A. 双剑合并

题意

$N\le 10^6的数组A，和M\le 10^6的数组B，求max\{\ A_i \oplus B_j\ \}$

分析

$各选1个数的这种，当然是xor\ trie了，只要把A数组插入trie里，然后枚举B一个一个找，更新答案即可$

思考

$交题之前还是想想这个题需要多少空间，题目给了多少空间，也许出题人没注意呢$

B. 单词替换

题意

$|L|\le 5\times 10^6的字符串S，把所有的不重叠的A子串串替换成B字符串，A和B长度不会太大$

分析

$kmp从S中匹配A，同时存答案，当然标记最后一起输出也可以$

思考

$其实string::find和string::replace也跑的飞快的$

C. 01的时间

题意

$定义一类特殊的十进制数，只由01构成，不含前导0，求最小的能被n\le 466整除的这种数$

分析

$由于最终数可能很大，所以当然不能直接开到状态里直接bfs了，考虑一下利用余数$
$发现这也满足bfs的性质，f_{mod}：=到达余数为mod的最小步数，然后记录路径打印路径可以$

思考

$当然数据小，出题人有意发散思维，可以dfs构造打表，数不多$
$或者直接打表，以及各种xj8搜，当然dp也可以$

D. GooZy的游戏时间

题意

$题意是个奇怪的搜索，$

分析

$按照从左到右，从上到下，一个一个的去放就好辣$
$不过思考一下极限数组，5\times 5=25个矩形，24相同，1个不同$
$可以考虑相同的合并，为解答树剪枝，经典技巧辣$
$不过还是可以卡掉的，但是搜过去辣$

思考

$玄学搜真是好难$

E. RunningPhoton's Nightmare

题意

$N，M\le 600，N\times M的迷宫，身上有一个剩余时间是T\le 600的炸弹$
$要跑出迷宫，迷宫有C\le 150个炸弹刷新装置，求跑出的最短时间$

分析

$一开始想直接淦，发现状态是个玄学，150个R不能状压，如果直接暴力开状态搞的话$
$f[i][j]:=到(i,\ j)的最小步数，遇到R就刷新剩余时间，并标记剪枝$
$同时如果到某个地方剩余时间没变多显然也剪枝$
$蓝儿这个复杂度是玄学$
$之后发现可以把R拿出来，看作类似加油站的东西，包括起终点$
$只要bfs\ 600步求出每个R到其它R的距离，然后floyd求起终点距离这题就做完了$
$复杂度是完美的O(NMT+C^3)$

思考

$经典想法了，但是反映的有点慢$

F. 表达式

题意

$一开始是1，不断的自加或者自减，产生新数，以及和新数做这种操作$
$求产生n的最小步数$

分析

$解答树空间爆炸的题， 一般都是IDA*来剪枝$
$显然的估价就是如果最大的那个经过剩余步数都不行那就再见$
$发现每个数都是要选择的，先后无所谓，就可以利用cur优化了$
$然后飞快的就跑过去了$

思考

$cur优化的正确性总是每次让我感觉到搜索的玄学与可怕$

G. 神舟的宝藏

题意

$C题强化版，N\le 5000，进制有16进制$

分析

$做法是一样的，不赘述了$

思考

$题意还是要枚举一下的，0只有0是解，猜测出题人的意思这种能力也要有的$

H. DNA序列

题意

$N\le 8个DNA，每个长度不超过5个，求一个最短的串包含他们作为子序列$
$输出长度$

分析

$显然的话，可以暴力IDA*去搜这个长度，根据每个DNA匹配的长度来估价$
$如果最长的那个都不能的话，就再见$
$决策的时候就优先选择匹配更多的就搜过去了$
$其实是数据太水。果然搜索题我还是不行啊$

思考

$其实可以6进制压缩匹配位置，总状态数6^8\approx1\times 10^6$
$然后就算case数这么大，也能跑过去$
$高进制状态压缩要熟练啊$

I. 小冰和小娜

题意

$N，M\le 50，N\times M的迷宫，车轮状态有4个方向，以及颜色$
$每步可以选择前进、左转、右转，问从起始点出发到达终点，并且颜色相同么$
$输出最小步数$

分析

$f[x][y][dir][color]:=到(x,\ y)，方向是dir，颜色是color的最小步数$
$bfs一波就做完了$

思考

$简单多状态bfs$

J. TooEasy Or TooDifficult

题意

$给定N\le 10^5的字符串，定义每个字符的战斗力p_i为以i为中心的回文长度$
$MZ:=max\{p_i\}，JD：=定义的运算式子$
$SC_{ij}:=p_i\oplus p_{i+1}\oplus\cdots\oplus p_j，FJD=max\{ SC_{ij}\}$
$比较JD和FJD的大小$

分析

$MZ用Manacher解决，至于FJD可以用过把xor前缀和插入trie中解决$
$pre_i:=p_1\oplus p_{2}\oplus\cdots\oplus p_i，xor(i,\ j)=pre_j\oplus pre_{i-1}$

思考

$熟练技巧就好$

K. 奶牛合影

题意

$求一个字符串的循环最小表示$

分析

$可以直接上最小表示法$

思考

$可以倍增字符串后套sa，找到sa最小的且跨越2个字符串的即可$

L. 奶牛序列

题意

$给定N\le 5\times 10^5的字符串，T_i:=i字符开头的后缀$
$求\displaystyle\sum_{1\le i\le j\le n} len(T_i)+len(T_j)+2\times lcp(T_i,\ T_j)$

分析

$sa求出height之后，根据lcp引理，lcp(i,\ j)=min\{height_{i+1},\ height_{i+2},\ height_j\}$
$对于每个height的贡献，显然是左右比它大的能延伸的距离的积，根据乘法原理左右端点的选择嘛$
$对于前面的式子，O(n)算就可以了$
$预处理左右延伸的位置l_i,\ r_i，可以利用单调栈，不过由于重复height的原因$
$我们可以利用技巧就是一个是\ge 另一个是>就可以了$
$直观解释就是5\ 6\ 5\ 6\ 5，对于中间那个5，先算3个5，再算2个5的，再算1个5的$
$就不重不漏了，复杂度解释就，下次不要计算上次计算过的$

思考

$经典统计贡献的技巧呀$

M. 奶牛硬盘

题意

$水题不表$

分析

$其实与数字无关$

思考

$水题不表$

N. 奶牛情书

题意

$给定N\le 60个字符串S_i，|S_i|\le 100，字符集为大写字母$
$求至少包含1个S_i的长度为M\le 100的字符串的个数$

分析

$逆向思维，答案就是26^M-1个都不包含的串数$
$第二个可以利用ac自动机预处理N个S_i的失配指针$
$f[node][c]:=添加字符c，且当前走到第node个节点的不包含方法数$
$显然1个都不包含的串数=\sum f[sz][i]$

思考

$关键还要是要搞清楚fail指针的含义，失配后的lcp，这点与kmp的nxt数组是一样的$