信友队 2023 国庆集训 做题记录

发表于 分类于

Day 1

0 + 0 + 0 + 0．

A. 商店

考虑在时刻 tt，若先去 ii 再去 jj 比先去 jj 再去 ii 更优，那么我们有

t+tai+bi+1+(t+tai+bi+1)aj+bj≤t+taj+bj+1+(t+taj+bj+1)ai+bi⇒bi+biaj+aj+bj≤bj+bjai+ai+bi\begin{alignedat}{} & & t + ta_i + b_i + 1 + (t + ta_i + b_i + 1)a_j + b_j &\le t + ta_j + b_j + 1 + (t + ta_j + b_j + 1)a_i + b_i \\ & \Rightarrow & b_i + b_ia_j + a_j + b_j &\le b_j + b_ja_i + a_i + b_i \end{alignedat}

很神奇啊，tt 没了，也就是说对于选取的一个集合，我们去买东西的顺序其实是一定的．

将序列按照上述方式排序后，问题弱化为选出子序列，最大化子序列长度，容易设计一个 DP 来解决．设 fi,jf_{i, j} 表示考虑了前 ii 个商店，当前时刻为 jj 的最长子序列长度，转移是简单的．

这 DP 第二维有 10910^9，显然寄了，但是注意到 ai≠0a_i \not= 0 时的答案并不大，大概是 log⁡\log 级别的（这是因为每选一个 ai≠0a_i \not= 0 的商店时，时刻至少翻倍），于是考虑只 DP ai≠0a_i \not= 0 的部分，剩下的商店显然可以贪心拼接，然后将 DP 的值域和定义域换一下，设 fi,jf_{i, j} 表示考虑前 ii 个商店，子序列长度为 jj 的最小时刻，就可以解决了．

时间复杂度 O(nlog⁡n)O(n \log n)．

B. 下午茶

由于 pp 是奇数，我们建出 x→2x mod nx \to 2x \bmod n 的边，容易证明这张图由若干个环构成．

又由于 (2y+1,p)=1(2^y + 1, p) = 1，也就是说不存在 kk 使得 2k≡−1(modp)2^k \equiv -1 \pmod p，这证明 xx 和 −x-x 一定在不同的环中．且 xx 和 −x-x 所在的环中的元素仅相差一个符号，也就是说可以将其一一对应，我们的目标是用最小的代价使得对应元素相等．

上文中可以看出，环的总数为偶数，所以我们只需要解决有两个环的情况就解决了问题．

考虑将环对齐后对位相减，目标变成调整成 00，这不是我们 糖果传递 吗！然后就做完了．

C. 逆向惯性思维

下辈子注意别把式子抄掉几项．

容易发现题目让我们求的就是

∑S⊆U(max⁡i∈Sxi−min⁡i∈Sxi)×(max⁡i∈Syi−min⁡i∈Syi)\sum_{S \subseteq U} (\max_{i \in S} x_i - \min_{i \in S} x_i) \times (\max_{i \in S} y_i - \min_{i \in S} y_i)

拆！

∑S⊆Umax⁡i∈Sxi×max⁡i∈Syi−∑S⊆Umax⁡i∈Sxi×min⁡i∈Syi−∑S⊆Umin⁡i∈Sxi×max⁡i∈Syi+∑S⊆Umin⁡i∈Sxi×min⁡i∈Syi\sum_{S \subseteq U} \max_{i \in S} x_i \times \max_{i \in S} y_i - \sum_{S \subseteq U} \max_{i \in S} x_i \times \min_{i \in S} y_i - \sum_{S \subseteq U} \min_{i \in S} x_i \times \max_{i \in S} y_i + \sum_{S \subseteq U} \min_{i \in S} x_i \times \min_{i \in S} y_i

显然四个 ∑\sum 做法相同，我们只需要解决一个就行．以第一个为例．

考虑扫 xx，设当前的点为 (xi,yi)(x_i, y_i)，我们将贡献分成两个部分：max⁡y\max y 由 ii 取到的和 max⁡y\max y 由其他点取到的．第一部分是容易计算的，设在 ii 左下方的点的个数为 ct\mathrm{ct}，那么这一部分贡献就是 xiyi(2ct−1)x_iy_i(2^{\mathrm{ct}} - 1)．

考虑计算第二部分，我们可以枚举在 ii 左上方的一个点，显然在这个点下方的所有点都是可以随便选的，反演一下，每个点会对 yy 坐标大于自己的点造成一次 ×2\times 2 的贡献．但是这个做法无法处理存在 yy 坐标相同的点的情况．考虑 yy 坐标相同的点的贡献系数长什么样，发现状若一个等比求和，那么再多支持一个单点加就能做了．

D. 模糊的字符串

鉴定为烂．

由 经典套路 可得，直接使用主席树维护 hash 就能算 LCP．

考虑如何比字典序，若有一个串 LCP 后面一个字符此前没有出现过，那么肯定是这个串的字典序大．若此前都出现过，我们需要比较字符在子串中第一次出现位置，这个可以轻易用二分解决．

Day 2

10 + 30 + 80．

A. Counting

一点不会，狗都不补．

B. Graph

构造．/qd

先尝试一下树的部分分！

我们考虑以下的构造方案：

  1. 从一个点开始，对树进行 dfs．初始所有点都在 BB 集合中．

  2. 搜到 uu 时，将 uu 从 BB 移动到 pp 中．

  3. 从 uu 离开时，将 uu 从 pp 移动到 AA 中．

  4. 若某次操作后，∣A∣=∣B∣|A| = |B|，那么我们就得到了一组合法的构造．

