Posts

跳题 如果一道题认为难写，先看后面的题，也许有好写的部分分甚至是正解 如果一道题写完了挂了，认为很对： 找不到错误数据，就规定一段时间（一般为5~10分钟，或者直接执行），然后立刻跳题 找到了错误数据，就可以调时间长一些 如果要在开场把所有题读完（OI赛制专用），遇到难读的题目可以先不读 如果要把剩下的时间全部用在一道题上，先去吃其他题的保底，再开始写这道题 对拍（OI赛制专用） 如果说一道题强数据好造、暴力好写，那么一定要对拍 即使是模拟赛也要对拍，不止是正式比赛，把模拟赛当做正式比赛认真对待 总结 比赛后写一下总结，包括以下内容： 赛时记录，什么时候在干什么 估分 VS 得分 挂分原因（BBE） 赛后想一下赛时没有想到的部分分/满分/更优做法 策略总结+调整

网址 每天北京时间0点整会更新所有测验。 这里只说部分，其他的自行摸索。 猜城/猜城3D/猜国/猜旗/天眼/乡音/城景 线索 会给你关于这个行政区/国家的信息（如果是猜旗则随着你的猜测会逐步揭开）。 你有 $6$ 次机会去猜，输入方式是类似于查找然后点击的方式（可以自己试试就知道是啥意思了）。 判题 每次猜完后会告诉你答案在你猜的答案的（大致）哪个方位（八方向），以及距离是多少。 天眼不会告诉你方位，只会告诉你距离，所以非常难猜，没有足够实力不要去挑战。 不用管后面的百分比，这个是接近程度，按照距离除以一个很大的数去计算。 一旦猜对则游戏结束。 填省/填国/填歌 线索 给你一个表格，表头有限制条件。 判题 需要在表格内每一个方格填入数据库内同时满足行、列表头上的条件的元素。 尝试机会有限，看最上面的生命值。 填完则游戏结束。 猜Word 线索 跟Wordle一模一样。 判题 跟阴阳小游戏很像，但不同的是可以告诉你每个位置是匹配还是错位。 匹配显示为绿色，错位则是黄色，没有则是灰色。 歌词/诗文 线索 一开始所有格子都是黑色的状态。 你有无限次机会，每次可以输入一个字，然后这个字在这首歌（包括歌名、歌手、歌词）或诗（包括诗名、作者、内容）内出现的所有位置都会揭开。 判题 如果猜的字没有出现，则会提示“未出现”并将该字以红色背景显示在最底下。 如果猜过，则会提示“猜过”并不执行任何操作。 将歌名或诗名完全揭开即可。 连句 规则 给你一个表格，你要在里面找到固定数量（可以看最底下）的诗句或者歌词。 可以通过八方向的一条链表示该诗句，连接的时候可以交叉，可以自己玩一下。 每个字只能使用一次。 判题 尝试机会有限，看最上面的生命值。 如果连句成功则会标记为绿色，并不能再选。 全部为绿色则游戏结束。

更新中…… 稀有度 Common：绿 Unusual：un/黄 Rare：蓝 Epic：紫 Legendary：l/红 Mythic：m/青 Ultra：u/ul/粉 Super：s/书青 合成 合成Mythic：合青 合成Ultra：合粉/河粉 合成Super：合苏（su） 合成Ultra并失败：冒青烟 合成Super并失败：冒粉烟 用x个花瓣合成并成功：x=1（如5=1） 用x个花瓣合成并失败：-数字（如-2，但通常此处x=5） 花瓣 默认可以叫花瓣的英文名和大家普遍公认的中文名。 Ant Egg：agg/egg Antennae：ante/触 Basil：比勒（一般不叫它罗勒） Beetle Egg：bgg Bone：骨/装 Bubble：泡 Claw：头发（一般不叫他爪子/蟹爪） Dandelion：dande Dice：色（shǎi） Faster：罚 Iris：毒药 Lightning：lāi Magic Eye：me/魔眼 Magnet：mag Mana Orb：orb（拼写式读法） Pincer：品色/拼刺儿 Powder：pow Rice：米 Shovel：铲 Sponge：海 Third Eye：te/三眼 Uranium：uran Wing：羽毛 Yggdrasil：ygg（一般不叫它世界树） Yucca：于夹（一般不叫它丝兰） 生物 Queen Ant：queen Starfish：兴（xìng）禹（yú） 黄色瓢虫：shiny

