题目传送门 卧槽这题有点牛逼。 像我这种蒟蒻只看题面肯定没有什么头绪，所以只好看一眼数据范围，似乎只能依赖方案在 $O(m\log)$ 内解决。 至于为什么会想到 dp ，应该只能靠感觉吧，这题一看就很有线性dp的味道。 所以由前面的想法可以大概先设个 $f_i$ ，至于 $i$ 的含义只能结合方案的性质和所求的东西来考虑。 先整理一下：一个方案由四个参数 $T_i,L_i,R_i,C_i$确定，而我们需要最小化 $[1,n]$ 全部被覆盖的代价和。 那么 $i$ 的含义只和 $T_i,L_i,R_i$ 有关，而我们的最终状态中没有时间的限制，而 $L_i,R_i$ 在地位上是对等的，所以我们不妨只从 $R_i$ 考虑对 $i$ 含义的设计。 接下来这一步应该只能靠经验了，因为最终状态是全部覆盖，所以可以看成是由前缀全部覆盖递推而来，落到状态设计上就是设 $f_i$ 为覆盖前缀 $[1,R_i]$ 的最小代价。 这样就可以自然的写出方程： f_i=\min_{R_j-L_i+1\geq|T_j-T_i|}f_j+C_i残念ながら…这是一个有后效性的方程，似乎并不能按照某种拓扑序转移， ...

题目传送门 这题十分的顺，应该属于能一眼瞪出来的题。 首先不定数个整数异或和最大最好办法 (也有可能是唯一办法？) 就是线性基了。然后是树上路径查询问题，基本方法有两种：1. 处理每个点到根，从问题或点的性质入手，需要挖掘性质。 2.树剖，预处理加上暴力查询，相对无脑。 可以先看看简单的树剖，其做法是对树预处理 $O(\log)$ 条重链，每条重链维护该链预处理的信息并用线段树维护，而线性基确实支持 $(\log^2)$ 合并，这样一来时间复杂度就是 $O(q\log^2n\log^2 V )$ ，其中 $V$ 为值域。显然炸了。 那么只能选方法一，其实性质也很好挖，我们处理根到点的线性基，肯定希望线性基里留的都是深度较大的，而字典序的比较方式决定了深度大的尽量往高位送，然后代码也呼之欲出了。复杂度 $O(q\log^2V)$ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970 ...

代码实现和一些思路参考了一些题解。 遇到这种序列上研究大小的序列问题，应该主动考虑笛卡尔树。 对原序列建出一棵大根笛卡尔树。稍微转化一下问题的连边条件，首先每个节点必定和它的左子树同在所有点在同一个连通块，这样初步连边后可以看出连通块与连通块之间通过树上右链（从根一直向右走的链）的边进行连接，大概长这样： 其次还可能有一些连向右子树的边，而这些边连上后肯定只会使右链上相邻的若干个块合并，简单证一下：设 $x,y,z$ 为右链上的三个节点， $x$ 是 $y$ 祖先， $y$ 是 $z$ 祖先，$x,z$ 合并了而 $y$ 没有，根据连边条件，那么 $x$ 块中一定有一个节点值比 $z$ 小，由笛卡尔树性质， $y$ 又比 $z$ 大，所以 $y$ 一定能向 $x$ 连边合并，所以 $x$ 到 $z$ 之间的所有块都能和 $x,z$ 合并。 有了这个性质，统计连通块就可以变为统计右链上点满足其值小于树中出除去它的子树以外部分最小值（也就是连通块在右链上左端点）的个数，把上面结论所有推回序列上就是统计这么一个值 $v$ 的个数：若把大于 $v$ 的值看成 $1$ ，小于等于 $v$ 的值看 ...

题目描述有 $n$ 个灯笼排成一排，第 $i$ 个灯笼具有 $p_i$ 的亮度。每个灯笼要么朝向左，照亮左边编号为 $[i - p_i,i - 1]$ 的灯笼，要么朝向右，照亮右边编号为 $[i + 1, i + p_i]$ 的灯笼。 寻找一种方案，为所有的灯笼确定朝向，使得每一个灯笼被至少一个其他灯笼照亮。 Sol应该存在一种经典技巧吧，就是那种可行性DP通过某种手段（感觉最常见的是贪心）压缩一个状态维度。 看到这个题首先应该有个 $\texttt{native}$ 的想法（基于经验？）：考虑设 $f_{i,j}$ 为考虑前 $i$ 个灯笼，能覆盖前缀 $[1,j]$ 的可行性。 然后这里估计能列个方程吧，又或者是贪心的想一想，对于每个 $i$ ，显然我们只关心最大的 $j$ 使得 $f_{i,j}=1$ 。 所以重新考虑状态，设 $f_{i}=j$ 为能覆盖的最大前缀 $[1,j]$ 。 然后转移分讨一下即可。 Code1234567891011121314151617181920212223242526272829303132333435363738394041424344454 ...

