第一次也应该是最后一次考noip。 疑似本来都已经把电脑扔进犄角旮旯里了结果出分了。 估分：100+72+8+15=195 实际：100+76+12+40=228 貌似还能多陪OI走几个月？ 等待女生省队名额ing

> 给定 $n$ 对数 $(a_i,b_i)$，你可以选择其中一个放入第 $1$ 组，另一个放入第 $2$ 组。 > > 求对于所有选择方案，$\min\{(mx1-mn1)\times (mx2-mn2)\}$。 > > $1\le n\le 2\times 10^5,1\le x_i,y_i\le 10^9$。 考…

> $n$ 个节点的带权有向图（节点编号 $0\sim n-1$）。 > > 初始时 $\forall i\in [0,n-2]$，存在一条 $i\to i+1$ 且权值为 $0$ 的无向边。 > > 我们 $\forall i,j\in [0,n-1]\land i\not =j$，添加一条 $i\to j$ 的边，…

> 给定一个 $n$ 个点 $m$ 条边的有向图 $G$，无重边，找一个点集 $S\sube V$，含 $1,2$，使得 $G_S$（$S$ 的生成子图） 中 $1$ 可以到达 $2$，$2$ 也可以到达 $1$。 > > 求 $|S|$ 的最小值。 > > $1\le n\le 100$。 我们令 $dp_{i,j}…