每次操作都会使得 ∣B∣−∣A∣|B| - |A| 减少 11，而 dfs 前 ∣B∣−∣A∣=n|B| - |A| = n，完成 dfs 后 ∣B∣−∣A∣=−n|B| - |A| = -n，也就是说一定存在某次操作，操作完后 ∣A∣=∣B∣|A| = |B|，不存在无解．

考虑扩展到图上，发现这个做法的唯一阻碍在于，若我们搜出的生成树中有横叉边，那么 A,BA, B 集合间就可能有边．然而如果我们直接选取一棵 dfs 树，那么就解决了这个问题．

C. 演唱会

HBOI2022 模拟赛．/xia

考虑建出圆方树，那么一条路径上必经的点就是圆方树上两点间的圆点数目．题意转化为求有多少路径 (u,v)(u, v) 满足 uu 和 vv 均为圆点，且路径上的圆点数目等于 LL．

可以简单利用 DSU on tree 解决．卡下常就过了．

也可以利用长链剖分优化 DP 做到 O(n)O(n)，如果联赛没似就补．

Day 4

100 + 100 + 60 + 40．

A. 区块链

有

1n=1a⊕b+1b  ⟺  1n=(a⊕b)+b(a⊕b)b  ⟺  (a⊕b)b=((a⊕b)+b)n  ⟺  a⊕b=nbb−n\frac{1}{n} = \frac{1}{a \oplus b} + \frac{1}{b} \iff \frac{1}{n} = \frac{(a \oplus b) + b}{(a \oplus b)b} \iff (a \oplus b)b = ((a \oplus b) + b)n \iff a \oplus b = \frac{nb}{b - n}

枚举 bb 计算取 max⁡\max 即可．

B. 菜肴

shaber 玩意．按题意模拟即可．

C. 再买一件

不会．

D. 基因优化

O(n2)O(n^2) 能过是什么 shaber．

考虑贪心地从前往后翻．

对于相邻的两个能够翻动的位置，不同的翻动方式最多得到 22 个串，比一下字典序大小就行．

Day 5

30 + 20 + 52 + 0．

A. NOIP

注意到将 xx 升序排序后，每个赛站匹配的一定是连续的一段．

那么就可以根据这个性质来设计 DP．设 fi,jf_{i, j} 表示匹配了前 ii 个选手，使用了前 jj 个赛站．转移枚举本次匹配了多少，有

fi−x,j−1+cost→fi,jf_{i - x, j - 1} + \mathrm{cost} \to f_{i, j}

其中 cost\mathrm{cost} 代表 [i−x+1,i][i - x + 1, i] 这一段和 jj 匹配的代价．

容易使用线段树优化转移．

B. 大卫·马丁内斯

幽默．

尝试从全 mm 的属性值开始调整．

注意到 mm 组任务中对于属性值 ii 的要求构成排列，也就是说每将一个属性值下调 11，最多使一组任务失败．那么直接顺着调整，由于开始成功的任务组数为 mm，结束时成功数为 00，过程中每次至多减去 11，也就是说一定能调整到 ss．

C. 大大大

不会．

D. 启动

不会．

Day 6

75 + 40 + 30 + 20．

A. 巴士路线

有一个显然的倍增优化建边的做法．很可惜，空间寄了．

考虑先用若干根从 11 开始的巴士路线进行类似 bfs 的过程，但是只搜没有搜过的点．

由于第一次覆盖到某个点一定是换乘次数最少的方案，正确性显然．

B. 拍照

q≤100q \le 100，只需考虑如何线性求到达顺序确定后的丑陋值和．

设 tit_i 为编号为 ii 的人到达的时间，显然能和 ii 造成贡献的人只能是贡献了 [1,i−1][1, i - 1] 这个前缀中的某些后缀最小值的位置．

用一个单调栈维护，弹栈时顺便统计一下贡献．

C. 情报破译

由于是位运算，位与位之间独立，考虑拆位．

设 fk,i,j,0/1f_{k, i, j, 0 / 1} 表示从 aa 的第 ii 位，操作序列的第 jj 位开始往后操作 2k2^k 轮后，0/10 / 1 会变成什么．转移直接拼接前后两部分即可．细节有点多．

多带了个 log⁡\log 跑不大动，发现这个拆位可以通过位运算优化掉．具体地，将状态重新设为一个全 0/10 / 1 数会变成什么，这样也可以通过位运算 O(1)O(1) 转移，去掉拆位的 log⁡\log．

D. ⼩镇做题家

设集合 SiS_i 表示课程 ii 包含的学生集合．

若 Si∩Sj≠∅S_i \cap S_j \not= \varnothing，连边 i→ji \to j，边权为 Sj−∣Si∩Sj∣S_j - |S_i \cap S_j|．

这个图上 ii，jj 间的最短路的含义是某题从课程 ii 传递到课程 jj 需要被多少人看到．

那么对于点对 (x,y)(x, y)，答案就是

min⁡x∈Si,y∈Sj∣Si∣+dist⁡(i,j)\min_{x \in S_i, y \in S_j} |S_i| + \operatorname{dist}(i, j)

预处理学生到所有课程的最短路即可 O(n3)O(n^3) 完成．

Day 7

摆了．