20260715

P6627 [省选联考 2020 B 卷] 幸运数字

P6627 [省选联考 2020 B 卷] 幸运数字。

这道题离散化附近的点，然后差分就行了。

为什么我要写线段树？

P7514 [省选联考 2021 A/B 卷] 卡牌游戏

P7514 [省选联考 2021 A/B 卷] 卡牌游戏。

这道题直接做不好做，所以我们考虑在值域上面做。

我们把 abab 放在数轴上排序，然后我们利用双指针维护可行的区间，最后答案就是最小的。

这个区间需要保证 aa 的个数不能太少。

P5283 [十二省联考 2019] 异或粽子

P5283 [十二省联考 2019] 异或粽子。

首先，先前缀和，val(l,r)=sl−1⊕srval(l,r)=s_{l-1}\oplus s_r。

转化为给定一个长度为 n+1n+1 的数组 sis_i ，求 i<ji<j 时， si⊕sjs_i\oplus s_j 的取值中前 kk 大的值的和。

然后这个 i<ji<j 的限制很不好，所以我们先忽略掉，考虑 k×2k\times 2 然后最后再把答案除回去。

然后我们可以把这些值放到 trie 上面。维护一个大根堆，对中维护现有的每一个 sis_i 与其他值异或的最大值，取出一个之后需要放进下一大的值。

20260716

P5268 [SNOI2017] 一个简单的询问

P5268 [SNOI2017] 一个简单的询问。

暴力莫队 + 循环展开可以过。

正解的话需要容斥，然后就变成了 rr 以内的这种形式拆成了四部分。

把每一个问题拆成四部分，每一次处理的就是 ll 以内与 rr 以内的相互贡献。

P4324 [JSOI2016] 扭动的回文串

P4324 [JSOI2016] 扭动的回文串。

我们可以发现，选定一个中心点，可以贪心地一直向右在同字符串匹配，直到不行了再在另一个字符串匹配。

P3349 [ZJOI2016] 小星星

P3349 [ZJOI2016] 小星星。

首先容易想到 fi,j,sf_{i,j,s} 表示第 ii 个点编号为 jj，其子树用了的集合为 ss。

由于要枚举子集，所以复杂度带有 O(3n)O(3^n)。我们需要优化掉子集的枚举。

如果直接去掉这个限制，答案会因为编号重复而变大，我们需要尝试容斥掉。容斥的方法是枚举整棵树的子集，然后需要让树上所有的点的编号都在这个子集中。

20260717

P5358 [SDOI2019] 快速查询

P5358 [SDOI2019] 快速查询。

我甚至维护了 ax+bax+b 的 aa 和 bb。。。

不过需要注意乘 00 的情况。

我的写法不特判可以过原数据，但是过不了 Hack。

P6619 [省选联考 2020 A/B 卷] 冰火战士

P6619 [省选联考 2020 A/B 卷] 冰火战士。

首先，我们需要画出的图像是前缀和的，我们需要让两者最小的点最大。所以我们肯定要选取交点或者靠近交点的点。

直接二分是两个 log⁡\log 的，过不了，所以我们需要改成一个 log⁡\log 的算法。然后用到一个叫树状数组二分的东西，这个的本质就相当于利用之前算过的东西。

不要对着错误的思路（例如三分）一直想。

P5319 [BJOI2019] 奥术神杖

P5319 [BJOI2019] 奥术神杖。

首先拆根号，方法就是左右同时 ln⁡\ln：

ln⁡Ans=1c∑i=1cln⁡wi\ln\mathrm{Ans}=\frac{1}{c}\sum_{i=1}^{c}\ln w_i

为了去掉 1c\frac{1}{c}，可以变成 0/1 分数规划问题。我们需要让这个大于 00。注意不要写成 ≥\ge 了，不然会有全 $$ 咒语

∑i=1c(ln⁡vi−mid)\sum_{i=1}^c \left(\ln v_i-mid\right)

fi,jf_{i,j} 表示到了第 ii 位，在节点 jj 的最大值。

