依旧云斗集训

· · 个人记录

Day 1

T1

给定长度为 n 的两个数列 \{a_n\},\{b_n\}，你可以花费 1 的代价从两个数列中取出一个数，该操作可以做任意多次。

假设最终你一共取了 k 个数，其中从 \{a_n\} 中取的数的和为 A，从 \{b_n\} 中取的数的和为 B，求：

\max\{\min\{A,B\}-k\}

一只老哥。

把 a,b 降序排序，显然对于一种方案取的是 a 的一段前缀和 b 的一段前缀。

枚举 k，设你从 a 里取了 x 个数，则从 b 里取了 k-x 个数，两者取 \min，显然关于 x 单峰，三分即可，一只老哥。

T2

给定一个初始值域为 [0,n) 的可重集 S，可以进行如下操作若干次：

  • 选择一个（可以为空的）子集 T\subseteq S，T 中元素不可重。
  • 从 S 中删掉 T（重复元素只删一个）。
  • 把 \operatorname{mex}(T) 放进 S。

求最少进行多少次能使 n\in S。

给定 S 的方式是对于 i\in [0,n)，每个 i 在 S 中有 f_i 个。

正序递推是 O(ans) 的，不可做，考虑倒序。

倒着找到最后一个 0 的位置，如果想让其属于 S，则至少花费一次，且前面的每个数都得取出来一次。

于是我们继续向前，设 ans 表示到当前为止的答案，则对于 i 来说，如果 f_i-ans\le 0，那最后需要补到 1，所以 ans\gets ans+(1+ans-f_i) 就结了，线性。

T3

数轴上有 n 个点，有 m 次加点操作，每个点的移动速度是 1 单位长度每秒。

每次加点操作后，输出所有点间距 \ge D 的最小时间。

一只老哥。

考虑任意两点之间的最优走法一定是相向而行，并且最终的相对位置关系一定与初始时无异，所以对于答案 t 来说，必然有：

a_j-a_i+2t\ge D(j-i)

移项得：

t\ge\frac{(Dj-a_j)-(Di-a_i)}{2}

用线段树维护 \{Di-a_i\}，合并时更新答案即可。

可以标记永久化，也可以直接区间加 tag，一只老哥。

T4

待补。

Day 2

T1

给定长为 n 的数列 \{a_n\}，找长度最小的区间 [l,r]，满足在 i\in [0,l)\cup(r,n] 中 a_i 没有重复的数。

显然可以双指针，找到最大的 l，该前提下找到最小的 r，然后让 l 逐渐减小，r 对应逐渐增大，线性。

T2

给定长为 n 的数列 \{a_n\}，选择一个区间 [l,r] 区间加上 d\in[-x,x]，求 \{a_n\} 的最长上升子序列。

一只老哥。

假设 d 为正，则取得区间显然最优是一个后缀，而 d 为负的情况显然可以等价为 d 为正。

则我们算前缀的 LIS，后缀的 LIS，枚举一下分界点在哪里就好了，一只老哥。

T3

这我怎么形式化题意？？

你有 1\times 1\times1 和 2\times1\times1 的乐高积木若干，你需要搭一个 w\times h\times 1 的一堵墙，有多少种情况是这堵墙是锁死的。

w\cdot h\le 2\times10^5

O(w^2) sol

显然锁不死的情况是这堵墙能够被纵向分割，所以记 f_i 表示 i\times h\times 1 且锁死的情况数，g_i 表示 i\times h\times 1 且锁不死的情况数，fib_i 表示斐波那契数列的第 i 项，则：

g_i=\sum_{j=1}^{i-1}f_{i-j}\cdot g_j\\~\\ f_i=fib_i^h-g_i

其实这个东西可以直接上多项式科技就做完了。

O(wh^2) sol

考虑锁死的充要条件，显然是每一条接缝处都得有长为 2 的积木连接，于是设状态 f_{i,j} 表示第 i 条接缝有 j 个长为 2 的积木连接，则：

f_{i,j}=\sum_{k=1}^{h-j}f_{i-1,k}\times\binom{h-k}{j}

正解

平衡复杂度即可做到 O(w^{\frac{4}{3}}h^{\frac{4}{3}})。

T4

待补。

Day 3

T1

给定长度为 n 的数列 \{a_n\}，以及一个折扣系数 q。

把 \{a_n\} 中的元素分成若干组，用集合 T_1,T_2,T_3,\cdots 表示。

  • 若 |T_i|\ge 3，则令 T_i 中最小的元素变为 0。
  • 若 |T_i|<3，则令 T_i 中元素变为原来的 1-q 倍。

