Good Problem

Gold14526 · 2023-08-08 14:50:11 · 个人记录

Good Problems

目前收录题目数量:19

题意

Ashish 和 Jeel 在玩游戏，有一个 n\times m(1\le n,m\le100) 的棋盘，每个格子有一个非负整数的权值。

两个人轮流操作，每次操作先选择一个权值非 0 的格子作为起点，然后选择起点右下角的一个格子作为终点，然后选择它们之间的一条最短路径，然后给起点的权值减一个正整数、路径上每个点的权值随意加减（也可以不改变），但是都不能改成负数。

不能操作（全变成 0）就输了，Ashish 先手，问谁必胜。

做法

（以下的斜线指从右上到左下的斜线）

如果当前每条斜线的异或和都为 0，下一步一定会把至少一条斜线的异或和变为非 0，因为至少要给一个格子减去一个正整数。

如果当前有斜线的异或和不为 0，下一步一定可以把每条斜线的异或和都变为 0，因为可以选择最靠左上的非 0 斜线中的最大值，并将后面每条斜线的异或和都更改为 0。

全为 0 的局面肯定只会出现在每条斜线异或和都为 0 的情况下，所以如果刚开始时有至少一条斜线的异或和不为 0 则先手必胜，反之后手。

题意

有 n(1\le n\le2\times10^5) 道单选题，每道题有 k(1\le k\le10^9) 个选项。

你的答案发生了错位，第 1 题的答案填到了第 2 题的位置上，第 2 题的答案填到了第 3 题的位置上，\dots，第 n-1 题的答案填到了第 n 题的位置上。特别的，第 n 题的答案填到了第 1 题的位置上。

现在给出正确答案，求你错位之后的正确率比原来高的方案数 mod\ 998244353 后的结果。

做法

假设第 x 题的答案被填到了第 y 题，分两种情况：

• 如果两题答案相同，显然错位前后都对或都错，对正确率的变化没有贡献。
• 如果不同，对于除了两题答案外的答案，显然没有贡献，否则会使正确题目数量加一或减一，均为一种方案。

所以对于一个增加 x 正确率的方案，总能使其变成相对的减少 x 正确率的方案。

所以增加 x 正确率的方案数等于减少 x 正确率的方案数。

所以增加正确率的方案数等于减少正确率的方案数。

假设增加正确率的方案数为 S_{1}，减少的为 S_{-1}，不变的为 S_0。

即 S_1=S_{-1}。

考虑到总方案数 \sum S=k^n，即 S_1+S_0+S_{-1}=k^n。

所以 2S_1+S_0=k^n，S_1=\frac{k^n-S_0}{2}。

现在我们只需要求出 S_0 就可以求出答案 S_1 了。

首先考虑到错位前后正确答案相同的位置是没有贡献的，所以先计算出有贡献的位置数量 m。

题意

给出一棵 n(2\le n\le10^5) 个节点无根树的每一条边，但是边权未知，且对于 1\le i\lt n，给出节点 i 到节点 i+1 的路径长度 d_{i,i+1}(1\le d_{i,i+1}\le 10^{12})。

要求还原这棵树的边权，且每条边的边权都是正整数，无解输出 -1。

做法

以 1 为根建树，考虑对于 1\lt i\le n 有如下式子：

其中 dep_i 为节点 i 到根节点 1 的路径长度。

移项得：

考虑通过以上式子递推，因为 d_{i-1,i} 和 dep_{i-1} 都是已知的（dep_1=0），唯一的问题就是 dep_{lca(i-1,i)} 可能未知。

但是我们可以递推 dep_{i}\mod 2 的值，因为 2\times dep_{lca(i-1,i)} \equiv0\ (mod\ 2)。

然后，我们将模数增到 4 ，此时我们可以根据之前的结果递推，因为 2\times dep_{lca(i-1,i)}\equiv 2\times (dep_{lca(i-1,i)} \ mod\ 2)\ (mod\ 4)

以此类推，我们可以计算出 dep_i\ mod\ 2^k 的值。

具体的：

当 k\ge 60 时，由于模数比原数大，所以 dep_i\ mod\ 2^k=dep_i，此时的 dep_i 就是原 dep_i。

