QOJ #5439. Meet in the Middle 题解
Description Byteland 有 nnn 座城市，从 111 到 nnn 编号，且有 n−1n-1n−1 条双向公路和 n−1n-1n−1 条双向铁路连接它们。 对于任意一对城市，都可以仅通过公路互相到达；同样，仅通过铁路也能互相到达。 Alice 和 Bob 计划在 Byteland 进行 qqq 次长途旅行。在每次旅行中，Alice 从第 aaa 座城市出发，只通过公路访问一些其
QOJ #7324. Eulerian Orientation 题解
Description 众所周知，一个无向图是欧拉图，当且仅当它的每个顶点的度数都是偶数。 现在，Yuuka 有一张包含 nnn 个顶点、mmm 条边的无向图，顶点方便地编号为 1,2,…,n1, 2, \dots, n1,2,…,n。所有的边一开始都是蓝色的。Yuuka 计划把其中一些边涂成红色，剩下的保持蓝色。 如果由红色边构成的子图是欧拉图，那么她会将 x2x^2x2 加到计数器中，其中
CF2062H Galaxy Generator 题解
Description 在一个二维宇宙中，恒星可以用平面上的点 (x,y)(x, y)(x,y) 表示。当且仅当两颗恒星的 xxx 或 yyy 坐标相同，且它们之间的线段上没有其他恒星时，这两颗恒星直接相连。定义星系为由直接或间接（通过其他恒星）相连的恒星组成的连通分量。 对于一个恒星集合，其价值定义为：经过任意次（可能为零次）以下操作后，能够得到的最小星系数量。每次操作中，你可以选择一个没有恒
CF2062G Permutation Factory 题解
Description 给定两个长度为 nnn 的排列 p1,p2,…,pnp_1, p_2, \ldots, p_np1,p2,…,pn 和 q1,q2,…,qnq_1, q_2, \ldots, q_nq1,q2,…,qn。每次操作中，你可以选择两个不同的整数 1≤i,j≤n1 \leq i, j \leq n1≤i,j≤n 并交换 pip_ipi 和 pjp_jpj。该操作
CF1456E XOR-ranges 题解
Description 有 nnn 个位数不超过 KKK 的二进制变量 x1,x2,…,xnx_1, x_2, \dots, x_nx1,x2,…,xn，其中 xix_ixi 的取值范围是 [li,ri][l_i, r_i][li,ri]。 给出数列 c0,c1,…,cK−1c_0, c_1, \dots, c_{K-1}c0,c1,…,cK−1，并由此定义一个代价函数 f(x
CF2066F Curse 题解
Description 给定两个整数数组 a1,a2,…,ana_1, a_2, \ldots, a_na1,a2,…,an 和 b1,b2,…,bmb_1, b_2, \ldots, b_mb1,b2,…,bm。 你需要判断是否可以通过若干次（可能为零）如下操作将数组 aaa 转换为数组 bbb。 在所有 aaa 的非空子数组∗^{\text{∗}}∗中，选择一个具有最大和的子数
[ABC310Ex] Negative Cost 题解
Description 一头怪兽挡在你的面前，它有 HHH 的血量。 你有 nnn 种技能，每个技能都可以以任意合法顺序无限次使用。 你有一个魔力值，初始为 000 。 第 iii 种技能会消耗 CiC_iCi 的魔力值，并对怪兽造成 DiD_iDi 的伤害。你要时刻保证魔力值非负。 特别的， CiC_iCi 可能为负数，此时该技能会增加 −Ci-C_i−Ci 的魔力值。 当怪物血量不
P8523 [IOI 2021] 位移寄存器 题解
Description 有 999 种位运算操作，利用这 9 种操作实现数组取最小值和数组排序。 Solution 首先考虑对于两个数怎么求较小值。由于这些操作中没有比较操作，很难办。 不妨设第一个为 xxx，第二个为 yyy。 注意到有加法操作，这启发我们用加法判断大小，即如果 x+(2k−1−y)x+(2^k-1-y)x+(2k−1−y) 有进位，则 x>yx>yx>y，