专栏文章

依旧云斗集训

xxixisuper九倍体水稻
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min90yk4
此快照首次捕获于
2025/12/01 22:32
3 个月前
此快照最后确认于
2025/12/01 22:32
3 个月前
查看原文

Day 1

T1

给定长度为 nn 的两个数列 {an},{bn}\{a_n\},\{b_n\}，你可以花费 11 的代价从两个数列中取出一个数，该操作可以做任意多次。
假设最终你一共取了 kk 个数，其中从 {an}\{a_n\} 中取的数的和为 AA，从 {bn}\{b_n\} 中取的数的和为 BB，求：
max⁡{min⁡{A,B}−k}\max\{\min\{A,B\}-k\}
一只老哥。
把 a,ba,b 降序排序，显然对于一种方案取的是 aa 的一段前缀和 bb 的一段前缀。
枚举 kk，设你从 aa 里取了 xx 个数，则从 bb 里取了 k−xk-x 个数，两者取 min⁡\min，显然关于 xx 单峰，三分即可，一只老哥。

T2

给定一个初始值域为 [0,n)[0,n) 的可重集 SS，可以进行如下操作若干次：
  • 选择一个（可以为空的）子集 T⊆ST\subseteq S，TT 中元素不可重。
  • 从 SS 中删掉 TT（重复元素只删一个）。
  • 把 mex⁡(T)\operatorname{mex}(T) 放进 SS。
求最少进行多少次能使 n∈Sn\in S。
给定 SS 的方式是对于 i∈[0,n)i\in [0,n)，每个 ii 在 SS 中有 fif_i 个。
正序递推是 O(ans)O(ans) 的，不可做，考虑倒序。
倒着找到最后一个 00 的位置，如果想让其属于 SS，则至少花费一次，且前面的每个数都得取出来一次。
于是我们继续向前，设 ansans 表示到当前为止的答案，则对于 ii 来说，如果 fi−ans≤0f_i-ans\le 0，那最后需要补到 11，所以 ans←ans+(1+ans−fi)ans\gets ans+(1+ans-f_i) 就结了，线性。

T3

数轴上有 nn 个点，有 mm 次加点操作，每个点的移动速度是 11 单位长度每秒。
每次加点操作后，输出所有点间距 ≥D\ge D 的最小时间。
一只老哥。
考虑任意两点之间的最优走法一定是相向而行，并且最终的相对位置关系一定与初始时无异，所以对于答案 tt 来说，必然有：
aj−ai+2t≥D(j−i)a_j-a_i+2t\ge D(j-i)
移项得：
t≥(Dj−aj)−(Di−ai)2t\ge\frac{(Dj-a_j)-(Di-a_i)}{2}
用线段树维护 {Di−ai}\{Di-a_i\}，合并时更新答案即可。
可以标记永久化，也可以直接区间加 tag，一只老哥。

T4

待补。

Day 2

T1

给定长为 nn 的数列 {an}\{a_n\}，找长度最小的区间 [l,r][l,r]，满足在 i∈[0,l)∪(r,n]i\in [0,l)\cup(r,n] 中 aia_i 没有重复的数。
显然可以双指针，找到最大的 ll，该前提下找到最小的 rr，然后让 ll 逐渐减小，rr 对应逐渐增大，线性。

T2

给定长为 nn 的数列 {an}\{a_n\}，选择一个区间 [l,r][l,r] 区间加上 d∈[−x,x]d\in[-x,x]，求 {an}\{a_n\} 的最长上升子序列。
一只老哥。
假设 dd 为正，则取得区间显然最优是一个后缀，而 dd 为负的情况显然可以等价为 dd 为正。
则我们算前缀的 LIS，后缀的 LIS，枚举一下分界点在哪里就好了，一只老哥。

T3

这我怎么形式化题意？？
你有 1×1×11\times 1\times1 和 2×1×12\times1\times1 的乐高积木若干，你需要搭一个 w×h×1w\times h\times 1 的一堵墙，有多少种情况是这堵墙是锁死的。
w⋅h≤2×105w\cdot h\le 2\times10^5

O(w2)O(w^2) sol

