JOI Open 2023

T2 怎么 std 9k。

*loj3985. 「JOI Open 2023」古代机器 2

tag：交互，字符串，线性代数。

感觉很厉害。

解法一：\(m=n+2\)。

考虑按位确定，那么确定第 \(i\) 位的时候建立如下自动机：对于 \(j<i\)，\(a_j=b_j=j+1\)，\(a_i=i+1,b_i=i+2\)，然后在 \(i+1,i+2\) 连两个自环。

解法二：\(m=n+1\)。

仍然是按位确定，只不过是从后往前。考虑如何判断一个后缀是否为给定字符串 \(T\)，做法是建立 \(T\) 的 KMP 自动机然后在上面跑，最后判断匹配长度是不是 \(|T|\) 即可。回到原问题，每次在 \(T\) 开头尝试添加一个字符并询问即可。

解法三：\(m=114\)。

重量级。

发现可以询问出所有数的和：造两个点，然后互相连。

想到这个可以得到一个扩展：询问出 \(i\bmod p=q\) 的所有 \(s_i\) 的和。这样可以得到一个线性方程组，消元即可。

考虑怎么做，可以建立 \(2p\) 个点，前 \(p\) 个点连一个环，后 \(p\) 个点连一个环，然后考虑把 \(b_q\) 和 \(b_{p+q}\) 交换一下。最后只要判断点在哪个环上面。

对于 \(p\leq 57\) 的所有 \(p\) 询问可以得到 \(n\) 个线性无关的方程组。

正解：

考虑把三个做法拼起来。对于前 \(100\) 个点用做法一，后 \(100\) 个点用做法二，然后对 \(p\leq 51\) 的所有 \(p\) 做可以得到足够的线性无关方程组，最后消元即可。注意使用 bitset 优化。

*loj#3987. 「JOI Open 2023」花园

tag：最大矩形问题，扫描线。

以下在 \([0,2d)\times[0,2d)\) 范围讨论。

只会一个巨大斜率优化做法，大概就是枚举下边界，然后枚举左边界，这样高就是不被包含的第二类点的最大值，但是注意到第二类点有两列，所以这个最大值实际上是一个区间最大值，然后写个单调栈，然后把单调栈上的点加进凸包里面。

这个我不知道对不对啊，谁爱写谁写去！

正解是枚举左边界然后递推地计算右边界。乍一看不太好做，因为直接在纵坐标上做的话需要写双指针，如果还要动态加入一些限制基本上做不得。但是问题实际上有更好的刻画：注意到 \([d,2d)\) 是 \([0,d)\) 复制而来的，所以可以把这个东西看成一个环。那么环上包含所有点只需要求出两两之间最大的空隙即可，然后就可以用链表维护了！

完全没意识到是环，火大。