Q779’s Blog

洛谷P4383 [八省联考 2018] 林克卡特树 题解 题目链接：P4383 [八省联考 2018] 林克卡特树 题意： 小 L 最近沉迷于塞尔达传说：荒野之息（The Legend of Zelda: Breath of The Wild）无法自拔，他尤其喜欢游戏中的迷你挑战。 游戏中有一个叫做 LCT 的挑战，它的规则是这样子的：现在有一个 \(N\) 个点的树，每条边有一个整数边权 \(v_i\)，若 \(v_i \geq 0\)，表示走这条边会获得 \(v_i\) 的收益；若 \(v_i \lt 0\) ，则表示走这条边需要支付 \(-v_i\) 的过路费。小 L 需要控制主角 Link 切掉（Cut）树上的恰好 \(K\) 条边，然后再连接 \(K\) 条边权为 0 的边，得到一棵新的树。接着，他会选择树上的两个点 \(p,q\)，并沿着树上连接这两点的简单路径从 \(p\) 走到 \(q\)，并为经过的每条边支付过路费/ 获取相应收益。 海拉鲁大陆之神 TemporaryDO 想考验一下 Link。他告诉 Link，如果 Link 能切掉合适的边、选择合适的路径从...

CF1147E Rainbow Coins 题解 题目链接：Rainbow Coins 题意： cxy 有 \(n\) 枚各种颜色的硬币，她想把它们分类成堆。这些硬币标号为 \(1, 2, \ldots, n\)，每个硬币是红色、绿色或蓝色之一。她希望将硬币分类成三堆，其中一堆包含所有的红色硬币，一堆包含所有的绿色硬币，另一堆包含所有的蓝色硬币。 不幸的是，cxy 是色盲，因此她无法完成这项任务。幸运的是，她有一个朋友可以检查一对硬币并告诉 cxy 它们是否是同一种颜色。利用她的朋友，cxy 相信她现在可以对硬币进行分类。 堆之间的顺序无所谓，只要相同颜色的硬币在同一堆里，不同颜色的硬币不在同一堆里即可。 她的朋友会批量回答关于多个硬币对的问题，并且会并行回答这些对的所有问题。每个批次中，每个硬币最多只能出现在一个对中。同一个硬币可以出现在不同的批次中。 cxy 只能使用 \(7\) 次询问。帮她找到分类后的硬币堆。 交互格式： 会给出多个测试用例。第一行包含一个整数 \(t\) \((1 \leq t \leq 5)\)——测试用例的数量。 每个测试用例的第一行包含一个整数 ...

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.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] 序列 题意： 给定两个长度为 \(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] 弹飞绵羊 题意： 某天，cxy 发明了一种超级弹力装置，为了在她的绵羊朋友面前显摆，她邀请小绵羊一起玩个游戏。 游戏一开始，cxy 在地上沿着一条直线摆上 \(n\) 个装置，每个装置设定初始弹力系数 \(k_i\)，当绵羊达到第 \(i\) 个装置时，它会往后弹 \(k_i\) 步，达到第 \(i+k_i\) 个装置，若不存在第 \(i+k_i\) 个装置，则绵羊被弹飞。 绵羊想知道当它从第 \(i\) 个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，cxy 可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。 输入格式： 第一行包含一个整数 \(n\)，表示地上有 \(n\) 个装置，装置的编号从 \(0 \sim n-1\)。 接下来一行有 \(n\) 个正整数，依次为那 \(n\) 个装置的初始弹力系数。 第三行有一个正整数 \(m\)，表示操作次数。接下来 \(m\) 行每行至少有两个数 \(i,j\)。 若 \(i=1\)，你要输出从编号为 \(j\) ...

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\) 。 输入格式： ...