显然可以通过每个节点的 dep_i 求出每条路径的长度。

最后判断是否有非正边权以及计算得到的 d_{i,i+1} 是否与输入的相同，输出 -1 或边权即可。

题意

给出一个长度为 n(1\le n\le10^6) 的序列 a，对于 1\le i\le n，保证 i-n\le a_i\le i-1。

求选择其中一些数，和为 0 的一种方案。

做法

将 i-n\le a_i\le i-1 转化为 1\le i-a_i\le n。

对于每个 i，将其对 i-a_i 连边。

由于连的是 n 条边，所以连出来的是一棵基环内向森林。

对于其中的一个环，显然其中的 i 与其中的 i-a_i 一一对应，所以其中的 \sum i=\sum (i-a_i)，即 \sum i=\sum i-\sum a_i。

显然 \sum a_i=0。

所以其中任意一个环的编号都是答案。

题意

这是一道交互题

有一个未知的长度为 n(2\le n\le 1000) 的序列 A(0\le A_i\le 2^{63}-1) ，通过序列 A 求出序列 P，使得 P_i 为序列 A 中除了 A_i 以外所有数的或。

你可以查询最多 13 次序列中若干个数的或和。

你需要求出 P 数组。

做法

有一个显然的 20 次的做法：

如下二进制分组（1 代表选中，0 代表不选中）：

1:1 0 1 0 1 0 1 0 1 0 1...
2:0 1 0 1 0 1 0 1 0 1 0...

3:1 1 0 0 1 1 0 0 1 1 0...
4:0 0 1 1 0 0 1 1 0 0 1...

5:1 1 1 1 0 0 0 0 1 1 1...
6:0 0 0 0 1 1 1 1 0 0 0...

......

对于任意一个位置，总可以找到若干次查询，使得他们查询了所有其它的位置。

考虑查询次数 13，看上去像是二进制分组的位数。

现在第 i 个数的编号相当于 i。

我们可以考虑更改所有数的编号，使得对每一位都只要查询一次就可以了。

现在我们对于编号 x，我们要求的是所有 x 二进制中 0 位的或和。

唯一的问题是对于 x，如果它改一位 1，变为 0，这个编号的答案不会被算进去。

所以可以想到一个方法，就是让所有编号 1 的个数相同，就可以解决这个问题。

所以我们只要把 13 位二进制数中有刚好 6 位为 1 的数作为编号就可以了。

题意

对于一个 01 序列我们可以把其中的00变为11，或把其中的11变为00若干次。

我们定义把序列 a 通过以上操作变为序列 b 所需的最少次数为 a,b 之间的距离，若无法完成则距离为 0。

现给出两串长度为 n(2\le n\le2000) 的字符串，均由0，1和?组成，求把其中的?均填上0，1的所有填法下，两个字符串之间的距离之和。

做法

当我们翻转所有奇数位后，原操作变为交换相邻两个数，这样的好处是，在不翻转的序列中能保证交换的两个数是相同的。

此时如果有解，一定有一种最优方案中整个过程 1 的相对位置不变，即第一串中的第 i 个 1 会交换到第二串中的第 i 个 1。

所以对于原来两个串中的 i,j 两个位置，它们的贡献是 |i-j| 乘上第 i 个位置为 1 且要交换到第 j 个位置的方案数。

设 dp_{i,j,0/1} 表示位置 i,j 都为 1 且在 1 中排名相同的方案数，其中第三维表示是从左往右数的排名还是从右往左数的排名，那么第 i 个位置为 1 且要交换到第 j 个位置的方案数就是 dp_{i,j,0}\times dp_{i,j,1}。

第 i,j 都为 1 且在 1 中排名相同当且仅当两个位置都不为 0 且排名比他们小 1 的两个位置与这两个位置之间均为 0。

分别从 i,j 前的最后一个1开始枚举，它们的 dp 之和即为 dp_{i,j}。

不难发现每次转移都是一个矩阵，所以用二维前后缀和优化即可。

题意

定义 f(x) 表示 x 各位数字之和，例如 f(1234)=1+2+3+4=10。

现在给定一个 a(1\le a\le 10^{18})，你要找出一对 L,R，满足 1\le L \le R \le 10^{200},且 \sum^R_{i=L}f(i) 是 a 的倍数。