前言 2-SAT中的SAT是适定性（Satisfiability）问题的简称，一般形式为 $k$ - 适定性问题，简称 $k$ - SAT，但由于 $k>2$ 时问题为NP完全问题（只有指数级别复杂度的解法，或者多项式级别复杂度的相似解法），而 $k=1$ 时都不用解了 （废话） ，所以下面全部考虑 $k=2$ 的情况。 定义 2-SAT问题简单来说就是，有 $n$ 个集合，每个集合包含两个元素（集合 $i$ 包含元素 $2i-1$ 和 $2i$，但其实编号是无关紧要的，任意都行），你必须要在每个集合里分别选择刚好一个元素，但某些元素之间可能有矛盾，即这两个元素不能在一种方案里被同时选择，问你是否有解，报告出来，如果有解，输出一种方案（可能不用输出）。 题目 看上面的定义可能有点难懂，这里举个题目。 有一场宴会，这场宴会只有 $n$ 对幸运夫妻可以参加，每对夫妻里只能选择刚好一个人去参加这场宴会。 但部分人之间可能有矛盾，会给出所有有矛盾的两人编号。 问你，是否可以构造一种合法方案，如果不行，报告无解，否则输出一种方案。 解法 （下面统一默认要解决的是实际问题，不是定义里的问题） 定义点、边 我们考虑把夫妻编个名字： 第一对夫妻：A男、A女 第二对夫妻：B男、B女 第三对夫妻：C男、C女 以此类推 然后，我们考虑建图。 但这个建图就要用到一点思维了。 我们不以其他的定义定义点，我们就把一个点当做一个现实。 比如： $1$ 号点代表第一对夫妻是A男参与宴会，$2$ 号点代表A女参与宴会 $3$ 号点代表第二对夫妻是B男参与宴会，$4$ 号点代表B女参与宴会 $5$ 号点代表第三对夫妻是C男参与宴会，$6$ 号点代表C女参与宴会 以此类推 边的定义也很难思考出： 一条有向边 $u \to v$，代表现实 $u$ 满足了，现实 $v$ 也要满足。 举个例子 所以，如果说A男和B女、C男和A女之间都有矛盾，那么就需要在： ...

CDQ分治是一种解决三维、四维偏序的算法。 三维偏序 三维偏序问题形如： 有 $q$ 次询问，每次询问有两种： 修改：会给定 $t$、$x$、$y$、$v$，表示在时刻 $t$，在二维坐标 $(x,y)$ 上加上权值 $v$，修改会永久改变权值 （废话）。 查询：会给定 $t$、$x$、$y$，表示求在时刻 $t$ 时，所有满足 $x’ \leq x$，$y’ \leq y$ 的二维坐标 $(x’,y’)$ 上的权值和。 $q \leq 2 \times 10^5$ $t,x,y \leq 2 \times 10^5$ $v \leq 10^9$ 这种问题都有一个通用的解决方法，就是CDQ分治，接下来我们讲一下算法的原理。 我们先把所有的询问离线下来，然后按时刻（第一维）升序排序，显然排序前和排序后，相同询问答案不变。 接下来我们定义函数 $\text{solve}(l,r)$，代表只考虑 $l \sim r$ 内的修改，然后准确回答 $l \sim r$ 内的询问。 既然是分治，我们就要构建好整个分治思路，像这道题，就这样做： 找到 $mid$ 为区间 $[l,r]$ 的中点 $\left\lfloor \dfrac{l+r}{2} \right\rfloor$。 考虑 $l \sim mid$ 内的修改对 $l \sim mid$ 内的询问的影响：递归调用 $\text{solve}(l,mid)$。 考虑 $mid+1 \sim r$ 内的修改对 $mid+1 \sim r$ 内的询问的影响：递归调用 $\text{solve}(mid+1,r)$。 考虑 $l \sim mid$ 内的修改对 $mid+1 \sim r$ 内的询问的影响： 把 $l \sim mid$ 内的修改，和 $mid+1 \sim r$ 内的询问，统统存入一个数组 $b$。 把 $b$ 中所有元素按 $x$ 坐标（第二维）升序排序。 有人对这一步的正确性有疑问，此处解释一下。 ...

