hnczy

摘要： 其实容易想到 KMP 自动机，但是对其的理解过于浅薄。 先明确 KMP 的 fail 的意义，即为这个前缀的 border 而 KMP 自动机处理的则是 \(s[1\sim i]\) 加一个字符 \(j\) 的 border 而建立完自动机，转移为 \(f_{i+1,len} =max{f_{i,j 阅读全文

摘要： 似乎没有块门。 这题分块也是可以做的，时间复杂度 \(O(n\sqrt n)\) 是大手子 @ 在场上想出来的，非常浅显易懂也好码。 首先对修改分块，每一次修改到块的最右边的时候，对块进行构造。具体的说，将块内修改的 \(l\) 和 \(r+1\) 离散化并且记录 \(1\sim n\) 每一个点的 阅读全文

摘要： 算法一 枚举所有区间，用 bitset 维护可以做到 \(O(\frac{n^3}{w})\) ,实际上 \(O(n^3)\) 可过，然而我并没有写这个算法，因为算法二更好写，而且时间复杂度可以过。 预计得分:20pts. 实际得分:20pts. 算法二 离散化之后枚举原来的值和更改后的值，将所有这 阅读全文

摘要： 算法一 状压 DP，naive 的，不写。 预计得分:20pts. 实际得分:20pts. 算法二 比较简单的 DP 想法，其实也是比较好想的，场上细节没写好。 显然有一个 \(dp_{i,j,k}\) 表示 \(i\) 个节点，第一个树中 \(j\) 个节点预计是非叶子，但是目前还是叶子，第二个树 阅读全文

摘要： 你的感受，就是你大脑的“运行日志” ——一份关于意识感受的长篇探索 [目录] 引言：一个奇怪的bug 第一章：你是一台压缩机器 1.1 记住的不是原物，而是特征指纹 1.2 为什么代码审查AI没有“熟悉感” 1.3 解压：把浓缩胶囊泡开 1.4 预测加工：大脑是一个“猜谜机” 1.5 记住：大脑绝大 阅读全文

摘要： WQS 二分 有一类问题，是从 \(n\) 个物品中恰好选择 \(k\) 个，而且如果没有恰好 \(k\) 个的限制的话，那就变得比较简单的题目。如果只有这样的限制的话，可以贪心来写。但是一般收益不是固定的，一般可以使用 WQS 二分来写。 举一个例子： 在分布在一条直线上的 \(n\) 个村庄中选 阅读全文

摘要： 二进制分组学习笔记 二进制分组，一种将较在线的东西，加一个 \(\log n\) 变成在线的技术。 具体来讲，就是你将元素的个数用二进制表示，比如 \(23 = 2^4 + 2^2 + 2^1 + 2^0\) ，那就有 4 个容器，分别放 16个元素，4个元素，2个元素，1个元素。每一次增加，就往后 阅读全文

摘要： 定义 网络：一种特殊的有向图 （\(G=(V,E)\)），在一般的图中多了源点（s），汇点（t）和每一条边都有容量，指的是这条边能流过的最大的流量。 流量：\(f(x,y)\) 表示这条边已经流过了多少，\(f(x)\) 表示这个点往外流了多少，有 \(f(x)= \sum_{i} f(i,u) - 阅读全文

摘要： 浅谈 FFT 单位根 定义：单位根 \(w_n^k\) 表示将单位圆 \(n\) 等分，在第 \(k\) 个复数的值。 显然的 \(w_{n}^0 = w_n^n=1\) 而 \(w_n^{k}\) 也可以理解为 \(x^n=1\) 的解集。 对于 \(w_n^k\) 。因为 \(e^{2k\pi 阅读全文

摘要： 考虑一个基于比较的排序算法，观察数据范围发现大概是 \(O(n\log n)\) 级别的。 可能是归并排序或者快速排序。 这里使用归并排序，发现一边归并排序之后，最终的序列肯定是多个递减的序列组成，直接 reverse 一下即可。 阅读全文