你需要最小化分组后所有组内元素和。

如果你想要免费那一档，那分的组的大小显然不可能超过 3，不然多余的丢给折扣更优。

然后注意到免费那一档一定是选值域上连续的三个数，微扰即证。

所以排个序后 dp 即可，状态转移方程为：

f_i=\min\{f_{i-1}+(1-q)\cdot a_i,f_{i-3}+a_{i-1}+a_{i}\}

一只老哥，瓶颈在于排序。

T2

Lottery

T3

给定平面内 n 个点，问有多少个点对 (a,b),(c,d) 满足：

a<c\\b<d\\\not\exist(e,f),e\in(a,c),f\in(b,d)

两只老哥。

考虑 cdq，把所有的点的第二维从 mid 劈开，则对于上面的点来说，其所能对应的下半区间的点一定是当前的前缀 \min，于是下半单调栈，树状数组维护点个数即可。

主定理分析时间复杂度两只老哥。

T4

待补。

Day 4

T1

给定长为 n 的排列 \{p_n\}，定义二元函数 w(i,j) 的定义域满足 i<j，则：

w(i,j)=|p_i-p_j|\cdot|i-j|

取 w(i,j) 前 k 小的和。

k<n

因为 k<n，而直接取 w(i,i+1) 就一定 <n，所以所有的 w 一定都小于 n。

若 ab<n，则 a<\sqrt n 或者 b<\sqrt n。

所以原排列直接向前扫 \sqrt n 个，值域与位置对调后再扫一遍就做完了。

用 nth_element 是 O(n\sqrt n) 的，用优先队列还得带个老哥。

T2

有 m 个形如 \oplus_{i=l}^ra_i=x 的限制，判断是否存在一个满足条件的数列。

转成前缀异或，然后二进制拆分。

用扩展域并查集维护相对关系即可，两只老哥。

T3

给定一个长为 n 的环，第 i 个位置上有数 a_i。

有多少种分割方案，满足分割出来的每一段的按位与都不为 0。

一只老哥。

考虑破环为链，直接计算怎么做。

对于单次 dp，可以做到 O(n\log n) 预处理出 bitand 的 st 表。dp 计算每个位置时需要知道最远可以与到哪个位置，所以需要一个二分，然后前缀和优化即可做到 O(n\log n)。

如何不重不漏的计算所有情况？可以考虑每次算完之后，直接 a_1\gets a_1\operatorname{bitand} a_n，然后让数列长度缩 1，每次缩完后直接暴力 dp 就是 O(n^2\log n) 的。

这时你注意到整个 dp 实际上仅关心 a_1 的取值，而 a_1 的更新依赖于 \operatorname{bitand}，所以不同的 a_1 仅有 O(\log V) 个，我们只需要在 a_1 改变的时候进行 dp 即可做到 O(n\log n\log V)。

最后你考虑每次 dp 的时候都求一遍 st 表是没有必要的，因为我们仅会改变 a_1 的值。又发现每次求值的二分也是没有必要的，对于那些二分出来的界大于 1 的位置，由于这些数根本不会变，所以一次二分即可。对于那些界正好是 1 的位置，我们只需要在更新的时候判断一下还能不能与到 1 即可，于是时间复杂度 O(n\log V)。

T4

是个好题。

Day 5

T1

给定 L,D，有长为 m 的数列 \{a_m\}，与长为 n 的数列 \{b_n\}。

从 \{a_m\} 中取出尽可能多的没有交的递增子序列，满足相邻两项差值 \le D，且最小值 \le D，且最大值 \ge L+1-D。

记上述问题答案为 t，则从 \{b_n\} 中取出 n-t 个数最小是多少。

首先是一些观察，取出来的 b 显然是最小的部分，所以排个序。

然后考虑怎么做，我们二分答案 t，考虑如何验证，发现一定是 t 个位置一起向前跳，显然跳的越远越好，这个过程等价于从 0 开始跳最接近 D 的点，然后把这个点从 a 中删掉。

于是二分答案是没有必要的，直接把 a 丢进 set 中维护然后暴力删点即可，一只老哥。

T2

给定长为 n 的数列 \{a_n\}，求该数列的极长区间 [l,r]，满足存在 x,y 且 x\ge2，i\in[l,r] 内的所有 a_i\bmod x=y。

输出最长长度。

鉴定为典完了。

直接差分取绝对值，然后从差分数组中找到最长的 \gcd 不为 1 的区间即是答案，用你喜欢的数据结构维护即可，两只老哥（也有说用 st 表是一只老哥的）。

T3

