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$ 的大小关系。

$2x>y$，此时 $y\% x==y-x$ ，
$2x\leq y$ ，此时 $y\% x<y-x$。
$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$ 的信号。

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