CF76A Gift 题解
CF76A Gift 题解 题目链接:CF76A Gift 题意: 一张 \(N\) 个点 \(M\) 条边的无向图,每条边有两个属性 \((g_i, s_i)\)。 给定 \(G, S\),求一棵图的生成树 \(T\),使得 \(G \times \max(g_i) + S \times \max (s_i)\) 最小。(\(i\in T\)) 注意:图可能包含重边和自环。 数据范围: \(2 \le N \le 200,~1\le M \le 50000,~1 \le G,S \le 10^9\) 。 建议先写 洛谷P2387 [NOI2014] 魔法森林 考虑将边化成点,然后按 \(g_i\) 排序,依次加入每条边, 同时维护 \(s_i\) 的最小生成树,每次图连通时更新答案。 维护 \(s_i\) 的最小生成树时,如果两个点不连通直接合并,否则我们需要找到所成环上的 \(s_i\) 最大值。 考虑用 LCT 维护链上的 \(s_i\) 最大值即可。更新答案的话,可以开两个 multiset 维护边集。 时间复杂度 \(\mathcal{O}(m \log n)\) ...
UOJ180 【UR #12】实验室外的攻防战 题解
UOJ180 【UR #12】实验室外的攻防战 题解 题目链接:#180. 【UR #12】实验室外的攻防战 题意: 经过跳蚤侦察兵的勘察,跳蚤国王发现Picks博士的防御工事有着 \(n\) 处薄弱点,于是他把他的跳蚤大军分成了 \(n\) 支小队,并打算让它们分别进攻每一个薄弱点。但是因为战场混乱,这 \(n\) 支小队的位置被打乱了,重新整队之后,跳蚤国王发现第 \(i\) 个位置的小队编号为 \(A_i\)(显然 \(A\) 是一个排列)。 经过计算,跳蚤国王发现,让第 \(i\) 个位置的小队编号为 \(B_i\) 时,他的军队可以发挥出最大的战斗力(保证 \(B\) 也是一个排列)。 跳蚤国王可以发出指令来改变小队们的排列顺序。每一次,他都会报出一个整数 \(i~(1 \leq i < n)\)。如果排在第 \(i\) 个位置的小队编号大于第 \(i+1\) 个位置的小队,那么这两支小队会交换顺序,否则这个命令将会被忽略。 现在跳蚤国王希望他的军队能够发挥出最强大的战斗力,于是他想要知道是否存在一种指令序列,使得小队们可以按照排列 \(B\) 的方式排列。 但...
一些不常见的三角函数
一些不常见的三角函数 先放一张图片,来源于维基百科。 好吧其实我不关心这些奇奇怪怪的函数是什么,我只是觉得这张图非常好(
洛谷P5904 [POI2014] HOT-Hotels 加强版 题解
洛谷P5904 [POI2014] HOT-Hotels 加强版 题解 题目链接:P5904 [POI2014] HOT-Hotels 加强版 题意: 给出一棵有 \(n\) 个点的树,求有多少组点 \((i,j,k)\) 满足 \(i,j,k\) 两两之间的距离都相等。 \((i,j,k)\) 与 \((i,k,j)\) 算作同一组。 输入格式: 第一行一个整数 \(n\)。 接下来 \(n-1\) 行,每行两个整数 \(a,b\),表示在 \(a,b\) 之间有一条边。 输出格式: 一行一个整数,表示所有合法的点的组数。 数据范围: 对于 \(100\%\) 的数据, \(1\le n\le10^5, 1\le a\le b\le n\)。 设 \(f(i,j)\) 为 \(i\) 所在子树中 \(\mathrm{dis}(x,i)=j\) 的 \(x\) 的个数。 设 \(g(i,j)\) 为 \(i\) 所在子树中满足 \[ \mathrm{dis}(\mathrm{LCA}(x, y), x)= \mathrm{dis}(\mathrm{LCA}(x, y), y)...
AT_code_festival_2017_qualb_e Popping Balls 题解
AT_code_festival_2017_qualb_e Popping Balls 题解 题目链接:Popping Balls 题意: 有 \(A+B\) 个球排成一行,其中左边 \(A\) 个是红色的,右边 \(B\) 个是蓝色的。 你可以选定一对整数 \((s,t)~(1\le s<t\le A + B)\),然后重复进行以下操作直到球被取完: 将第一个球或第 \(s\) 个球或第 \(t\) 个球(当前球的数量必须够才能执行)拿出来。 求最后拿出来的球的颜色序列有多少种不同方案数。答案对 \(10^9+7\) 取模。 方案不同当且仅当存在某一次取出的球的颜色不同。 输入:\(A,B\) 。输出:一行答案。数据范围:\(A, B \leq 2000\)。 非常有趣的计数题。 注意到每次在 \(1\) 处拿球时,\(s,t\) 相当于向右移动一格;而从 \(s\) 处拿球,\(t\) 相当于向右一格。 那么当 \(s,t\) 均可用时, 若 \(s\) 处是红球,那么从 \(0\) 处拿球一定不劣于从 \(s\) 处拿球。 若 \(s\) 处是蓝球,那么从 \(...
洛谷P4383 [八省联考 2018] 林克卡特树 题解
洛谷P4383 [八省联考 2018] 林克卡特树 题解 题目链接:P4383 [八省联考 2018] 林克卡特树 题目描述 qry 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔,他尤其喜欢游戏中的迷你挑战。 游戏中有一个叫做 LCT 的挑战,它的规则是这样子的:现在有一个 \(N\) 个点的树,每条边有一个整数边权 \(v_i\),若 \(v_i \geq 0\),表示走这条边会获得 \(v_i\) 的收益;若 \(v_i \lt 0\) ,则表示走这条边需要支付 \(-v_i\) 的过路费。qry 需要控制主角 Link 切掉(Cut)树上的恰好 \(K\) 条边,然后再连接 \(K\) 条边权为 0 的边,得到一棵新的树。接着,他会选择树上的两个点 \(p,q\),并沿着树上连接这两点的简单路径从 \(p\) 走到 \(q\),并为经过的每条边支付过路费/ 获取相应收益。 海拉鲁大陆之神 TemporaryDO 想考验一下 Link。他告诉 Link,如果 Link 能切掉合适的边、选择合适的路径...
CF1147E Rainbow Coins 题解
CF1147E Rainbow Coins 题解 题目链接:Rainbow Coins 题意: qry 有 \(n\) 枚各种颜色的硬币,她想把它们分类成堆。这些硬币标号为 \(1, 2, \ldots, n\),每个硬币是红色、绿色或蓝色之一。她希望将硬币分类成三堆,其中一堆包含所有的红色硬币,一堆包含所有的绿色硬币,另一堆包含所有的蓝色硬币。 不幸的是,qry 是色盲,因此她无法完成这项任务。幸运的是,她有一个朋友可以检查一对硬币并告诉 qry 它们是否是同一种颜色。利用她的朋友,qry 相信她现在可以对硬币进行分类。 堆之间的顺序无所谓,只要相同颜色的硬币在同一堆里,不同颜色的硬币不在同一堆里即可。 她的朋友会批量回答关于多个硬币对的问题,并且会并行回答这些对的所有问题。每个批次中,每个硬币最多只能出现在一个对中。同一个硬币可以出现在不同的批次中。 qry 只能使用 \(7\) 次询问。帮她找到分类后的硬币堆。 交互格式: 会给出多个测试用例。第一行包含一个整数 \(t\) \((1 \leq t \leq 5)\)——测试用例的数量。 每个测试用例的第一行包含一个整数 ...
CF725E Too Much Money 题解
CF725E Too Much Money 题解 题目链接:Too Much Money 题意: 给定一件 \(c\) 元的物品,以及 \(n\) 个硬币,其中硬币的面值可以时任意价格,第 \(i\) 个硬币面值为 \(a_i\) 现在要用这 \(n\) 个硬币恰好凑出 \(c\) 元。有这样一种贪心策略: 初始选择集合 \(S\) 为空,每次选择不超过剩余所需价值的最大面值硬币并将其加入 \(S\) 中。 但是出题人表示不服,要卡掉这个算法。 他要加入任意数量的硬币,每个硬币可以是任意面值,使得最后算法不能得出合法的 \(S\) 集合。 同时他想最小化加入硬币的总价值。 输入数据: 第一行两个正整数 \(c,n\) 。第二行 \(n\) 个正整数 \(a_i\) 。 输出数据: 输出该组数据最小代价,如果出题人永远无法卡掉这个算法,那么输出 Greed is good。 首先,我们只需要一枚硬币就能卡掉错误的情况。 考虑反证法。假设需要两枚硬币 \(a,b~(a \le b)\) ,那么当前值不小于 \(a+b\) 时肯定不能卡掉,否则只需要一枚。 那么我们直接枚举 \([...
《组合数学》 §3.1 学习笔记
《组合数学》 §3.1 学习笔记 前言:本章节主要讲述容斥原理。可参考 容斥原理 学习笔记 3.1.1 ~ 3.1.3 略。 定理 3.1.4 (容斥原理) 设 \(S\) 为一有限集,\(\mathcal{P} = \{P_1,P_2,\cdots,P_m\}\) 为一族性质。 对 \([m]\) 的任一子集 \(I\) ,令 \(X_I\) 表示 \(S\) 中满足性质 \(P_i\) (对于所有 \(i \in I\) )的那些元素构成的集合。 特别地,当 \(I=\{i\}\) 时,简记 \(X_{\{i\}}\) 为 \(X_i\) 。记 \(\overline{X_I} = S \setminus X_I\) 。 则集合 \(S\) 中不具有 \(\mathcal{P}\) 中任何一种性质的元素个数由下式给出 \[ \begin{aligned} \left|\overline{X_1}\cap\overline{X_2}\cdots\cap\overline{X_m}\right| &= |S| - \sum_i |X_i| + \sum_{i < j...
洛谷P5470 [NOI2019] 序列 题解
洛谷P5470 [NOI2019] 序列 题解 题目链接:P5470 [NOI2019] 序列 题意: 给定两个长度为 \(n\) 的正整数序列 \(\{a_i\}\) 与 \(\{b_i\}\),序列的下标为 \(1, 2, \cdots , n\)。 现在你需要分别对两个序列各指定恰好 \(K\) 个下标,共 \(2K\) 个下标 要求至少有 \(L\) 个下标在两个序列中都被指定,使得这 \(2K\) 个下标在序列中对应的元素的总和最大。 形式化地说,你需要确定两个长度为 \(K\) 的序列 \(\{c_i\}, \{d_i\}\),其中 \[ 1 \leq c_1 < c_2 < \cdots < c_K \leq n , 1 \leq d_1 < d_2 < \cdots < d_K \leq n \] 并要求 \(\{c_1, c_2, \cdots , c_K\} \cap \{d_1, d_2, · · · , d_K\}\geq L\) ,目标是最大化 \(\sum^{K}_{i=1} a_{c_i} +\sum^{K}_{...
洛谷P3203 [HNOI2010] 弹飞绵羊 题解
洛谷P3203 [HNOI2010] 弹飞绵羊 题解 题目链接:P3203 [HNOI2010] 弹飞绵羊 题意: 某天,qry 发明了一种超级弹力装置,为了在她的绵羊朋友面前显摆,她邀请小绵羊一起玩个游戏。 游戏一开始,qry 在地上沿着一条直线摆上 \(n\) 个装置,每个装置设定初始弹力系数 \(k_i\),当绵羊达到第 \(i\) 个装置时,它会往后弹 \(k_i\) 步,达到第 \(i+k_i\) 个装置,若不存在第 \(i+k_i\) 个装置,则绵羊被弹飞。 绵羊想知道当它从第 \(i\) 个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,qry 可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。 输入格式: 第一行包含一个整数 \(n\),表示地上有 \(n\) 个装置,装置的编号从 \(0 \sim n-1\)。 接下来一行有 \(n\) 个正整数,依次为那 \(n\) 个装置的初始弹力系数。 第三行有一个正整数 \(m\),表示操作次数。接下来 \(m\) 行每行至少有两个数 \(i,j\)。 若 \(i=1\),你要输出从编号为 \(j\) ...
CF436E Cardboard Box 题解
CF436E Cardboard Box 题解 题目链接:Cardboard Box 题意: 每个玩过《Cut the Rope》的人都很清楚游戏的玩法。游戏中的所有关卡都分为多个盒子。最初只有一个包含一些关卡的盒子是可用的。玩家需要通过完成关卡来获得星星,收集星星可以解锁包含新关卡的盒子。 假设你是第一次玩《Cut the Rope》。目前你只有第一个盒子的关卡(顺便说一句,它被称为“纸箱盒”)。每个关卡有两个整数特征:\(a_{i}\) — 完成该关卡以获得一颗星所需的时间,\(b_{i}\) — 完成该关卡以获得两颗星所需的时间(\(a_{i} < b_{i}\))。 你想尽快打开下一个盒子。因此,你需要至少获得 \(w\) 颗星。如何实现这一目标?注意,每个关卡只能通过一次:要么获得一颗星,要么获得两颗星。不一定需要通过所有关卡。 省流: \(n\) 个关卡,对每个关卡,你可以花 \(a_i\) 代价得到一颗星,也可以花 \(b_i\) 代价得到两颗星也可以不玩。 问获得 \(w\) 颗星最少需要多少时间。保证 \(a_i < b_i\) 。 输入格式: ...



![洛谷P5904 [POI2014] HOT-Hotels 加强版 题解](/qwq/img/p208.webp)

![洛谷P4383 [八省联考 2018] 林克卡特树 题解](/qwq/img/p40.webp)



![洛谷P5470 [NOI2019] 序列 题解](/qwq/img/p26.webp)
![洛谷P3203 [HNOI2010] 弹飞绵羊 题解](/qwq/img/p161.webp)



![洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解](/qwq/img/p214.webp)
![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p230.webp)