Q779’s Blog

洛谷P2120 [ZJOI2007] 仓库建设 题解 题目链接：P2120 [ZJOI2007] 仓库建设 题意： L 公司有 \(n\) 个工厂，由高到低分布在一座山上，工厂 \(1\) 在山顶，工厂 \(n\) 在山脚。 由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L 公司的总裁 L 先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是 L 先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。 由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第 \(i\) 个工厂目前已有成品 \(p_i\) 件，在第 \(i\) 个工厂位置建立仓库的费用是 \(c_i\)。 对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于 L 公司产品的对外销售处设置在山脚的工厂 \(n\)，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，一件产品运送一个单位距离的费用是 \(1\)。 假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到以下数据： 工厂 \(i\) 距离工厂 \(1\...

洛谷P1450 [HAOI2008] 硬币购物 题解 题目链接：P1450 [HAOI2008] 硬币购物 题意： 共有 \(4\) 种硬币。面值分别为 \(c_1,c_2,c_3,c_4\)。 某人去商店买东西，去了 \(n\) 次，对于每次购买，他带了 \(d_i\) 枚 \(i\) 种硬币，想购买 \(s\) 的价值的东西。请问每次有多少种付款方法。 输入格式： 输入的第一行是五个整数，分别代表 \(c_1,c_2,c_3,c_4, n\)。 接下来 \(n\) 行，每行有五个整数，描述一次购买，分别代表 \(d_1, d_2, d_3, d_4,s\)。 输出格式： 对于每次购买，输出一行一个整数代表答案。 数据范围： 对于 \(100\%\) 的数据，保证 \(1 \leq c_i, d_i, s \leq 10^5\)，\(1 \leq n \leq 1000\)。 首先可以想到朴素的背包dp，不过复杂度是 \(\mathcal{O}(4ns)\) 的。 考虑如果 \(d_i\) 足够大时，实际上我们不需要再去做 dp 了，只需要做一次 dp 存下来即可 不过这没...

洛谷P6137 [IOI2012] 理想城 题解 题目链接：P6137 [IOI2012] 理想城 题意： 像许多同龄的科学家和艺术家一样，小 L 对城市规划和城区设计很感兴趣.他致力于构建一个理想城。理想城由 \(N\) 个区块组成，而这些区块放在一个无限大的正方形网格上。第 \(x\) 行第 \(y\) 列的单元格由有序数对 \((x,y)\)来标识。单元格 \((0,0)\) 位于网格的左上角。给定一个单元格 \((x,y)\)，与之相邻的单元格（如果存在的话）分别为：\((x-1,y)\)，\((x+1,y)\)，\((x,y-1)\)，\((x,y+1)\)。每个区块在网格上恰好覆盖一个单元格。一个区块能够被放置在单元格 \((x,y)\) 上，当且仅当 \(1 \le x,y \le 2^{31}-2\) 。我们将使用单元格的坐标同时来代表单元格上面的区块。若两个区块被放在相邻的单元格中，则视它们为相邻区块.理想城所有的区块连在一起，里面没有“洞”存在.换言之，所有单元格必须满足下述两个条件： - 对于任意两个空白的单元格，至少存在一连串相邻的空白单元格连接它们。 ...

洛谷P4859 已经没有什么好害怕的了 题解 题目链接：P4859 已经没有什么好害怕的了 题意： 已经使 Madoka 有签订契约，和自己一起战斗的想法后，Mami 忽然感到自己不再是孤单一人了呢。 于是，之前的谨慎的战斗作风也消失了，在对 Charlotte 的傀儡使用终曲——Tiro Finale 后，Mami 面临着即将被 Charlotte 的本体吃掉的局面。 这时，已经多次面对过 Charlotte 的 Homura 告诉了学 OI 的你这样一个性质：Charlotte 的结界中有两种具有能量的元素，一种是“糖果”，另一种是“药片”，各有 \(n\) 个。在 Charlotte 发动进攻前，“糖果”和“药片”会两两配对，若恰好糖果比药片能量大的组数比“药片”比“糖果”能量大的组数多 \(k\) 组，则在这种局面下，Charlotte 的攻击会丟失，从而 Mami 仍有消灭 Charlotte 的可能。 你必须根据 Homura 告诉你的“糖果”和“药片”的能量的信息迅速告诉 Homura 这种情况的个数。 省流： 给出两个长度均为 \(n\) 的序列 \(a\) 和...

二项式反演 引入 根据容斥原理 \[ \left|A_1 \cup A_2 \cup \cdots \cup A_n\right|=\sum_{1 \leq i \leq n}\left|A_i\right|-\sum_{1 \leq i<j \leq n}\left|A_i \cap A_j\right|+\cdots+(-1)^{n-1} \times\left|A_1 \cap A_2 \cap \cdots \cap A_n\right| \] 的另一种形式 \[ \left|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}\right|=|S|-\sum_{1 \leq i \leq n}\left|A_i\right|+\sum_{1 \leq i<j \leq n}\left|A_i \cap A_j\right|-\cdots+(-1)^n \times\left|A_1 \cap A_2 \cap \cdots \cap A_n\right| \] 由于集合的补集的补...

[ABC291G] OR Sum 题解 题目链接：[ABC291G] OR Sum 题意： 给定两个长为 \(n\) 的序列 \(A_i,B_i\) 。 你可以对 \(A\) 进行若干次循环移位操作，即 对于任意 \(i~(0 \le i < n)\) ，令 \(A'_i \gets A_{(i + 1) \bmod n}\) 。 然后令 \(A \gets A'\) ，这相当于让 \(A\) 整体向左循环移位了一次。 请求出 \[ \max\left\{\sum_{i=0}^{n-1}\ (A_i \lor B_i)\right\} \] 其中 \(\lor\) 表示二进制下的或运算。 数据范围： \(2 \le n \le 5\times10^5,~0 \le A_i,B_i \le 31\) 发现 \(\lor\) 操作并不好做，考虑将 \(A_i,B_i\) 取反，然后求 \(\land\) 的最小值。 枚举循环移位了 \(j\) 次，考察 \(A,B\) 二进制下第 \(k\) 位，记为 \(a,b\) 。 那么记答案为 \(c_j\) ，...

CF1632E2 Distance Tree (hard version) 题解 题目链接：Distance Tree (hard version) 题意： 本题与 CF1632E1 的唯一区别在于 \(n\) 的数据范围。 给定一个包含 \(n\) 个节点的树，每条边的长度为 \(1\)。给出如下定义： 定义 \(d(v)\) 为从节点 \(1\) 到节点 \(v\) 的距离。 定义 \(f(x)\) 为在任意两个点 \(a,b\) 之间添加一个长度为 \(x\) 的边后，\(\max\limits_{1\le v\le n}d(v)\) 的最小值。 现在，对于所有的 \(1\le x\le n\)，求出 \(f(x)\) 的值。 数据范围： \(t\) 组数据，\(1\le t\le 10^4,~2\le \sum n\leq 3\times 10^5\)。 显然，以 \(1\) 为起点连边一定不劣。 设我们已经求出了 \(f(x)=k\) ，那么我们只需要考察 \(d(x) > k\) 的点即可，因为 \(d(x)\le k\) 的 \(x\) 连边也没意义。...

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】实验室外的攻防战 题解 题目链接：#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 加强版 题意： 给出一棵有 \(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 题解 题目链接：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\) 处是蓝球，那么从 \(...