Before
T1
像是一个$LCS(tring)$题
$N^2$ 可承受
T2
矩阵？$1500$……
T3
真·难
像是个数学+图论……
也许暴力建边是可行的……
During
T1
$30$ 分 是白送的 $k=0$
修改一次长度至少$+1$
如果可以贪心……尽量找两个可以拼在一起的……
试试叭，
枚举更改点并求一下最长长度。
总复杂度$N^3$
真·T1
没有任何对拍的想法……不知道除了暴力还有什么好打的……
=。=
试试对拍，然后发现暴力好难写$XoX$
$Give\, up\, and\, Give\, in$
T2
好像就是矩阵，每乘一次就是走了一步……
但是$N=1500$ 让我很闹
先想下：
如果把简单路径拆到每一个点上
一个点能以 $4$ 步到的点
那么每个点的贡献就会多（到别的点，被别的点到）
最后 $/2$ 就好了
一个很奇怪的问题：
作者只让大家求了走 $4$ 步不重的情况……
就 $4$ 步？
如果是毒瘤题应该又有输入
所以考虑简单容斥……（雾）
分析$ing$
走一步：
无非法
第二步：
有非法且与走一步的点数相同
第三步：
还有非法且多了一种：走回$1$号点
剩下的好像就和上面一样，是走原路了。
第四步：
$gugugu$
发现$N^3$ 已经死了
$1500^3=3375000000$
想先打个电风扇……$40\%$
注释：
电风扇：DFS
T3
可以打一颗$Trie$树=。=（话说上回的还没调出来）
试试？
前 $40\%$暴力建，$dij$
Tire树
全插入，然后查一下
好像不行……又不是亦或……
于是暴力
Result
|
23
|
Miemeng | 100
03:06:41
|
40
03:07:06
|
40
03:07:06
|
180
03:07:06
|
Day1要比这个拿得多啊……不然就跪了。