显然锁不死的情况是这堵墙能够被纵向分割，所以记 fif_i 表示 i×h×1i\times h\times 1 且锁死的情况数，gig_i 表示 i×h×1i\times h\times 1 且锁不死的情况数，fibifib_i 表示斐波那契数列的第 ii 项，则：
gi=∑j=1i−1fi−j⋅gj fi=fibih−gig_i=\sum_{j=1}^{i-1}f_{i-j}\cdot g_j\\~\\ f_i=fib_i^h-g_i
其实这个东西可以直接上多项式科技就做完了。

O(wh2)O(wh^2) sol

考虑锁死的充要条件，显然是每一条接缝处都得有长为 22 的积木连接，于是设状态 fi,jf_{i,j} 表示第 ii 条接缝有 jj 个长为 22 的积木连接，则：
fi,j=∑k=1h−jfi−1,k×(h−kj)f_{i,j}=\sum_{k=1}^{h-j}f_{i-1,k}\times\binom{h-k}{j}

正解

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

T4

待补。

Day 3

T1

给定长度为 nn 的数列 {an}\{a_n\}，以及一个折扣系数 qq。
把 {an}\{a_n\} 中的元素分成若干组，用集合 T1,T2,T3,⋯T_1,T_2,T_3,\cdots 表示。
  • 若 ∣Ti∣≥3|T_i|\ge 3，则令 TiT_i 中最小的元素变为 00。
  • 若 ∣Ti∣<3|T_i|<3，则令 TiT_i 中元素变为原来的 1−q1-q 倍。
你需要最小化分组后所有组内元素和。
如果你想要免费那一档，那分的组的大小显然不可能超过 33，不然多余的丢给折扣更优。
然后注意到免费那一档一定是选值域上连续的三个数，微扰即证。
所以排个序后 dp 即可，状态转移方程为：
fi=min⁡{fi−1+(1−q)⋅ai,fi−3+ai−1+ai}f_i=\min\{f_{i-1}+(1-q)\cdot a_i,f_{i-3}+a_{i-1}+a_{i}\}
一只老哥，瓶颈在于排序。

T2

Lottery

T3

给定平面内 nn 个点，问有多少个点对 (a,b),(c,d)(a,b),(c,d) 满足：
a<cb<d∄(e,f),e∈(a,c),f∈(b,d)a<c\\b<d\\\not\exist(e,f),e\in(a,c),f\in(b,d)
两只老哥。
考虑 cdq，把所有的点的第二维从 midmid 劈开，则对于上面的点来说，其所能对应的下半区间的点一定是当前的前缀 min⁡\min，于是下半单调栈，树状数组维护点个数即可。
主定理分析时间复杂度两只老哥。

T4

待补。

Day 4

T1

给定长为 nn 的排列 {pn}\{p_n\}，定义二元函数 w(i,j)w(i,j) 的定义域满足 i<ji<j，则：
w(i,j)=∣pi−pj∣⋅∣i−j∣w(i,j)=|p_i-p_j|\cdot|i-j|
取 w(i,j)w(i,j) 前 kk 小的和。
k<nk<n
因为 k<nk<n，而直接取 w(i,i+1)w(i,i+1) 就一定 <n<n，所以所有的 ww 一定都小于 nn。
若 ab<nab<n，则 a<na<\sqrt n 或者 b<nb<\sqrt n。
所以原排列直接向前扫 n\sqrt n 个，值域与位置对调后再扫一遍就做完了。
用 nth_element 是 O(nn)O(n\sqrt n) 的，用优先队列还得带个老哥。

T2

有 mm 个形如 ⊕i=lrai=x\oplus_{i=l}^ra_i=x 的限制，判断是否存在一个满足条件的数列。
转成前缀异或，然后二进制拆分。
用扩展域并查集维护相对关系即可，两只老哥。

T3