做法

首先，当 x\le10^{18} 时，显然 f(x+10^{18})=f(x)+1。

其次，\sum^{10^{18}-1}_{i=0} f(i)=81\times10^{18}，可以对每一位分别考虑，在其它每一位都确定的情况下，这一位有 10 种填法，总和是 45，而其它每一位都有 10 种填法，共 17 位，所以是 10^{17} 种填法，所以每一位贡献是 45\times10^{17} ，共 18 位，所以总和是 18\times45\times10^{17}，等于 81\times10^{18}。

所以：

如果 81\times10^{18} \rm mod a=p 的话，81\times10^{18}+a-p 就是 a 的倍数。

即 x=a-p，输出 x 和 10^{18}+x-1 即可。

题意

给出一个长度为 n(1\le n\le 5000) 的序列 a(1\le a_i\le 10^9)，接下来会进行 m(1\le m\le10^9) 次操作，每次操作会等概率选择一段非空后缀，将其中所有数增加 v(1\le v\le 10^9)，求最后 \prod a_i 的期望值，答案对 10^9+7 取模。

做法

考虑最后的答案 \prod(a_i+v+v+...)，把它用分配律展开，那么对于每一个 i，在一项中肯定是 a_i 或其中一个 v。

设 dp_{i,j} 表示前 i 个位置放了 j 个 v 的贡献。

分类讨论：

若第 i 个位置乘 a_i：dp_{i-1,j}\times a_i\to dp_{i,j}

若第 i 个位置乘了之前放的 v：dp_{i-1,j}\times j\times v\to dp_{i,j}

（乘 j 是因为可以选择乘之前放的 j 个 v 中的任何一个）

若第 i 个位置乘了一个新放置的 v：dp_{i-1,j-1}\times(m-j)\times i\times v\to dp_{i,j}

（乘 m-j 是因为可以选择任意一次没有选择过的操作来放 v ，乘 i 是因为可以放在前 i 个位置中的任何一个）

最后答案就是

题意

给出一张 n\times m(1\le n,m\le200) 的网格图，其中有些格子是黑的，你要用若干个长为一或宽为一的长方形覆盖所有黑色格子，且不能覆盖其它格子，长方形也不能重叠，求最少需要的长方形个数。

做法

考虑把格子当做节点，黑色的格子之间连边：

即开始时每个黑色格子都是一个连通块，要在连接的边中选择一些边使得连通块数量尽量小。

也就是边的数量尽量大。

接下来考虑连接同一个格子的两条边不能同时选这个限制。

给连接同一个黑色格子的两条边连边：

显然这是一张二分图，它的最大匹配数量即为最少的不能选的边的数量。

那么总的黑格子之间边的数量减去二分图最大匹配就是最多能选的边的数量。

黑格子数减去最多能选的边的数量就是最少连通块数量，也就是答案。

拜谢 @LYS_AK_IOI 和 @Tx_Lcy 的 \rm Dinic 模板。

题意

给一个 n\times m(1\le n,m\le500) 的网格图涂上四种颜色，要求每个格子都涂一种颜色并且每一对曼哈顿距离为 d 的格子颜色都不相同。

做法

首先了解一个距离叫做切尔雪夫距离：

题意

定义有至少一个数在区间 [x,x+k-1] 内且相邻两个数的差的绝对值不超过 k 的非负整数序列为 Fancy arrays。

现在给出 n,x,k(1\le n,k \le 10^9,0\le x\le 40)，求长度为 n 的 Fancy arrays 的个数，对 10^9+7 取模。

做法

我们定义“有至少一个数在区间 [x,x+k-1] 内”为条件一，“相邻两个数的差的绝对值不超过 k”为条件二。

显然答案为序列最小值在 [0,x+k-1] 内且满足条件二的序列个数，减去整个序列都在 [0,x-1] 的序列个数。

考虑怎么算最小值在 [0,x+k-1] 内且满足条件二的序列个数，即选择一个 [0,x+k-1] 内的数作为最小值，显然是 x+k 种选法，再求差分数组的个数，显然为 (2k+1)^{n-1}，所以这个数就是 (x+k)(2k+1)^{n-1}。

