本文主要是介绍北大集训 / CTT 2021 部分题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

忘报名北大集训，还是能看到题，省了 8000 块钱，赢麻了。

鸽表示没代码，may be 无正解思路。

Day 1

A. 末日魔法少女计划

鸽。

\(k = 2\) 的做法：考虑分治，取中间点，处理所有跨过中点的，连上左右两边所有到这里的边，递归下去，是 \(O(n \log n)\) ，但是有很多重复，恰好卡进。

\(k = 3\) 的做法，取若干关键点分成若干块，开头结尾两块只用连后缀 / 前缀边，中间每块连前后缀，并且中间关键点两两连边，用 dp 算出最优的分块位置。

\(k > 3\)，考虑扩展，可能可以分成 \(k - 2\) 部分，每部分两两连边啥的。

B. 魔塔 OL

令怪物总数、询问数量是 \(O(n)\) 量级，\(g, l, d\) 值域是 \(V\)。

顺序如果确定，打怪物看成 \(-a, b\)，答案就是 $- $ 前缀 \(\min\)。

首先过程可以贪心描述，先打能回血的，回血里按 \(a\) 从小到大打，之后每次血量都会变小，一定按 \(b\) 从大到小打（考虑微绕 \(\min(-a_1, -a_{1}+b_1-a_2) \ge \min(-a_2,-a_2+b_2-a_1)\)，两个括号左边不可能作为全局最小值，即 \(b_1 \ge b_2\)，答案不会更劣）

于是问题变成了四维偏序空间内，按一定顺序排好的前缀 \(\min\)。（可以理解为有 \(5\) 个维度？

每次暴力是 \(O(qn)\)，有 \(10\) 分。

\(>3\) 维偏序，\(\log\) 类分治数据结构不如根号，根号不如 bitset。

但这个还得按特殊顺序排序，考虑每 \(B\) 块预处理，我们只会每块 \(O(2^B)\) 的复杂度预处理，所以预处理总复杂度 \(O(\frac{n}{B}2^B)\)。

查询的时候，把每一维的 bitset 整出来 and，然后在预处理的东西里查询即可，复杂度 \(O(\frac{n^2}{B})\)

取 \(B = \log n\) 最优，复杂度为 \(O(\frac{n^2}{\log})\)。

感觉蠢爆了。但是在这个数据复杂度确实很优越。。。

为了规避巨大空间，可以按块处理，这样空间就是线性了。

Code

C. 基因编辑

咋会还有这种题。

记 \(pre_i\) 是 \(i\) 同颜色前驱。

选择的 \(x, y\) 需满足，\(a_y\) 在 \([r + 1, n]\) 中唯一，\(a_x\) 在 \([1, y]\) 中唯一，\(x \ge pre_y\)。

按 \(y\) 从小往大，维护出现一次的 \(x\) 的集合，取最大的元素看一下就行。

\(O(n \log n)\)

Code

Day 2

A. 简单数据结构

全局操作，考虑记个 \(tag\) 表示进行了几次操作 \(2\)。

那么每个值设为 \(a_i + tag \times i\)。那么每次 \(1\) 相当于全局对 \(v - tag \times i\) 这个等差数列进行 \(\text{chkMin}\)。

如果一开始 \(a\) 无穷大是好做的，每次改变的是一个后缀，维护一个栈算一下覆盖的后缀是哪些，区间覆盖等差数列就好了。

考虑算一下每个 \(i\)，\(a_i\) 什么时候第一次被 \(\text{chkMin}\)，之后的过程就是类似上面的，相当于维护一个 \(01\) 序列，支持维护 \(1\) 的那些点的和，覆盖等差数列，以及单点 \(0\) 变 \(1\)。

找到第一次，可以整体二分 + 李超树 \(O(n \log ^2n)\)，瓶颈也是这里。

Code

B. Datalab

此题可以做到两次，深感恐惧，还没读代老师代码。

垃圾做法：

\(8200\) 次：从高到低确定每位，考虑每次问两个一样的串，只有第 \(i\) 位是 \(1\)，那么他会进位到后面的一段 \(1\)，期中满足最后一个 \(1\) 位置和他同号，中间那些和他异号。

考虑并行这个过程，但是如果低位扩展太长影响高位就寄了，，

考虑分块，把 \(8200\) 分成 \(90\) 块，每块从开头开始扩展，发现每次要么都扩展了至少 \(1\)，要么有一块跨越段爆了，复杂度貌似可以保障，从小到大找到最小的跨越一段的块，前面的往右边跳，这个块跨完了，分析一下上界是 \(2\sqrt{8200} = 180\) 的，卡点通过，又慢又拉。
Code

C. 随机游走

首先肯定只有 \(x \rightarrow 1\) 这样的边让他回去更快。

然后打表发现是这么放的（令 \(x\) 表示连 \(x \rightarrow 1\) 的边）：

• 最前面 \(n - 1\) 个：\(n,n-1,\dots,3,2\)（没有 \(1\) ！）
• 后面每 \(n\) 轮从大到小各放一个。

设 \(c_i\) 表示 \(i\) 到 \(1\) 连的边数。\(c\) 颜色相同连续段最多 \(3\) 段。

同时自然列出 \(O(n)\) dp，发现可以矩阵快速幂优化 发现 \(c\) 相同一段其实就是等比数列求和。

\(O(T \log n)\)

Code

Day 3

A. 小明的树

诈骗。

