Fanyi's Blog

未完待续…… upd: 虽然未完，但是不想续了。 听说现在全人类都会 FFT 了？ 这里做个小小结。 大概就是这样的一个东西： 系数：\(a_0, a_1, a_2,\cdots, a_{n-1}\)。 次数：如果最高位非 \(0\) 系数是 \(a_k\)，那就称 \(A(x)\) 的次数为 \(k\)。 多项式加法：若 \(A(x) = \sum_{i=0}^{n-1}a_ix^i, B(x) = \sum_{i=0}^{n-1}b_ix^i, C(x) = \sum_{i=0}^{n-1}c_ix^i\)，\(A(x) + B(x) = C(x)\)，那么 \(c_i=a_i+b_i\)。 多项式乘法：用乘法结合率算一下即可。如 \(A(x) =-10x+9,B(x) = 4x-5\)，则 离散卷积：我们常说“\(A(x)\) 与 \(B(x)\) 的卷积”其实可以简单理解为…

本想没做一道题写一篇题解。刚立下这个 flag 我就后悔了。于是就写一句话题解吧。事实证明旗子不能随便插啊。 如果有题目我专门开一篇文章我会加上链接。 以前做过的觉得有趣的题目也会一点点地加上来。 如果有 CE 的，可以试试 -std=c++11。 【CF3D】将每个问号变成左括号和有括号都有一个代价，求是最终串匹配的最小代价。用堆贪心，括号匹配问题。code 【CF6E】单调队列。code 【CF7D】字符串哈希。code 【CF7E】dp，大细节题。code 【CF9D】dp 题，询问 \(n\) 个点组成二叉树，高度大于等于 \(h\) 的有多少个。令 \(f[i][j]\) 表示 \(i\) 个节点高度小于等于 \(j\) 的二叉树有几个。code 【CF10D】经典的 dp 题。code 【CF13C】\(\mathcal{O}(n^2)\) dp 可过，但有…

原题链接 给出正整数 \(n\)，你要把 \(1\sim n\) 之间的正整数两两分组，使得每一组两个数的最大公约数大于 \(1\)。输出能分成最多个组，并按任意顺序输出每组的两个数。 官方题解说得很简单。就是枚举从大到小质因数 \(x\)（如果 \(2x\ge n\) 显然就不用管了），找出所有之前没有匹配过得 \(x\) 的倍数，如果是偶数个就两两匹配，否则把 \(2x\) 除去即可。 那为什么这样是对的呢？ 我们来看最后枚举到 \(x=2\) 的情况。如果有偶数个，那正好可以两两匹配，显然最优。如果是奇数个，那我们发现所有可能被匹配的数（即所有枚举到的数）有奇数个，即我们至少需要扔掉一个。现在我们只扔掉了一个（因为之前除去的 \(2x\) 都在此时被匹配了），所以这种情况是最优的。

原题链接 有一个长度为 \(n(n\le 10^5)\) 的序列 \(\{a\}(a_i\le 10^5)\)，你可以对它进行操作，操作如下：首先选择三个数 \(v, t, k\)，满足 \(a_v = a_{v+t} = a_{v + 2t} = \cdots = a_{v + kt}\)，然后将其删除，得到一个新的序列。每次操作结束后你都能将新数列重排。 现有 \(Q(Q\le 10^5)\) 个询问，每次询问 \([l, r]\) 表示问要把 \([l, r]\) 删除所需的最小步数。 （以上翻译改写自洛谷） 感觉像是 HH 的项链 的升级版。 不难发现答案就是 \([l, r]\) 不同数的个数 \(+\) 第一次在 \([l,r]\) 中是否有一种数被删掉。 记两个数组 \(fa[i]\) 与 \(ffa[i]\)，\(fa[i]\) 表示上一次第 \(i\) 个数出现在了那里，…

原题链接 有 \(n\) 个位置 \((1\sim n)\)，第 \(i\) 个位置上有 \(a_i\) 个箱子。有 \(m\) 个人，开始在 \(0\) 位置（即在 \(1\) 号位置左边），每一秒钟每个人都可以选择搬走自己位置上的一个箱子或向前走一步（即从位置 \(i\) 走到位置 \(i+1\)）。问最少需要多少时间才可以将箱子全部搬完。 输入第一行两个正整数 \(n, m(n, m\le 10^5)\)，第二行 \(n\) 个整数 \(a_i(0\le a_i\le 10^9)\)。 发现正着做比较麻烦，于是考虑二分答案。 如果需要验证的答案为 \(x\)，那我们就让每个人都有 \(x\) 秒。 我们考虑让人一个一个来，一个显然的贪心就是让每个人都拿尽量远的箱子。 然后大力模拟即可。

