A:给定序列 $a_{1\cdots n}$,称一个值 $1\leq k\leq n$ 是可行的当且仅当若干次选择恰好 $k$ 个序列里的值并消去它们二进制下的公共部分可以使得序列变为全 $0$,求所有可行的 $k$。

$1\leq n\leq 2\times 10^5$,$0\leq a_i<2^{30}$。

sol

考虑每一位是独立的,设二进制下第 $i$ 位为 $1$ 的有 $c_i$ 个,则答案为非零的 $\gcd\{c_i\}$ 的所有因子。

因为显然每一步只能消掉恰好 $0$ 或 $k$ 个第 $i$ 位上的 $1$,只有 $k|c_i$ 才能恰好消完。时间复杂度 $O(n\log a_i)$。


B:有一口 $n$ 米深的井,从井底($n$ 米处)向上跳,在 $x$ 米处可以向上跳 $[0,a_x]$ 米,跳到 $y$ 位置后会向下滑 $b_y$ 米,求跳到 $0$ 米处的最小步数以及方案。

$1\leq n\leq 3\times 10^5$,不会有方式移动到 $[0,n]$ 以外。

sol

可以冲一发 线段树优化建图 莽过去,但是太难写了。

考虑 bfs,每个点 $y$ 被跳上来,下滑 $b_y$ 米之前第一次到达就是最优的,所以每个点只会被搜到一次。

那么我们就可以把 $[0,n-1]$ 塞进 STL::set,每次把 $[u-a_u,u]$ 中还没被访问过的点拉出来更新并放入下滑后的点入队列,然后把它们删除掉,每个点只会贡献一次删除和入队,时间复杂度 $O(n\log n)$。


C:给定序列 $a_{1\cdots n}$ 与 $b_{1\cdots m}$,将这 $n+m$ 个数重组为序列 $c_{1\cdots n+m}$,要求 $a$ 是 $c$ 的子序列,求 $c$ 的最小逆序对数。

$1\leq n,m\leq 10^6$,$1\leq a_i,b_i\leq 10^9$。

sol

考虑是把 $b$ 里的元素任意插到 $a$ 序列中,则 $b$ 序列插入的相对位置一定是小的在前,大的在后,否则交换则可以减少至少一对逆序对,则 $b$ 的插入只会和 $a$ 中元素构成逆序对。

两个序列一起离散化后先计算 $a$ 中逆序对,然后对 $a$ 序列建立线段树,枚举指针 $v$,$<v$ 的设为 $1$,否则设为 $0$,那么在 $pos$ 后插入 $v$ 的花费就是 $[1,pos]$ 中 $1$ 的个数加上 $(pos,n]$ 中 $0$ 的个数,记为 $d_{pos}$,我们要求的就是把 $v$ 移到 $b_i$ 后最小的 $d_{pos}$,线段树也实际维护的是 $d_{0\cdots pos}$。

实际上把 $p$ 位置的 $0$ 改为 $1$ 对应的就是给 $[p,n]$ 减一,$[0,p)$ 加一。注意特殊处理一下相等的情况即可。

时间复杂度 $O(m\log n)$。


D:给定 $n$ 个二元组 $(s_i,a_i)$ 与初值 $d$,任意重排之后执行 for(int i=1;i<=n;i++)if(d<=s[i])cnt++,d=max(d,a[i]);,求可能的最大的 $cnt$ 的值。

$1\leq n\leq 5\times 10^5$,$0\leq d,s_i,a_i\leq 10^9$。

sol

按照 $(\max\{s_i,a_i\},s_i,a_i)$ 三元组排序后贪心。

考虑调整法,相邻两个数的信息分别为 $s_1,a_1,s_2,a_2$,$1$ 代表 $s_1$ 或 $a_1$,$2$ 代表 $s_2$ 或 $a_2$,讨论大小关系。

  • $1,1,2,2$,此时显然让 $1$ 更先走优,因为不会影响到 $2$。
  • $1,2,2,1$:

    • $a_1,2,2,s_1$,此时选择让 $2$ 先走,因为 $2$ 不会影响到 $1$ 的贡献。
    • $s_1,2,2,a_1$,此时任意选择贡献都相同,即 $1$ 先走时只有 $a_1=s_2$ 可以都上,$2$ 先走时只有 $s_1=a_2$ 时可以都上,是对称的。
  • $1,2,1,2$:

    • $1,a_2,1,s_2$,让 $1$ 先走,因为 $1$ 不会影响到 $2$ 的贡献。
    • $1,s_2,1,a_2$:让 $1$ 先走,因为 $2$ 先走 $1$ 就没得贡献了,而 $1$ 先走还可能贡献到 $2$。

综合就是先按照 $\max\{s_i,a_i\}$ 排序,若相等可以再类似地手玩一下(

时间复杂度 $O(n\log n)$。


E:给定序列 $a_{1\cdots n}$ 与常数 $k$,在 $i$ 处可以花费 $a_i$ 把数轴上 $[j,j+k-1]$ 标记,其中 $j\ge i$,允许一个位置被重复标记。$q$ 次独立的询问从 $l_i$ 不回退地向右走到 $r_i$ 并使得 $[l_i,r_i]$ 都被标记的最小花费。

$1\leq n,q\leq 3\times 10^5$,$1\leq k\leq n$,$1\leq a_i\leq 10^9$。

sol

没有多组询问时显然是可以贪心的。设 $b_i=\min_{j=i-k}^i\{a_i\}$,则询问 $[l,r]$ 的答案为 $a_l+b_{l+k}+\min\{b_{l+k},b_{l+2k}\}...+\min\{b_{l+k},b_{l+2k}+\dots +b_{l+tk}\}$,其中 $t$ 是最大的满足 $l+tk\leq r$ 的整数。

考虑后面那个前缀 $\min$ 的前缀和的形式,我们把它抽离出来,设得到了序列 $c_{1\cdots m}$,求 $f_i=\sum_{j=i}^n \min\{c_{i\cdots j}\}$,这部分可以用单调栈处理出 $nxt_i$ 表示 $i$ 后面第一个值小于 $c_i$ 的位置,则 $f_i=f_{nxt_i}+(nxt_i-i)·c_i$。

题目中求的形式是 $\sum_{i=l}^r \min\{c_{l\cdots i}\}$,求这个可以找到 $c_p=\min\{c_{l\cdots r}\}$,则前面的式子就等于 $f_l-f_p+c_p·(r-p+1)$,这个的意义是从 $l$ 到 $p$ 都是用的 $f_l$ 的方案,从 $p$ 开始往后,$f_l,f_p$ 用的都是同一个方案,对应的值自然相同,可以相减,而 $[p,r]$ 段用的最小值都是 $c_p$,再加回来即可。

精细实现可以做到线性,但 ST 表就可以通过了,时间复杂度 $O(n\log n)$。

F 还没做。

最后修改:2021 年 10 月 27 日
如果觉得我的文章对你有用,请随意赞赏