赛时喜提 $\textcolor{green}{100}+\textcolor{red}{0}+\textcolor{orange}{30}+\textcolor{red}{5}=\textcolor{orange}{135}$ ，但其实真的是信心赛，毕竟我当时还没开始复习板子，写得慢很多。赛后随便一补就 $\textcolor{green}{100}+\textcolor{green}{100}+\textcolor{orange}{30}+\textcolor{gold}{65}=\textcolor{yellowgreen}{295}$ 了。 T1 Divisors水题，对每个数 $O(\sqrt n)$ 求因子，开桶开 map 算贡献即可。 123456789101112131415161718192021222324252627282930313233#include<bits/stdc++.h>using namespace std;#define fio(x) freopen(x".in","r",stdin),freo ...

首先简化问题很明显，每组有用的只有前缀最大值。 先想想贪心，不可做，因为一组的贡献会被其他组影响，所以考虑 $\texttt{dp}$ 组与组之间无序，不能沿编号轴 $\texttt{dp}$ ,考虑值域轴，每接上一个组只需要考虑当前最大值，且较大最大值一定由较小最大值转移而来，所以设 $f_i$ 表示当前最大值为 $i$ 的最优值，方程： f_i=\max_{0\leq j< i,p\in M_i}\{f_j+cnt(p,j)\}其中 $M_i$ 表示最大值为 $i$ 的专辑集合， $cnt(p,j)$ 表示在专辑 $p$ 中 $>j$ 的元素个数，暴力转移是 $O(n^2)$ 的。 考虑优化，注意到总元素个数是 $O(n)$ 级别的，所以每次依赖每个元素转移，具体做法：用线段树维护 $f_{0…j}$ ，每次转移暴力枚举一个专辑相邻的两个元素对 $f$ 数组的贡献做一个区间加取 $\max$ ，同时维护叶子原始值保证下次转移还能用，复杂度 $O(n\log n)$

传送门 $k$ 太小了，结合题目易于想到枚举前 $ 2^k$ 位的状态，然后限制不是一般算法能做的，考虑 $\texttt{dp}$ ，每加一位贡献只跟前 $k-1$ 位有关，设进状态转移，设 $f_{i,j}$ 表示考虑到第 $i$ 位，后 $k-1$ 位状态为 $j$ 的方案数，每次转移分别考虑 $j$ 新加一位 $ 0$ 或 $ 1$ 是否合法就行，$O(2^{2^k+k-1}n)$。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include<bits/stdc++.h>using namespace std;using ll=long long;const ll mod=998244353;int n,k;ll f[501][11];ll ans;int rev(int x){ int res=0; for(int i=0;i<k;++i) res|=(((x>>(k-1-i))&1)<< ...

一道树上复杂路径 $\texttt{dp}$ ，要整整拆分 28 种情况，真是傻逼呢。 有个经典转化，路径转为考虑两个端点，发现子树中路径的形态只跟端点是否在子树中有关，在综合点的状态可设 $f{u,1/0},g{u,1/0},h_{u,1/0}$ 为三种形态，走完子树路径后子树根亮或不亮，点亮子树内除根以外所有点的的最小代价，然后按照定义仔细分类转移即可。

考虑整个建边过程，任意 $(a,b)$ 都连边肯定不好搞，因为只要求连通，所以看一下有没有等价方案，发现在某一天 $m-i+1=g$ 时，把所有的 $kg$ 向 $g$ 连边是等价的，可以直接把询问两个端点丢到对应集合里，每次合并枚举小集合查大集合就能做到 $n\log n$ 12345678910111213141516171819202122232425262728293031323334353637383940414243#include<bits/stdc++.h>using namespace std;#define fio(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)#define tio() freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)using ll=long lo ...

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475[传送门](https://www.luogu.com.cn/problem/P14254)赛时交错代码喜提 $\texttt{0pts}$ ，~~虽然赛后再交一遍也只有44pts就是了~~感觉我自己想的分讨不是一般的复杂，改天有空补点简单做法吧/cy首先看到题面这么复杂，还是个计数题，这种时候就应该把**题目的限制**用数学语言描述清楚。首先大概看一眼，对于计数对象有两个限制：非降和下面那一坨柿子，然后对于序列计数，不妨试试依赖于特殊元素计数，比如这题中我就使用了最小的元素 $u=b_1$ ，也就是要枚举的东西。形式化上面两个限制，注意到所谓**子树中所有结点在原树中的深度值去重后组成一个集合**其实是一个区间 $[d_u,h_u]$ ，$h_u$ 为 $u$ 子树内深度最大值。非降： ...