All - WrongAnswer90's Blog

Ds 选讲

CF2006E Iris’s Full Binary Tree 度数有大于 $3$ 的不合法。要选一个度数 $\leq 2$ 的点使得其偏心距最小。偏心距可以看成是，到树的中心的距离加上直径的一半。加点之后中心最多移动 $0.5$ 的距离，可以拿一个线段树维护所有点到其的距离。 QOJ8235 Top Cluster 二分答案之后就是求，一个点到一个点集的距离的最大值，维护直径...

Posted by WrongAnswer_90's Blog on November 20, 2024

计数选讲

CF1943D2 Counting Is Fun (Hard Version) 充要条件是不存在 $1<i<n$ 使得 $a_i>a_{i-1}+a_{i+1}$。可以归纳证明。对这个东西计数，暴力需要记两维，$f_{i,j,k}$ 表示 $i$ 上填了 $j$，$i-1$ 填了 $k$ 的方案数。核心性质是，$i$ 和 $i-1$ 不能同时不合法。所以设 $f_...

Posted by WrongAnswer_90's Blog on November 13, 2024

CF1423M Milutin's Plums

题解

My Blogs CF1423M Milutin’s Plums 完全单调性的定义：一个 $n\times m$ 的矩阵，如果对于所有 $S\subseteq \{ 1,2,3\dots n \} $，$T\subseteq \{1,2,3\dots m \}$，只保留 $S$ 中的行和 $T$ 中的列时，每行第一个最小值的位置都是非降的，则称其有完全单调性。 SMAWK 算法：一种能...

Posted by WrongAnswer_90's Blog on November 12, 2024

杂题选讲

做题

CF2029F Palindrome Everywhere 表示愤怒。首先有如果两个颜色都有大于 $1$ 的连续段那一定不合法。接下来只有一个颜色有连续段。如果其有大于等于两个偶数连续段一定不合法，方法就是考虑两个端点的奇偶性。如果没有偶数连续段，考虑 $0$ 把 $1$ 分成了若干段，如果全是奇数手玩可以发现两个点的相对距离是不太会变的。相对距离指两者间的 $0$ 个数和 $...

Posted by WrongAnswer_90's Blog on November 11, 2024

DS 选讲

做题

CF193D Two Segments 一个段是非常经典的问题 pudding monsters。序列上做不大了，考虑在值域上做。两个连续段可以用点减边，相邻两个同时出现的贡献是 $-1$，一个数字的贡献是 $+1$，这样要求就是贡献和小于等于 $2$。也是好维护的。 QOJ2743 Seats 全局想维护一个矩形很困难。考虑一个局部的性质：四个角上都是三白一黑，必要条件显然是三白...

Posted by WrongAnswer_90's Blog on November 6, 2024

Ucup 题选讲

做题

QOJ9540 Double 11 挺魔怔的啊。柯西不等式得，要求的就是把序列分组，使得 $\sum_i \sqrt{sum_icnt^i}$ 最小。排序（？），wqs 二分（。），决策单调性（。）。我也不知道为什么但是确实是这么做并且一眼看上去也是这么做/kx/kx。 QOJ9522 A Simple String Problem 考虑单串怎么做。一个神秘做法是分治（？），然后要...

Posted by WrongAnswer_90's Blog on November 4, 2024

2024 NOIP 代码源

模拟赛

Day 1 有点烦。2h 只会 D 的次低档暴力。 T1 答案和连续段有关，所以是一堆卡特兰数乘起来。 T2 可以发现 $SG_x(i)=i\bmod {(x+1)}$。现在就是要对于每个 $x$ 求出 $\displaystyle \bigoplus_{i=1}^n a_i\bmod {(x+1)}$。首先扔到桶里，然后考虑倍增，预处理 $f_{i,j}$ 表示 $\disp...

Posted by WrongAnswer_90's Blog on October 31, 2024

ARC186 vp

做题

ARC186 不打好亏！ ARC186A 打表猜个结论就过了，结论是若存在序列 $a[1,k],b[1,k]$ 满足 $\forall i\in[1,k],a_i,b_i\geq 2$ 且 $\sum a,\sum b\leq n$，则 $n^2-\sum_{i}a_ib_i$ 合法。大概就是很多个行列不交的矩形，然后矩形内部都是不固定的。官解：建一个 $2n$ 个点的有向二分图，...

Posted by WrongAnswer_90's Blog on October 28, 2024

P6809 BalticOI 2010 Day2 Mines

题解

My Blogs P6809 [BalticOI 2010 Day2] Mines 17k 的含金量。设 $c_{i,j}$ 表示答案，$a_{i,j}$ 表示输入数据。首先可以确定 $c_{3,3}=a_{2,2}-a_{2,1}-a_{1,2}+a_{1,1}$，用二维差分可以知道 $c_{i,j},c_{i-3,j},c_{i,j-3},c_{i-3,j-3}$ 的关系...

Posted by WrongAnswer_90's Blog on October 24, 2024

2024 集训队互测

做题

Day 1 T1 感觉能做。首先考虑给定了一个序列如何判是否合法。如果确定了三种子序列分别的出现次数，暴力 DP 是记录 A,B,C,AB,BC,CA 的出现次数的方案是否合法。从前向后扫 $s$ 串，如果当前出现了一个字符 A，他可以单独成一个新的序列，可以拼到 C 上，也可以拼到 BC 上。感性理解就是因为三个串是循环同构的，考虑如果新成一个序列，他后面还要接 B,C，拼...

Posted by WrongAnswer_90's Blog on October 22, 2024

2024.10.15 DP

做题

CF1993E Xor-Grid Problem 考虑新加一行一列，则每次操作就是第 $i$ 行和第 $n+1$ 行交换，或者第 $j$ 列和第 $m+1$ 列交换，这样行列就独立了。分别求出来删掉一行后，列上面的最短哈密顿路，还有删掉一列之后，行上面的哈密顿路，时间复杂度 $\mathcal O(2^nn^2m+2^mm^2n+nm)$。 CF1852D Miriany and M...

Posted by WrongAnswer_90's Blog on October 15, 2024

P8367 LNOI2022 盒

题解