20260718

P5329 [SNOI2019] 字符串

P5329 [SNOI2019] 字符串。

哈希 + 二分。预处理一点东西就行了。

还可以这样。

P5300 [GXOI/GZOI2019] 与或和

P5300 [GXOI/GZOI2019] 与或和。

我们把问题转化成只有 0/10/1 的矩阵，然后我们发现对于每一行，拥有一些高度不同的柱子，我们需要计算有多少种矩阵。可以直接用单调栈做。

还有 31n331n^3 暴力可以过。。。

P6640 [BJOI2020] 封印

首先这道题肯定要用 SA 这种东西。

我们可以把 t 拼在 s 前面，然后中间放一个分隔符。我们需要对于每一个 ss 的后缀在 tt 中找一个点让这个点和 ss 的这个后缀的 LCP 最大。

然后查询 [l,r][l,r] 就是二分答案，如果 [l,r−mid+1][l,r-mid+1] 中的那个 LCP 最大值为 midmid 就是可以的。

20260720

P7521 [省选联考 2021 B 卷] 取模

P7521 [省选联考 2021 B 卷] 取模。

暴力可以随便过。

首先肯定是排序 + 双指针，然后 n^2 log 分析复杂度，发现这个是斐波那契数列。

P4587 [FJOI2016] 神秘数

P4587 [FJOI2016] 神秘数。

首先容易想到，需要从小到大，对于所有的 ii，s[i]>=a[i+1]−1s[i]>=a[i+1]-1 ，第一个不满足的 s[i]+1s[i]+1 就是答案。

然后考虑用主席树维护，对于一个 ansans，如果小于等于 ansans 的数的和比 ansans 大，那么 ans=res+1ans=res+1。

因为比如现在 ansans 合法，我们把 [1,ans][1,ans] 以内的添加都合法。由于这个类似扩倍（或者斐波那契），比如到了 ii 加的至少就是 ii 了，所以复杂度正确。

P6622 [省选联考 2020 A/B 卷] 信号传递

P6622 [省选联考 2020 A/B 卷] 信号传递。

问题转化：我们可以把一条变的贡献拆成两部分。

对于点 xx，有 x→yx\to y，如果 x≤yx\le y 代价为 kk 否则是 −1-1，反过来就是 kk 和 11，然后最后就对于每一个点的代价乘坐标。

预处理 g(i,s)g(i,s) 表示 ii 前面的点集为 ss 的时候对答案的贡献。然后：

f(s)+g(i,s)→f(s∪{i})f(s) + g(i,s) \to f(s\cup\{i\})

gg 的空间会炸掉，但是我们可以发现转移中 ii 不能在 ss 里面，于是就行了。

还可以用：二进制从 00 数到 nn，所有比特位变化的总次数为 O(n)O(n)。

P5770 [JSOI2016] 无界单词

P5770 [JSOI2016] 无界单词。

首先第一个问可以直接 dp：

pi=2i−∑m=1⌊i/2⌋pm⋅2i−2mp_i=2^i-\sum_{m=1}^{\lfloor i/2\rfloor} p_m\cdot 2^{i-2m}

对于第二问，我们一次决定每一位，然后尝试 a 里面的够不够，不够就去 b。

对于确定到了 ii，我们设 fjf_j 表示长度为 jj 的最短 border 能构成的无界单词的方案数。

当 j≤ij\le i 可以直接用 kmp 做，j>ij>i 的时候：

fj=2(j−i)−∑t=1⌊j/2⌋ft×2 j−max⁡(i,t)−tf_j = 2^{(j-i)} - \sum_{t=1}^{\lfloor j/2 \rfloor} f_t \times 2^{\,j - \max(i, t) - t}

计算答案也是同理，容斥即可。

首先这道题需要用 kmp 和容斥优化 dp。我们对于第二问，看当前位填 a 的方案数来决定填什么。至于方案数，设 fjf_j 表示长度为 jj 的最短 border 能构成的无界单词的方案数。我们可以通过减去重复的来转移，就减去其 border 构成的更短的。

