CF1889C2 Doremy's Drying Plan (Hard Version) 题解
CF1889C2 Doremy’s Drying Plan (Hard Version) 题解 题目链接:Doremy’s Drying Plan (Hard Version) 题意: 多组数据。有 \(n\) 个点和 \(m\) 条线段,你可以选择 \(k\) 条线段删除, 要求最大化未被线段覆盖的点的数量,输出最大值。 数据范围: \(1 \le T \le 10^4,~1 \le \sum n,\sum m \le 2\times 10^5,~2 \le k \le \min(10, m),~1\le l_i \le r_i \le n\) 。 设 \(f(i,x,y)\) 为前 \(i\) 条线段,删除了 \(x\) 条,没有删除的线段的右端点是 \(y\) 时,覆盖位置的最小值。 把线段按左端点升序排序,这样转移考虑枚举当前线段是否被删除即可。 虽然 \(y\) 的值域非常大,但因为只有 \(k+1\) 个极大的右端点是有用的。 于是总状态数为 \(\mathcal{O}(mk^2)\) ,实现的时候可以用 \(i\times 2^{22} + x\times 2^...
CF19E Fairy 题解
CF19E Fairy 题解 题目链接:CF19E Fairy 题意: 给定 \(n\) 个点,\(m\) 条边的无向图,可以从图中删除一条边,问删除哪些边可以使图变成一个二分图。 输入格式: 第一行包含两个正整数 \(n,m~(n,m\le10^6)\),分别表示点数和边数。 第 \(2\sim m+1\) 行,每行两个正整数 \(x,y~(1 \le x,y \le n,~x\ne y)\),表示有一条 \((x,y)\) 的边。 输出格式: 第一行输出一个整数,表示能删除的边的个数。 第二行按照从小到大的顺序输出能删除的边的序号。 首先,一个图是二分图当且仅当图中没有奇数长度的环,即没有奇环。 那么我们只需要找到一些边,使得整个图删掉这些边以后没有奇环即可。 考虑建出原图的 DFS 树,则每个奇环对应了一条或多条非树边。 考虑只有一条非树边的奇环,不妨称之为主奇环。 结论1 若 \(e\) 为非树边,则 \(e\) 能被删除的当且仅当它位于(且仅位于)一个主奇环上。 证明 必要性显然,考虑证明充分性。 根据假设,若删除后还有奇环,则一定不是主奇环。 而任何一个非主奇环...
UOJ12 【UER #1】猜数 题解
UOJ12 【UER #1】猜数 题解 题目链接:#12. 【UER #1】猜数 题意: 给定一个完全平方数 \(n=a\times b=g \times l\) ,其中 \(a,b,g,l\) 均为正整数。 每次给出 \(g,l\) ,求 \(a + b\) 的最小值和最大值,保证 \(g \mid a\) 且 \(g \mid b\) 。 根据均值不等式,有 \(a + b \ge 2\sqrt{ab} = 2\sqrt{n}\) 。 由于 \(n=gl\) 是完全平方数,我们可以求得 \(\sqrt{n}\) 的值,得到 \(a + b\) 的下界,当 \(a=b=\sqrt{n}\) 时等号成立。 那么当 \(g \mid a,~g\mid b\) 时还能取到等号吗? 设 \(a = a_0g,~b = b_0g\) ,则 \(n = a_0b_0g^2\) ,则 \(l = a_0b_0g\) ,故 \(g \mid l\) 。 设 \(l = kg\) ,则 \(gl = kg^2\) 为完全平方数,故 \(k\) 也为完全平方数。 设 \(k=t^2\) ,则 ...
UOJ139 【UER #4】被删除的黑白树 题解
UOJ139 【UER #4】被删除的黑白树 题解 题目链接:#139. 【UER #4】被删除的黑白树 题意: 很久很久以前,有一棵树加入了 UOJ 群。 这天,在它讨论“一棵树应该怎么旋转”的时候一不小心被删除了,变成了被删除的树。 突然间,它突然发现它失去了颜色,变成了一棵纯白的树。这让它感觉很焦躁,于是它来拜托你给自己染上一些颜色。 我们可以把它描述为一棵 \(n\) 个节点的有根树(默认树的根为 \(1\) 号节点),所有非根的度数为 \(1\) 的节点被称为叶子节点。最开始所有的节点都是白色的。 现在你需要选出一些节点并把这些节点染成黑色的。为了迎合树的审美,你的染色方案必须要满足所有叶子节点到根路径上的黑色节点个数相同。 你发现黑色节点个数越多,树就会越高兴,所以你想要知道在所有合法的染色方案中,黑色节点总个数最多是多少。 输入格式: 第一行一个正整数 \(n\) 表示树的节点个数。 接下来的 \(n-1\) 行,每行是两个整数 \(u,v\ (1 \leq u,v \leq n,u \neq v)\) 表示树上的一条边。 输出格式: 一个整数,表示在所有合法方案...
洛谷P2473 [SCOI2008] 奖励关 题解
洛谷P2473 [SCOI2008] 奖励关 题解 题目链接:P2473 [SCOI2008] 奖励关 题意: 你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关。在这个奖励关里,系统将依次随机抛出 \(k\) 次宝物,每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再吃)。 宝物一共有 \(n\) 种,系统每次抛出这 \(n\) 种宝物的概率都相同且相互独立。也就是说,即使前 \((k-1)\) 次系统都抛出宝物 \(1\)(这种情况是有可能出现的,尽管概率非常小),第 \(k\) 次抛出各个宝物的概率依然均为 $ n $。 获取第 \(i\) 种宝物将得到 \(p_i\) 分,但并不是每种宝物都是可以随意获取的。第 \(i\) 种宝物有一个前提宝物集合 \(s_i\)。只有当 \(s_i\) 中所有宝物都至少吃过一次,才能吃第 \(i\) 种宝物(如果系统抛出了一个目前不能吃的宝物,相当于白白的损失了一次机会)。注意,\(p_i\) 可以是负数,但如果它是很多高分宝物的前提,损失短期利益而吃掉这个负分宝物将获得更大的长期利益。 假...
洛谷P2120 [ZJOI2007] 仓库建设 题解
洛谷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] 硬币购物 题解 题目链接: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] 理想城 题解 题目链接: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 已经没有什么好害怕的了 题解 题目链接: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| \] 由于集合的补集的补...
AT_abc291_g [ABC291G] OR Sum 题解
AT_abc291_g [ABC291G] OR Sum 题解 题目链接:AT_abc291_g [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\) 位,记为 \(...
CF1632E2 Distance Tree (hard version) 题解
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\) 连边也没意义。...




![洛谷P2473 [SCOI2008] 奖励关 题解](/qwq/img/p186.webp)
![洛谷P2120 [ZJOI2007] 仓库建设 题解](/qwq/img/p2.webp)
![洛谷P1450 [HAOI2008] 硬币购物 题解](/qwq/img/p226.webp)
![洛谷P6137 [IOI2012] 理想城 题解](/qwq/img/p40.webp)


![AT_abc291_g [ABC291G] OR Sum 题解](/qwq/img/p74.webp)


![洛谷B3869 [GESP202309 四级] 进制转换 题解](/qwq/img/p184.webp)

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