P4839

发布于 2024-05-27 | 标签: 线性基、数据结构 | 7分钟 | 1292字数

有人搞错了复杂度白开心了一下午/kk

基于离线 ST 表+前缀线性基合并的 $O(m\log m\log^2V)-O(\log^2V)$ 做法。

upd：@chenxinyang2006 的在线 $O(n\log V(\log V+\log m))$ 做法。

阅读全文 »

CF1584D

发布于 2024-05-27 | 标签: 交互、二分 | 4分钟 | 651字数

vp 时候搞出来的 $\le\log n+2+?$ 次询问做法。看了一圈没有做法跟我相同的，为什么呢。

首先看到 $40$ 次猜测是一次二分的 $\log$ 加上常数。然后发现，如果我们找到了 $j$ ，又知道 ? 1 n 和 ? 1 j-1 的结果，就可以解出来 $i,k$ 。于是想怎么二分。

设当前二分到 $mid$ ，我们先询问 $[1,mid]$ 得到 $x$ ，然后开始分讨：

阅读全文 »

AT_arc139_c

发布于 2024-05-27 | 标签: 贪心 | 3分钟 | 492字数

会正解做法之后还以为 10 10 答案是 $37$ ……

钦定 $n\le m$ ，从 $3x+y$ 与 $x+3y$ 的匹配的角度考虑。考虑对于一对 $x,y$ ，我们保持 $3x+y$ 不变， $x\to x-1$ ， $x+3y$ 如何变化。发现 $x+3y\to (x-1)+3(y+3)=x+3y+8$ 。于是对于一个 $3x+y=p$ ，符合条件的 $x+3y=q=8k+z$ ， $z$ 为定值且 $k$ 为一个区间。

再进一步，设 $k\in[l,r]$ ，容易发现对于 $3x'+y'=p-8$ ， $z$ 不变，但是 $l,r$ 变化。具体地 $l'\le l,r'\le r$ 。则贪心地想，从小到大枚举 $p$ ，每个 $3x+y$ 都选择最小的满足条件的 $k$ （即选择能匹配的最小的 $x+3y$ ），这样一定是不优的。开个数组对每个 $z$ 记录当前已经选了的最大的 $k$ ，从前往后扫 $p$ ，从 $k+1$ 开始判断是否可行。