P3041 [USACO12JAN]视频游戏的连击Video Game Combos 可以想到，用 dp(i,j)dp(i,j)dp(i,j) 代表输入字符串长度为 iii ，匹配到节点 jjj 时可以达到的最大分数。 我们有 dp(i,ch(j,k))=min⁡{dp(i−1,j)}dp(i,ch(j,k))=\min\lbrace dp(i-1,j)\rbracedp(i,ch(j,k)...

首先，观察到 n≤12n \le 12n≤12 ，可以想到状压，我们用 f(u,sta)f(u,sta)f(u,sta) 表示可不可能走到 AC 自动机上节点 iii ，并且状态为 stastasta 的字符串已经是现在串的字串。并且，通过 BFS ，我们可以保证串的长度最短。 关键在于如何找出方案，我们记录 pre(u,sta)pre(u,sta)pre(u,sta) 二元组，代表 f(u...

这题其实就是点分治的一个扩展。

这题真的很套路，很没意思。 考虑换根dp，然后就是爆拆式子： （AAA为除去uuu之后的uuu子树，BBB为除去vvv之后的vvv子树） 以uuu为根： ∑i∈Adis(i,u)2c[i]+w2c[v]+∑i∈Bdis(i,u)2c[i]\sum _{i\in A}dis(i,u)^2 c[i]+w^2c[v]+\sum _{i\in B}dis(i,u)^2c[i]∑i∈A​dis(i...

创建一个哈夫曼树，不同的是一个节点可以有kkk个子节点，并且根节点没有任何编码。 考虑我们构造编码的过程，每次可以选择kkk个子树，将它们合并为一个大的树，并且给子树们的根节点编号钦定为0,1,...k−10,1,...k-10,1,...k−1，此时每个子树深度增加111，这棵树的深度变为max⁡(maxdep(subtreei))+1\max(maxdep(subtree_i))+1m...

P1600 天天爱跑步 这道题细节多比较烦人。 对于一个观察员uuu，考虑哪些跑步者可以对他被他观察到。 性质1 （搞笑情况） $s \in subtree(u) \ t \notin subtree(u) \to 从从从s$出发，在上行路线上被观察到 $t \in subtree(u) \ s \notin subtree(u) \to 在在在t$结束，在下行路线上被观察到 ...

假设我们设答案坐标(x1,x2,⋯ ,xn)(x_1,x_2, \cdots ,x_n)(x1​,x2​,⋯,xn​)，对于两个点(a1,a2,⋯ ,an),(b1,b2,⋯ ,bn)(a_1,a_2, \cdots ,a_n),(b_1,b_2, \cdots ,b_n)(a1​,a2​,⋯,an​),(b1​,b2​,⋯,bn​)显然有(a1−x1)2+(a2−x2)2+⋯(an−xn)...

ProProPro 定义一个串AAA是QQQ的周期，仅当AAA是QQQ的properproperproper前缀（即A!=QA!=QA!=Q的意思），而且QQQ是AAAAAA的前缀（没有properproperproper的限制）。比如说abababababab和ababababababababab是abababaabababaabababa的周期。 给你一个字符串，求出它所有前缀的最大周...

补很久以前的坑 图片来自lxl课件 显然，将每栋楼房都求一个斜率，然后发现一个楼房能被看到可以等价于它的斜率比之前的任何一个都大。 于是我们要求∑i=1n[a[j]≤a[i] for j∈[1,i−1]]\sum _{i=1}^n [a[j] \le a[i] \ for \ j \in [1,i-1]]∑i=1n​[a[j]≤a[i] for j∈[1,i−1]]。 这个怎么求？ 考虑...

传送门 我们有一个搞笑的做法： dp[i][sta]dp[i][sta]dp[i][sta]，其中stastasta表示后MMM为stastasta的方案数，然后转移也非常简单，每次转移完更新stastasta为[\frac{sta}{10}] \t\dfrac10+a[i]即可。 显然这样会炸。 考虑如何压缩后一维的状态。 还是考虑InsertInsertInsert函数，对于一个给定的j...