20231009

考试。

20231010

[AGC057E] RowCol/ColRow Sort

给定一个 \(n\times m\)，值域 \([0,9]\) 的矩阵 \(B\)，请你计数有多少个大小相同的矩阵 \(A\) 满足下列条件：

• 分别对 \(A\) 的 每一列 中元素从小到大排序，再分别对 \(A\) 的 每一行 中元素从小到大排序能够得到 \(B\)。
• 分别对 \(A\) 的 每一行 中元素从小到大排序，再分别对 \(A\) 的 每一列 中元素从小到大排序能够得到 \(B\)。

\(1\le n,m\le 1500\)，答案对 998244353 取模。

参考题解

https://linshey.blog.luogu.org/solution-at-agc057-e#

[USACO09OPEN] Tower of Hay G

为了调整电灯亮度，贝西要用干草包堆出一座塔，然后爬到牛棚顶去把灯泡换掉。干草包会从传送带上运来，共会出现 \(n\) 包干草，第 \(i\) 包干草的宽度是 \(W_i\)，高度和长度统一为 \(1\)。干草塔要从底层开始铺建。贝西会选择最先送来的若干包干草，堆在地上作为第一层，然后再把紧接着送来的几包干草包放在第二层， 再铺建第三层……重复这个过程，一直到所有的干草全部用完。每层的干草包必须紧靠在一起，不出现缝隙，而且为了建筑稳定，上层干草的宽度不能超过下层的宽度。 按顺序运来的干草包一定要都用上，不能将其中几个干草包弃置不用。贝西的目标是建一座最高的塔，请你来帮助她完成这个任务吧。

参考解法

设 \(f_i\) 表示物体 \(i~n\) 能到的最大高度， \(g_i\) 表示高度为 \(f_i\) 的最小宽度， \(s_i\) 表示后缀和， \(j\) 表示 \(i~n\) 中满足 \(g_{j+1}\leq s_i-s_{j+1}\) 最小的物块。

\(f_i=f_{j+1}-1\) , \(g_i=s_i-s_{j+1}\) 。

[ABC138F] Coincidence/CF1245F Daniel and Spring Cleaning

找出有多少整数对 \((x,y)\) 满足 \(L\leq x\leq y\leq R\)，\(y\bmod x=x\oplus y\)。
其中 \(\oplus\) 表示异或运算。

输出答案对 \(10^9+7\) 取模的结果。

参考解法

考虑 \(x\) 与 \(y\) 的大小关系。

1. \(2x>y\)，此时 \(y\% x==y-x\) ，
2. \(2x\leq y\) ，此时 \(y\% x<y-x\)。
3. \(y-x\leq x\oplus y\) 。

因此，当 \(2x\leq y\) 时，不存在 \(y\bmod x=x\oplus y\)。

所以依此可得， \(2x>y\) ，\(x\) 与 \(y\) 的二进制位数相同，最高位同时为 \(1\) 。

问题就变成求 \(y- x=x\oplus y\) 的 \((x,y)\) 的对数。

若满足此条件， \(y\) 二进制下为 \(1\) 时， \(x\) 可以为 \(0\) 或 \(1\) ， \(y\) 二进制下为 \(0\) 时， \(x\) 必须为 \(0\) 。

考虑数位dp，先枚举哪一位为最高位， \(f[i][x1][x2]\) 表示前 \(i\) 位，数的大小是否达到达到上下界的方案数，转移时先枚举 \(y\) ，再枚举 \(x\) 。

这种类型的数位dp不像常规的数位dp，差分一下，用 \(0~r\) 的答案减去 \(0~l-1\) 的答案就是 \(l~r\) 的答案。

CF1245F 就是把减法换成加法，做法相像，不做赘叙。

CF983E NN country

给定一棵树和若干条路线，每条路线相当于 \(x,y\) 之间的路径，途径路径上的每个点

给出若干个询问，每次询问从 \(u\) 到 \(v\) 至少需要利用几条路线

\(N,M,Q\le 2\times 10^5\)

参考解法

主席树大好！！1代码简洁有力！！1

考虑如果是一条链怎么做。

此时我们朝某个方向走的时候一定是要尽可能去远的地方，暴力寄寄寄，很容易想到倍增优化。

树上呢？

要求最少乘车，我们知道，在树上两点之间不重复经过点的路径是唯一的，同样倍增，将路分为两段，然后跳两点的LCA。

问题来了，跳过了LCA怎么办？

