wjyppm's Blog

被诈骗的一集。 话说你是打得好才记吗，下次打的不好更应该记录反思的好吧。 T1 CF1295D Same GCDs - 洛谷 暴力肯定是不行的，考虑如何对这个 xxx 计数，考虑算术唯一分解定理，对于 gcd⁡\gcdgcd 来说就是所有质数上指数取 min⁡\minmin，那么对 gcd⁡(a+x,m)=gcd⁡(a,m)\gcd(a+x,m)=\gcd(a,m)gcd(a+x,m)=gcd(a,m) 可以把 xxx 以质因数分解的形式看待的话，就是加上 xxx 之后取 min⁡\minmin 的值不变，可以分析出几个性质： xxx 不会添加新的质数，质数取集只在 a,ma,ma,m 之间。 xxx 不会改变 aaa 取到 min⁡\minmin 指数的质数贡献。 那么有 gcd⁡(x,m)=gcd⁡(a,m)\gcd(x,m)=\gcd(a,m)gcd(x,m)=gcd(a,m)，除掉 gcd⁡(a,m)\gcd(a,m)gcd(a,m)，gcd⁡(xgcd⁡(a,m),mgcd⁡(a,m))=1\gcd(\frac{x}{\gcd(a,m)},\frac{m}{\gc...

头脑风暴！ 注意到 xxx 对答案一点用都没有，因为我们求的是长度，光一个 ddd 就能够确定答案了。 发现最长严格上升子序列的性质不太好刻画，我们考虑这个添加数的操作过程能不能以一种形式来表现出来。注意到每一个数具体取值只和最后一个数的变化有关，而且变化是连续的，考虑给它拍到二维平面上，横轴按照每一次添加一个数划分时间，纵轴为最后一个值的具体取值，原操作在二维平面上表现的是斜率为 1 或 -1 的一堆直线，如下图，红点表示一次插入操作的： 最长严格上升子序列的性质就很好刻画了，因为根据图来看其实就是最低点和最高点的极差就是我们的长度（因为斜率为 ±1\pm 1±1）。让后我们考虑这个子序列个数怎么解决。发现直接 DP 求解答案十分困难，考虑发掘性质，首先不难发现一个性质：一个段不可能贡献超过一种答案，即一个点不可能成为最低点或最高点。 这个性质有什么用呢，也就是说，我们可以统计对段的答案进行贡献统计。然而注意到段数极小（数据范围 nnn），值域极大，有一个强烈的矩阵味道，但是我到现在连状态都没设计耶？ 最长严格上升子序列可能从任意值拼过来，考虑在状态中加上这一个，设 f(i,...

好题。 有一个显然的想法就就是二分图带权最大匹配，但是时间复杂度是 O(n3)O(n^3)O(n3) 及其难受，考虑 DP 但直接 DP 十分困难，考虑发掘一些性质。 利用贪心思想，先对 www 和 hhh 进行从小到大的排序，一个基本思想就是对应位置的相乘，用调整法不难证明这是最优决策，但是本题目中存在第 iii 个人不能骑自己的马，所以最优解可能不会取到。 考虑到这个限制只是限制自己不能骑自己的马，合理猜测 iii 位置匹配马的决策是一个范围，有结论：匹配范围为 [i−2,i+2][i-2,i+2][i−2,i+2]。证明考虑反证法，设 iii 的禁止匹配位置为 baniban_{i}bani​。那么反证法，假设如果在这个以外的范围选，那么最多向前会造成两次 (i,i−1)(i,i-1)(i,i−1) 无法匹配，自行画图发现这种情况最劣情况下也只会在 i−2i-2i−2 的情况形成匹配。 借用 _sys的图： 完美匹配至少有三个红线和黑线相交整法不难证明如果两条线相交那么交换这两个匹配会得到更优的解。 让后考虑交换的过程，我们如果前 iii 个人和前 iii 匹马匹配完全，...

形式化题面如下： 给定一棵有 nnn 个节点的无向树和一个整数 kkk，选出最多 kkk 条不分叉的路径（即简单链），使得这些路径覆盖的不同节点数尽可能多。输出最多能覆盖的节点数。 DP 显然不太好，考虑贪心，那么贪心尽量让链长。考虑直径一定作为答案的一部分出现，而剩下的就是直径上的分支，分支跨直径配对成路径。考虑这个如何配对，其实就是不同链的叶子两两配对，考虑以直径一端点为根，长链剖分加排序（链长大到小）取 2L−12L-12L−1 个叶子即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include<bits/stdc++.h>#define pir pair<int,int>using namespace std;constexpr int MN=1e6+1520;int n,L,rt,ftot,ans;pir...

0.前言 后缀自动机，在字符串算法中居于一种万能的地位，其本体代码编写较简单，优美的 O(n)O(n)O(n) 构建复杂度，是一类极其有用但难以真正理解的字符串后缀结构。笔者投入了大约一周的时间来学习，现在进行总结复习，看看能不能悟到一些新的东西。 同时后缀自动机本身的难度（10 级）决定了理解较难，笔者同时也是这样的感受。我在编写第一二三章节的时候会尽量用图来解释，尽量减少繁杂的符号化语言。必要的也不会省略。 后缀自动机在做习题的时候，需要有非常扎实的 DS 基础以及面向对象程序设计思想，不然在编写的时候就会炸掉（不然大纲为什么要有这个程序设计思想）。 一些基本约定： 本文章默认字符串下标从 111 开始。 我们用打字机字体表示字符串的内容，如：s=wjyppm1403s=\texttt{wjyppm1403}s=wjyppm1403。 拼接：s+ts+ts+t 表示将 ttt 拼接 sss 后。 字符集：即构成字符串中字符的集合。 空串：不含任何字符的字符串称为空串。 子串：在 sss 开头或末尾删去若干字符得到的字符串称作为 sss 的子串，sss 本身和空串也是 ss...

0. 前言 前置知识： 状压 DP。 1. 概念与介绍 SOSDP，翻译过来就叫做子集和 DP，又称作高维前缀和，用来解决一些涉及子集和计算的问题。 我们通过一道例题来进行引入： 给你一个含 2n2^n2n 的集合 SSS，对于所有的 i∈[0,2n−1]i\in [0,2^n-1]i∈[0,2n−1]，求解 ∑j⊂isj\sum_{j\subset i}s_j∑j⊂i​sj​。 有一个显然的想法是模拟即可 O(4n)O(4^n)O(4n)，但是显然我们可以通过枚举子集轻松做到 O(3n)O(3^n)O(3n)，还能不能可以更优？ 上面枚举子集的方法我们看有没有什么问题，我们发现当一个状态的二进制位上有 kkk 个 0，那么它将在其他状态的带的时候被访问 2k−12^k-12k−1 次，存在许多重复且无用的计算，原因是因为我们每一个对应的 sis_isi​ 没有和状态建立起对应的练习，而是直接暴力枚举子集，我们需要添加另一个状态来避免上述的重复计算。 我们考虑状态的设计与添加，设状态 S(sta)={x∣x⊂sta}S(sta)=\{ x|x \subset sta\...

1. 介绍 我们称一个 nnn 维向量组是线性无关的，当且仅当不存下不全为 0 的一组数 cic_ici​，使得 ∑ciai=0\sum c_i a_i =0∑ci​ai​=0。 而线性基认为是一个 nnn 维向量集合中极大的线性无关向量子集，可以证明任何向量集合存在线性基，且一个向量集合的任意线性基大小相同。 最坏情况下线性基会有 nnn 个元素，即全部都线性无关。我们可以通过维护一个向量数组 aia_iai​（i∈[1,n]i\in [1,n]i∈[1,n]）来表示最终得到的线性基。 依次加入每一个向量 vvv，从高到低扫描每一位，如果 vvv 的第 iii 位非零，那么就检查 aia_iai​： 若 aia_iai​ 不存在，那么令 ai←va_i \leftarrow vai​←v，结束循环。 若 aia_iai​ 存在，那么令 v←vxai,xaiv \leftarrow \dfrac{v_x}{a_{i,x}}a_iv←ai,x​vx​​ai​，继续循环下一位。 上述算法时间复杂度为 O(n2m)O(n^2 m)O(n2m)，其中 mmm 为加入的向量数量。溶蚀...

0. 前言 你需要掌握的知识： 矩阵与矩阵运算。 行列式。 1. 概念与应用 1.1 概念 LGV 引理是用于解决图上不交路径计数的问题。同时也是线性代数中行列式的一个经典应用。 我们阐述一下概念。 对于一张有边权的有向无环图 GGG，定义一条路径 PPP，的权值 w(P)w(P)w(P) 为路径上所有边的边权的乘积，也就是说 w(P)=∏(u,v)∈Pval(u,v)w(P)=\prod_{(u,v)\in P} val(u,v)w(P)=∏(u,v)∈P​val(u,v)。 定义 e(u,v)e(u,v)e(u,v) 为 u→vu \to vu→v 的所有路径 PPP 的权值之和，也就是 ∑P:u→vw(P)\sum_{P:u\to v} w(P)∑P:u→v​w(P)。 定义两个大小为 nnn 的点集的子集 A,BA,BA,B，分别称之为起点集合与终点集合，则一组从 A→BA\to BA→B 的不交路径 SSS 为：SiS_iSi​ 是一条从 Ai→Bσ(S)iA_i \to B_{\sigma(S)_i}Ai​→Bσ(S)i​​。其中 σ(S)\sigma(S)...

正解 首先在分析问题的时候不难发现操作的一个性质就是同一个 xix_ixi​ 对应多个所谓的 p[l,r]p_{[l,r]}p[l,r]​ 序列。 对于这种操作对应多个序列不好计数的限制，一般情况下我们有下面两种思路 探究一下什么序列能够被得到，而不是从操作序列的角度设计 DP 状态。 若硬是从操作序列入手，我们可以通过给操作附上某种特定的顺序，让每一个序列都附上一个唯一的代表元，而这个代表元就是我们需要分题目去设计的。 如果你从第一个思路想的话你会很快陷入瓶颈，不建议自行尝试不然你会很痛苦。 我们从第二个思路入手，那么我们要对操作序列确定一个顺序，使得我们的决策可以唯一化。 考虑用插入法，我们可以从大到小钦定每一个值的位置，就是倒着遍历 n,n−1,n−2,…,2,1n,n-1,n-2,\dots,2,1n,n−1,n−2,…,2,1,。每一次我们把对应的值插到当前最左端的位置。 通过这种方式，我们可以将问题从对 xxx 计数变为对上面合法构造的排列 ppp 进行计数。 考虑如果 DP，注意到每一次操作都是涉及的是 max⁡\maxmax 操作，不妨考虑利用大根堆笛卡尔树...

0.前言 侧重于理论以及做题大方向，方法论的指导。 本博客若没有特殊说明，所有变量默认取值范围为 Z\mathbb{Z}Z。 1.半群线段树 1.1 定义 我们都说，线段树能维护具有结合律的信息，不能维护没有结合律的信息，那么为什么线段树只能维护有结合律的信息呢？这里我们可以利用半群线段树的理论来进行说明。 首先要定义什么是半群，半群是一个二元组 (S,×)(S,\times)(S,×)，其中： SSS 是一个非空集合； ×\times× 是一个定义在 SSS 上的运算，即 x∈S,y∈S,x×y=z,z∈Sx\in S,y\in S,x\times y=z,z\in Sx∈S,y∈S,x×y=z,z∈S，即满足封闭性。 这个 ×\times× 运算满足结合律，即 (x×y)×z=x×(y×z)(x\times y)\times z=x\times(y\times z)(x×y)×z=x×(y×z)。 注意这里上面的 ×\times× 不是乘法，是抽象代数中的集合运算，这里用乘法符号让读者更好理解。同时要注意，半群并不要求拥有单位元和逆元。 而半群线段树是一种数据结构，...