考虑怎么求整个序列都在 [0,x-1] 的序列个数，显然可以 dp，设 dp_{x,y} 为前 x 个数以 y 结尾的方案数，显然有转移方程 dp_{i,j}=\sum_{t=i-k}^{i+k}dp_{i-1,t}，但是 n 太大了，考虑矩阵快速幂，具体的，初始矩阵为一个 1\times x 的全 1 矩阵，转移矩阵 A 是一个 x\times x 的矩阵，满足 A_{i,j}=[|i-j|\le k]。

然后减一下就是答案了。

题意

你要把 n 个士兵分配成 m 个军队 (1\le m\le n\le10^6)，去攻打对方的 m 个军队，对面的每一个军队都有一个士兵数量 hp_i(1\le hp_i\le10^6)，每一轮战役，你可以给每一个军队分配一个目标（可以相同），对面的每一个军队的士兵都会减少攻打它的士兵数量，你要歼灭对方士兵，并使用最少的战役数量，给出方案（分配方案和每轮的攻打方案）。

做法

考虑到战役轮数最少也是 \lceil\frac{\sum hp_i}{n}\rceil。

考虑如何达到这个下限。

可以先让 n 个人依次围攻每一个军队，这样只要考虑对方每一个军队 mod\ n 的部分。

可以先打对方第一个军队，让剩下的军队去打第二个军队，然后打对方第二个军队，让剩下的军队打对方第三个军队，以此类推。

由于考虑到我方和敌方的军队数量是相同的，所以一定有一种方案使得战役数量达到下限。

所以我们一定要能够不浪费，也就是军队一定能够配成敌方军队人数的每一个前缀和。

所以，我们可以先计算出每一个前缀和，然后排个序，进行差分即可。

题意

给出正整数 n,k(3\le n\le10^6,k\le n-2)，输出最小的 p，使得在一个圆上可以找到 p 个点，满足有至少 k 个不同边数且边数不超过 n 的正多边形的端点都属于这 p 个点。

做法

如果有两个数 x,y(x<y\le n,x|y)，如果你要选一个正 y 边形，那么再选择一个 x 边形一定是不劣的，所以我们默认选择一个正多边形的时候，所有以该正多边形边数的因子为边数的正多边形都已经被选上了。

那么当添加一个正 x 边形时，原本我们应当增加 x 个点，但是对于 x 的一个因子 c，正 \frac{x}{c} 边形已经被选上了，那么如果我们对这 x 个点顺时针进行编号，那么编号为 c 的倍数的点都已经存在了，也就是编号与 x 不互质的点都已经存在，剩 \varphi(x) 个点需要添加。

所以只需要将 3~n 的 \varphi(x) 排个序，求前 k 个的和即可。

题意

有 n(1\le n\le10^3) 个节点，每天从 i 到 j 的边都有 p_{i,j} 的概率存在，经过每条边需要花一天，若按照最优方案走，求从节点 1 走到 n 的期望天数。

做法

设 E_x 表示从 x 走到 n 的期望天数，某天一个点 y 可以对其产生贡献当且仅当所有满足 E_k<E_y 的节点 k 在当天都未开放，于是，节点 y 对节点 x 的贡献是 (E_y+1)\times\prod\limits_k^{E_k<E_y}(1-p_{x,k})。

设 best_{x,y}=\prod\limits_k^{E_k<E_y}(1-p_{x,k})，即节点 y 是对于节点 x 来说的最优走向的概率。

在上述的式子里可以得到一个隐含条件 E_y<E_x，因为 p_{x,x}=1。

设 others_x 表示除了 x 节点以外的节点对节点 x 的贡献，那么 others_x=\sum\limits_{y}^{E_y<E_x}best_{x,y}(E_y+1),E_x=best_{x,x}(E_x+1)+others_x。

移项得 E_x=\frac{others_x+best_{x,x}}{1-best_{x,x}}。

由于刚才说到只有满足 E_y<E_x 的节点 y 才能对 x 产生贡献，所以每次找到 E_y 最小的点 y 并对其他的点计算贡献，类似 Dijkstra。

题意