听说 zkw 线段树优化 dijkstra 跑得很快呢，洛谷最优解都是用这个的。 然后我就自己打了一发。 确实快了许多，但还是被最优解吊着打…… 但至少能过 bzoj3040。 把普通堆优 dij 的堆改成线段树就可以了。

一道有趣的矩乘题。 查看原题 PDF 显然元辅音可以分开来看，那我们就只看元音。 于是我们就可以很自然地推出 \(ans=\sum_{i=1}^n(i+1)p^i\)。由于有一个叫重音的东西，所以系数是 \(i+1\)。直接算会 T（70 分），于是我们就想到了矩阵快速幂。 首先我们当然想到是推 \(2\times 2\) 的，于是写出初始矩阵 \(\begin{bmatrix}0 & 2p \end{bmatrix}\)，要转移到 \(\begin{bmatrix}2p & 3p^2+2p\end{bmatrix}\)。发现矩阵的系数有变化，无法转移。于是我们就需要添加一格来辅助转移。观察两矩阵的系数变化，我们就不难推出辅助的那个应该填什么：…

原题链接 假设有 \(n\) 个数，每种每个数获取机率相同，而且每个数亦无限供应。若取 \(t\) 个，能集齐这 \(n\) 个数的概率是多少？ 我们考虑当你手上已有 \(i\) 种不同的数，从集合中任选一个数得到新数的概率，为 \(\frac{n-i+1}{n}\)，那期望即为 \(\frac{1}{p} = \frac{n}{n-i+1}\)。所以总期望为 \(\sum_{i = 1}^{n}\frac{n}{n-i+1} = \sum_{i=1}^{n}\frac{n}{i}\)。 当然也可以用概率 dp 来推： 我们设 \(f_i\) 表示取了 \(i\) 种数时还须取的数的期望。 显然 \(f_n = 0\)，答案为 \(f_0\)，所以为逆推。 又由于选第 \(i\) 个数后再选一个数与已经选过的数不同的概率为 \(\frac{n-i}{n}\)，相同为…

原题链接 \(0\sim m-1\) 的数被分成两个集合，你可以分别从两个集合中取一个数相加并对 \(m\) 取模，求 \(0\sim m-1\) 中不能构造出的数。 感觉如果sxd666来做这题肯定能一眼秒，然而他正忙着切其他题。 首先我们发现如果要让 \(a + b \equiv x \pmod m​\)，如果已知 \(a, x​\)，那 \(b​\) 一定是唯一的。也就是说，假设给定集合是 \(A​\)，与之对应的集合为 \(B​\)，如果有 \(a\in A​\) 但找不到 \(b\in A​\) 使得 \(a + b \equiv x\pmod m​\)。那么 \(x\in A + B​\)（定义 \(A + B = \{a + b : a\in A, b\in B\}​\)）。反过来讲，如果 \(x\notin A + B​\)，那么一定能把 \(A​\) 中所有元素配对（可能…

原题链接 给你一个有 \(n\) 个元素的数组 \(a\)，让你构造一个数组 \(b\)，满足从 \(a\)、\(b\) 中任选出 \(k\) 个下标对应的元素，它们的和不同，其中 \((0<k<n)\)，也就是说选择的子集不能是空集或全集。注意，数组中每个数都互不相同。 （来源：https://blog.csdn.net/zuzhiang/article/details/78575126） 害怕，乱搞了一发，然后就 A 掉了（我 -1 都没判啊）。 大概就是排序之后全部右移一位，然后把最大的数于最小的数配。 现在想想确实是这样啊。 这里给出证明： 假设排序后数组为 \(\{a_i\}\)，右移后数组为 \(\{b_i\}\)。如果集合不选 \(a_1, b_1\)，那么显然有 \(\sum a < \sum b\)。选 \(a_n, b_n\)？把 \(\{x_i\}\) 取个补集即可（…