考虑什么时刻是合法的，发现是未点亮的联通块是一 \(\Rightarrow\) 当前两头都未点亮边数是 $n - 1 - $ 当前操作次数。

有根树居然推出无根限制，真神秘。。。限制每条边独立。

同时如果合法的，目前贡献相当于一头点亮一头未点亮个数。

所以合法位置个数可以转化为区间加，求 \(0\) 的个数，同时求 \(0\) 的位置那些贡献和，还得区间加贡献 ，线段树维护最小值 \(\&\) 最小值次数，同时维护最小值对应的贡献值之和即可。

树真恐怖。

\(O((n + m) \log n)\)。

Code

B. 出题高手

个人理解，区间长度不会太长。

果不其然，\(2000\) 足以。

扫描线，\(O(1)\) 改，\(O(\sqrt{n})\) 区间 \(\min\)。

喜提最劣解。

\(O(m \sqrt {n})\)

Code

C. 扑克比大小

鸽。

Day 4

A. 算术

应该是任意一种情况，对应系数成比例。

设长度是 \(n\)。

那么对应关系是 \(b^i \leftrightarrow (-1)^{\lfloor\frac{i}{k}\rfloor} b^{\lfloor\frac{n}{k}\rfloor - \lfloor\frac{i}{k}\rfloor\ +\ i\ \bmod\ k}\)

代入 \(i = 0\) 发现这个比例是 后者是前者的 \(b^{\lfloor\frac{n}{k}\rfloor}\) 倍。

\[b^i = (-1)^{\lfloor\frac{i}{k}\rfloor} b^{ - \lfloor\frac{i}{k}\rfloor\ +\ i\ \bmod\ k} \]

\[b^{\lfloor\frac{i}{k}\rfloor\times(k+1)} = (-1)^{\lfloor\frac{i}{k}\rfloor} \]

这个 \(i\) 是随便取的，那么就得有 \(b^{k+1} = -1\)。

就大概就是半阶 \(-1\)。

根据一些数论知识，\(b, p\) 不互质没有阶，没有阶没有半阶。

半阶的奇数倍也都是 \(-1\)。

阶的所有倍都是 \(1\)。

考虑半阶若存在只能是阶 \(/2\)，如果不是，会发现阶会变的更小，矛盾。

这样只用找阶，分解素因数后，可以有每次 \(\log\) 做法。

考虑分解 \(\phi(p)\) 质因数，每次考虑一个质因子至少需要几个，剩下的都凑足了，重复直到是 \(1\) 即可，每个质因子独立。

有些情况要特判 \(p = 2\)，半阶为 \(1\) 时答案是 \(2\)。

复杂度 \(O(\sqrt{p} + T \ \times \log p)\)

Code

B. 经典游戏

注意每次操作有后效性。。。

没有特殊条件的基础游戏，每个棋子 \(sg\) 函数就是子树 \(mex\)，就是子树高度。

加上特殊条件，如果根确定，当前状态就是 \(a\) 奇数位置的高度的 \(xor\)，K 想赢，必须选一个 sg 函数恰好是当前状态的把异或为 \(0\)，而又他能选的是一段区间满足 \(\le\) 最大高度。

定义 \(w_x\) 为距离 \(x\) 最远的距离。

转化完题意就是一个点是好的当且仅当以它为根 \(1\) 的位置的高度的 \(xor\) 大于 \(w_x\)。

直接求 \(O(nm)\) 可以 \(45\)。。

就是问一个临域有多少好的。

可以发现若干根号平衡方法，但是在树上，通常有链剖分的形式来转化为 \(\log\)。

考虑一个点的影响，相当于最多对 dfn 的三个区间 xor 相同的数。

考虑长链剖分，相当于每次修改，子树外部分，长儿子，轻儿子们 xor 的数各自一样。

那么就简单的做到了 \(O(\log)\) 改、查单点。这样能得 69 分，11 那个过了感觉是数据太水。

考虑单独维护每个点轻儿子的答案，剩下的暴力查。

发现几乎全部点，他们轻儿子也都是整体 xor 一个树，除了 \(x\) 如果是自己父亲的轻儿子，那可能只用改 \(x\) 在清父亲中的影响。

那么我们考虑这样一个数据结构，初始有两个序列 \(a_{n}, b_{n}\)，每次 \(a\) 整体异或 \(k\)，求有多少个 \(i\) 有 $a_i > b_i $。

这题其实限制更紧，\(b_i\) 都一样，不过我没发现。。。

记录当前异或的总量 \(k\)，发现对于一个 \(i\)，有贡献的 \(k\) 可以拆成 trie 树上 \(\log\) 个子树，那么插入的时候把这些子树加，查询单点查走到底加起来就行。

复杂度 \(\log\)。

总复杂度 \(O((n + m) \log n)\)。

Code

C. 随机数据

\(30\) 分：先看成 \(i \rightarrow (i+d) \bmod n\) 的若干环。b 每次能选肯定选没坏处。可以转化为相邻两个可用之间连边，权值是两个的 \(\min\) 的最大匹配。首先考虑一组方案一定能找到这样匹配，然后这样一组匹配 b 也有方案，就是 a 占一个，b 立刻占另一个，如果 a 占到 min 的，a 拉了，b 更厉害了。这样可以在线段树上维护这个东西，记一下左右两边和选没选，\(O(q\log n)\)，寄。

可能需要类 / 万欧？我好菜，不会。

这篇关于北大集训 / CTT 2021 部分题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！