对于一个长为 n(1\le n\le2\times10^3) 的排列，有 m(n\le m\le min(n^2,5\times10^5)) 条限制，每条限制形如 (x,y)，表示第 x 个数可填 y，分别求去掉每条限制后合法序列的数量是否为奇数，保证初始限制下合法序列数量为奇数。

做法

设 A_{x,y} 表示第 x 个位置是否可填 y。设 s 表示合法序列数量，显然有 s=\sum\limits_{p}\prod\limits_{1\le i\le n}A_{i,p_i}，其中 p 表示合法序列。

考虑到一个矩阵的行列式为 \sum\limits_{p}(-1)^k\prod\limits_{1\le i\le n}A_{i,p_i}，其中 k 为 p 的逆序对数量。

实际上乘 -1 对奇偶性没有影响，所以可等价的认为 s 为矩阵 A 的行列式。

删掉一个限制 (x,y) 后的排列数，相当于删掉了第 x 个数为 y 的合法排列数，于是只要求删掉矩阵第 x 行和第 y 列后的 (n-1)\times(n-1) 的矩阵的行列式。

即代数余子式。

代数余子式：矩阵 A 的代数余子式 M_{i,j} 表示删去矩阵第 i 行和第 j 列后的矩阵行列式。

伴随矩阵：对于一个 n\times m 的矩阵 A，一个 m\times n 的矩阵 T 满足 T_{i,j}=(-1)^{i+j}M_{j,i}，那么 T 就是 A 的伴随矩阵。

所以只需要求出矩阵 A 的伴随矩阵 T，每次查询 T_{x,y} 是否为偶数即可。

在奇偶性意义下，加减乘除可用位运算代替，所以求 T 的过程可用 bitset 优化。

题意

在 [0,1] 之间均匀随机 n(1\le n\le20) 个实数 x_{1\dots n}，给出 m(0\le m\le n^2+n) 条限制，每条限制形如以下两种中的一种：

• x_i+x_j\le1
• x_i+x_j\ge1

求满足所有限制的概率。

做法

将 x 数组全部减去 0.5，原题变为在 [-0.5,0.5] 间随机，每条限制形如 x_i+x_j\le0 或 x_i+x_j\ge0。

考虑到 x_i+x_j=0 的概率为 0，于是限制可写为 x_i+x_j<0 或 x_i+x_j>0。

不妨设 |x_i|<|x_j|，此时 x_i+x_j 的正负完全取决于 x_j 的正负。

于是我们只需要求出有多少种可能的 |x_i| 的排序和 x_i 的正负性，最后除以 n!2^n 即可。

题意

有 n(1\le n\le100) 个物品，每次你可以花 x(1\le x\le10^4) 的费用抽取一个物品，如果这个物品你已经拥有，则返还 \frac{x}{2} 的费用，你也可以直接花 c_i(x\le c_i,\sum c_i\le 10^4) 的费用直接购买第 i 个物品，求最优策略下期望最小花费。

做法

如果先买再抽，无疑是增加了抽到已经拥有的物品的概率，显然不优，所以一定先抽再买。

如果你已经购买了 k 个物品，再抽一个新的物品的概率是 \frac{n-k}{n}，期望抽 \frac{n}{n-k} 次，期望花费 x+\frac{x}{2}\times(\frac{n}{n-k}-1)。

显然抽奖的花费是越抽越贵的。

假设你已经买了 k 个物品，这些已买物品的总花费为 t，所有物品总价格为 s。

考虑到先抽后买，如果打算抽到这里收手，剩下都买的话，要花 s-t 的费用，相当于抽 n-k 次，每次抽出一个新的物品，每次花费 \frac{s-t}{n-k}。

这样的好处是将直接买和抽奖归为同一类，即你可以花 x+\frac{x}{2}\times(\frac{n}{n-k}-1) 的费用或 \frac{s-t}{n-k} 抽出一个新的物品。

即你可以花费 min(x+\frac{x}{2}\times(\frac{n}{n-k}-1),\frac{s-t}{n-k}) 的费用抽一个新的物品。

设 dp_{i,j} 为选 i 个物品，总价为 j 的方案数，不难 O(n^2\sum c) dp 求出，则抽 i 个物品，总价为 j 的概率为 \frac{dp_{i,j}}{C_n^i}。

期望总花费显然等于每种情况的概率乘该情况下一步的花费，即

