题解

题目传送门 前置知识 贪心 | 构造 解法 对于任意一个未加入序列 \(P\) 的数 \(x<A_{i}(1 \le i \le k-1)\)，如果其放在了 \(A_{i}\) 的前面，会导致最长上升子序列长度加一，从而不符合题目要求。因此我们需要把 \(x\) 放在 \(A_{i}\) 后面，同理 ......

由于大家的做法需要大量分类讨论和代码量，这里提供一种不怎么分类的，容易实现的做法。 首先，由于墙体会随时变化，所以直接对墙体本身维护不是很方便。 我们可以牺牲一点常数，对 \((i,j)\) 建立四个点 \(UL_{i,j},UR_{i,j},DL_{i,j},DR_{i,j}\) 分别表示 \(( ......

Upd on 2023.10.14 08:21：修改了推式子和题意的一些小错误。 前言 一道恐怖的绿题。显然我认为应该是蓝题。（不过在这篇题解写到一半的时候升蓝了，感谢 @StudyingFather。） 名字挺好的。 题意 给定 \(n\)，求出满足以下条件的三元组 \((x, y, z)\) 的 ......

题目大意 有一条长度为 \(n\) 个单位长度的路，蚂蚁们要从起点走到终点。蚂蚁们每走 \(1\) 个单位距离需要 \(T\) 秒钟。现在，出题人可以在路上修筑 \(3\) 种防御塔来阻挡蚂蚁的进攻，每个单位距离只能修筑 \(1\) 座塔，塔的作用分别如下： 激光塔：蚂蚁在塔前时每秒会受到 \(r\ ......

前言 今天考试考到这道题，挂惨了。 题意 有 \(n\) 道菜肴，编号为 \(1 \sim n\)。有 \(m\) 个条件，形如 \((i, j)\)，表示菜肴 \(i\) 必须在菜肴 \(j\) 之前制作。需求出一个菜肴的制作顺序，满足： 在满足所有限制的前提下，\(1\) 号菜肴尽量优先制作。 ......

题目大意 有一个数列，初始时只有一个数 \(X\)。你可以对它进行一种操作：设末尾的数为 \(Y\)，从 \(1 \sim \sqrt{Y}\) 中选一个数加到数列的末尾。如此进行 \(10^{100}\) 次操作，问数列一共有多少种可能的状态。 解法 考虑 DP。 设 \(dp_i\) 表示以数字 ......

题目大意 有一个数列，初始时只有一个数 \(X\)。你可以对它进行一种操作：设末尾的数为 \(Y\)，从 \(1 \sim \sqrt{Y}\) 中选一个数加到数列的末尾。如此进行 \(10^{100}\) 次操作，问数列一共有多少种可能的状态。 解法 考虑 DP。 设 \(dp_i\) 表示以数字 ......

题意 不难理解，不多赘述。 思路 首先考虑对于性质 A 的情况，我们可以这样做： 定义一个代表变量的结构体，里面存几个参数：首先肯定要存种类（\(type\)）和名称（\(name\)），其次为了方便，我们把该变量的大小（\(siz\)），起始位置（\(fir\)）和对齐要求（\(mx\)）也存了。 ......

题意 给定 \(k\) 和一个排列 \(P'\)，问有多少个排列 \(P\) 以最少步数交换相邻两个元素来进行收敛，最终的排列可能是 \(P'\)，一个排列是收敛的当且仅当对于每一个数，在该数前且比这个数大的数的个数不超过 \(k\) 个。 思路 考虑正向的让一个排列收敛，我们设在第 \(i\) 个 ......

题意 给定 \(k\) 和一个排列 \(P'\)，问有多少个排列 \(P\) 以最少步数交换相邻两个元素来进行收敛，最终的排列可能是 \(P'\)，一个排列是收敛的当且仅当对于每一个数，在该数前且比这个数大的数的个数不超过 \(k\) 个。 思路 考虑正向的让一个排列收敛，我们设在第 \(i\) 个 ......

题意 给定一棵既有点权也有边权的树，构造一个完全图，图中两点间边的边权为树中两点点权之和加上两点间的距离，求该图的最小生成树。 思路 发现完全图总边数太大，考虑减少边数。 这里有一个性质： 如果在一个图中选取任意个联通的边集，使得它们的并为全集，则整个图的最小生成树中的边一定在 分割后的两个边集的最 ......

题意 一个 \(n\times m\) 的区域内，有以下 \(5\) 种地形： ~：无法通行。 .：只能通行 \(1\) 次。 @：可以通行 \(+\infty\) 次。 *：初始有一个人的 .。 #：安全位置，可以通行 \(+\infty\) 次，但至多能容纳 \(p\) 个人。 人每次可以走到相 ......

题意 二维平面内有 \(n\) 个冰块，给出冰块的坐标，冰块上的企鹅数和最大跳出次数，企鹅可以在冰块间跳跃，每次跳跃的距离不能超过 \(d\)，问哪些冰块可以让所有企鹅跳到上面？ 思路 网络流，由于每个冰块有跳出次数限制，所以把一个冰块拆成入点和出点，入点向出点连一条流量为最大跳出次数的边，由源点向 ......

题意 给你一张有向图，点有点权，现进行以下操作直到无法进行： 选择两条首尾相连的边 \((a,b)\) 和 \((b,c)\) 且 \(a\) 与 \(c\) 间没边，添加边 \((a,c)\)。 求操作完后图中最长的 不经过重复点的路径，并求这种路径中经过的点的点权和最小值。 思路 先考虑 DAG ......

题意 给一个 \(n\) 阶全排列 \(a\)，每次把不满足 \(a_i = i\) 的 \(a_i\) 向右循环移位一位，问从移位多少次后起所有 \(i \in [1,n]\) 都满足 \(a_i = i\)。 思路 先断环成链后再复制一次，可以发现此时的移位等价于向右移位。发现一条性质：若 \( ......

题意 给一个 \(01\) 矩阵，多次求在给定区间内最大的全 \(1\) 正方形边长。 思路 容易想到二分： 先预处理出以每个位置为右下角的最大合法正方形的边长 \(mx_{i,j}\)，然后对于每个询问，我们二分边长 \(mid\)，设当前询问的区间左上角为 \((x_1,y_1)\)，右下角为 ......

题意 一个 \(n\times m\) 的区域内，有以下 \(5\) 种地形： ~：无法通行。 .：只能通行 \(1\) 次。 @：可以通行 \(+\infty\) 次。 *：初始有一个人的 .。 #：安全位置，可以通行 \(+\infty\) 次，但至多能容纳 \(p\) 个人。 人每次可以走到相 ......

题意 二维平面内有 \(n\) 个冰块，给出冰块的坐标，冰块上的企鹅数和最大跳出次数，企鹅可以在冰块间跳跃，每次跳跃的距离不能超过 \(d\)，问哪些冰块可以让所有企鹅跳到上面？ 思路 网络流，由于每个冰块有跳出次数限制，所以把一个冰块拆成入点和出点，入点向出点连一条流量为最大跳出次数的边，由源点向 ......

题意 给你一张有向图，点有点权，现进行以下操作直到无法进行： 选择两条首尾相连的边 \((a,b)\) 和 \((b,c)\) 且 \(a\) 与 \(c\) 间没边，添加边 \((a,c)\)。 求操作完后图中最长的 不经过重复点的路径，并求这种路径中经过的点的点权和最小值。 思路 先考虑 DAG ......

发现我们给一个点染上色后有： 我们称这是一个大小为 1 的十字。 进一步地，我们给这 5 个点再次染上色后有： 我们称这是一个大小为 2 的十字。 同理可得，我们给这 5 个点染上相同的大小为 2 的十字，可得一个大小为 4 的十字： 假设我们图的边长为 \(N=2^n\)，我们只需要染上一个大小为 ......

萌萌构造题，随便构造构造就做出来了。似乎跟官方题解思路一样。 首先解决以下问题：给定一个质数 \(P\)，构造一个每个数在 \(0\sim P-1\) 的大小为 \(P^2\times P^2\) 的矩阵，满足不存在 \(x_1\ne x_2,y_1\ne y_2\) 使得 \(a_{x_1,y_1 ......

题目链接 点击打开链接 题目解法 很妙的题！！！ 考虑 \(x\) 是无穷大的数，所以可以认为 \(x^i\) 的系数是单独的一项，不会和 \(x^j(j\neq i)\) 合并 所以问题转化成了：每个数初始是 \(x^i\)（\(x\) 可以理解是元），进行题目中的操作，问最后形成的 \(n\) ......

对每个点随机黑白染色，强制答案链的前 \(\lfloor \frac{k}{2}\rfloor\) 个点和后 \(\lceil \frac{k}{2} \rceil\) 个点的颜色不同。 计算答案只需要枚举中间这条两端颜色不同的边 \((u,v,w)\)，然后分成两边计算 \(u,v\) 出发的经过 ......

题目链接：CF 或者 洛谷 可以看到查询和插入就是李超线段树的基本操作，但在原有基础上多了一个删除操作，李超线段树不支持删除操作，但支持可撤销和可持久化，所以我们容易想到外层再套一个线段树分治即可。本题用可撤销就远远足够了，很好写。 具体的，我们读入所有操作，对于操作一，为当前下标线段读入它的 \( ......

传送门 思路 提供一个不太一样的容斥做法。 首先容易发现答案只和每个点到 1 号点的奇偶最短路有关，可以先 \(O(n)\) 求出来。 然后考虑枚举距离 \(d\)，计算有多少个 K 元组的距离为 \(d\)。不妨设 \(d\) 为奇数，那么条件就是： 每个点的奇最短路的最大值为 \(d\)； 存在 ......

LG LG9979 [USACO23DEC] Target Practice S code LG9980 [USACO23DEC] Flight Routes G sol 1 已知邻接矩阵求路径数奇偶性是容易的，倒着做即可 bitset 实现。时间复杂度 \(O(\frac{n^{3}}{\omeg ......

一种很好写的 \(O(n\log ^2 n)\) 的做法和处理技巧，不需要会任何 border series 的知识，只需要会 SAM 和一些基础数据结构就行。 考虑 \(\text{MaxBorder}(l,r)\) 可以被写成即找到最大的 \(p \leq r - l\) 满足 \(S[l:l+ ......

考虑一个卡牌区间怎样才不是”陀螺无限“。 一个是费用在打到一半时费用就不够了。考虑构造一个卡牌序列使其尽量能够在打到一半时费用就不够，如何构造呢？ 把 \(a_i > b_i\) 的卡牌称作消耗型卡牌，其他叫做获得型卡牌。我们可以构造把消耗型卡牌全部放在前面，后面突然来个很大的 \(a_i\) 就可 ......

Autosynthesis - 洛谷 https://codeforces.com/contest/1876/problem/C 这次也差点想出来了 \(QwQ\) 遇到这种题第一感觉是建图。把 \(i \rightarrow a_i\) 得到一个 章鱼森林 （这里忘记了每个点只有一个出边，是章鱼森 ......

考虑到不管怎么变化 \(x_i\) 的值其在 \(t\) 时刻的位置都能被一个一次函数 \(x_i\times t + b\) 表示。 而且 \(b\) 是好算的，考虑到知道现在的斜率 \(k\) 和现在的时间 \(t\) 以及现在的值 \(f(t)\)，则整个函数就是 \(f(x) = f(t) ......