P5303 [GXOI/GZOI2019] 逼死强迫症

P5303 [GXOI/GZOI2019] 逼死强迫症。

设 gig_i 表示没有 1*1 的时候的答案（hh 表示其前缀和），fif_i 表示本题的答案：

fi=fi−1+fi−2+2gi−1−2f_i = f_{i-1} + f_{i-2} + 2g_{i-1} - 2

因为如果当前是 1*1，左边的 1*1 之后的只有一种，之前的随便。

然后这个可以用矩阵快速幂优化。还有斐波那契数列的前缀和是 fi+2−1f_{i+2}-1。

P3246 [HNOI2016] 序列

P3246 [HNOI2016] 序列。

单调栈 + 莫队 + 主席树应该很好想。

单 log⁡\log 的做法：

我们先观察到可以在最小值的位置将序列拆开。

用单调栈找出左边和右边第一个小于 aia_i 的位置。

然后定义 frifr_i 表示以 ii 为右端点，所有左端点 ≤i\le i 的子区间的最小值之和。flifl_i 表示以 ii 为左端点，所有右端点 ≥i\ge i 的子区间的最小值之和。

然后对于询问，利用最小值拆分，还有 flfl 和 frfr 的前缀和计算。

20260722

P3745 [六省联考 2017] 期末考试

P3745 [六省联考 2017] 期末考试。

注意 nn 和 mm 不要写反。

P4064 [JXOI2017] 加法

P4064 [JXOI2017] 加法。

呃呃呃，竟然是简单题，应该做这道题的。

首先肯定是二分，我们二分答案，然后从左往右扫，对于每一个 aa 选择能覆盖到更右边的点的区间。

然后用树状数组维护 aa，大根堆维护最优区间。

P4067 [SDOI2016] 储能表

P4067 [SDOI2016] 储能表。

我的想法是每一个数值的出现次数的种数很少，于是直接二分维护，再利用数位 dp。但是需要 10s10s 倍卡常了。

所以我们换一种做法。我们考虑直接数位 dp。需要维护的是异或值大于 kk 的对数和异或和。

然后设 fi,a,b,cf_{i,a,b,c} 表示考虑到了第 ii 位，第一个数的第 ii 位是否比 nn 小，第二个数的第 ii 位是否比 mm 小， 异或起来是否比 kk 小的异或和。

P3267 [JLOI2016/SHOI2016] 侦察守卫

P3267 [JLOI2016/SHOI2016] 侦察守卫。

状态设计对了，但是转移写复杂了。这道题的转移就是依次转移每一个子树，然后把子树的贡献加在现有的东西里面。转移的时候决定哪个方向贡献了 11。

还有一个技巧就是状态设计成 ii 以内的会好一些。

P6628 [省选联考 2020 B 卷] 丁香之路

P6628 [省选联考 2020 B 卷] 丁香之路。

我们可以转化成欧拉回路的一些东西。

题目要求给定的边的 degdeg 需要是 22 的倍数，起点的需要是奇数。

我们先用给定的边和起点到终点的边，然后要求所有的点 degdeg 都是偶数。

然后我们还需要使用贪心，把每一个度数为奇数的点和下一个点相连，这样一定是最优的。然后如果最后的图不联通，就用并查集锁点，求最小生成树。

P5768 [CQOI2016] 路由表

P5768 [CQOI2016] 路由表。

首先这道题肯定是要放到 trie 树上面做，我们把一个字符串塞进 trie 里面，然后标记时间。

对于查询我们需要进行差分，问题就转化成了求 [1,x][1,x] 里面的东西了。

然后我们发现这种东西可以用类似单调栈的东西来维护。

20260724

P5340 [TJOI2019] 大中锋的游乐场

P5340 [TJOI2019] 大中锋的游乐场。

分层图最短路模板。

P5769 [JSOI2016] 飞机调度

P5769 [JSOI2016] 飞机调度。

