CF730I Olympiad in Programming and Sports 题解
CF730I Olympiad in Programming and Sports 题解 题目链接:Olympiad in Programming and Sports 题意: 有 \(n\) 个学生每人有两种技能,分别是 \(a,b\) 表示编程能力和运动能力。你需要将他们分为两个团队分别参加编程比赛和体育比赛,编程团队有 \(p\) 人,体育团队有 \(s\) 人,一个学生只能参加其中一项。每个团队的力量是其成员在对应领域能力总和,请问如何分配能使得两个团队的实力和最大? 输入格式 共三行,第一行包含三个正整数 \(n,p,s\)。 第二行有 \(n\) 个整数 \(a_1,a_2\cdots a_n\),第三行,有 \(n\) 个整数\(b_1,b_2\cdots b_n\)。 输出格式 第一行输出整个团队最大的实力,然后给出一种构造方案即可。 数据范围: \(2\le n\le 3\times 10^3,~1\le p+s\le n,~1\le a_i,b_i\le 3000\)。 经典的多个堆维护反悔贪心。做完这题可以去做一下 CF436E 和 P5470 考虑将最...
洛谷P3545 [POI2012] HUR-Warehouse Store 题解
洛谷P3545 [POI2012] HUR-Warehouse Store 题解 题目链接:P3545 [POI2012] HUR-Warehouse Store 题意: 现在有 \(n\) 天。第 \(i\) 天上午会进货 \(A_i\) 件商品,中午的时候会有顾客需要购买 \(B_i\) 件商品,可以选择满足顾客的要求,或是无视掉他。 如果要满足顾客的需求,就必须要有足够的库存。问最多能够满足多少个顾客的需求。 输入格式: 第一行包含一个整数 \(n\),表示有 \(n\) 天。 第二行有 \(n\) 个整数 \(a_i\),表示第 \(i\) 天上午进货 \(a\) 件商品。 第三行包含 \(n\) 个整数 \(b_i\),表示在第 \(i\) 天中午有顾客来买 \(b\) 件商品。 输出格式: 第一行一个整数,表示最多能满足几天中顾客的需求。 第二行输出满足这么哪些天顾客的需求。 数据范围: \(1\le n\le 2.5\times 10^5,~0\le a_i,b_i \le 10^9\)。 考虑反悔贪心。每次直接选 \(b_i\) 。 如果发现库存不够了,就从之...
洛谷P2107 小Z的AK计划 题解
洛谷P2107 小Z的AK计划 题解 题目链接:P2107 小Z的AK计划 题意: 在小 Z 的家乡,有机房一条街,街上有很多机房。每个机房里都有一万个人在切题。小 Z 刚刷完 CodeChef,准备出来逛逛。 机房一条街有 \(n\) 个机房,第 \(i\) 个机房的坐标为 \(x_i\) ,小 Z 的家坐标为 \(0\)。小 Z 在街上移动的速度为 \(1\),即从 \(x_1\) 到 \(x_2\) 所耗费的时间为 \(|x_1 - x_2|\)。 每个机房的学生数量不同,ACM 题目水平也良莠不齐。小 Z 到达第 \(i\) 个机房后,可以花 \(t_i\) 的时间想题,然后瞬间 AK;当然,也可以过机房而不入。 小 Z 现在只有 \(m\) 个单位时间,之后他就该赶着去打 Codeforces 了。现在他想知道自己最多能在多少个机房 AK,希望你帮帮他。 输入格式: 第一行包含两个整数 \(n,m\)。 接下来 \(n\) 行,每行包含两个整数 \(x_i,t_i\)。 输出格式: 第一行包含一个整数,表示小 Z 最多能 AK 的机房数量。 数据范围: \(1 \le...
AT_agc006_d [AGC006D] Median Pyramid Hard 题解
AT_agc006_d [AGC006D] Median Pyramid Hard 题解 题目链接:AT_agc006_d [AGC006D] Median Pyramid Hard 题意: 给出一个 \(N~(1 \le N \le 10^5)\) 层的方格金字塔,自顶向下依次标号为第 \(1\) 到第 \(N\) 层。 其中第 \(i~(1 \le i \le N)\) 层有 \(2i - 1\) 个方格(具体形态见下面的图) 第 \(N\) 层有一个 \(1\) 到 \(2N-1\) 的排列,其他层的数字按以下规则生成: 方格 \(b\) 中填写的整数,是方格 \(b\) 正下方、左下方和右下方方格中所写整数的中位数。 现在给出第 \(N\) 层的数字,请你求第一层的数字。 考虑二分最上层这个数 \(\ge x\),然后令 \(\ge x\) 的数为 \(1\) ,\(<x\) 的的数为 \(0\) 。 那么原题可以转化为,每次操作对于相邻的三个数, 如果 \(1\) 的个数 \(\ge 3\) 则为 \(1\) ,否则为 \(0\) ,最终最上面的那个数是...
CF73D FreeDiv 题解
CF73D FreeDiv 题解 题目链接:FreeDiv 题意: 你要执行以下两步操作: 在图中任意连边 在第一步操作后得到一张新图,在新图中继续连边。 要求每个点只能在这步中连一条边,每个新图中的连通块只能连 \(k\) 条边 要求在这两步操作后图是连通的,求第一步中最少要连多少边 数据范围: \(1 \le n,k \le 10^6,~0 \le m \le 10^6\) 显然这个第一步操作实际上是由第二步的决策决定的。 注意到要使得图连通,我们可以用两个连通块连一条边这样的方式合并 考虑把原图的连通块看作一个点,设有 \(d\) 个连通块。 由于让这 \(d\) 个点连通至少需要 \(d-1\) 条边,则当且仅当 \[ \sum_{i=1}^d \min \left(a_i, k\right) \geq 2(d-1) \] 时,我们可以通过操作二完成合并。 而第一个操作实际上在减少 \(d\) ,同时左侧如果加的边不好可能会让左侧减小。 考虑用小根堆维护每个连通块的大小,每次取最小的两个连通块合并,直到上述不等式成立即可。 时间复杂度 \(\mathcal{O}(...
模拟赛题讲解[35]
模拟赛题讲解[35] 题目链接:noi.ac #3714 (让 mygr 巨佬帮我交的隐藏题) 一、题面 菜汪酱发现了 \(n\) 个宝箱,编号为 1 到 \(n\)。 这些宝箱被 \(m\) 条铁链绑在了一起。每条铁链连接两个宝箱。 菜汪酱希望拿走尽可能多的宝箱。但是宝箱不能乱拿,否则会触发机关。经过解密,菜汪酱知道一种方案是安全的当且仅当: 拿走的宝箱两两之间有铁链连接。 没有拿走的宝箱两两之间没有铁链连接。 菜汪酱希望在保证安全的情况下拿走尽可能多的宝箱。这个问题的解决方案交给你了。 输入格式 第一行两个整数 \(n\) 和 \(m\)。 接下来 \(m\) 行每行两个整数 \(u\) 和 \(v\),表示一条铁链连接宝箱 \(u\) 和 \(v\)。 保证不会有两条铁链连接相同的宝箱。 保证存在一种安全的方案。 输出格式 第一行输出一个整数 \(\rm ans\),表示拿走的宝箱个数。 第二行输出 \(\rm ans\) 个整数,表示选择的宝箱编号。 输入输出样例 输入: 7 9 2 5 3 5 5 7 7 1 1 4 1 2 5 4 7 4 1 5 输出: 4 5...
CF746G New Roads 题解
CF746G New Roads 题解 题目链接:New Roads 题意: 在Berland有 \(n\) 个城市,每一座城市都有一个单独的编号——在 \(1\) 到 \(n\) 范围内的一个整数,首都的编号是 \(1\)。现在,在Berland有一个极其严峻的问题:城市之间没有道路相连。 为了使得每个城市之间都有路相连,要在城市之间建造 \(n-1\) 条路。 在建造计划中一共有 \(t\) 个整数 \(a_1,a_2,\cdots,a_t\) ,其中 \(t\) 等于首都与离首都最远的城市之间的距离。\(a_i\) 表示一共有 \(a_i\) 座城市与首都之间的距离是 \(i\)。两个城市之间的距离等于从一座城市到另一座城市所经过的道路的数量。 而且,除了首都以外一共会有 k 座城市仅与一条道路相连。这些城市是“死胡同”,它们没有经济吸引力。首都不算在内(即,即使只有一条道路与首都相连,首都也不算在“死胡同”里)。 你的任务是做出符合所有条件的计划,或是说明符合所有条件的计划是不存在的。 输入格式: 输入数据的第一行包括三个整数 \(n,t,k~(2 \le n \le ...
洛谷P2831 [NOIP2016 提高组] 愤怒的小鸟 题解
洛谷P2831 [NOIP2016 提高组] 愤怒的小鸟 题解 题目链接:P2831 [NOIP2016 提高组] 愤怒的小鸟 题意: Kiana 最近沉迷于一款神奇的游戏无法自拔。 简单来说,这款游戏是在一个平面上进行的。 有一架弹弓位于 \((0,0)\) 处,每次 Kiana 可以用它向第一象限发射一只红色的小鸟,小鸟们的飞行轨迹均为形如 \(y=ax^2+bx\) 的曲线,其中 \(a,b\) 是 Kiana 指定的参数,且必须满足 \(a < 0\),\(a,b\) 都是实数。 当小鸟落回地面(即 \(x\) 轴)时,它就会瞬间消失。 在游戏的某个关卡里,平面的第一象限中有 \(n\) 只绿色的小猪,其中第 \(i\) 只小猪所在的坐标为 \(\left(x_i,y_i \right)\)。 如果某只小鸟的飞行轨迹经过了 \(\left( x_i, y_i \right)\),那么第 \(i\) 只小猪就会被消灭掉,同时小鸟将会沿着原先的轨迹继续飞行; 如果一只小鸟的飞行轨迹没有经过 \(\left( x_i, y_i \right)\),那么这只小鸟飞行的全过...
AT_agc023_f [AGC023F] 01 on Tree 题解
AT_agc023_f [AGC023F] 01 on Tree 题解 题目链接:AT_agc023_f [AGC023F] 01 on Tree 题意: 给出一棵 \(n\) 个节点的树,以及一个空序列。每个节点上有一个取值在 \(\{0, 1\}\) 中的数。 每次你可以选择没有父亲节点的点删除,并且将这个节点上的数字放在当前数列末尾。 请你求出这个数列可能得到的最小逆序对数。 \(1 \le n \leq 2 \times 10^5\) 。 听说是 Exchange Argument 的经典题,之前没见过。 首先这个删父亲再倒序放实在是有些奇怪,我们可以把它看作一棵内向树的某种拓扑序。 显然,如果可选的节点中存在 \(0\) ,那么优先选这些节点一定不劣。 考虑每次选择一个节点后,将其与父亲合并。 这里考虑并查集即可,然后维护当前节点有多少个 \(0,1\) 。 对于两个节点 \(a,b\) ,记 \(a_0,a_1\) 和 \(b_0,b_1\) 是他们的 \(0,1\) 个数 由于 \(a,b\) 的子树已经按最优方案选择了,所以我们只需要考虑最小化因他们的顺序产生...
CF1100E Andrew and Taxi 题解
CF1100E Andrew and Taxi 题解 题目链接:Andrew and Taxi 题意: 给定一个 \(n\) 个点 \(m\) 条边的有向图,边有权值 \(w_i\) 。 要求改变其中某些边的方向,使其成为一个有向无环图。 现在求一个改变边方向的方案,使得所选边边权的最大值最小。 数据范围: \(1 \le n,m \le 10^5,~1 \le w_i \le 10^9\) 。 考虑二分边权的最大值 \(x\) ,那么现在所有边分成了两种 边权 \(w_i\) 小于等于 \(x\) 的边 边权 \(w_i\) 大于 \(x\) 的边 显然,如果第二种边构成了环,那么这种情况是不行的。 考虑拓扑排序判环,顺便记录一下每个点的拓扑序。 那么需要翻转的第一种边 \(u_i \to v_i\) 一定有 \(T(v_i) < T(u_i)\) ,其中 \(T\) 表示节点的拓扑序。 于是这道题就做完了,还是蛮简单的。结果我连拓扑排序判环都没想到,很少用。 时间复杂度 \(\mathcal{O}(n \log m)\) 代码: #include <bit...
CF662B Graph Coloring 题解
CF662B Graph Coloring 题解 题目链接:Graph Coloring 题意: 给出一张 \(n\) 个点,\(m\) 条边的无向图,一开始每条边可能是红色或者蓝色, 翻转一个点可以使相连的边变成相反的颜色,要求把所有边变成红色或者蓝色 问最少需要翻转的点数,并给出具体的方案 输入格式: 第一行输入 \(n,m\),分别表示点的数量和边的数量 \((1\leq n,m\leq 100000)\) 。 第二至 \(m+1\) 行 \(u_i,v_i,c_i\),分别表示无向边的两个点以及它的颜色,保证没有重边和自环 输出格式: 如果没有方法使其合法输出 \(-1\), 否则第一行输出最少需要翻转的点数,第二行用空格分隔输出翻转点的编号,只需要输出一种方案 考虑对全部染成 \(\mathbf{R}\) 和全部染成 \(\mathbf{B}\) 的方案取 min。 下面以 \(\mathbf{R}\) 为例。显然每个点至多翻转 \(1\) 次,那么记 \(i\) 为点 \(i\) 不翻转,\(i + n\) 为点 \(i\) 翻转。 若 \(c_i = \mat...
2–SAT 学习笔记
2–SAT 学习笔记 现在 2–SAT 已经是蓝题了吗。 由于我的模板都不知道是多少年前写的了,所以就有了这边文章。 2–SAT 问题 模板题链接:P4782 【模板】2–SAT 题意: 有 \(n\) 个布尔变量 \(x_1,x_2,\cdots,x_n\),另有 \(m\) 个需要满足的条件,每个条件的形式都是 「\(x_i\) 为 true / false 或 \(x_j\) 为 true / false」。比如 「\(x_1\) 为真或 \(x_3\) 为假」、「\(x_7\) 为假或 \(x_2\) 为假」。 2–SAT 问题的目标是给每个变量赋值使得所有条件得到满足。 输入格式: 第一行两个整数 \(n\) 和 \(m\),意义如题面所述。 接下来 \(m\) 行每行 \(4\) 个整数 \(i,a,j,b\),表示 「\(x_i\) 为 \(a\) 或 \(x_j\) 为 \(b\)」\((a, b\in \{0,1\})\) 输出格式: 如无解,输出 IMPOSSIBLE;否则输出 POSSIBLE。 下一行 \(n\) 个整数 \(x_1,x_2,\cdots...

![洛谷P3545 [POI2012] HUR-Warehouse Store 题解](/qwq/img/p57.webp)

![AT_agc006_d [AGC006D] Median Pyramid Hard 题解](/qwq/img/p55.webp)

![模拟赛题讲解[35]](/qwq/img/p120.webp)

![洛谷P2831 [NOIP2016 提高组] 愤怒的小鸟 题解](/qwq/img/p143.webp)
![AT_agc023_f [AGC023F] 01 on Tree 题解](/qwq/img/p169.webp)



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

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