曹轩鸣的博客

前言 前排提示：由于作者水平很菜，所以本篇文章不会讲最优性证明、复杂度证明。如有需要请自行搜索 前排提示2；本文巨无敌长，阅读并完全理解可能需要 1∼21\sim 21∼2 小时。但对于 SAM 这种恐怖算法来说，222 小时其实并不多（毕竟我当初断断续续学了两天才理解）。 前排提示3：可能有点啰嗦，但在能忍受的情况下建议看完，会加深理解。 本篇文章的例子和插图全部来自 pecco 大佬的博客，作者也是通过那篇文章学会的 SAM。但那篇文章的思维跳跃比较快，有些理解写的也不是很完整（大佬博客通病），这篇文章可以看作那篇文章的详细版、简单版。 SAM 是干什么的 SAM，后缀自动机，顾

ARC154D. A + B > C ? 题目传送门 题意：**交互题。**有一个长度 200020002000 以内的排列 ppp，你每次可以询问 i,j,ki,j,ki,j,k，交互库 pi+pj>pkp_i+p_j>p_kpi​+pj​>pk​，返回 Yes/No。在 250002500025000 次询问内得出排列。 可以想到，如果能询问 pi>pjp_i>p_jpi​>pj​ 是否成立，就可以直接通过 nlog⁡nn\log nnlogn 次询问将下标排序，从而还原排列 ppp。由于排列的数互不相同，所以这是能够做到的：加入找到了 px=1p_x=1px​=1 的 xxx，那么询

题目传送门 题意：有 3n3n3n 张卡片，每张有一个 1∼n1\sim n1∼n 的数字。每次可以将最左边的 555 张卡片任意排列，删掉前 333 张，如果这三张数字相等则得一分；最后剩下的三张如果相等也的一分。求最大总得分。 模拟一下这个过程可以发现，相当于你有两张“手牌”，每次新加入三张，你从五张中扔掉三张，还是剩下两张。于是可以考虑一个 DP 状态：f[i][x][y]f[i][x][y]f[i][x][y] 表示进行 iii 次操作，操作后手上剩下的牌为 x,yx,yx,y 的最大得分。转移也不难，枚举下一次新加进来三张后如何选即可。时空复杂度 O(n3)O(n^3)O(n3)

比赛传送门 A. Parallel Projection 题意：有一个 w×d×hw\times d\times hw×d×h 的长方体，顶面和底面有两个点，只能走直线且不能穿过长方体，求最短距离。 显然曼哈顿距离必须要走。多出来绕弯的距离一定是选一个点，到边缘的最短距离 ×2\times 2×2。 By cxm1024 1 2 3 4 5 6 7 8 9 10 11 12 #include using namespace std; signed main() { int t; cin>>t; while(t-->0) {

阅读全文 »

比赛传送门 C. Interesting Sequence 题意：给你 n,xn,xn,x，求最小的 m≥nm\ge nm≥n，使 n&(n+1)&(n+2)&⋯&m=xn\&(n+1)\&(n+2)\&\cdots\&m=xn&(n+1)&(n+2)&⋯&m=x，或判断无解。 首先每一位独立，分别考虑。与运算每一位都越来越小，所以 xxx 的每一位都不能大于 nnn，否则直接无解。于是一位的情况只剩 n0x0,n1x0,n1x1 这三种情况。对于第一种 n0x0 的情况，任意 mmm 都合法，因为 nnn 这一位不会从 000 变成 111。对于第二种情况，要求选的 mmm 足够大，使

比赛传送门 C. Cash Register 题意：给你一个数字串（没有前导零），每次可以敲一个 0∼90\sim 90∼9 的数字以输入，或敲一次 00 键以输入两个 000。问输入这个数字串的最少步骤。 显然遇到两个 000 合并即可。 By SSRS 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include using namespace std; int main(){ string S; cin >> S; int N = S.size(); int ans = N; for (int

阅读全文 »

题目传送门 题意：有 1∼3n1\sim 3n1∼3n 的正整数，不重不漏地划分到 nnn 个栈内，每个栈有 333 个元素。每次从所有栈顶中选择最小的元素取出，直至取完，每次取的元素生成了一个 1∼3n1\sim 3n1∼3n 的排列，求该排列的方案数。 考虑排列应该长什么样。从左往右考虑不好考虑，因为没法确定一开始选什么元素，所以可以从右往左考虑。注意到，最大的元素 3n3n3n 一定只会在没有别的栈顶可选的时候才会选，此时只剩一个栈，栈顶为 3n3n3n。选完 3n3n3n 后，栈中剩下的 0∼20\sim 20∼2 个元素一定都会依次选完。所以，元素 3n3n3n 和剩下的 0∼2

题目传送门 题意：有一个 A×BA\times BA×B 的矩阵，所有格子全为白色。每次可以选择往右添加一列或网上添加一行白格子，并选择添加的其中一个格子染成黑色，问变成 C×DC\times DC×D 的矩阵时图案的方案数。 做法一 By betrue12 B - 扩展 首先考虑以下 DP dp[i][j]=dp[i][j]=dp[i][j]= 通过本问题的操作，可以操作到有垂直 iii 行和水平 jjj 列的板数。 看起来，这个 DP 中的 "在上面加一排，把其中一排涂成黑色 "的转移和 "在右边加一列，把其中一列涂成黑色 "的转移已经足够了，但重要的是最后的板数，所以必须注

题目传送门 题意：有一个 n×mn\times mn×m 的矩阵，每个格子有一个权值。每次操作会选择一个 x×yx\times yx×y 的矩形区域，花费为“每个位置的权值减去最小权值”之和，区域之间不能重叠。每次会选择花费最小的区间，如果有重复，则优先选上面的，再优先选左边的。输出每次的区域和花费。 显然选区域不会影响其他区域的花费，只会影响其他区域是否可选。思考可以发现，选择一个左上角为 (a,b)(a,b)(a,b) 的区域，会导致左上角在 (a−x+1∼a+x−1,b−y+1∼b+y−1)(a-x+1\sim a+x-1,b-y+1\sim b+y-1)(a−x+1∼a+x−1,b

比赛传送门 A. Average distance 题意：有一棵 nnn 节点的带边权树，求不同点对的平均距离。 平均距离即为总距离除以数量，所以考虑总距离。显然可以树形 DP，让点对的贡献在 LCA 处统计。维护 f[u]f[u]f[u] 表示以 uuu 为根的子树内所有节点到 uuu 的距离之和，sz[u]sz[u]sz[u] 表示子树大小，转移显然。统计答案时，对于每个儿子 u→v(w)u\to v(w)u→v(w)，考虑从 vvv 内的每个节点往其他子树的贡献都需要先到 uuu，而往其他子树贡献的次数为 sz[u]−sz[v]sz[u]-sz[v]sz[u]−sz[v]，所以每个