发现 $m,K$ 很小，考虑状压 dp。 我们考虑**生成路径**，枚举 $x$ 从 $n$ 到 $1$，考虑把 $x$ 插入路径。 eg: $$ n=10,m=3\\ (9)\\ (9\text{ }7) (7\text{ } 9) $$ 考虑尝试插入 $x$ 时的序列，$P_1,P_2\dots ,P_k(P_i>…

看到这道题第一反应就是枚举 $s$ 在哪个位置上 $ #define FL(i,a,b) for(int i=(a);i =(b);i--) #define ll long long #define ld long double #define PII pair using namespace std; const i…

问把 $n$ 个数按某种顺序拼起来能被 $11$ 整除的方案数。 我们考虑一个能被 $11$ 整除的数的特征，即它的奇数位和偶数位的差是 $11$ 的倍数。 我们定义一个数的**价值** $val$ 为从前往后的奇数位减偶数位（即最高位定义为奇数位）的差。 我们考虑拼一个数到序列末尾可能的贡献，可能为 $+val$，也…

发现 $m$ 的范围很小，考虑状压 dp。 我们令 $f_{u,i,j}$ 表示 $A$ 树中的点 $u$ 匹配了 $B$ 树中的点 $i$，$B$ 子树中除 $j$ 以外的与 $i$ 相连的点和 $A$ 子树内的点匹配。 每次在 $u$ 点转移我们枚举 $i$，钦定 $g_{S}$ 表示 $u$ 与 $i$ 匹配且在…

发现如果 $s$ 数组全部符号为 $ $，我们分别维护一个树状数组，对于符号 $=$ 我们维护一个数组，每次取三种情况中较大的那种即可（很明显不会出现两种情况答案相等的情况，可以证明在 $i$ 处取最大的 $f_j$ 转移一定最优）。 附上代码： ```c++ #include #define FL(i,a,b) fo…

考场上写了 3.5h 树形 dp 然后挂完了... 赛后补的是**树的直径**的做法。 有个很妙的结论，所有关键点到所有离它最远的关键点的所有路径都经过一个点：距离最远的一对关键点（即**带权**的**树的直径**）的**中点**（如果中点在点上我们设其为 $C$，如果中点在边上我们用 dfs 求出这条边的两个端点 $…

血的教训了，以后会写特殊性质的时候一定先写了再去冲 T2... 首先可以很容易想出朴素的 dp 状态，令 $dp_{i,0/1}$ 表示前 $i$ 个数，最后一个子串以 $i$ 结尾，子串不能/能被 $D$ 整除的方案数。 然后我们枚举上一个子串的结尾 $j$，令 $Calc(j+1,i)$ 表示 $[j+1,i]$…

在讨论《请不要用官解的代码对拍》回复：

怎么也在写这道题/bx

我们令 $f_i$ 表示以 $i$ 结尾的最长上升子序列长度，显然若 $i$ 在最终作为答案的最长上升子序列中，$i$ 一定在 $f_i$ 这个位置。 不妨设作为答案的最长上升子序列的长度为 $len$。 如果我们将源点 $S$ 连向 $f_i=1$ 的 $i$，容量为 $\infty$，$f_i=len$ 的 $i$…

我们把权值取反然后求**最大权闭合子图**， 题目给了条件，任意 $k(k>0)$ 个集合的并集，包含的不同数字不会少于 $k$ 个。 即对于任意左部点集合 $S$ , $|N(S)|\ge|S|$，我们给每个数字赋上 $-lim$ 的权值，给每个集合赋上 $+lim(lim #define FL(i,a,b) for…

考场上碰到的题，一眼整体二分然后场切了， 用最短路算出来每个点到 $K$ 个关键点的最近距离 $dis_u$。 然后把边 $(u,v)$ 按照 $\min(dis_u,dis_v)$ 从小到大排序。 我们直接 $solve(l,r,L,R)$。 令 $mid=\frac{l+r}{2}$，然后每次把编号在 $[mid+…

考场上把自己绕晕了，不知道怎么刻画一个合并后的状态，遗憾离场。 我们首先枚举每个点 $i$，把它作为树的根进行 dp。 很明显一条边有贡献当且仅当它的一个端点已经与 $i$ 合并在一起了。 我们令 $f_{u,j}$ 表示 $u$ 子树内还剩 $j$ 条边没有操作时点 $u$ 已经与 $i$ 合并在一起的概率。 （我的…

发现在背包里面加入一个物品是 $\mathcal{O}(k)$ 的，但是删除一个物品是 $\mathcal{O}(nk)$ 的。 我们考虑如何避免删除操作，发现**每个物品存在的时间是一个连续段**， 我们考虑**线段树分治**。 我们把每个物品存在的时间拆成线段树上 $\log q$ 个区间，离线处理询问， 然后对于…

看官解看晕了，来写一篇详细的题解供后人理解。 我们不妨假设 $(a_2,…,a_n,0)$ 的 SG 值已知且为 $t$。 根据题意 $(a_1,a_2,\dots,a_n,0)$ 的后继状态有 $(a_1−1,a_2,\dots,a_n,0),(a_1−2,a_2,\dots,a_n,0),\cdots,(a_2,\…

**SG 函数**模板题。 显然 $1\times 1$ 的纸条是先手必败态，$1\times x,x\times 1$ 是先手必胜态。 可以列出 $sg$ 函数的定义： $$ \begin{cases} sg(1,1)=0\\ sg(n,m)=\mathrm{mex}(\{sg(i,m) \oplus sg(n-i,…

这道题怎么出现在点分树的专题题单里...不过也算广义的点分树吧。 > 给定一棵 $n$ 个节点的树，让你求一个点分树让它的叶子尽量多。 > > 特别地，点分树的根节点如果度数为 $1$（即选的分治中心本身是叶子），那么它也算一个叶子。 > > $2\le n\le 2\times 10^5$。 发现从叶子开始取比不从叶…

模拟赛碰到这道题的加强版，值域 $V=500$，花了 2h 切掉了，时间复杂度 $\mathcal{O}(V^3+V)$。 首先如果一个矩形都不加，那么答案就是涂了 $K$ 次的面积和，这个可以用二维差分维护。 我们考虑加一个矩形的情况，我的想法是维护一个二维前缀和，把涂了 $K$ 次的设为 $-1$，把涂了 $K-1…

我们令 $dp_i$ 表示前 $i$ 个贝壳可以变出柠檬数量的最大值。 然后我们可以列出转移方程： $$dp_i=\max\{dp_{j-1}+val(i,j)\}$$。 $val(i,j)$ 表示 $[i,j]$ 段变出柠檬数量的最大值。 然后我们发现 $dp_i$ 是单调不减的，那么一个转移是有意义的当且仅当 $a…

首先 $A_ix+B_iy\to B_i(\frac{A_i}{B_i}x+y)$，然后括号里面这个式子可以转换成一次函数形式 $kx+b$： $$ \begin{cases} k_j = X_j\\ b_j = Y_j\\ x_i = \frac{A_i}{B_i}\\ \end{cases} $$ 然后问题就转换为…

学了几次也是终于写懂李超线段树了，来写一篇模板题题解供初学者理解。 ### 算法介绍 李超线段树是一种支持插入一个定义域为 $[l,r]$ 的一次函数（即线段，一次函数便于理解）以及求与 $x=k$ 相交的所有线段中交点纵坐标最大的线段的编号的数据结构，常用于优化斜率优化的题目。 ### 算法流程 李超线段树的每个区间…

考场上尝试维护分裂的区间然后被统一分裂维护一个起点序列这种操作给绕晕了，最后还是任命用优先队列维护获得了 35pts。 然后发现正解很妙的地方就是每个分裂出来的段它没有记录这个段的起点，只记录了这个段是从哪个原始区间分裂出来的，然后就可以把一些连续段一起处理了（记录它们从哪个原始区间分裂出来以及长度和数量），每个原始区…

首先我们可以发现只有一个儿子的节点可以构成很多条链，我们考虑把每一条这样的链缩成一个点。 然后每一个有两个儿子的节点都会分出两条链出来，所以有两个儿子的节点不会被缩掉，并且有可能成为 $lca$，但这样的点只有 $n$ 个再加上最后一层的 $n+1$ 个节点所以最后剩下的点的个数是 $\mathcal{O}(n)$ 的…

我们把爱边称作 $1$ 边，恨边称作 $0$ 边。 我们发现对于任意三点 $(A,B,C)$ 构成的三角形的边集为 $(1,1,1)$ 或 $(1,0,0)$。 当有任意两条边为 $1$ 边时可以推出三条边都是 $1$ 边（所以可以理解为 $1$ 这种关系具有传递性，$a\to b,b\to c\Rightarrow…

学了不知道多少次斜率优化终于学会了并通过了这道题... 首先题意可以转化为每次至多可以删去 $k$ 个叶子节点，要求每次只能删去一层叶子节点，问最少多少次操作可以删去整棵树。 我们考虑对于一个询问，给出的 $k$ 为 $K$，我们发现执行一次删除操作有两种情况： 1. 当前叶子结点数量 $\ge K$ 个，那么删除 $…

非常好玩的题啊，考试的时候开到这道题只剩五分钟了，并没有切出来。 们考虑一个点 $u$ 的 $f(u)$ 怎么算，一个点 $v$ 对 $f(u)$ 有贡献当且仅当它在 $u$ 的子树里，这时候我们考虑转为求 $u$ 子树中每个点权值对 $u$ 的贡献。 然后我们可以发现对于子树内的点 $v$，它对 $f(u)$ 的贡献…

首先我们发现题目求“最小值最大”，并且答案具有单调性，我们不难想到通过二分答案将最优解问题转化为验证性问题。 我们考虑验证一个答案 $d$ 是否可行，首先因为题目要求选一个点覆盖，所以我们可以得出一个很 2-SAT 的条件，就是对于任意一条边 $(u,v)$，当 $u$ 不选时推出 $v$ 必须选。 然后因为我们固定了…