给定一个长为 nn 的环，第 ii 个位置上有数 aia_i。
有多少种分割方案，满足分割出来的每一段的按位与都不为 00。
一只老哥。
考虑破环为链，直接计算怎么做。
对于单次 dp，可以做到 O(nlog⁡n)O(n\log n) 预处理出 bitand 的 st 表。dp 计算每个位置时需要知道最远可以与到哪个位置，所以需要一个二分，然后前缀和优化即可做到 O(nlog⁡n)O(n\log n)。
如何不重不漏的计算所有情况？可以考虑每次算完之后，直接 a1←a1bitand⁡ana_1\gets a_1\operatorname{bitand} a_n，然后让数列长度缩 11，每次缩完后直接暴力 dp 就是 O(n2log⁡n)O(n^2\log n) 的。
这时你注意到整个 dp 实际上仅关心 a1a_1 的取值，而 a1a_1 的更新依赖于 bitand⁡\operatorname{bitand}，所以不同的 a1a_1 仅有 O(log⁡V)O(\log V) 个，我们只需要在 a1a_1 改变的时候进行 dp 即可做到 O(nlog⁡nlog⁡V)O(n\log n\log V)。
最后你考虑每次 dp 的时候都求一遍 st 表是没有必要的，因为我们仅会改变 a1a_1 的值。又发现每次求值的二分也是没有必要的，对于那些二分出来的界大于 11 的位置，由于这些数根本不会变，所以一次二分即可。对于那些界正好是 11 的位置，我们只需要在更新的时候判断一下还能不能与到 11 即可，于是时间复杂度 O(nlog⁡V)O(n\log V)。

T4

是个好题。

Day 5

T1

给定 L,DL,D，有长为 mm 的数列 {am}\{a_m\}，与长为 nn 的数列 {bn}\{b_n\}。
从 {am}\{a_m\} 中取出尽可能多的没有交的递增子序列，满足相邻两项差值 ≤D\le D，且最小值 ≤D\le D，且最大值 ≥L+1−D\ge L+1-D。
记上述问题答案为 tt，则从 {bn}\{b_n\} 中取出 n−tn-t 个数最小是多少。
首先是一些观察，取出来的 bb 显然是最小的部分，所以排个序。
然后考虑怎么做，我们二分答案 tt，考虑如何验证，发现一定是 tt 个位置一起向前跳，显然跳的越远越好，这个过程等价于从 00 开始跳最接近 DD 的点，然后把这个点从 aa 中删掉。
于是二分答案是没有必要的，直接把 aa 丢进 set 中维护然后暴力删点即可，一只老哥。

T2

给定长为 nn 的数列 {an}\{a_n\}，求该数列的极长区间 [l,r][l,r]，满足存在 x,yx,y 且 x≥2x\ge2，i∈[l,r]i\in[l,r] 内的所有 ai mod x=ya_i\bmod x=y。
输出最长长度。
鉴定为典完了。
直接差分取绝对值，然后从差分数组中找到最长的 gcd⁡\gcd 不为 11 的区间即是答案，用你喜欢的数据结构维护即可，两只老哥（也有说用 st 表是一只老哥的）。

T3

好题。
给定长为 nn 的 0101 数列，你最多可交换 kk 对位置，要求最后相邻两个 11 的间隔不能 >m>m，特别的，我们把位置 00 与位置 n+1n+1 钦定为 11。
n≤2×105,k≤200n\le2\times10^5,k\le200
暴力配对是不可做题，考虑怎么转化题意。
显然你不会交换 0000 或者 1111，你也不会交换同一个点两次，所以假设你交换了 BB 对点，则等价于对这个数列进行如下操作：
  • 选择 BB 个位置从 0→10\to 1；
  • 选择 BB 个位置从 1→01\to 0。
这个东西看起来就很可以 dp 的样子，所以我们开始设状态。设 fi,j,pf_{i,j,p} 表示前 ii 个位置，一共走了 jj 个位置，其中走了 pp 个 0→10 \to 1 的位置的可行性，转移是随便转移的，不细想的话大概是 O(n2k2)O(n^2k^2) 的。
优化啊优化，dp 有一个非常经典的优化就是把可行性 dp 转化成最优化 dp，即把 dp 的某一维状态丢进答案中进行转移。
由于我们想要的时间复杂度应该是 O(nk)O(nk) 的，而现在的状态数是 O(n2k)O(n^2k) 的，我们显然要考虑把某一个 nn 的维度丢进答案，应该是丢哪个都可以，感觉把第一维丢掉是比较自然的，所以设状态 fj,pf_{j,p} 表示走了 jj 个位置，其中有 pp 个位置 0→10\to 1，所能走到的最远距离。
预处理出每个位置 ii 后距离 mm 以内最远的 00 或者 11，分别记为 b0ib0_i 和 b1ib1_i，则转移是 naive 的：
fj,p=max⁡{b1fj−1,p,b0fj−1,p−1}f_{j,p}=\max\{b1_{f_{j-1,p}},b0_{f_{j-1,p-1}}\}
最后对于每个状态判断一下是不是满足条件就做完了，转移 O(1)O(1)，则总时间复杂度就是 O(nk)O(nk) 的。