好题。

给定长为 n 的 01 数列，你最多可交换 k 对位置，要求最后相邻两个 1 的间隔不能 >m，特别的，我们把位置 0 与位置 n+1 钦定为 1。

n\le2\times10^5,k\le200

暴力配对是不可做题，考虑怎么转化题意。

显然你不会交换 00 或者 11，你也不会交换同一个点两次，所以假设你交换了 B 对点，则等价于对这个数列进行如下操作：

这个东西看起来就很可以 dp 的样子，所以我们开始设状态。设 f_{i,j,p} 表示前 i 个位置，一共走了 j 个位置，其中走了 p 个 0 \to 1 的位置的可行性，转移是随便转移的，不细想的话大概是 O(n^2k^2) 的。

优化啊优化，dp 有一个非常经典的优化就是把可行性 dp 转化成最优化 dp，即把 dp 的某一维状态丢进答案中进行转移。

由于我们想要的时间复杂度应该是 O(nk) 的，而现在的状态数是 O(n^2k) 的，我们显然要考虑把某一个 n 的维度丢进答案，应该是丢哪个都可以，感觉把第一维丢掉是比较自然的，所以设状态 f_{j,p} 表示走了 j 个位置，其中有 p 个位置 0\to 1，所能走到的最远距离。

预处理出每个位置 i 后距离 m 以内最远的 0 或者 1，分别记为 b0_i 和 b1_i，则转移是 naive 的：

f_{j,p}=\max\{b1_{f_{j-1,p}},b0_{f_{j-1,p-1}}\}

最后对于每个状态判断一下是不是满足条件就做完了，转移 O(1)，则总时间复杂度就是 O(nk) 的。

T4

待补。

Day 10

T1

给定集合 S，你可以进行如下操作若干次：

  • 选择 x,y\in S，把 x\operatorname{bitand} y 放进 S 中；
  • 选择 x,y\in S，把 x\operatorname{bitor} y 放进 S 中。

保证 S 中初始时的元素 <2^k，你需要对于 [0,2^k) 中的每个数判断最终其是否可以通过若干次操作使其进入 S 中。

挺好的题。

考虑 x\operatorname{bitand} y\operatorname{bitor} z，由于这两种位运算互有分配律，所以有：

x\operatorname{bitand} y\operatorname{bitor} z=(x\operatorname{bitor} z)\operatorname{bitand} (y\operatorname{bitor} z)

那么我们可以先跑出仅通过 \operatorname{bitor} 能够得到的数，再跑出通过 \operatorname{bitand} 能够得到的数。

对于前者，我们考虑高位前缀和的过程，显然把一个子集内的所有数都或起来一定是不劣的，所以我们记 f_i 表示把 i 内的所有数与起来所得到的数是什么，最终只需要判断 f_i 等不等于 i 即可。

把 01 取反后后者就变成了前者，所以你就做完了这一题，时间复杂度 O(k2^k)。

T2

不可做题

T3

给定一棵 n 个节点的树，根节点为 1，每个点有点权，每次询问给定 c，需要从该节点走向一个点权大于等于 c 且最小的儿子，你需要输出最终在哪里不能走了。

可以对点权进行修改。

两只老哥。

这真是何意味题目。

考虑这是一条链怎么做，显然二分一下，限一下下界与上界就能知道最远跳到哪里了。

那，直接剖，就是 O(n\log^2n) 的了啊。

何意味？

T4

定义一个数列是好的当且仅当：

  • 相邻两个数的差的绝对值等于 1。
  • 中间的数大于等于相邻两个数的算数平均数。

给定长为 n 的数列 a 和 v，每次你可选择 a 的一段好的字串，假设其为 [l,r]，将其删掉，你得到 v_{r-l+1} 的价值。

你可进行若干次这样的操作，不要求最终把数列删干净，最大化你能得到的价值。

这为什么放 T4？

考虑区间 dp，设状态 f_{l,r} 表示把 [l,r] 删掉得到的最大价值，所有的区间都求完之后再跑一个 O(n^2) 的 dp 就是答案。

你考虑什么是个好的串，显然是一个单峰，且相邻两个相差 1 的段。

除了 [l,k]\cup(k,r] 这样的转移外，还需要统计一个把 l,r 放到一起相消的情况。由于好的串是单调递增的，所以你可以额外开两个数组辅助转移，对于一个位置 k，你只需要知道值为 a_k-1 的位置 j，显然这样的点对关系是 O(n^2) 对，你只需要对于每个 l 和每个 r 都求出对应的最优转移即可。

时间复杂度 O(n^3)。