My Blogs P8367 [LNOI2022] 盒旧题新做，发现仍然是唯一真神。首先考虑给定了 $b$ 序列如何计算答案，把 $a,b$ 都做一遍前缀和，则答案即为 $\sum_{i=1}^nw_i\lvert a_i-b_i\rvert$。对每个位置 $i$ 算贡献，枚举 $j=b_i$： \[\begin{aligned} f(i,n,m,k)&=\sum_{j=...

Posted by WrongAnswer_90's Blog on October 11, 2024

2024.10.11 图论

做题

CF1209F Koala and Notebook 首先最小化位数，然后最小化字典序。每个边拆边成一位数之后，建分层图，每层依次处理，用类似求 SA 的方法，给每层的点重标号。 CF325C Monsters and Diamonds 判 -1 -1：一个点存在操作全变成 $-1$ 那它自己就可以消完，做一个类似拓扑排序的东西（如果一个规则的后继点全部确定了难就把这个规则的出发点...

Posted by WrongAnswer_90's Blog on October 11, 2024

ATxmascon23C Clamp Clamp Clamp

题解

My Blogs [ATxmascon23C]Clamp Clamp Clamp 首先看成先确定一个数，然后再选 $n$ 个区间，不断地把这个数放到区间里。如果所有区间的交不为空，容易发现答案一定是 $n$。先用 $(n!)^2$ 确定后面的相对顺序，然后 $(2n+1)$ 确定第一个数插在哪里，所以首先 $v_n=(2n+1)(n!)^2$。考虑枚举 $k$ 作为极长的有交的后...

Posted by WrongAnswer_90's Blog on October 10, 2024

ARC184E Accumulating Many Times

题解

My Blogs [ARC184E] Accumulating Many Times 感觉比 C 简单啊/kk。文中序列下标从 $0$ 开始。根据前缀和的定义，一个序列 $A[0,n-1]$ 做 $k$ 次前缀和之后，每个位置可以看成是每次可以向后走若干步。所以 $i$ 对 $j$ 的贡献就等价于一共要走 $j-i$ 步，每次可以走若干步的方案数，插板法可以得到系数是 $\binom...

Posted by WrongAnswer_90's Blog on October 9, 2024

ARC170E BDFS

题解

My Blogs [ARC170E] BDFS 唐完了。翻译一下题目在说什么：有两个指针 $L,R$，一开始均为 $0$。一开始有一个 $opt=0$，发生以下事件 $n-1$ 次：如果 $opt=0$，则 $L\leftarrow L +1$，否则。$R\leftarrow R +1$。 $opt$ 有 $P$ 的概率保持不变，有 $1-P$...

Posted by WrongAnswer_90's Blog on October 9, 2024

ARC184D Erase Balls 2D

题解

My Blogs [ARC184D] Erase Balls 2D 剩下的点的不同方案不好计数，对操作方案计数会算重。考虑在剩余点的方案和操作之间构建一个双射：对于一个剩下的方案，不断操作不会新删去当前剩下的点的点直到没有点可以操作，这样操作方案就和剩下的球的方案一一对应了。所以需要计数的序列是，操作任意一个没有被删去且没有被操作的点都会导致其他没有被删去的点删掉的操作方案。设 ...

Posted by WrongAnswer_90's Blog on October 7, 2024

ARC184B 123 Set

题解

My Blogs [ARC184B] 123 Set 首先一个最基本的性质是如果 $x$ 不是 $2$ 或者 $3$ 的倍数则 $x$ 一定会被操作。基于这个简单观察，可以进一步的发现：取出所有不是 $2,3$ 的倍数的数 $x$，则对于不同的 $x$，$2^i3^jx$ 之间是没有关系的。所以可以对于不同的 $x$ 分别处理。考虑操作了 $x$ 之后可以覆盖掉 $2x,3x$，很深...

Posted by WrongAnswer_90's Blog on October 7, 2024

IOI2024

做题

T1 考虑把 $D$ 从小到大做。看成没有性质二分图匹配肯定是做不了的，所以应该把 $W$ 从小到大排序，把二分图匹配这个比较烂的东西变得好一点。如果一种方案中，匹配了的点是另一个方案的子集，那这个方案一定不优。观察一下性质，对于 $n=4$ 的情况，如果 $i$ 和 $i-3$ 匹配了，$i-2$ 和 $i-1$ 一定能匹配且会匹配。对于 $n$ 更大的情况也可以用归纳法证明，$i$...

Posted by WrongAnswer_90's Blog on October 1, 2024

ARC174E Existence Counting

题解

My Blogs [ARC174E] Existence Counting 比较机械的处理方式。和 NOID2T2 是一个性质，只不过简单多了。枚举生成序列和 $P$ 的第一个不同位置 $i$，则第 $i$ 个位置能填的数的个数 $g_i$ 是 $<a_i$ 并且之前没有出现过的数，$g_i$ 可以简单用树状数组求出。然后考虑如何统计答案。对于 LCP 中所有数的贡献：首先...

Posted by WrongAnswer_90's Blog on September 28, 2024

ARC171E Rookhopper's Tour

题解

My Blogs [ARC171E] Rookhopper’s Tour 因为每行每列都最多只有一个石子，所以一定是横竖相间的走。首先手玩一下，可以发现白色石子放置好了之后，最多只有一种合法的走法，因为确定了第一步走的方向，后面由于题目中没有行列相同的白石子，所以之后的路线是唯一的。所以算重只需要考虑把路线反过来还能走。然后画一下图就可以发现显然不合法（可能严谨一点的需要归纳）。 ...

Posted by WrongAnswer_90's Blog on September 26, 2024

2024 CSP 代码源

模拟赛

Day 1 挂分仙人。 T1 比较简单，找到所有区间，算每个颜色不被多少区间包含。因为贡献区间长度固定，所以可以转成对 $l$ 的限制，前缀和一下做完了。 T2 建出 trie 树，根据右儿子的奇偶性判断：如果为奇数，则右儿子至少有一个不匹配，然后可以找一个不匹配，剩下的两两匹配这一位就都是 $0$，一定不劣。有两种方案，第一种是选一个单独成集合，第二种是选一个和左子树异或...

Posted by WrongAnswer_90's Blog on September 20, 2024

2024 NOIP 炼石计划

模拟赛

Day 1 T1 可以做快速幂，每次 $\times 2$ 或者 $\times 2+1$。然后从后向前考虑后面对前面的影响即可。 T2 考虑枚举出现次数 $k$，计算众数出现次数 $\geq k$ 的序列数，转成 $n^m$ 减去所有颜色出现次数都 $<k$ 的序列数。考虑一种颜色指数生成函数 $F(x)=\sum_{i<k}\frac{x^i}{i!}$，需要求这个多...

Posted by WrongAnswer_90's Blog on September 20, 2024

梦熊 NOIP 2024

做题

QOJ8824 Slay the Spire 首先可以新建超级源点，把药水和起点的限制去掉。问题变为，选择一些边，支付其边权的代价改变其入点，改完之后使得图存在一个欧拉回路。然后对于出度大于入度的点，需要把一些出边作为没有贡献的边删掉。可以证明只要删掉上述不合法的边，一定能使得所有点入度等于出度（随便接到出度小于入度的点上面即可）。现在的问题是图的连通性。把删的边 $(u,v)$ ...

Posted by WrongAnswer_90's Blog on September 10, 2024

ABC221G Jumping sequence

题解

My Blogs [ABC221G] Jumping sequence 做法有点深刻，优化方式非常深刻。首先是哈密顿距离和切比雪夫距离的转化：把坐标系旋转四十五度，变成每次向左上，右上，左下，右下走 $\sqrt 2 a_i$ 的距离，要求最后走到 $(A+B,A-B)$。然后这样可以对于横纵坐标分开做了（非常神奇）。问题转化成了询问是否存在序列 $x$ 满足 $\forall ...

Posted by WrongAnswer_90's Blog on September 5, 2024

ARC171C Swap on Tree

题解

My Blogs [ARC171C] Swap on Tree 科技改变生活。以 6ms 的速度拿下了目前最优解（如果已经确定了 $u$ 的一个儿子 $v$ 内部的操作顺序，考虑在某个时刻交换 $(u,v)$。设 $a[1,k]$ 是操作 $v$ 子树内部时 $v$ 上面的颜色，可以发现在第 $i$ 个时刻交换和在第 $j$ 个时刻交换，方案本质不同的充要条件是 $a_i\not= ...

Posted by WrongAnswer_90's Blog on September 4, 2024

ARC173F Select and Split

题解

My Blogs [ARC173F] Select and Split 在 Kevin 题解的基础上解释了一下。分裂这个过程感觉很不自然，考虑倒过来做合并。经过简单的观察，可以发现一个集合的属性只和在 $[1,A]$ 内的元素个数和 $[A+1,A+B]$ 内的元素个数有关，分别设其为 $a_i,b_i$。合并两个点的方案数是 $a_ib_j+a_jb_i$。合并两个集合 $S,...

Posted by WrongAnswer_90's Blog on September 1, 2024

ARC183E Ascendant Descendant

题解

My Blogs [ARC183E] Ascendant Descendant 一个直接的想法是求出 $L_i,R_i$ 表示极大的区间 $[L_i,R_i]$ 满足 $\forall j\in[L_i,R_i],b_j\in \mathrm{subtree}(a_i)$。由于树的性质，$[L_i,R_i]$ 之间要么相离，要么包含。但是 $L_i,R_i$ 并不是 $i$ 能真正到...

Posted by WrongAnswer_90's Blog on August 27, 2024

ARC180E LIS and Inversion

题解

My Blogs [ARC180E] LIS and Inversion 首先考虑要求代价为 $0$ 的一个暴力 DP：$f_{i,j}$ 表示填了前 $i$ 个数，此时相对值域末尾为 $j$ 的数结尾的 LIS 的最大值。填第 $i+1$ 个数的时候，把它插在某两个数之间，所以转移是： \[f_{i,j}= \begin{cases} f_{i-1,j-1}\qquad\qquad\...

Posted by WrongAnswer_90's Blog on August 27, 2024

ARC175E Three View Drawing

题解

My Blogs [ARC175E] Three View Drawing 哎，构造。首先考虑 $m=n^2$ 怎么做：显然是最上面一层填满第一条主对角线，第二层填满第二条主对角线…（主对角线指可以循环的对角线）。把 $n$ 变成满足 $n^2\geq m$ 的最小的 $n$。然后考虑删去 $n^2-m$ 个。可以发现（谁能发现啊啊啊）在矩形的右下角删掉一个 L 型即可。如果 $...

Posted by WrongAnswer_90's Blog on August 27, 2024

ABC367G Sum of (XOR^K or 0)

题解

My Blogs [ABC367G] Sum of (XOR^K or 0) 考虑求出 $ans_i$ 表示选了 $m$ 的倍数个数，异或和是 $i$ 的方案数再统计答案。先考虑 $m=1$ 怎么做。相当于是 $ans_i=[x^i]\prod_j (x^0+x^{a_j})$，这里的乘法是异或卷积。如果直接 xor-FWT 复杂度不如暴力。令 $F_i(x)$ 表示第 $i$ 个数...

Posted by WrongAnswer_90's Blog on August 27, 2024

ARC183D Keep Perfectly Matched

题解

My Blogs [ARC183D] Keep Perfectly Matched 这场不打感觉亏麻了，怎么大家都不会 D。首先匹配路径长度之和最大，很典的想到取重心，猜测答案上界 $\sum_i dep_i$ 可以取到。取完重心之后，希望不断把两个不同的子树里的点进行匹配，直到删空。因为原树本身存在完美匹配，所以找一对不同子树里的点删去后，根节点的匹配一定变了。所以选的点一定有...

Posted by WrongAnswer_90's Blog on August 26, 2024

AGC067B Modifications

题解

My Blogs [AGC067B] Modifications 谔谔，做过类似的题还是不会啊啊啊。首先考虑给定一个 $a$ 序列如何进行判定。倒着做这个覆盖的过程，每次可以看成是，如果 $[l_i,r_i]$ 剩下的点的颜色都相同，则可以把 $[l_i,r_i]$ 删掉。如果最后能删空就是合法的。区间 DP 判定这个过程：$f_{l,r}$ 表示考虑了左右端点都则区间 $[l,...

Posted by WrongAnswer_90's Blog on August 25, 2024

ARC176D Swap Permutation

题解

My Blogs [ARC176D] Swap Permutation 对每个位置分别算贡献。一个很重要的观察是其他所有数都是等价的（非常神奇）。设 $A$ 表示原来 $i$ 位置上的数，$B$ 表示原来 $i+1$ 位置上的数，$C$ 表示其他的数，设 $f_{0\sim 7}$ 表示经过 $m$ 次操作之后 $AB,BA,AC,CA,BC,CB,CC$ 的概率。每个位置 $i$ 的 ...

Posted by WrongAnswer_90's Blog on August 24, 2024

ARC177F Two Airlines

题解

My Blogs [ARC177F] Two Airlines 有点魔怔的题。一个基本的观察是如果当前某个人 $A$ 拿着盒子走到了位置 $i$，那位置小于 $i$ 的人一定永远没用了。如果之后要用到前面的人 $B$，就应当让 $B$ 拿着盒子走到 $i$ 而不是让 $A$，这样 $A$ 待在原来的位置，代价一定不会更劣。再手玩一下，可以发现每次的过程都是：某个人 $A$ 拿起盒...

Posted by WrongAnswer_90's Blog on August 23, 2024

ARC083F Collecting Balls

题解

My Blogs [ARC083F] Collecting Balls 建图，连边 $(x_i,y_i+n)$，这样会形成一个基环树森林。对于基环树的每条边，需要把他归到他连接的两个点中任意一个，并且每个点只能拥有一条边。对于每个基环树分别计算，树边归属的点一定是它两端深度较大的那个，环边归属点整体只有两种方式：顺时针和逆时针。确定了边挂在哪个点上之后，操作顺序的限制就是，如果边 $...

Posted by WrongAnswer_90's Blog on August 23, 2024

ARC178E Serval Survival

题解

My Blogs [ARC178E] Serval Survival 非常生气，点开一道看起来很正常的计数，推着推着就发现需要多项式/fn。首先对于“撞上了之后调头”这种东西有经典的思想：可以看成是互相穿过并没有调头。但是因为要求第 $i$ 只猫走过的路，所以可以看成是和撞上的猫互换身份。手玩一下可以发现，如果第 $i$ 只猫向左走，它会和 $a_i$ 左边的第一只向右的猫互换身...

Posted by WrongAnswer_90's Blog on August 16, 2024

ARC182E Sum of Min of Mod of Linear

题解

My Blogs [ARC182E] Sum of Min of Mod of Linear 首先把 $A$ 排序去重。考虑什么时候 $a_i$ 会成为答案。对于 $v_i=C\times i\bmod m$，一定是希望找一个尽量小的 $j$ 满足 $v_i+a_j\geq m$，这样可以恰好发生一次进位，贡献是 $m-a_j$。如果找不到 $j$，就会选择 $a_1$，贡献是 $a...

Posted by WrongAnswer_90's Blog on August 15, 2024

ARC182F Graph of Mod of Linear

题解

My Blogs [ARC182F] Graph of Mod of Linear 首先判掉 $A\leq 1$ 的情况，接下来默认 $A\geq 2$。原图是基环树森林，数连通块数等价于数环的个数。比较自然的一点是，把问题分为 $A,N$ 是否互质。因为如果 $A$ 和 $N$ 互质，则 $Ai+B$ 在 $\mod N$ 意义下互不相同，所以每个点都在一个环里。 1. $A\n...

Posted by WrongAnswer_90's Blog on August 13, 2024

ARC182D Increment Decrement Again

题解

My Blogs [ARC182D] Increment Decrement Again 判掉 $m=2$。接下来有个奇妙的转化：看成 $A$ 不对 $m$ 取模，要求变为 $\forall i<n,\lvert a_i-a_{i+1}\rvert<m\wedge a_i\not= a_{i+1}$。然后发现 $a$ 的大小关系是不会变的，所以如果固定了 $a’1$，则后...

Posted by WrongAnswer_90's Blog on August 13, 2024

ARC182C Sum of Number of Divisors of Product

题解

My Blogs [ARC182C] Sum of Number of Divisors of Product 见过一万遍的套路啊啊啊啊啊。首先如果序列乘积是 $\prod c_i^{p_i}$，答案就是 $\prod (p_i+1)$。$M$ 以内的质数个数只有 $6$ 个：${2,3,5,7,11,13}$。然后考虑这个式子的组合意义：对于每个质因子，可以看成在其每次出现的时...

Posted by WrongAnswer_90's Blog on August 13, 2024

ARC179E Rectangle Concatenation

题解

My Blogs [ARC179E] Rectangle Concatenation 唐完了。稍微观察一下发现矩形只有两种形态。考虑暴力：从每个 $i$ 开始向后扫，设 $f_{j,0}$ 表示能否拼在左右，$f_{j,1}$ 表示能否拼在上下。设 $S_{l,r}$ 表示 $[l,r]$ 内矩形的面积和，没想到用面积判就败了： \[\begin{aligned} f_{j,0}=...

Posted by WrongAnswer_90's Blog on August 10, 2024

P10008 [集训队互测 2022] Range Minimum Element

题解

My Blogs P10008 [集训队互测 2022] Range Minimum Element 难点在于双射构造。首先考虑给定了 $b$ 如何进行判定。从小到大填数 $x$，每次把能填的地方（$b_i>x$ 的区间之外）全部填上 $x$，这样填一定是最优的。合法当且仅当这样生成的序列 $a$ 对应的 $b$ 就是 $b$ 本身。发现通过这样的生成方式，合法的 $a$ ...

Posted by WrongAnswer_90's Blog on August 9, 2024

CF1988F Heartbeat

题解

My Blogs CF1988F Heartbeat 最大值把序列分成两部分，前一部分对前缀最大值个数有贡献，后一部分对后缀最大值个数有贡献，可以分开算。设 $f_{i,j,k}$ 表示 $[1,i]$ 的排列，有 $j$ 个前缀最大值，$k$ 个上升的位置的方案数。不断向右边加数不好做，不断加入 $n+1$ 也不好做，因为可能前缀最大值个数会变少。所以考虑不断的加入新的 $1$，把...

Posted by WrongAnswer_90's Blog on August 9, 2024

ARC181F Colorful Reversi

题解

My Blogs [ARC181F] Colorful Reversi 首先观察一下，对于 $a,b,c,a$ 这种情况来说，两个 $a$ 之间永远不可能发生操作。而 $a,b,c,b,a$ 这种情况，两个 $a$ 之间是有关联的。有一个很天才的想法是建树，一开始只有一个节点表示 $a_1$，维护一个指针 $pos$ 表示当前在树上的哪个节点，接下来依次加入每个点 $a_i$： ...

Posted by WrongAnswer_90's Blog on August 8, 2024

ARC181E Min and Max at the edge

题解

My Blogs [ARC181E] Min and Max at the edge 场上没人过的神题。（大概是搬运的官方题解）先考虑如何 chk 一个图是否存在好生成树。观察好生成树的限制，发现其对于非树边的限制是在生成树上连接两点的路径有关。而 Kruskal 的证明就是对于每条非树边，其边权大于所有其路径上的树边，两者很像。但是题目中的限制是点的限制，转到边上的想法是给点赋...

Posted by WrongAnswer_90's Blog on August 8, 2024

P10359 [PA2024] Kolorowy las

题解

My Blogs P10359 [PA2024] Kolorowy las /tuu。写了三天。首先考虑树的形态不变怎么做，直接的想法是树分治这种东西可以做到一只或者两只 $\log$。但是点分这种东西不太好扩展到动态树的问题。但是因为这是单点查询，所以可以不用真正的树上染色，只需要回答每个询问即可。考虑对于每个询问，考虑找到在它之前第一次给这个点染色的操作，这样这次操作就是答案...

Posted by WrongAnswer_90's Blog on July 8, 2024

P10432 [JOISC 2024 Day1] 滑雪 2

题解

My Blogs P10432 [JOISC 2024 Day1] 滑雪 2 感觉是挺好的观察性质题，vp 的时候场切了。首先酒店一定是建在最低的某一个点。把高度离散化之后，把点扔到对应的位置。可以发现高度为 $i$ 的层的所有点，如果能接上一层的连接器那一定会尽量接上（因为到了下一层它本身也可以贡献一个空的连接器）。设 $v_i$ 是高度为 $i$ 的点里最小的 $C$，则从 ...

Posted by WrongAnswer_90's Blog on June 13, 2024

P10430 [JOISC 2024 Day1] 鱼 3

题解

My Blogs P10430 [JOISC 2024 Day1] 鱼 3 首先操作可以看成是单点减 $k$ 和后缀减 $1$，问区间能不能全部减到 $0$，并最小化单点操作次数。假设先进行所有的单点修改，则一定是把一个区间改成单增的。考虑扫描线，从左向右依次新加入数，并且在这个过程中要保持当前的序列单增。可以用一个单调栈来维护连续段。这里的连续段指的是相邻两个数的差小于 $...

Posted by WrongAnswer_90's Blog on June 13, 2024

CF1534G A New Beginning

题解

My Blogs CF1534G A New Beginning 不太懂为啥是黑。需要先会基本的 slope trick。首先切比雪夫距离可以转成曼哈顿距离但是没啥必要。因为只能向右上走，所以考虑把每个关键点归到它属于的斜率为 $-1$ 的直线上，即按照 $x_i+y_i$ 排序分类。容易发现一定是走到了某条灰线上之后再收取该灰线上的所有点。所以设 $f_{i,j}$ 表示走...

Posted by WrongAnswer_90's Blog on June 10, 2024

P10550 [THUPC2024] 贸易

题解

My Blogs P10550 [THUPC2024] 贸易首先可以观察到，对于每种颜色，括号匹配（把 $0$ 看成左括号，$1$ 看成右括号）一定是最优的。所以可以先找出所有匹配 $[x,y]$，然后问题变成给定 $[l,r]$，求有多少个 $[x,y]\subseteq[l,r]$，离线做一遍扫描线，树状数组维护即可。 1 2 3 4 5 6 7 8 9 10 11 12 13 ...

Posted by WrongAnswer_90's Blog on May 31, 2024

P10543 [THUPC2024] 黑白

题解

My Blogs P10543 [THUPC2024] 黑白签到题。首先要判联通性。判完之后，统计全局的白格子个数 $s$。因为删到最后，一定会留下一条白色路径，然后路径的长度在 $\bmod\;2$ 意义下和 $n+m-1$ 同余。而我们只关心能操作次数的奇偶性，所以只需要判断 $s-n-m$ 的奇偶性即可。 1 2 3 4 5 6 7 8 9 10 11 12 13 14...

Posted by WrongAnswer_90's Blog on May 31, 2024

P10542 [THUPC2024] RPG

题解

My Blogs P10542 [THUPC2024] RPG 一个有配合的“状态加攻击”一定是一个连续段，段内都在摸鱼。所以设 $f_i$ 表示考虑了前 $i$ 个人的最大收益： \[f_i=\begin{cases} f_{i-1}+d_{b_i}\\ \max_{(x,y,z)\in \mathbb{E},y=b_i}g_x+z+d_{b_i} \end{cases}\] 其中...

Posted by WrongAnswer_90's Blog on May 31, 2024

P10541 [THUPC2024] 研发计划

题解

My Blogs P10541 [THUPC2024] 研发计划首先看上去就比较像流，直接考虑怎么建模。如果没有 $h$ 就是裸的最大权闭合子图：$S$ 向每个技术连边，每个收益向 $T$ 连边，然后技术指向收益的边连 inf，做最小割（割掉的表示支付的代价），答案就是收益之和减去最小割。现在有了 $h$，要做的大概形如：如果一堆技术全都割掉了和 $S$ 的边，那某个技术代价可...

Posted by WrongAnswer_90's Blog on May 31, 2024

THUSC PKUSC APIO 游记

游记

My Blogs THUSC 前情提要：THUWC $200+10$ 参与奖。 Day -1 坐高铁啦啦啦。身份证落在出租车上，费了很大劲才找回来，感觉很不牛。晚上饥荒启动。 Day 1 进考场前疯狂背诵 dwt 的 sublime 编译教程，进考场默写对了/kx/kx。 T1 唐题，一眼秒了。 T2 唐题，一眼秒了。 T3 想了一下，发现状态只需要记一维，然后二分...

Posted by WrongAnswer_90's Blog on May 20, 2024

初等双射构造

学习笔记

My Blogs 下文中 $[n]$ 表示 ${1,2,3\dots n}$。 P0 对于正整数 $n$，称 $a_{1\dots k}$ 是 $n$ 的有序划分，当且仅当 $\sum_i a_i=n$。给定 $n(\geq 2)$，求满足 $\sum_{i}[2\vert a_i]$ 是偶数的有序划分个数。答案：$2^{n-2}$。 $n$ 的所有划分可以看成有 $n-...

Posted by WrongAnswer_90's Blog on May 1, 2024

CF1951I Growing Trees

题解

My Blogs CF1951I Growing Trees 首先考虑确定了 $x_i$ 如何判定是否合法。可以很容易的找出这样一个必要条件：$\forall i,x_i\leq k$。这是两个点的情况，考虑点数更多的情况。手玩之后可以推广到：对于任意导出子图，要求其内部的边数 $\leq k(\lvert S\rvert-1)$。这个条件也是充分的，证明类似 $\mathrm{Ha...

Posted by WrongAnswer_90's Blog on April 30, 2024

ARC176F Colorful Star

题解

My Blogs [ARC176F] Colorful Star 感觉很考验想象力和计数基本功 QWQ。首先考虑给定了局面之后如何进行判定。考虑把覆盖的过程倒着做：如果 $i$ 旁边有和它颜色相同的棋子，那它就可以变成任意的颜色，然后要求最终能不能 $n$ 种颜色都只剩一种。然后这个还是不太本质。考虑如果有一个能变成任意颜色的，可以把它变成周围的另一个颜色，然后另一个颜色就能变成...

Posted by WrongAnswer_90's Blog on April 27, 2024

ARC176E Max Vector

题解

My Blogs [ARC176E] Max Vector $n=10$ 其实有点误导性。其实这个题不是指数级的算法，而且贪心也不是很合理，同时“要么…要么…”有点像最小割。一次操作可以看成要求 $x_j\geq a_{i,j}$ 或者 $y_j\geq a_{i,j}$。考虑切糕的模型，建 $2n$ 条链，割哪条边就表示第 $i$ 个变量的取值。其中 $x_i$ 的链要正着建，$y...

Posted by WrongAnswer_90's Blog on April 25, 2024

ARC145D Non Arithmetic Progression Set

题解

My Blogs [ARC145D] Non Arithmetic Progression Set 考虑三进制，如果只选只有 $01$ 的数就一定合法。然后可以考虑平移，即每个数同时 $\pm C$。如果原序列合法，经过该操作之后一定仍然合法。所以只需要构造一个序列，使得和 $\bmod\;n$ 意义下和 $m$ 同余。暴力选取最小的 $n-1$ 个合法三进制数，接下来补一个非常...

Posted by WrongAnswer_90's Blog on April 25, 2024

P5897 [IOI2013] wombats

题解

My Blogs P5897 [IOI2013] wombats 有点恐怖。首先 $R,C$ 很不平衡，考虑用一棵竖着的线段树维护较大的 $R$ 维，每个节点上需要存的是 $C\times C$ 的数组 $d$，$d_{i,j}$ 表示该节点的最上面一行第 $i$ 个到最下面一行第 $j$ 个的最短路。因为已经处理好了左右儿子内部的最短路，所以只需要枚举 $mid$ 处经过了哪条...

Posted by WrongAnswer_90's Blog on April 21, 2024

P5469 [NOI2019] 机器人

题解

My Blogs P5469 [NOI2019] 机器人首先考虑如何比较简单的进行判定合法。每一次执行一个找最大值的过程（如果有多个最大值则取最右侧的），然后从这个位置把序列劈成两半，递归判定。因为最大值的位置能走到序列的最左侧和最右侧，所以要求最大值的位置 $\lvert ((n-p)-(p-1))\rvert\leq 2$。所以考虑区间 DP，设 $f_{i,j,k}$ 表...

Posted by WrongAnswer_90's Blog on April 17, 2024

P8290 [省选联考 2022] 填树

题解

My Blogs P8290 [省选联考 2022] 填树很有意思的拉插优化 DP。首先可以枚举 $L$ 来限制选的数的值域在 $L,L+k$ 中。然后进行树上 DP：设 $v_i$ 表示当前点 $i$ 能填多少种数，$w_i$ 表示当前点 $i$ 能填的数的和。 $f_i$ 表示当前 $i$ 子树内的所有合法根链数量，$g_i$ 表示 $i$ 子树内所有根链的权值之和。假设在合...

Posted by WrongAnswer_90's Blog on April 16, 2024

P5904 P6109 [Ynoi2009] rprmq1

题解

My Blogs P6109 [Ynoi2009] rprmq1 毒瘤 Ynoi。对于加的矩形，显然是差分的拆成 $(l_1,l_2,r_2,+v)$ 和 $(r_1,l_2,r_2,-v)$ 两个线段。如果是查询的是和那是好做的，线段树历史和板子。但是要查的是最大值，矩形查最大值因为没有可减性，不能差分，非常的困难。考虑一个弱化问题：如果是查 $3-\mathrm{side}$...

Posted by WrongAnswer_90's Blog on April 15, 2024

P8990 [北大集训 2021] 小明的树

题解

My Blogs P8990 [北大集训 2021] 小明的树首先连通块个数可以用经典的点边转化，用点的个数减去边的条数。观察之后可以发现定合法的充要条件是黑色的点构成一个连通块，同样使用点边转化。现在可以看成有两个序列（时间轴），$V$ 和 $S$，操作是区间 $v$ 的修改，区间 $s$ 的修改，和查询全局 $v=1$ 的 $s$ 的和。对于一个点，设 $p_i$ 为其...

Posted by WrongAnswer_90's Blog on April 14, 2024

SDOI2024 游记

游记

Day 0 上午李还让去学校，差评。效率也不高，复习了一下 SAM 发现自己全忘干净了，只能奶一口省选不考串串。 8 点到校 11 点半回家吃饭，最自由的一集23333。下午打了个流的板子，然后去试机。slyz 全员考号都很靠前，我是 006。键盘手感很差，鼠标滚轮也有点问题但是懒得换了。忽然发现 dev 不能调试，询问 dwt 后发现是存在 d 盘根目录下导致的。。window...

Posted by WrongAnswer_90's Blog on April 3, 2024

2024 一轮省集

模拟赛

My Blogs Day 1 $80+10+0$ 垫底。 T1 神秘题。人类智慧发现 $S$ 不会太长，生成一个 $10^6$ 的串，然后建一个类似线段树的结构。预处理出数组 $f_{i,j}$ 表示 $T$ 的第 $i$ 位匹配一个 $S_j$ 能跳到最远的地方，可以类似倍增处理。然后双指针在 $S$ 上跑，复杂度 $\mathcal O(n\log n)$。 T2 完...

Posted by WrongAnswer_90's Blog on April 1, 2024

CF1943E2 MEX Game 2 (Hard Version)

题解

CF1943E2 MEX Game 2 (Hard Version) 更好的阅读体验好难啊好难啊好难啊，完全想不到 QAQ。显然满足单调性，进行二分答案 $mid$，表示答案在双方最优策略下能否达到 $mid$。 Alice 的策略很简单，每次选取 $[0,mid-1]$ 中 $f$ 最小的没有选过的元素即可。而 Bob 应当尽量把操作平均摊到多个 $f$ 上，不然一个 $f...

Posted by WrongAnswer_90's Blog on March 25, 2024

AGC036F Square Constraints

题解

AT_agc038_f [AGC038F] Two Permutations 更好的阅读体验下面默认 $P,Q$ 均整体加了 $1$，下标从 $1$ 开始。首先考虑如果 $a_i=i$，则 $p_j=i$ 的 $a_j=j$。然后多迭代几次，一定会回到 $i$。这提示我们把排列拆成若干个环，每个环 $R$ 满足 $p_{r_{len}}=r_1\wedge\forall i<...

Posted by WrongAnswer_90's Blog on March 19, 2024

CF903G Yet Another Maxflow Problem

题解

CF903G Yet Another Maxflow Problem 更好的阅读体验神奇的模拟最小割。（？）另一道类似的题暴力流显然跑不过。考虑最大流等于最小割，考虑割去那些边使得 $a_1,b_n$ 不连通。一个重要的性质是 $A$ 链上和 $B$ 链上都最多只会删一条边。原因很显然，如果删了很多条边，可以只保留 $A$ 中最靠前的边和 $B$ 中最靠后的边。为了方便处理，设...

Posted by WrongAnswer_90's Blog on March 17, 2024

CF1131G Most Dangerous Shark

题解

CF1131G Most Dangerous Shark 更好的阅读体验题解区大佬的题解都看不懂捏。提供一个可能更简单的思路？首先可以线性求出 $pre_i,nex_i$ 表示向左，向右能推倒的最远的骨牌的下标，以求 $pre$ 为例，具体方法是从小到大扫 $i$，初始化 $j$ 为 $i-1$，然后不断执行如果 $i-j<a_i$ 则令 $j$ 变成 $pre_j-1$，否...

Posted by WrongAnswer_90's Blog on March 13, 2024

P4563 [JXOI2018] 守卫

题解

P4563 [JXOI2018] 守卫更好的阅读体验这道题让我充分认识了我一点不会 dp。首先可以预处理一个点能看到的左边的所有点。注意到一个区间一定会选择右端点，设右端点不能看到的所有极长区间为 $[l_1,r_1],[l_2,r_2]\dots[l_k,r_k]$，区间 $[L,R]$ 的答案即为 $1+\sum f_{l_i,r_i}$。。。吗。上述思路是错的，因为看不...

Posted by WrongAnswer_90's Blog on February 27, 2024

AGC036F Square Constraints

题解

[AGC036F] Square Constraints 更好的阅读体验可以看成是求值域两个半圆间的排列的个数。首先对于每个 $i$ 设 $L_i,R_i$ 表示 $p_i$ 取值的下界和上界。如果没有小圆的限制即没有下界，问题很简单：把 $R$ 从小到大排序，然后 $\prod_{i=1}^nR_i-i+1$ 即为答案，原因显然，因为前面已经选了 $i-1$ 个并且前 $...

Posted by WrongAnswer_90's Blog on February 26, 2024

P8987 [北大集训 2021] 简单数据结构

题解

P8987 [北大集训 2021] 简单数据结构更好的阅读体验挺有意思的题。初步的想法是如果 $i<j\wedge a_i\leq a_j$ 则在之后的操作中 $a_i$ 一定仍然不大于 $a_j$。接下来是一个很妙的转化：把每个数看成坐标系中 $i,a_i$ 的点。正常的取 $\min$ 操作是对于一条直线 $y=k$ 取 $\min$，但是经过了几次 $2$ 操作后...

Posted by WrongAnswer_90's Blog on February 22, 2024

CF235C Cyclical Quest

题解

更好的阅读体验 CF235C Cyclical Quest SAM 做法：对于主串建 SAM，然后 parent tree 上 DP 出 $f_i$ 表示节点 $i$ 后缀等价类的出现次数。询问先用 KMP 求最小循环元 $m$，然后接下来需要把 $[1,n],[2,n]\dots[m-1,n+m-1]$ 扔进 SAM 里跑。暴力显然过不去，但是跑完一次可以删去最开始的字符然后继...

Posted by WrongAnswer_90's Blog on February 4, 2024

CF1730F Almost Sorted

题解

更好的阅读体验 CF1730F Almost Sorted 挺有意思的一道题。刚看到可能有好几种思路，按照 $p$ 的大小填 $q$，或者按照下标顺序填等等。试了几次之后考虑按照 $i$ 从小到大填入 $q_i$，设 $pos$ 为当前填了的最大的 $p_{q_i}$，由于题目的要求，$1\sim(pos-m-1)$ 的所有数一定都用过（$p_{q_j},j<i$）。所以...

Posted by WrongAnswer_90's Blog on February 4, 2024

2023 Luogu 省选计划

模拟赛

Day 1 1. 星辰对合排列的限制是假的，因为 $P$ 的逆序对等于 $P$ 的逆排列的逆序对，非对合排列之间构成双射。考虑生成函数： \[\begin{aligned} F(x)&=\prod_{i=0}^{n-1}(\sum_{j=0}^i x_j)\\ &=\prod_{i=1}^n\frac{1-x^i}{1-x}\\ &=\frac{1}{(1...

Posted by WrongAnswer_90's Blog on February 1, 2024

CF1340F Nastya and CBS

题解

更好的阅读体验 CF1340F Nastya and CBS 绷不住了，30min 写完，虚空调试 2h+/lh/lh。如果要准确做的话太困难了，考虑 hash。多次区间询问，考虑线段树。一个区间如果内部合法，把内部能匹配的都匹配上，一定是左边一段右括号加上右边一段左括号。节点需要记录左边长度，右边长度和左右分别的 hash 值。合并的时候，如果左儿子和右儿子有内部不合法的情...

Posted by WrongAnswer_90's Blog on January 19, 2024

P6105 [Ynoi2010] y-fast trie

题解

更好的阅读体验 P6105 [Ynoi2010] y-fast trie 首先把所有数对 $C$ 取模，分类讨论： $x+y\geq C$ 因为只会取模一次，这时显然取最大值和次大值。 $x+y<C$ 一开始的想法是对于每一个数 $a$ 找到另一个数满足 $a+b<C$ 的最大的 $b$，这样是一棵外向树（环长一定 $=2$），修改如果修改到入度比较大...

Posted by WrongAnswer_90's Blog on January 18, 2024

根号分治

学习笔记

根号分治的核心思想是平衡。板子题。很容易想到两种暴力：一是不做预处理，每次询问暴力查询，这样复杂度是 $\mathcal O(q\times \dfrac{n}{p})$。二是预处理每个池子的值，每次 $\mathcal O(1)$ 查询，复杂度为 $\mathcal O(np)$。观察两个式子，由于 $q,n$ 同阶，结合以下两种算法，发现可以平衡一下 $p$ 的取值，只预处理 $...

Posted by WrongAnswer_90's Blog on January 10, 2024

CF1550F Jumping Around

题解

更好的阅读体验 CF1550F Jumping Around 提供一个不用动脑子的方法。首先题目可以看成是求一个点到 $s$ 的最小瓶颈路，设这个值为 $v_i$，自然想到最小生成树，但是边数是 $\mathcal O(n^2)$ 的，不可接受。考虑使用 prim，一开始联通块里只有一个点 $s$，每次新加入距离联通快距离最小的一个点，问题在于如何找到全局最小值。直接求肯定没...

Posted by WrongAnswer_90's Blog on January 10, 2024

CF1801F Another n-dimensional chocolate bar

题解

更好的阅读体验 CF1801F Another n-dimensional chocolate bar 高妙的数论分块优化 DP。第一步设计状态就有很大问题，如果直接设 $f_{i,j}$ 表示前 $i$ 个数成绩为 $j$ 那就死了。这完全没有利用到整除的性质。正确做法是设 $f_{i,j}$ 表示前 $i$ 个数把 $k$ “削”成了 $j$（要求 $\prod_{k=i+1}^...

Posted by WrongAnswer_90's Blog on January 6, 2024

ARC150F Constant Sum Subsequence

题解

更好的阅读体验 [ARC150F] Constant Sum Subsequence 很有意思的题。设 $nex_{i,j}$ 表示位置 $i$ 后面的最小的满足 $k>i\wedge a_k=j$ 的 $k$，则问题可以抽象为： \[f_i=\max_{j=1}^inex_{f_{i-j},j}\] 直接做是 $\mathcal O(S^2\log S)$ 的。这个东西也...

Posted by WrongAnswer_90's Blog on January 5, 2024

P9678 [ICPC2022 Jinan R] Tree Distance

题解

更好的阅读体验 P9678 [ICPC2022 Jinan R] Tree Distance 支配对，不是非常难。显然如果 $a\leq b<c\leq d$ 且 $dis(a,d)>dis(b,c)$ 则点对 $(a,d)$ 是无用的，猜想点对数不会太多，事实也正是如此。树上距离是很复杂的东西，考虑简化：使 $root$ 为根，暂且让 $dis(x,y)=dep_x...

Posted by WrongAnswer_90's Blog on January 3, 2024

CF566C Logistical Questions

题解

更好的阅读体验 CF566C Logistical Questions 好强的题，感觉完全想不到。如果对于每个点都计算答案的话复杂度是 $\mathcal O(n^2)$，但是由于题目中给了一个 $\frac{3}{2}$ 次方这么一个非常恶心人的东西，这个算法基本没有优化空间，所以考虑换一种思路，先选择一个点，然后尝试对答案进行调整。对于一个点，它的答案是： \[f(u)=\...

Posted by WrongAnswer_90's Blog on December 29, 2023

P5163 WD与地图

题解

更好的阅读体验 P5163 WD与地图喵喵题，但其实没有那么难。删边倒序转成加边是显然的，询问可以通过值域线段树合并实现，修改，合并，查询都是好做的。考虑如何维护动态加边的 SCC。难点是每个时刻缩点后的图是一个 DAG，并不像无向图的搜索树一样好维护，而且新加入的边可能不会立刻构成 SCC 而是和再之后加入的边构成。简化问题，可以通过计算出每条边被并到某个 SCC 里的时...

Posted by WrongAnswer_90's Blog on December 27, 2023

P9361 [ICPC2022 Xi'an R] Contests

题解

更好的阅读体验 P9361 [ICPC2022 Xi’an R] Contests 首先观察一下性质，每个 $l$ 在每场比赛里一定是对应着某个前缀。发现题目要求的是最小的满足要求的 $l$，最暴力的大概是维护五个指针，每次答案 $+1$，然后尝试跳一步，什么时候某个前缀包含了 $x$ 当前的计数器就是答案。考虑如何优化。这个东西显然满足单调性，首先想到的是二分答案或者整体二分之...

Posted by WrongAnswer_90's Blog on December 22, 2023

SP19543 GSS8 - Can you answer these queries VIII

题解

更好的阅读体验 SP19543 GSS8 - Can you answer these queries VIII fhq + 二项式定理。提供一个不太一样的思路。默认下标从 $1$ 开始。首先插入删除，区间查询，想到可以平衡树维护或者离线下来做线段树。本文中是用的是 fhq，好写一些。 $k$ 非常的小，考虑对于每一个 $k$ 的答案如何维护。观察答案的式子： \[ans_k=\...

Posted by WrongAnswer_90's Blog on November 28, 2023

SP1557 GSS2 - Can you answer these queries II

题解

SP1557 GSS2 - Can you answer these queries II 更好的阅读体验扫描线。把询问挂在右端点上，扫描右端点，纵轴仍为序列维。对于这种出现多次的数只算一次的，记 $pre_i$ 表示 $i$ 这个值上一次的出现位置，套路化的可以强制让出现多次的在 $pre_i<l\wedge i$ 统计，用二维线段树状物维护，但是这道题可以做的更简单。 ...

Posted by WrongAnswer_90's Blog on November 27, 2023

P9447 [ICPC2021 WF] Spider Walk

题解

更好的阅读体验很有意思的一道题。设 $f_i$ 表示第 $i$ 根线的答案，首先有一个关键结论：任意两根相邻的线答案只差一定小于 $1$。原因显然，可以在无限远的地方加一根线来构造。该结论可以扩展一下，对于距离为 $d$ 的两根线，答案之差不会超过 $d$。考虑进行倒着加线，考虑加了一根线会有什么影响：首先会把这两根线的答案交换，然后用上面的结论去更新答案。对于交换的两根线，...

Posted by WrongAnswer_90's Blog on November 27, 2023

Min_25 筛

学习笔记

My Blogs 杜教筛是一种能在 $\mathcal O(n^{\frac 2 3})$ 的时间复杂度内求积性函数前缀和的筛法。虽然复杂度比较优秀，但是被筛的积性函数需要满足特殊性质。 Min_25 筛由 Min_25 发明，相对更通用，其时间复杂度为 $\mathcal O(\frac{n^{\frac 3 4}}{\log n})$。首先构造一个完全积性函数 $f’(x)$ 满...

Posted by WrongAnswer_90's Blog on November 20, 2023

P7560 [JOISC 2021 Day1] フードコート

题解

P7560 [JOISC 2021 Day1] フードコート更好的阅读体验神奇的换维扫描线。直接做感觉十分困难，因为是区间操作，并且清空到 $0$ 之后就不再清空，查询不好处理到底是第几个人。但是如果知道了这个点的操作序列，问题就简单很多。询问是单点查询并且可以离线。综合上面所有因素，考虑换一维扫描线：对序列维扫描，横轴为序列维，纵轴为操作序列即时间维。一个操作 $1,2$，...

Posted by WrongAnswer_90's Blog on November 7, 2023

Min-Max 容斥

学习笔记

My Blogs 核心公式 \[\begin{aligned} \max_{i\in S}x_i=\sum_{T\subseteq S}(-1)^{\lvert T\rvert-1}\min_{j\in T}x_j\\ \min_{i\in S}x_i=\sum_{T\subseteq S}(-1)^{\lvert T\rvert-1}\max_{j\in T}x_j\\ \end{al...

Posted by WrongAnswer_90's Blog on November 3, 2023

P1411 树

题解

P1411 树更好的阅读体验简单 DP，但是毒瘤。开高精还卡空间。。树形 DP。只关心根节点所处连通块大小，自然记 $f_{i,j}$ 表示以 $i$ 为根的子树中和 $i$ 联通的 $j$ 个点的贡献还没有被计算的答案。这里没有被计算的意思是实际的值为 $j\times f_{i,j}$，只计算了其他连通块的贡献。转移类似树形背包，两种情况：断 $(i,to)$ 边和保留。 ...

Posted by WrongAnswer_90's Blog on November 1, 2023

CF1039D You Are Given a Tree

题解

CF1039D You Are Given a Tree 更好的阅读体验一种神奇套路：对答案根分，根分的依据是链的长度和答案大致是一个成反比的关系。考虑确定了 $k$ 怎么做。因为一个点只能在一条链里，所以 dfs 的时候如果能拼成一条链就一定会拼成一条链，不然就把贡献传给父亲继续尝试。对于 $k$ 比较小的时候可以暴力计算。对于 $k$ 较大的情况，发现答案一定非严格单减，并...

Posted by WrongAnswer_90's Blog on November 1, 2023

CF1891F A Growing Tree

题解

CF1891F A Growing Tree 更好的阅读体验有点诈骗。好多人都写的 LCT，但是这题其实连树剖都不需要。提供一个简单的单 $\log$ 小常数做法。动态加点是假的，可以离线下来得到最后树的结构，记一下 dfn 序。一个操作对一个点有可能贡献当且仅当操作在加点之后进行。所以我们把询问从后向前扫一遍，扫到加点就记录这个点的答案为此时的点权，子树加就直接子树加，B...

Posted by WrongAnswer_90's Blog on October 31, 2023

P8476 「GLR-R3」惊蛰

题解

P8476 「GLR-R3」惊蛰更好的阅读体验好厉害的题。去年打比赛拿了 60 暴力，今年考古补了。首先有结论 $\forall i\in[1,n],\exists b_i=a_j$，可以类似归纳法的方式证明。证明：对于 $i=1$，若 $b_1\geq a_1$，则令 $b_1$ 为最大的 $a_j$ 最优。若 $b_1<a_1$，则令 $b_1$ 为小于 $...

Posted by WrongAnswer_90's Blog on October 28, 2023

SP10570 LONGCS - Longest Common Substring

题解

SP10570 LONGCS - Longest Common Substring 更好的阅读体验提供一个后缀数组解法。多字符串，中间加分隔符然后后缀排序求出 $sa$ 和 $height$。把每个字符串对应的位置染上颜色，问题变为寻找 $i,j$ 使得区间 $[i,j]$ 包含 $n$ 种颜色并且 $\min_{k=i+1}^{j}height_k$ 最大。可以从后向前扫一遍，枚...

Posted by WrongAnswer_90's Blog on October 27, 2023

P5901 [IOI2009] Regions

题解

P5901 [IOI2009] Regions 更好的阅读体验根号分治，过掉不难，但是想 $\mathcal O(n\sqrt n)$ 还是有一些思维含量的。经过思考，发现 polylog 十分困难，考虑根号的算法。首先有一种暴力：预处理两两颜色间的答案，$\mathcal O(1)$ 查询。首先枚举颜色数，然后每种颜色 $\mathcal O(n)$ 扫一遍，这样预处理的复杂...

Posted by WrongAnswer_90's Blog on October 26, 2023

P4182 [USACO18JAN] Lifeguards P

题解

P4182 [USACO18JAN] Lifeguards P 更好的阅读体验提供一个比较优秀大常数的时间 $\mathcal O(nm)$，空间线性的做法。由于变量名冲突，本文中 $m$ 均指题目中的 $k$。推推性质，发现若区间包含了另一个区间，则一定删掉被包含的区间，正确性显然。这样我们得到了一些左右端点都递增的线段。将端点从小到大排序，很自然的设 $f_{i,j}$ 表...

Posted by WrongAnswer_90's Blog on October 26, 2023

CSP2023 游记

游记

Day 0 中午 12 点多出发，车上一开始 lgx，larry76 和 dwt 在打雀，我在旁边看，后来上手两把，我和 dwt 噶噶自摸，larry76 表示没有任何游戏体验，最后他甚至点了个一炮双响，我还是七对子。打的非常爽，感觉 rp 要掉光了。晚上吃饭，感觉比学校食堂好吃。去试机，幸运的抽到了 win10，嘎嘎好用，但是键盘键位有点阴间，试了试 debug 能用，打缺省源的...

Posted by WrongAnswer_90's Blog on October 20, 2023

CF513G3 Inversions problem

题解

CF513G3 Inversions problem 更好的阅读体验推式子题。 task 1 直接爆搜，统计每种结果的答案，最后加在一起除以总方案数。 task 2 数据范围变大，显然不能记录整个数组的状态，考虑拆位算贡献。设 $f_{i,j,k}$ 表示交换了 $k$ 步，$(i,j)$ 构成一对逆序对的概率，直接暴力枚举 $i,j$ 和反转区间的两个端点暴力 $\mathc...

Posted by WrongAnswer_90's Blog on October 18, 2023

ABC301Ex Difference of Distance

题解

AT_abc301_h [ABC301Ex] Difference of Distance 更好的阅读体验一道基础图论，很好口胡，但是实现不太简单。考虑离线，把询问挂在边上，按边权从小到大处理。处理到一个边权时，把边权小于它的边的两端用并查集合并，对于等于这个边权的边在并查集上建图，跑一边 tarjan，因为问的是边，所以把边双锁点。对于当前的边权，一个询问的答案是 $1$...

Posted by WrongAnswer_90's Blog on October 16, 2023

CF585F Digits of Number Pi

题解

CF585F Digits of Number Pi 更好的阅读体验观察数据范围，考虑数位 DP。首先把长串中 $len\geq\lfloor \frac{d}{2}\rfloor$ 的串提出来，塞进一个 trie 里，然后建立 ACAM，然后直接 DP 就行了。设 $f_{i,j,0/1,0/1,0/1}$ 表示当前在 trie 图上走了 j 步到达了第 i 个节点，是否已经...

Posted by WrongAnswer_90's Blog on October 15, 2023

P7600 [APIO2021] 封闭道路

题解

P7600 [APIO2021] 封闭道路 APIO 从 CF 搬的题，模拟赛又搬了一遍/jy。首先考虑暴力怎么做，即做 $n$ 次树形 DP，设 $f_{i,0}$ 表示强制删掉 $(i,fa_i)$ 这条边的最小代价，$f_{i,1}$ 表示强制保留 $(i,fa_i)$ 这条边的最小代价。对于一个点 $u$，在限制度数为 $x$ 时，对于 $f_{i,0}$ 需要删 $deg...

Posted by WrongAnswer_90's Blog on October 14, 2023

P4099 [HEOI2013] SAO

题解

P4099 [HEOI2013] SAO 很有意思的一道题。考虑树形 DP。首先考虑的是 $f_i$ 表示 $i$ 为根的子树内合法的拓扑序数量，但是这样合并子树的时候是无法计算的，如下图：假设 $1$ 当前合并了 $3$ 这棵子树，接下来要合并红色和蓝色的部分，此时 $2$ 必须在 $1$ 之后挑战，但是方案数并不是简单地两个 $f$ 值相乘，观察可以发现 $5,4,7$ 号...

Posted by WrongAnswer_90's Blog on October 12, 2023

P7782 「MCOI-Zero - AC6-M03」 Sipli Field

题解

P7782 「MCOI-Zero / AC6-M03」 Sipli Field 更好的阅读体验单 log 淀粉做法。回想正常淀粉计算的是树上的路径问题，但题目中要求计算经过每个点的答案，这样我们选取重心后一棵子树对另一棵子树的答案就会少算，所以我们淀粉时不仅要算根的答案，也要考虑子树间的相互贡献。首先以根为重心 dfs 一遍统计出 $f_i$ 表示深度为 $i$ 的点有多少个，...

Posted by WrongAnswer_90's Blog on October 11, 2023

P4652 [CEOI2017] One-Way Streets

题解

P4652 [CEOI2017] One-Way Streets 基础图论。题目中是关于无向图边方向的问题，而边双有一个优秀的性质：边双内的任意两点间至少有两条不经过同样的边的路径，因此对于边双内的边无论有没有题目中 $x$ 能走到 $y$ 的限制，它的方向都是不能确定的，因此首先边双缩点把问题转化为树上问题。对于限制条件，从 $x$ 到 $y$ 的树上路径是唯一的，所以把这些边的...

Posted by WrongAnswer_90's Blog on October 9, 2023

CF1878G wxhtzdy ORO Tree

题解

CF1878G wxhtzdy ORO Tree 设 $f(x,y)$ 表示树上 $x$ 到 $y$ 简单路径上的点权或和中 $1$ 的个数。有一个性质：选取的 $z$ 节点一定满足它比它左边的点（$l$）或者右边的点（$r$）的贡献至少要多一位，即 $f(x,l)<f(x,z)$ 或 $f(y,r)<f(y,z)$，有了这个性质，问题就简单很多了。即 $d_{i,...

Posted by WrongAnswer_90's Blog on October 9, 2023

CF1878F Vasilije Loves Number Theory

题解

CF1878F Vasilije Loves Number Theory 首先约数个数是积性函数，题目中要求 $\gcd(n,a)=1$，所以 $a$ 和 $n$ 互质，$n=d(a)d(n)$ ,于是问题转化为 $n$ 是否整除 $d(n)$。观察题目，$n$ 可能会非常大，但这也启发我们把它质因数分解来存储，而对于 $d(n)$ 直接用一个变量 $ans$ 存下来，考虑 $n\ti...

Posted by WrongAnswer_90's Blog on October 9, 2023

CF125E MST Company

题解

CF125E MST Company 对于一类凸函数，有时我们寻找极值是简单的，但如果加上一维限制，问题就变成了函数在某个特定位置的值，这时问题不好处理 wqs 二分通过二分斜率后寻找极值，可以用复杂度加一只 $\log$ 的代价消去一维的限制。具体来说，在本题中，设以 $1$ 为端点的边为特殊边，以特殊边选的个数横坐标，对于 MST 的权值作为纵坐标，可以得到一个下凸的函数（感性理...

Posted by WrongAnswer_90's Blog on October 9, 2023

DDCC2020D Parsey

题解

AT_ddcc2020_final_d Pars/ey 重工业题。找环然后树形 DP 是显然的，先考虑断开环上的边怎么做。把环复制一遍放在结尾，记 $sum_i$ 为环长的前缀和，$f_i$ 为该子树内的最长根链的长度，问题变为每次给定一个区间，要求找到 $i,j(i>j)$ 使得 $sum_i-sum_j+f_i+f_j$ 最大，可以使用线段树实现。注意要与同一棵树里的直径...

Posted by WrongAnswer_90's Blog on September 23, 2023

P6961 [NEERC2017] Journey from Petersburg to Moscow

题解

P6961 感觉很神奇的题。一条路径的代价是前 $k$ 大的边的权值和，有个假的做法是每个点维护一个堆，表示走到这个点前 $k$ 大边的权值，读者可以思考一下这个做法为什么是假的。既然直接最短路不好处理，自己观察性质，可以发现前 $k$ 条边权值和等价于每条边边权变为 $\max(val-val_k,0)$，然后跑最短路后 $dis_n+k\times val_k$。一开始的想...

Posted by WrongAnswer_90's Blog on September 19, 2023

P3533 [POI2012] RAN-Rendezvous

题解

P3533 [POI2012] RAN-Rendezvous 题目大意：给定外向树森林，每次给定两个起始点，求两个点沿边移动最少步数相遇。 $n$ 个点，$n$ 条边，并且每个点有唯一的出边，显然构成了多棵基环树，对于每个基环树分别处理：找出环上的点，因为要求支持求出任意两点距离，前缀和一下即可。对于询问，如果在两棵不同的基环树上（具体判断使用并查集），那么一定无解。如果在一棵基环树...

Posted by WrongAnswer_90's Blog on September 9, 2023

CF231E Cactus

题解

CF231E Cactus 点仙人掌的性质：每个点最多只在一个环里。对于 $u,v$ 之间的路径，显然一定是由一些链和一些环拼接而成的。对于链，只能按照唯一的方式行走。对于环，有两种走的方案：顺时针和逆时针走。各个环间互不影响，乘法原理得到答案就是 $2$ 的环个数次方。边双所点后维护前缀和，变成树上 LCA 问题，倍增或树剖或 tarjan 即可。 1 2 3 ...

Posted by WrongAnswer_90's Blog on August 28, 2023

P6302 [NOI2019] 回家路线加强版

题解

P6302 [NOI2019] 回家路线加强版斜率优化好题。观察后猜想应该是 dp。经过思考发现如果以点为状态，在时间这一维上是存在后效性的，而如果开二维数组 $f_{i,j}$ 表示在第 $j$ 个时刻到了 $i$ 个点过不去加强版，考虑以列车为状态。题目有两个限制，一是出发点和结束点的限制，即上一辆车的 $y$ 是下一辆车的 $x$，二是时间的限制，即上一辆车的 $q$ 要...

Posted by WrongAnswer_90's Blog on August 27, 2023

CF1763F Edge Queries

题解

CF1763F Edge Queries 圆方树板子题，这题真的有3000吗。首先想到的是缩边双，但是以下情况边双不好处理：点 $2,3,4$ 在一个边双里，缩点之后该边双在 $1$ 到 $6$ 的路径上，但是显然 $(2,3),(3,4),(2,4)$ 这三条边并不属于 $1$ 到 $6$ 的路径。考虑建立圆方树，定义方点的权值为它所代表的边双中边的数量（只有一条边时权值...

Posted by WrongAnswer_90's Blog on August 27, 2023

P3521 [POI2011] ROT-Tree Rotations

题解

P3521 [POI2011] ROT-Tree Rotations 首先合并两棵子树的时候只关心子树内值的个数，并不关心子树内具体是什么顺序，引导从下向上线段树合并计算代价。每一个值只会出现一次，首先每个叶子节点开一棵动态开点值域为 $1-n$ 的线段树维护，初始只有自己的值的位置为 $1$。然后对于每个非叶子节点，从下至上合并，两棵子树有两种方案，计算时使用 $sum1$ 和 ...

Posted by WrongAnswer_90's Blog on August 26, 2023

P5904 [POI2014] HOT-Hotels 加强版

题解

自然的想法是枚举共同的交点，然后进行换根 dp，复杂度可以做到 $\mathcal O(n^2)$，可以通过简单版，但是显然过不了 $10^5$ 的数据，考虑进行优化。记 $(x,y,z)$ 为满足要求的点，即满足 $a=b+c$，树形 dp 原则是子树内的信息无后效性，尽量把子树内的信息合并在一起。所以 $a-b=c$，在这个等式种，$a-b$ 和 $c$ 在以 $2$ 为根的两棵...

Posted by WrongAnswer_90's Blog on August 25, 2023

CF1862F Magic Will Save the World

题解

bitset 优化可行性 DP。注意到所有怪物需要魔法的和是一定的，问题转为判定是否能够恰好消耗 $i$ 点水魔法和 $sum-i$ 点火魔法，用 $f_i$ 表示这种分割方案是否可行，直接 dp 大概率会超时，使用 bitset 优化即可，最后根据 $f_i$ 统计答案。代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 int T,A,B,n,minn,su...

Posted by WrongAnswer_90's Blog on August 25, 2023

CF1662C European Trip

题解

My Blogs CF1662C European Trip 感觉很不错的矩阵乘法加速题。从 $n,k$ 的数据范围大致可以看出是矩阵乘法加速递推。设 $f_{k,u,v}$ 表示从 $u$ 走到 $v$ 走了 $k$ 步的合法方案数，初始状态 $f_1$ 即为邻接矩阵，最终答案为 $\sum_{i=1}^{n} f_{k,i,i}$。正常的转移方程为 $f_{k,u,v}=...

Posted by WrongAnswer_90's Blog on August 24, 2023

基础计数

学习笔记

My Blogs 开个新坑，目前大多数是蓝书上的题。不会更高级的东西，只写怎么数数，不考虑高级优化。状态设计：这里满足的要求不再是无后效性，而是要求一个阶段的所有状态能不重不漏的覆盖掉所有情况。转移：寻找合适的基准点，围绕这个基准点把大的状态拆出一个小的不可划分的状态，和剩下的状态进行计算（一般是乘起来）。过河卒plus 基础题。黑色格子很少，但是棋盘大小非常大，做法应当...

Posted by WrongAnswer_90's Blog on October 10, 2022