T4

待补。

Day 10

T1

给定集合 SS，你可以进行如下操作若干次：
  • 选择 x,y∈Sx,y\in S，把 xbitand⁡yx\operatorname{bitand} y 放进 SS 中；
  • 选择 x,y∈Sx,y\in S，把 xbitor⁡yx\operatorname{bitor} y 放进 SS 中。
保证 SS 中初始时的元素 <2k<2^k，你需要对于 [0,2k)[0,2^k) 中的每个数判断最终其是否可以通过若干次操作使其进入 SS 中。
挺好的题。
考虑 xbitand⁡ybitor⁡zx\operatorname{bitand} y\operatorname{bitor} z，由于这两种位运算互有分配律，所以有：
xbitand⁡ybitor⁡z=(xbitor⁡z)bitand⁡(ybitor⁡z)x\operatorname{bitand} y\operatorname{bitor} z=(x\operatorname{bitor} z)\operatorname{bitand} (y\operatorname{bitor} z)
那么我们可以先跑出仅通过 bitor⁡\operatorname{bitor} 能够得到的数，再跑出通过 bitand⁡\operatorname{bitand} 能够得到的数。
对于前者，我们考虑高位前缀和的过程，显然把一个子集内的所有数都或起来一定是不劣的，所以我们记 fif_i 表示把 ii 内的所有数与起来所得到的数是什么，最终只需要判断 fif_i 等不等于 ii 即可。
把 0101 取反后后者就变成了前者，所以你就做完了这一题，时间复杂度 O(k2k)O(k2^k)。

T2

不可做题

T3

给定一棵 nn 个节点的树，根节点为 11，每个点有点权，每次询问给定 cc，需要从该节点走向一个点权大于等于 cc 且最小的儿子，你需要输出最终在哪里不能走了。
可以对点权进行修改。
两只老哥。
这真是何意味题目。
考虑这是一条链怎么做，显然二分一下，限一下下界与上界就能知道最远跳到哪里了。
那，直接剖，就是 O(nlog⁡2n)O(n\log^2n) 的了啊。
何意味？

T4

定义一个数列是好的当且仅当：
  • 相邻两个数的差的绝对值等于 11。
  • 中间的数大于等于相邻两个数的算数平均数。
给定长为 nn 的数列 aa 和 vv，每次你可选择 aa 的一段好的字串，假设其为 [l,r][l,r]，将其删掉，你得到 vr−l+1v_{r-l+1} 的价值。
你可进行若干次这样的操作，不要求最终把数列删干净，最大化你能得到的价值。
n≤400n\le 400，vv 可能 <0<0。
这为什么放 T4？
考虑区间 dp，设状态 fl,rf_{l,r} 表示把 [l,r][l,r] 删掉得到的最大价值，所有的区间都求完之后再跑一个 O(n2)O(n^2) 的 dp 就是答案。
你考虑什么是个好的串，显然是一个单峰，且相邻两个相差 11 的段。
除了 [l,k]∪(k,r][l,k]\cup(k,r] 这样的转移外，还需要统计一个把 l,rl,r 放到一起相消的情况。由于好的串是单调递增的，所以你可以额外开两个数组辅助转移，对于一个位置 kk，你只需要知道值为 ak−1a_k-1 的位置 jj，显然这样的点对关系是 O(n2)O(n^2) 对，你只需要对于每个 ll 和每个 rr 都求出对应的最优转移即可。
时间复杂度 O(n3)O(n^3)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...