参考： 老师讲解 Fighting_Peter 的文章 其实Kruskal重构树并不难。 概览 首先，Kruskal重构树，顾名思义就是把整棵树重构。 并且其是基于Kruskal算法的。 它能解决很多问题，并且变种很多。 但我们先从基础的实现说起。 实现过程 我们考虑，在Kruskal算法里，我们每次会合并两个并查集集合。 准确来说是在两个点 $u$、$v$ 之间加一个边权为 $w$ 的无向边。 那么，我们就考虑，在重构树里，我们找到 $u$ 和 $v$ 分别所在的子树，把这两个子树的根拎出来，设为 $u’$ 和 $v’$。 然后，我们就新建一个点 $w$，然后把 $u’$ 和 $v’$ 的父亲设为 $w$。 此时我们就得到了另外一棵树。 比如说这个例子： 而在代码中，我们需要给这些方点一个别的编号，而不是以 $w$ 作为编号，否则会重，并且会炸。 特性 我们讲一些Kruskal重构树的特性： 这棵树一定是二叉树。 原树中的点放到重构树上一定是叶子，重构树上其他点都是原树中的边权。 节点个数一定是 $2n-1$，且 $2n-1$ 一定是根。 如果是最小生成树，那么这棵重构树一定是大根堆1，否则是小根堆。 原图中两个点 $u$、$v$ 之间所有路径上的边权最大值的最小值，就是该图的最小生成树重构树上，$u$ 和 $v$​ 的LCA的权值。 尚未想到证明方式 对于一个最小生成树上的点 $x$，其只通过（边权）不超过 $v$ 的边，能到的点集；和 $x$ 在重构树上深度最浅的、权值 $\leq v$ 的点 $y$ 的子树内（叶子）节点集合，是一样的。 这里稍微证明一下。 就是我们根据上面的性质，可以发现，设后者对应集合为 $S$，那么显然 $S$ 内的点，和 $x$ 点，的LCA的权值一定不超过 $v$，显然。 ...

感谢这篇文章的作者。 wqs二分一般解决这类问题： 有 $n$ 个物品，你要选出恰好 $m$ 个（下称“选择物品个数限制”），可能有限制（下称“其他限制”），你要最大/小化某个权值。 但除此之外，还有一些限制： 如果我们设 $g_i$ 为选出恰好 $i$ 个时的最大/小权值，那么 $g$ 函数就应该是上凸（求最大权值）/下凹（求最小权值）的，即斜率单调递减（上凸）/递增（下凹）。 一般来说，如果没有任何限制（包括选择物品个数限制和其他限制），那么答案是很好求的。 一般来说，如果没有其他限制，那么选择物品数量越多，最小权值就越大/小。 以下是P5633的题解，顺带着讲了wqs二分的原理和应用。 在原题中，我们可以以标号为 $s$ 点在最小生成树上的出度为横坐标，以这个出度对应的答案为纵坐标，画出图像：（网上粘的图，只画了部分横坐标的情况） 显然D和E点就是最小值点。 接下来就是wqs二分的重点了 wqs二分也是二分，那它二分什么值呢，它二分的是斜率 $mid$。 具体而言，一个斜率就对应若干条平行的边，而总有一条边是完全切这个凸包的，如 $mid=-1$ 的时候，上图中被且的那个点就刚好是C点： 如果我们设题目要求 $s$ 的度数要恰好为 $6$，那么 $mid=-1$ 的时候被切的那个点C的纵坐标就是答案了。 但此时我们就有两个问题了： 如何求出被切的那个点的下标？ 就算求出了下标，那这个点的纵坐标又如何计算？ 接下来我们来解决这两个问题。 首先，这个切线肯定是所有经过某个点且斜率等于 $mid$ 的直线中截距最小的点： 具体地，根据切线的性质，在上述例子中，经过C点的斜率等于 $mid$ 的直线（即切线），与经过D点的斜率等于 $mid$ 的直线、经过E点的斜率等于 $mid$ 的直线相比，切线的截距肯定最小，后两者的截距肯定更大。 其次，显然，经过点 $(x,y)$ 且斜率等于 $k$ 的直线（肯定唯一），其截距一定等于 $y-kx$（$y=kx+b$，$b=y-kx$）。 而在二分的calc函数（此处不是check函数了，calc函数的返回值、返回值含义以及应用见下）中，我们已经知道了上述公式中的 $k$ 了（$k=mid$），所以我们只要让 $y-kx$ 最小、斜率为 $k$ 且经过了某个图上的点即可。 考虑到上述公式中的 $x$ 未知，所以我们可以干脆把所有 $s$ 的出边的边权都减 $mid$。（关于是加、减还是都彳亍的问题存疑） ...