题意

Alice 和 Bob 有一个 n\times m(1\le n,m\le2\times10^5) 的棋盘。每行恰好有一个棋子。

他们以如下的方式进行一个游戏：

• 选择一对整数 l,r(1\leq l\leq r\leq m)，将除第 l\sim r 列之外的部分从棋盘上移除。

• 轮流进行操作，Alice 先手。每一次操作，玩家需要选择一个棋子，并将其向左走任意正整数步（不能移出棋盘）。第一个不能移动的玩家判负。

给定 q(1\le q\le2\times10^5) 次独立的询问如 L_i,R_i 所示，试求如果第一步中选择的整数是 (L_i,R_i)，谁会赢得游戏。

做法

首先，这是一个 \rm Nim 游戏，原题显然可以等价于询问 \bigoplus\limits_{l\le a_i\le r}(a_i-l)。

设 cnt_i 表示 a 中等于 i 的数的个数除以二的余数。

询问变为 \bigoplus\limits_{l\le i\le r,cnt_i=1}i-l。

观察自然数的二进制：

2^3  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1
2^2  0  0  0  0  1  1  1  1  0  0  0  0  1  1  1  1
2^1  0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1
2^0  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1
     0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 ...

按位观察，发现第 i 位为 2^i 个 0 与 2^i 个 1 交替。

我们定义序列中长度为 x 的前缀中，下标 i 满足 i \equiv x\pmod {2^k} 的 cnt_i 的异或和为 x 的 k 级前缀异或和，记作 sum_{x,k}，不难通过递推求出。

现在，一段区间第 k 位的答案可以通过 sum_{x,k} 求出。

举个例子，求 [4,8] 第 1 位的答案：

2^2              0  0  0  0  1
2^1              0  0  1  1  0
2^0              0  1  0  1  0
i-l              0  1  2  3  4
i    0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 ...

只需求出 sum_{6,1}\bigoplus sum_{7,1}\bigoplus sum_{1,1}\bigoplus sum_{2,1} 即可。

但是这样效率还是不够，考虑求出 s_{x,k}=\bigoplus\limits_{1\le i\le x}sum_{i,k}。

于是，不难求出某一位的答案。

具体的：

设 len=r-l,x=2^i\times\lfloor\frac{len}{2^i}\rfloor+l,S_{l,r,k}=s_{r,k}\bigoplus s_{l-1,k}。

对于第 i 位，如果这一位最后 2^{i+1} 个数形如这样：

0 ... 0 0 1 1 ... 1 1 0 0 ... 0

此时，x-l\equiv 2^i\pmod{2^{i+1}}，当前位的答案为 S_{x-2^i+1,x,i}\bigoplus S_{l-2^i,l-1,i}。

如果形如这样：

1 ... 1 1 0 0 ... 0 0 1 1 ... 1

此时，x-l\equiv 0\pmod{2^{i+1}}，当前位的答案还要在异或一个 S_{r-2^{i+1}+1,r,i}，即 S_{x-2^i+1,x,i}\bigoplus S_{l-2^i,l-1,i}\bigoplus S_{r-2^{i+1}+1,r,i}。

即：

题意

给出一个长度为 n(1\le n\le5\times10^5) 的 01 串，你可以进行若干次以下操作：

• 选一段 0 和 1 个数相同的区间。
• 将它左右翻转
• 将其中的 0 改成 1，1 改成 0。

求能够变成的字典序最小的 01 串。

做法

搞一个变量 x，初始为 0。

从左往右扫整个串，遇到 0 把 x 减一，遇到 1 把 x 加一，我们把 x 的变化路径建成一张无向图，是一张半欧拉图（或欧拉图），而这条路径就是这张图的一条欧拉通路。

考虑 0 和 1 的数量相同意味着什么，这说明 x 在进入这段区间前是多少，走到这段区间结尾还是多少，即 x 经过了一个环。

现在我们再来考虑把区间翻转过来，再把 01 翻转意味着什么，这说明我们让 x 倒着走这个环。

现在，不难把题意变成：

给出一个无向图，从给定节点（节点 0）开始走，求字典序最小的欧拉通路。

直接贪心，能往小的走就往小的走即可。