考场的贪心可以过，只是 d[i][i]d[i][i] 需要赋成 00 最小路径覆盖问题直接把一个点拆成 ii 和 i+ni+n 然后总数 - 二分图最大匹配。

P5371 [SNOI2019] 纸牌

P5371 [SNOI2019] 纸牌。

其实这道题一步一步来就可以了，考试把部分分状态设计出来了（其实跟正解的一样），然后就去玩了。

fi,j,kf_{i,j,k} 表示前 ii 大的，其中 [i−1,i,i+1][i-1,i,i+1] 类型有 jj 个，[i,i+1,i+2][i,i+1,i+2] 类型有 kk 个。

然后关键在于，这个可以最多只用 22 次！

然后转移就比较顺其自然了：

直接用题解的，s=j+k+ls=j+k+l。

fi+1,k,l={fi,j,k⋅(⌊c−s3⌋+1),s≥ai+1fi,j,k⋅(⌊c−(s+3⋅⌈ai+1−s3⌉)3⌋+1),s<ai+1f_{i+1,k,l} = \begin{cases}f_{i,j,k}\cdot (\lfloor \frac{c-s}{3}\rfloor + 1) , s\geq a_{i+1} \\ f_{i,j,k}\cdot (\lfloor \frac{c -(s+3\cdot \lceil \frac{a_{i+1}-s}{3}\rceil )}{3}\rfloor+1) , s< a_{i+1}\end{cases}

加一个矩阵快速幂优化就行了，只是这需要分段快速幂。

其实这道题能这样做真的是因为 00 很多，而且这道题跟 00 的顺序无关。

20260725

P6620 [省选联考 2020 A 卷] 组合数问题

P6620 [省选联考 2020 A 卷] 组合数问题。

设 F(n,m)=∑k=0nkmxk(nk)F(n, m) = \sum_{k=0}^n k^mx^k\binom nk。

也就是说我们可以拆开 ff 里面每一项。

答案是 ∑iaiF(n,i)\sum_i a_iF(n, i)。

F(n,m)=∑k=0nkmxk(nk)=n∑k=0nkm−1xk(n−1k−1)\begin{aligned} F(n, m) &= \sum_{k=0}^n k^m x^k \binom nk\\ &= n\sum_{k=0}^n k^{m-1}x^k\binom {n-1}{k-1} \end{aligned}

然后：

F(n,m)=∑k=0nkmxk(nk)=∑k=0nkmxk((n−1k)+(n−1k−1))=F(n−1,m)+1nF(n,m+1)\begin{aligned} F(n, m) &= \sum_{k=0}^n k^mx^k\binom nk\\ &= \sum_{k=0}^n k^mx^k\left(\binom {n-1}k + \binom{n-1}{k-1} \right)\\ &= F(n-1,m) + \frac 1n F(n, m + 1) \end{aligned}

也就是说：F(n,m)=n(F(n,m−1)−F(n−1,m−1))F(n, m) = n(F(n, m - 1) - F(n - 1, m - 1))。

注意这个 nn 不是全局的那个。

然后就用部分分的 F(n,0)=(x+1)nF(n, 0) = (x + 1)^n。

P3760 [TJOI2017] 异或和

P3760 [TJOI2017] 异或和。

首先，这道题暴力循环展开可以过。

正解的话显然是按位拆分，然后对于这一位需要保证前缀和的那种算下来这一位是 11。

然后可以用权值树状数组维护 00 和 11。

还是需要考虑进位，因为如果低位不够，高位拿来补的时候也需要贡献。

20260806

P4364 [九省联考 2018] IIIDX

P4364 [九省联考 2018] IIIDX。

首先这道题容易想到一个贪心，然后我们可以在大样例发现过不了重复的情况，所以我们可以修改一下，就是当前这个值把这个值所有的数都放进来。

考场写了一个暴力挂了，然后就没有继续想了。正解是用线段树二分维护这个东西。

P4563 [JXOI2018] 守卫

P4563 [JXOI2018] 守卫。

首先这道题会发现一定会选 rr，然后我们对于任意 [l,r][l,r] 可以进行分段，分成很多段，然后这个可以用 dp 去优化转移。

P6793 [SNOI2020] 字符串

P6793 [SNOI2020] 字符串。

好像还简单一点，直接用 SA，我们可以用 height 数组找到代价最少的（相当于排序），然后相邻的合并，这样一直做就可以了。

20260807

P3698 [CQOI2017] 小Q的棋盘

P3698 [CQOI2017] 小Q的棋盘。

这道题我是直接用 dp，ff 表示在 ii，用了 jj 步，从 ii 回到了 ii，而 gg 是没有回来的。

题解甚至有直接用最长链的性质的。

P3702 [SDOI2017] 序列计数

P3702 [SDOI2017] 序列计数。

首先肯定很容易想到 dp：fi,j,0/1f_{i,j,0/1} 表示到了 ii， mod  p\bmod ~ p 的余数是 jj，是否用过质数。

然后矩阵快速幂可以优化，我直接左边是 00 右边是 11，转移矩阵可以分成 44 不分，根据质数/合数来分。

P3705 [SDOI2017] 新生舞会

P3705 [SDOI2017] 新生舞会。

首先很容易想到 0101 分数规划。

a1+a2+⋯+≥mid(b1+b2+⋯bn)a_1+a_2+\cdots + \ge mid(b_1+b_2+\cdots b_n)

需要 ai−=mid⋅bia_i-=mid\cdot b_i。

然后我们发现需要找到一个匹配使得权值 ≥0\ge 0。

然后考场没想到二分图最大权匹配。其实是觉得这样复杂了，意为有简单的方法。

这个的方法就很直接，费用流。。。

20260811

P6626 [省选联考 2020 B 卷] 消息传递

P6626 [省选联考 2020 B 卷] 消息传递。

想到了点分治 => 发现跟模板不一样 => 去写换跟 dp 过不了。

其实就是点分治，统计每一个重心不同子树的贡献，。用总数减去相同子树之间的贡献。

P4436 [HNOI/AHOI2018] 游戏

P4436 [HNOI/AHOI2018] 游戏。

做题做了一部分建议回首看看，可能有一些很重要的东西，思路需要清晰。

写暴力可以找感觉。首先我们需要找到每一个起点能走到的所有点。

6060 分还是很好拿的，只要 st 表数组不开小。

然后正解...很神，对于每一个起点，直接记忆化搜索暴力扩展。

先把没有锁的缩成一个块，然后对于这些块 dp，走到一个块就直接合并之前的值，这样一定是对的。于是线性复杂度...

判断钥匙有没有不要傻傻地用数组，直接判断是否在当前区间里面。

P5280 [ZJOI2019] 线段树

P5280 [ZJOI2019] 线段树。

fuf_u 表示 uu 上 tag 为 11 的线段树数量，gug_u 表示 uu 到根结点路径上没有 tag 为 11 的线段树数量。

然后根据是否覆盖/访问，标记下传分出 55 中方式转移。

20260812

P4428 [BJOI2018] 二进制

P4428 [BJOI2018] 二进制。

考场思路
C++
2 % 3 = 2
4 % 3 = 1
8 % 3 = 2
16 % 3 =1
二进制下 % 3 就是需要： 
比如 abcd： 2a+b+2c+d 这样 
然后我们需要根据 1 的个数来 

所以是不是只要可调整的数的个数 >=2 就一定有解 
就是 1 和 0 少的那一个数 

如果全是 0，一定可以，全是 1，偶数项可以 
一个 1，>=1 个 0，不可以 
一个 0，>=1 个 1，奇数项可以   
否则一定可以 
所以不可以的情况就是： 
全是 1，有奇数项 
只有 1 个 1 （和上一条需要去重） 
只有一个 0，有偶数项，（和上一条需要去重）

1. 相对简单，先把完整的求出来，再算两边 
2. 可以先把连续段的预处理出来，然后会剩下两边的 1 和中间的两段 0 
3. 也是预处理 

但是带修 
很容易想到莫队 
但是行不通，此题和位置有关 

其实拿数据结构维护上面的过程是可行的，但是很复杂了 
如果这个是正解的话，我 f**k 出题人 

能不能简化一下规律 
算了 

我想到了 ODT，应该没用。 
算了，写一个 O(n^2) 的跑路了，虽然有点复杂 
暴力都那么难写，我才不写正解

所以不合法的情况就是：

  • 全是 1，有奇数项。
  • 只有 1 个 1 （和上一条需要去重）。
  • 只有一个 0，有偶数项，（和上一条需要去重）。

为了简化代码量，我们修改一下限制：

  • 只有一个 11 的区间，00 的个数不少于 22 个。
  • 出现了奇数个 11，00 的个数为 0/10/1。

这真的是一个很神奇的合并。。。“人类智慧”。

然后我们用线段树维护不合法区间，参照题解状态设计：

dl0/1,0/1dl_{0/1,0/1} 表示强制选左端点的区间中，00 出现次数为 0/10/1，11 出现次数的奇偶性为 0/10/1 的个数，drdr 同理。

fl0/1/2fl_{0/1/2} 表示强制经过左端点，11 恰好出现 11 次，00 出现次数为 0,1,≥20,1,\ge 2 的个数，frfr 同理。

P4363 [九省联考 2018] 一双木棋 chess

P4363 [九省联考 2018] 一双木棋 chess。

记忆化搜索可以过。

P4437 [HNOI/AHOI2018] 排列

P4437 [HNOI/AHOI2018] 排列。

首先肯定需要进行问题转化。

首先如果 aj=ka_j = k 那么 kk 一定要在 jj 前面。

然后我们可以对原题建出一个形如谁在谁前面的图，也就是 k=aj→jk=a_j\to j。有环就无解。

然后就是怎么求最大值，尝试贪心，可以每次选择可以选择权值最小的点，如果它父亲没有被选，就一直和祖先捆起来。

然后怎么排序呢？

Wab=∑j=1m1(i+j)waj+∑j=1m2(i+j+m1)wbjW_{ab}=\sum_{j=1}^{m_1}(i+j)w_{a_j}+\sum_{j=1}^{m_2}(i+j+m_1)w_{b_j}

Wba=∑j=1m2(i+j)wbj+∑j=1m1(i+j+m2)wajW_{ba}=\sum_{j=1}^{m_2}(i+j)w_{b_j}+\sum_{j=1}^{m_1}(i+j+m_2)w_{a_j}

Wab−Wba=m1Wb−m2WaW_{ab}-W_{ba}=m_1W_b-m_2W_a

如果 Wab>Wba⇒Wam1<Wbm2W_{ab}\gt W_{ba}\Rightarrow \frac{W_a}{m_1}\lt\frac{W_b}{m_2}。

所以按照平均值排序就行了。用堆实现。

20260814

P7668 [JOI 2018 Final] 团子制作 / Dango Maker

P7668 [JOI 2018 Final] 团子制作 / Dango Maker。

这道题以中间为基准来转移贪心很方便。

P7669 [JOI 2018 Final] 月票购买 / Commuter Pass

P7669 [JOI 2018 Final] 月票购买 / Commuter Pass。

首先有一个很神奇的东西，我们可以建立出一个最短路径图，然后 UV 路径一定是顺着 / 逆着走一段（考试觉得这是双向图然后不会，炸了）。

然后分层图就做完了，2323 层分别是正着/反着走最短路径图。

P7670 [JOI 2018 Final] 毒蛇越狱 / Snake Escaping

P7670 [JOI 2018 Final] 毒蛇越狱 / Snake Escaping。

我们发现数据范围比较小，所以尝试看 01?01? 谁最少。如果 ?? 最少就暴力。00 最少：

我们需要先预处理出超集和，就是定义这个集合指定的为 11，剩下的随便。然后 00 的贡献就是所有 - 一定是 11。有多个 00 就用类似容斥的方法。

11 最少就同理，但是是利用子集和。