下面是三道与博弈论相关的题目及其做法。 题目1：皮肤病 题面 （改编自《不可思议事件簿 第5册 魔法学院》，由艾教提供变体） （原题名称：加试难题） 在一个学校内，共有 $100$ 个人，每个人都养了一只狗。 但由于某些原因，校长确定了这 $100$ 条狗内，必然存在至少一条狗有皮肤病。 现在那些学生要确定一下哪些狗有皮肤病。 他们准备这样确定： 每天上午的时候，所有人看一下除了自己的狗之外的所有狗。 如果确认自己的狗病了，就在晚上敲一下宠物房内的钟。 现在已知： 无论谁，看那只狗，都能立刻确认它是否有皮肤病。 假设皮肤病不会对狗的寿命造成影响，即所有的狗都不会死亡。 皮肤病不能传染，并且忽略“人患病”造成的影响。 所有人都绝顶聪明（废话 并且： 第 $1$ 天晚上，没有钟声响起。 第 $2$ 天晚上，没有钟声响起。 第 $3$ 天晚上，没有钟声响起。 … 直到第 $10$ 天晚上，终于有钟声响起了。 请问： 那天晚上，共有多少人共同敲响了钟？ 在第 $10$ 天后，除了那些敲钟的人养的狗，是否会存在其他病了的狗？ 答案 $10$ 个人 不会 题解 我们考虑一下，如果说第 $1$ 天晚上有人敲钟，那么代表啥。 我们从人的角度考虑，如果说一个人发现其他狗都是好狗（指没有皮肤病的狗），那么必然自己的狗有皮肤病 （除了自己的，还有谁的？难不成是他自己？）。 这种情况下，他便会去敲钟。 但第 $1$ 天晚上没有钟声，所以每个人都观察到了至少 $1$ 个病狗，也就是说至少有 $2$ 个病狗。 随后第 $2$ 天，如果说一个人观察到其他的狗内，只有 $1$ 个病狗，那么显然自己的狗也得有皮肤病。 ...

点分治和树剖有一个相同点，就是算法都是从暴力经过一小步优化而来，但就是这一小步，让算法复杂度有了质的飞跃。 下面来讲一下这个算法的原理。 概览 其实“点分治”也是一个名不副实的算法，看完下面的讲述你就会发现这个算法根“分治”几乎无关。 点分治是专门解决树上路径统计的一种算法（树剖则是解决对树上路径的判断的算法）。 点分治的思想很朴素，就是DFS一下 $\text{lca}$ 的节点编号 $x$，然后统计 $\text{lca}$ 值刚好为 $x$ 的、满足题目条件的路径的数量，并累加到答案。 但直接进行统计还是炸裂的，点分治则是对这种统计方式做了一步优化 解决题型 上面说了，「点分治是专门解决树上路径统计的一种算法」，但并不是所有的树上路径统计都可以用点分治解决。 其实看完下面的实现，你就能知道它解决什么类问题，不过这里还是说一下。 就是首先，这个条件是形如“总和比某个值低”、“总和是某个值的倍数”等“可累加”的条件。 其中“可累加”指的是，如果知道了 $A$ 部分的某个值，和 $B$ 部分的某个值，那么 $A$ 和 $B$ 部分合并后的部分是否合法也一定知道。 但其他的条件目前还没有太明确，得自己去总结。 算法实现 下面说一下点分治的实现。 大体思路 我们拿“路径长度（路径上的边的边权之和）刚好为 $k$”问题举例。 注：原题链接P3806 就是我们考虑，当DFS到某个点 $x$ 的时候，就如上所说，设 $x$ 为 $\text{lca}$ 值。 然后，我们按顺序遍历所有子节点 $to$。 由于只要两个点 $y$、$z$ 满足 $y$ 和 $z$ 分别在 $x$ 的两个不同儿子及其子树内，那么 $\text{lca}(y,z)=x$。 并且所有满足条件 $\text{lca}(y,z)=x$ 的对 $(y,z)$ 只有满足上述条件的对。 所以，我们可以通过（另一种）DFS（方式）求出 $to$ 到 ( 所有 $to$ 及其子树内的点 ) 之间的距离（加上 $x \to to$ 的边权）的集合 $T$。 ...