所以要判断一下是否有一条路可以跨过LCA即可，即判断有没有一趟车的线路两个端点分别在查询点在LCA上一次跳到的点的两个子树内，于是问题变成了二维数点问题，可以扫描线，但是主席树短短短。

The Hidden Pair (Hard Version)

这是一道交互题。困难版与简单版唯一的区别是交互次数限制。

本题有多组数据。

已知一棵 \(n\) 个顶点的树（边集已知），其中有两个不同的顶点被暗中做了标记。你现在需要通过若干次询问，猜出两个被标记顶点的编号。

一次询问的格式为 ? c x_1 x_2 ... x_c，即代表你向交互库请求关于 \(x_1,x_2,\cdots,x_c\) 这 \(c\) 个点的信息。

对于一次询问，交互库的返回格式为 x d，表示在询问的集合中，到两个被标记点的距离之和最小的点是 \(x\)，这个最小值为 \(d\)。如果有多个最小值点，\(x\) 的值可能是其中任意一个。

如果已经知晓答案，请用 ! x y 的格式来输出你的答案，任意顺序均可。在这之后，你会收到一个字符串 Correct 或者 Incorrect，代表你的猜测是否正确。如果收到了 Incorrect，请立即终止程序，否则请继续处理下一组数据。

对于每组数据，请你在不超过 \(11\) 次询问之内给出答案。

\(1\le t\le 10, 2\le n\le 1000\)。

Translated by Caro23333

参考解法

交互题总感觉很厉害！！1

为了方便，下文特殊路径指两个标记点之间的路径。

我们首先是要得到一些全局的信息的。在第一次查询中，我们令查询的集合为所有顶点，这样一定能得到一个在特殊路径上的顶点 \(A\) 和特殊路径长度 \(Len\) ，不妨下面将 \(A\) 定为树的根。

注意到：

若一个点 \(x\) 在特殊路径上，则 \(x\) 到两个标记点的距离和与 \(Len\) 相等，否则大于 \(Len\) 。利用该性质，我们可以判断查询的集合中是否有点在特殊路径上。

预处理出每个点的深度和若干集合，集合 \(S_i\) 表示所有深度为 \(i\) 的点组成的集合。

显然，特殊路径上深度最大的顶点一定是答案之一，根据此我们可以考虑二分深度。

具体地，查询 \(S_{mid}\) 这个集合，判断返回值的两点距离和是否等于 \(Len\) 。若相等则最大深度大于等于 \(mid\) ，否则小于 \(mid\) 。这样最后满足等于 \(Len\) 的点即为其中一个答案点，记为 \(a_1\) 。

最后查询与 \(a_1\) 距离 \(Len\) 的所有点，得到的即为另一个答案点，这样查询次数最多是 \(1+\left \lceil \log_{2}{1000} \right \rceil =12\) ，优化则考虑最大深度至少是 \(\left \lceil \frac{2}{Len} \right \rceil\) ，所以将二分的左端点设置为 \(\left \lceil \frac{2}{Len} \right \rceil\)，即可减少一次，通过F2。

20231011

考试

20231012

Radio Towers

在一条数轴上共有 \(n+2\) 个小镇，编号分别为 \(0\) 至 \(n+1\) ,第 \(i\) 个小镇位于点 \(i\) 。

你在编号为 \(1\) 至 \(n\) 的每个小镇里都有 \(\frac{1}{2}\) 的概率建造了一个无线电塔。之后，你在每个无线电塔上设置了一个整数信号功率 \(p\) \((1\leq p \leq n)\) ，对于所有的城市 \(c\) ，如果 \(|c-i|<p\) （其中 \(i\) 为该无线电塔所在的小镇的编号），那么这个城市将收到来自小镇 \(i\) 的信号。

你要计算出一个无线电塔的建造方案可以设置为以下状态的概率。

• 小镇 \(0\) 和 \(n+1\) 没有收到任何信号。

• 小镇 \(1\) 至 \(n\) 都收到了一个信号。

另外，你只需要算出答案对 \(998244353\) 取模的值。

参考解法

推理一下，不难发现 \(f_n\) 即为斐波拉切第 \(n\) 项，答案为其除 \(2^n\) ，所以直接搞就可以了。

Make Equal

给出 $ n $ 个数字 $ a_1 , a_2 , \ldots , a_n $ ，每次操作可以给其中一个数加上 $ 2 $ 的非负整数次幂。求最少的操作次数，使得这 $ n $ 个数相等。

参考解法

考虑记 \(popcnt(x)\) 表示二进制下 \(x\) 中 \(1\) 的数量。