wjyppm's Blog

把未感染和感染抽象为 0/1，那么原问题可以转化为初始有一个全为 111 的序列，可以在特定时间进行一次区间覆盖操作（有代价），111 会向左右扩散，问能不能将整个序列全部覆盖为 0 且使得操作代价最小。 对于选择区间进行覆盖的问题，这一类经典问题有一种状态设计就是设 f(i)f(i)f(i) 表示将 [1,i][1,i][1,i] 这个前缀进行覆盖的最小代价。但是问题在于这样转移是 O(nm)O(nm)O(nm) 的不太好搞，考虑这个 mmm 的瓶颈就是在于我们需要知道每一个覆盖区间右端点在哪里。考虑切换一下 dp 状态，设 f(i)f(i)f(i) 表示将 [1,ri][1,r_i][1,ri​] 覆盖的最小代价，转移通过 ttt 的偏序关系进行转移： f(i)←f(j)+cirj−li+1≥∣ti−tj∣\begin{aligned}f(i) & \leftarrow f(j)+c_i & r_j -l_i+1 \ge |t_i -t_j| \end{aligned} f(i)​←f(j)+ci​​rj​−li​+1≥∣ti​−tj​∣​ 时间复杂度还是 O...

题面过于复杂，有一个显然的想法就是让导师们去找学生，设 f(i,j,k,p)f(i,j,k,p)f(i,j,k,p) 表示四个导师选的人数状态下的方案数，转移判断满不满足题目中所给的派系和阵营限制即可，时间复杂度 O(nm4)O(nm^4)O(nm4)，不难发现只需要确定三个即可，时间复杂度 O(nm3)O(nm^3)O(nm3)。然后就不会了。 观察这个 DP 及其难以优化，因为如果我们缺任何一个信息都无法描述完整的子问题，而且复杂度要求的可是 O(nm)O(nm)O(nm)，你只知道一个信息那么肯定啥也导出不了啊。我们考虑发掘几个性质： 确定一个派系和一个阵营可以唯一确定一位导师。 题目中 ban 导师的相当于不选钦定的派系和阵营。 上述性质启示我们让每一个学生去确定它们的派系和阵营，而不是导师去确定学生。但是还有我们的 “坏” 学生，不喜欢选的。我们先丢掉它们，先考虑 k=0k=0k=0 的部分分。 有一个显然的 DP 就是 f(i,j)f(i,j)f(i,j) 表示 iii 个蓝阵营的人，jjj 个鸭阵营的人的方案数，剩余两个可以由这两个状态唯一表示出来，时间复杂度 ...

有很大一部分来自于 zxy，课件等，一般都是很强的 Trick。 7和8月 CF1476F 考虑 DP，设 f(i)f(i)f(i) 表示前 iii 个灯可以点亮的最长前缀，有转移： iii 朝右，若 f(i−1)≥if(i-1)\ge if(i−1)≥i，则 f(i)=max⁡(f(i−1),i+pi)f(i)=\max(f(i-1),i+p_i )f(i)=max(f(i−1),i+pi​)，若 f(i−1)<if(i-1)<if(i−1)<i，则 f(i)=f(i−1)f(i)=f(i-1)f(i)=f(i−1)。 iii 朝左：不难发现只要将前缀覆盖到 i−pii-p_ii−pi​ 即可就行，设 jjj 为第一个 f(j)≥i−pif(j)\ge i-p_if(j)≥i−pi​ 的位置，那么 [j+1,i−1][j+1,i-1][j+1,i−1] 的位置都可以朝右，那么 f(i)=max⁡k=j+1i−1k+pkf(i)=\max\limits_{k=j+1}^{i-1}k+p_kf(i)=k=j+1maxi−1​k+pk​，可以二分 jjj 加 ...

被诈骗的一集。 话说你是打得好才记吗，下次打的不好更应该记录反思的好吧。 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 为加入的向量数量。溶蚀...