洛谷P4694 [PA2013] Raper 题解 题目链接：P4694 [PA2013] Raper 题意： 你需要生产 \(k\) 张光盘。每张光盘都要经过两道工序：先在 A 工厂进行挤压，再送到 B 工厂涂上反光层。 你知道每天 A、B 工厂分别加工一张光盘的花费。你现在有 \(n\) 天时间，每天可以先送一张光盘到 A 工厂（或者不送），然后再送一张已经在 A 工厂加工过的光盘到 B 工厂（或者不送），每家工厂一天只能对一张光盘进行操作，同一张光盘在一天内生产出来是允许的。我们假定将未加工的或半成品的光盘保存起来不需要费用。 求生产出 \(k\) 张光盘的最小花费。 输入格式 第一行包含两个整数 \(n, k\)，表示有 \(n\) 天，要生产 \(k\) 张光盘。 第二行包含 \(n\) 个整数，第 \(i\) 个整数表示第 \(i\) 天送到 A 工厂加工光盘的花费。 第三行包含 \(n\) 个整数，第 \(i\) 个整数表示第 \(i\) 天送到 B 工厂加工光盘的花费。 输出格式 输出一行一个整数，表示最小花费。 数据范围： 保证 \(1 \le k \le n...

CF1147F Zigzag Game 题解 题目链接：Zigzag Game 题意： 这是一道交互题，并且有 \(T\) 组数据。 给出一个两边均有 \(n\) 个节点的完全二分图，左部点由 \(1\) 到 \(n\) 编号，右部点由 \(n+1\) 到 \(2n\) 编号。输入中会给出一个 \(n \times n\) 的矩阵 \(a\)，其中 \(a_{i,j}\) 表示连接 \(i\) 和 \(j+n\) 的边的边权。 现在有两个玩家 Alice 和 Bob 在这个图上玩游戏。首先 Alice 会选择 “increasing”（增加）或者 “decreasing”（减少）中的一个属性，Bob 则会自动选择另一个。接下来由 Alice 在图上选择一个起始节点 \(p\) 放上一枚棋子，Bob 选择一条连接节点 \(p\) 的边 \((p,q)\)，将棋子移动到 \(q\)。 接下来由 Alice 先手轮流进行操作。每一次操作时操作方需要选择一个与当前节点 \(x\) 相邻的未被经过的节点 \(y\)。设 \(w\) 为 \((x,y)\) 的边权，\(w'\) 为...

洛谷P4055 [JSOI2009] 游戏 题解 题目链接：P4055 [JSOI2009] 游戏 题意： Alice 和 Bob 得到了《喜羊羊和灰太狼》的电影票，都很想去观看，但是电影票只有一张，于是他们用智力游戏决定胜负，赢得游戏的人可以获得电影票。 在 \(n,m\) 的迷宫中有一个棋子，Alice 首先任意选择棋子放置的位置。然后， Bob 和 Alice 轮流将棋子移动到相邻的格子里。游戏的规则规定，在一次游戏中，同一个格子不能进入两次，且不能将棋子移动到某些格子中去。当玩家无法继续移动棋子时，游戏结束，最后一个移动棋子的玩家赢得了游戏。 例如下图所示的迷宫，迷宫中 . 表示棋子可以经过的格子，而 # 表示棋子不可以经过的格子： .## ... #.# 若 Alice 将棋子放置在 \((1,1)\)，则 Alice 则无论如何都无法赢得游戏。 而若 Alice 将棋子放置在 \((3,2)\) 或 \((2,3)\)，则Alice 能够赢得游戏。例如，Alice 将棋子放置在 \((3,2)\)，Bob 只能将它移动到 \((2,2)\)，此时 Alice 再将...

洛谷P4424 [HNOI/AHOI2018] 寻宝游戏 题解 题目链接：P4424 [HNOI/AHOI2018] 寻宝游戏 题意： 某大学每年都会有一次 Mystery Hunt 的活动，玩家需要根据设置的线索解谜，找到宝藏的位置，前一年获胜的队伍可以获得这一年出题的机会。 作为新生的你，对这个活动非常感兴趣。你每天都要从西向东经过教学楼一条很长的走廊，这条走廊是如此的长，以至于它被人戏称为 infinite corridor。一次，你经过这条走廊时注意到在走廊的墙壁上隐藏着 \(n\) 个等长的二进制的数字，长度均为 \(m\)。你从西向东将这些数字记录了下来，形成一个含有 \(n\) 个数的二进制数组 \(a_1,a_2,...,a_n\)。 很快，在最新的一期的 Voo Doo 杂志上，你发现了 \(q\) 个长度也为 \(m\) 的二进制数 \(r_1,r_2,...,r_q\)。 聪明的你很快发现了这些数字的含义。 保持数组 \(a_1,a_2,...,a_n\) 的元素顺序不变，你可以在它们之间插入 \(\land\)（按位与运算）或者 \(\lor\)（按位或...

AT_code_festival_2017_qualb_f Largest Smallest Cyclic Shift 题解 题目链接：Largest Smallest Cyclic Shift 题意： 定义 \(f(S)\) 为：对于一个字符串 \(S\)，每次将它最左边的字符放置到字符串末尾生成的字符串集合中，字典序最小的字符串。例如：对于 \(S\) 为 babca 的情况，\(f(S)\) 即为 babca、abcab、bcaba、cabab、ababc 中最小的那个，即 ababc。 你需要构造一个字符串 \(T\)，共包含 \(X\) 个字符 a、\(Y\) 个字符 b 和 \(Z\) 个字符 c，使得 \(f(T)\) 尽可能大，输出这个 \(f(T)\)。 数据范围：\(1 \le X + Y + Z \le 50\) 。 非常有趣的贪心题。注意到 \(X=Y=Z\) 时，最优方案是 \(\tt abc\) 。 考虑递归的构建字符串。设 \(s_1,s_2,s_3\) 是当前最优的三个字符串，规定 \(s_1 < s_2 < s_3\) 。 显然我...