GJ Round (2024.11) Round 22~38

lun_hao · 2024-11-06 20:39:37 · 个人记录

前言：

洛谷、博客园、CSDN 同步更新

点此返回 GJ Round 目录（博客园）

博客园可能食用更佳

Tip：博客园不等号渲染有问题，就像这样：\neq

Round 22 (11.4)

唯一一次快速补完了题

A

AT_arc077_a [ABC066C] pushpush

不懂这原题标号咋这么奇怪

给你一个序列 a_1 \dots a_n，按照如下规则构造新序列：

将 a_i 插入序列末尾

将整个序列反转

模拟 / 打表找规律：

当 n 为奇数时，答案为 a_n a_{n-2} \dots a_3 a_1 a_2 a_4 \dots a_{n-3} a_{n-1}
当 n 为偶数时，答案为 a_n a_{n-2} \dots a_4 a_2 a_1 a_3 \dots a_{n-3} a_{n-1}

时间复杂度 \mathcal O(n)

B

初始给定 n 个点 (x_i,y_i)，给两个点 i,j (i \neq j) 连边的代价为 |x_i-x_j|^3+|y_i-y_j|^3，q 次询问，每次加入一条新边，求每次将所有点连通所花费的最小代价

对原图跑 Prim 求最小生成树，保留 n-1 条边，再与新加入的 q 条边跑 q 次 kruskal，时间复杂度为 \mathcal O(n^2 + q m \log n + m \log m)，其中 m=n-1+q,\log n 为并查集的时间复杂度，若是并查集继续使用了启发式合并 / 按秩合并可以优化至 \mathcal O(n^2 + q m \alpha(n) + m \log m)，其中，\alpha(n) 为反阿克曼函数

实则还可以不跑 q 次 Kruskal，直接 dfs 找环删除环上最大边边即可，时间复杂度为 \mathcal O(n^2 + q n)

C

给你两个长度为 n 的序列 a,b，保证 \forall 1 \leq i < j \leq n，都有 a_i \neq a_j,b_i \neq b_j，定义他们的距离为 \sum_{i=1}^{n} (a_i-b_i)^2，求距离的最小值，答案对 998244353 取模，并求出最小化距离时所需要交换的次数

对于问题一，显然将 a 序列中的第 k 大与 b 序列中的第 k 大排在一起即可，易证

第二问直接 for 模拟一下每个数是否已到对应位置，总时间复杂度为 \mathcal O(n \log n)

D

魔法阵是一个任意大小的方阵，满足如下性质：

设 (i,j) 有 a_{i,j} 个魔法石，则有 a_{i,j} \geq m

设魔法阵大小为 k，任意从魔法阵中选出 k 个格子，满足任意两个格子不在同一行也不在同一列，那么选出的 k 个格子的石子数之和是相同的

魔法阵中对角线石子数之和不能超过 n

多测，给定 n,m，求方案数，答案对 998244353 取模

容易发现，a_{i,j}=x_i+y_j 是一个合法的方阵

钦定 \min(x_i)=0，则方阵与数列之间一一对应，此时 a_{i_j} \geq m 等价于 \min(y_i) \geq m

不妨将所有的 y_i 减去 m，使得问题转化成至多 (n-km) 个石子放入 2k 个格子，且前 k 个格子至少有 1 个没有的方案数，容斥后得：

ans= {n - km + 2k\choose 2k} - {n - km + k \choose 2 k}

询问时间复杂度为 \mathcal O(\sum \lfloor \frac{n}{m} \rfloor)，然后预处理逆元的复杂度只需要 \mathcal O(V) 即可，其中 V 为值域大小

Round 23 (11.11)

后三题紫紫黑，GJOJ 真是蒸蒸日上

某十三连测，原题赛，应该是蓝紫紫黑

A

给定一个长度为 2n 的扑克牌，初始第 i 张牌的权值 a_i=i，每次进行一次切牌操作，即将 a_1,a_2,\dots,a_{2n} 变成 a_1,a_{n+1},a_2,a_{n+2},\dots,a_n,a_{2n}，求最少切牌操作次数，使得扑克牌的顺序重新变为 1,2,\dots,2n，多组数据

很好的数论题，使我的大脑旋转

弱化版洛谷 P2755 洗牌问题，但这题单次询问就可达 n=10^{14} 规模，故不可直接暴力，考虑寻找规律优化复杂度

其实 1 和 2n 既然都不会改变，故可以不考虑这两张牌

将剩下的 2n-2 张牌全部减 1，发现每次操作都是 k \gets 2k \bmod (2n-1)，那么不难发现需要求一个最小的 p，使得 2^p \equiv 1 \pmod{(2n-1)} 即可，暴力时间复杂度为 \mathcal O(n)

根据欧拉定理，p 必然是 \varphi(2n-1) 的因数，直接枚举因数暴力快速幂求出最小 p 即可，单次询问时间复杂度为 \mathcal O(\sqrt m + d(k) \log k)，其中 m=2n-1,k=\varphi(m),d(k) 表示 k 的约数个数

注意到 n 最大可达 10^{14}，故快速幂里会爆 long long，请开 __int128，（我说我因为这里死活过不了样例你信吗）

B

AT_agc016_d XOR Replace

给你两个长度为 n 的序列 a 和 b，每次可以 a_i \gets \operatorname{xor} \lbrace a_1,a_2,\dots,a_n \rbrace，其中 \operatorname{xor} 表示二进制下按位异或和，求将 a 序列变成 b 序列的最小步数

钦定序列初始异或和为 x，每次相当于交换 a_i 和 x，显然地，判断无解只需判断 a \cup \lbrace x \rbrace \supseteq b 即可

考虑从 b_i 向 a_i 连边，尝试从 x 出发遍历所有边

若图是一个包含 x 的连通图，那么必然可以找到一条欧拉路径覆盖所有边
如果图不连通或 x 是独立点，那么答案即为边数加上连通块数再减去 1（若 x 为独立点则不用减 1）

考虑使用 STL 维护可重集，这里笔者使用了快排去重+并查集，时间复杂度为 \mathcal O(n \log n)

C

AT_arc108_f Paint Tree

给定一棵 n 个节点的树。你需要对每个节点黑白染色。

设 x 表示白色点之间的最大距离，y 表示黑色点之间的最大距离，那么定义一种染色的权值为 \max(x,y)。如果某种颜色没有出现那么对应的 x/y 就是 0。

求所有 2^n 种染色方式的权值和。对 10^9+7 取模。

先求出一条直径，若直径的两个端点颜色相同，则最长距离一定为直径。否则，令两个端点分别为 x,y，并钦定 x,y 不同色

枚举答案 d，令 c_u 表示点 u 的颜色，dis_{u,v} 表示点 u 到点 v 的最短路径，\forall u \in G \land dis_{u,x} > d,c_u=c_y，且 \forall v \in G \land dis_{v,y} > d,c_v=c_x，若存在一点 z 满足 dis_{x,z} \leq d \land dis_{y,z} \leq d，那么这个点的颜色不会对答案产生贡献

定义 cnt_i 表示到直径两端的距离不超过 i 的点数，那么对于枚举的 d，所产生的染色贡献为 2^{cnt_d}-2^{cnt_{d-1}}，总贡献为 \sum_{d=L}^{R} 2^{cnt_d}-2^{cnt_{d-1}}，不难得到，下界 L=\max \lbrace \min \lbrace \operatorname{dis}_{0,i},\operatorname{dis}_{1,i} \rbrace \rbrace，上界 R=\operatorname{dis}_{0,y}

注意到颜色可以互换，故贡献记得乘 2

考虑用 dfs 求解，cnt_d 可以考虑将其差分数组统计出来后前缀和求得即可，时间复杂度为 \mathcal O(n)

D

AT_arc152_f Attraction on Tree

你有一棵有 n 个点的树。一开始，树上的 1 号节点处有一个卡片。

你需要进行以下操作恰好 n 次：

选择一个之前没有被选择过的点，将卡片向那个点移动一条边。不能选择恰好在卡片位置的点

称一个选择点的顺序是好的，当且仅当 n 次操作后卡片在 n 号节点。

你需要回答，一个好的顺序在过程中卡片最少访问了多少个节点。或者报告不存在好的顺序。

超级无敌吊炸天逆天神仙题，AT *3664

咕咕咕

Round 24 (11.12)

A

有 n 个怪物，击杀第 i 个怪物可以获得第 i 个法术，且将上一个法术强制顶替掉，用法术 i 击杀怪物 j 需要消耗时间 w_{i,j} 和法力 c_{i,j}，特别地，w_{i,i}=c_{i,i}=0，且击杀第一只怪物不需要花费任何时间和法力，给定法力上限 m，求在不超过法力上限的情况下，最小化击杀所有怪物的时间，并输出击杀顺序，若无解输出 -1，多解输出字典序最小的击杀顺序

发现不能状压 dp，那么这只能是道神秘爆搜剪枝题

预处理出在分别不考虑时间和法力的情况下，从当前局面到最后需要的时间 / 法力，若当前劣与最优解则剪枝

时间复杂度 \mathcal O(n!)，肯定跑不满

B

在赛后不知道多少天才看到原题搬到 luogu 上了

P11306 [COTS 2016] 搜索树 Jelka

给定一棵 n 个点，以 1 为根的二叉树，多次修改，每次修改点 x 的点权，求有多少个结点 u，满足以 u 为根的子树是一棵二叉搜索树 ^\dag
- 不存在左子树或左子树**所有**点的点权都 $\leq x$ 的点权 - 不存在右子树或右子树**所有**点的点权都 $\geq x$ 的点权

不难发现，一棵子树是二叉搜索树当且仅当子树的中序遍历序列的点权单调不降，而每个子树的中序遍历显然是整棵树的中序遍历上的一段连续区间

设中序遍历为 a_1,a_2,\dots,a_n，子树 u 对应的区间为 [l,r]，若子树 u 为二叉搜索树，则 \forall i \in [l,r) \cap \mathbb Z,a_i \leq a_{i+1}

用树状数组维护区间不满足 a_i \leq a_{i+1} 的个数，发现每次修改只会影响这个点到根的路径，考虑树上倍增即可

C

给出长度为 2^n-1 的序列 a_1,a_2,\dots,a_{2^n-1} 和长度为 n 的序列 b_0,b_2,\dots,b_{n-1}，你需要给出长度为 2^n-1 的序列 c_1,c_2,\dots,c_{2^n-1}，满足：
\forall j \in [0,n-1] \cap \mathbb Z,\sum_{i=1}^{2^n-1} \left( \left\lfloor \frac{i}{2^j} \right\rfloor \bmod 2 \right) \times c_i = b_j
并且求出所有情况下 \sum_{i=1}^{2^k-1} a_i \times c_i 的最大值

咕咕咕

D

给定一棵根为 1 的树，初始只有根结点，有如下两种操作：

加入新结点

查询某个子树的自同构 ^\dag 的数量

1. $f(r)=r

咕咕咕

Round 25 (11.13)

某十三连测，原题赛，紫紫紫黑，你管这叫 NOIP 模拟赛，这怕不是 NOI Plus 模拟赛

题目还有误，GJ 搬题连题面都不给，唯一一道绑包题还乱绑，什么质量我不说了

A

AT_agc015_d A or...or B Problem

给定区间 [A,B]，在区间中选一个或多个整数按位或，求一共有多少种结果

神秘构造题，并且谴责在原题的基础上加了多测

考虑将 A 和 B 的最长公共前缀直接扔掉，此时 B 的最高位一定是 1，A 的最高位一定是 0（特判掉 A=B 的情况），反正按位或只会对该位产生影响，并且按位或后不会让原数变小，那直接考虑大于 B 的数产生的贡献即可

取 x,y \in [A^\prime,B^\prime] \cap \mathbb Z，构造两种方案如下：

x$ 只取 $B^\prime$ 的最高位 $1$，$y$ 取 $x-1$，这样 $x|y$ 就取到了每一位是 $1$ 的最大数，记作 $M$，将 $y$ 一直减小至 $A^\prime$，那么可以取得最小值 $x|A^\prime$，将该区间 $[x|A^\prime,M]$ 计入答案中 $\color{red}(I.)
x$ 只取 $B^\prime$ 的最高位和次高位的 $1$，$y$ 还是取 $x-1$，这样 $x|y$ 可以取得最大值，记作 $N$，同样地，将 $y$ 一直减少 $B^\prime+1$，将该区间 $[B^\prime+1,N]$ 计入答案中 $\color{red}(II.)

最后别忘了还有原区间 [A,B] 计入答案中 \color{red}(III.)，综上所得，对 \color{red}(I.)(II.)(III.) 这三个区间取并，即答案为 [x|A^\prime,M] \cup [B^\prime+1,N] \cup [A,B] 中整数的个数（注意此 A,B 非彼 A,B）

笔者不会神秘的二进制快速操作的一些函数，故时间复杂度为 \mathcal O(T \log n)，理论上如果有 \mathcal O(1) 的单次操作那么复杂度可降至 \mathcal O(T)

B

P3643 [APIO2016] 划艇 & CF1295F Good Contest

咕咕咕

C

谴责 GJ 搬题数据乱配乱绑，使我 subtask 1 puts(Yes); 爆零

AT_arc173_d Bracket Walk

给定一张 N 个点 M 条边的有向图，每条边上都有一个字符 ( 或 )，图上无自环无重边。

保证整张图是强连通的，也就是任意两点 s,t 间均至少存在一条 s 到 t 的路径。

问是否存在一条路径使得：

路径的起点与终点相同。

每条边至少在路径中被经过一次。

路径经过的边上的字符依次连接形成一个合法括号序列。

~~一切的起因都是观察到 subtask 1 的神秘特殊性质引导正解~~

subtask 1：图中存在一个标记为 ( 和标记为 ) 的自环

~~这不包有解吗~~

记 ( 为 1，) 为 -1，转化题意得，是否存在一条路径使得权值总和为 0 且保证每时每刻总权值不能 <0

抽象一点，那我是不是只要图中存在一个正环和一个负环就一定能保证有解（这个结论是对的~~，请读者自证或感性理解或前往原题看题解，真的不是我不想证而是我不会证~~）

然后跑 Bellman_Ford 找环就做完了，时间复杂度 \mathcal O(nm)

D

AT_agc008_f Black Radius

超级无敌吊炸天逆天神仙题，AT *3995

咕咕咕

Round 26 (11.14)

不给大样例还四题都模 10^9+7，难绷

A

给定一个数 x，那么记最近的完全平方数为 y^2，即令 |x-y^2| 最小，定义函数 f(x)，则：
f(x)=\begin{cases} x & \text{if} & y \text{为奇数} \\ -x & \text{if} & y \text{为偶数} \\ \end{cases}
现在给定两个正整数 l,r，求 \sum_{x=l}^{r} f(x)，答案对 10^9+7 取模

找规律题，不妨试着打表找一下规律

f(x):[1,2,-3],[-4,-5,-6,7,8],[9,10,11,12,-13,-14,-15],\dots

将 [k^2,(k+1)^2-1] 分成一组，发现这一组内和为 0，那么只需要找到 l 和 r 所在的组内即可

不难发现，第 k 组区间长度为 2k+1，前 k+1 个数同号，则 [k^2,k^2+k] 和 [k^2+k+1,(k+1)^2-1] 可以分别用等差数列快速求出，只需对询问端点 l 和 r 判断其在区间位置即可

时间复杂度为 \mathcal O(1)

B

给定一张有 N 个点 M 条边的带权有向图，从 1 到 x 有 n_x 条最短路径，第 i 条路径记作 d_{u,i}，|d| 则代表经过的边数，求下式对 10^9+7 取模：
\sum_{i=1}^{N}\sum_{j=1}^{n_i}\sum_{k=j+1}^{n_i} |d_{i,j}| \times |d_{i,k}|

诈骗题，不难发现

\begin{aligned} &\because \sum_{j=1}^{n_i}\sum_{k=j+1}^{n_i} |d_{i,j}| \times |d_{i,k}| = \frac{1}{2} \left( \left( \sum_{j=1}^{n_i} |d_{i,j}| \right) ^2-\sum_{j=1}^{n_i} |d_{i,j}|^2 \right) \\ &\therefore \text{原式} = \frac{1}{2}\sum_{i=1}^{N} \left( \left( \sum_{j=1}^{n_i} |d_{i,j}| \right) ^2-\sum_{j=1}^{n_i} |d_{i,j}|^2 \right) \\ \end{aligned}

分别维护路径的长度和以及平方和即可

C

给定一个长度为 n 的序列 a，进行如下 4 种操作：

1 l r 询问 \sum_{i=l}^{r} a_i

2 l r 询问 \sum_{i=l}^{r} a_i^2

3 l r p \forall i \in [l,r] \cap \mathbb Z,a_i \gets \lfloor \frac{a_i}{p} \rfloor（保证 p \neq 0）

4 pos v a_{pos} \gets v

答案对 10^9+7 取模

一眼势能线段树，可参考洛谷 P4145 上帝造题的七分钟 2 / 花神游历各国做法

操作 1,2,4 直接做就好，没什么好说的

考虑对操作三的 p 分类讨论：

这样做跑的飞快，在 GJ 的数据下不加任何优化可以最大点 86ms 通过此题

时间复杂度为 \mathcal O((n+m) \log V \log n)，其中 \log n 为线段树单次操作的时间复杂度，V 为值域大小

D

你有一个长度为 N 的 01 序列 a，显然会有 2^N 种方案数，给定 M 条关系 x_i,y_i，求：
\sum_{u \in S} \left( \sum_{i=1}^{M} [a_{x_i}=a_{y_i}=1] \right)^k
答案对 10^9+7 取模，其中 u \in S 表示枚举所有 2^N 种方案，k 为给定常数，[x] 的方括号为艾弗森括号，若逻辑表达式 x 为真则 [x] 取值为 1，否则 [x] 取值为 0

咕咕咕

Round 27 (11.15)

A

给定正整数 N，求有多少个非负整数对 (x,y),0 \leq x,y \leq N，满足 x \oplus y = x | y，其中 \oplus 为二进制按位异或，| 为二进制按位或

该题可以使用数位 dp、记忆化搜索、数学+dp 等方法通过此题

未知，笔者似乎找了下规律推了个式子后不会解释了

B

咕咕咕

C

咕咕咕

D

咕咕咕

Round 28 (11.16)

A

给定一个长度为 n 的 12 序列 a，每次可以交换相邻两位，求花费最小代价使得序列变成 11\dots22 或 22\dots11

对于任意方案，显然每个数移动的路径不可交叉，容易证明这样是最优的，因为只有两种数，所以就肯定立刻知道每个数移到的位置，时间复杂度为 \mathcal O(n)，n \leq 2 \times 10^5 注意开 long long

B

模拟题，懒得描述题意了，过

C

给定一张 n 个点 m 条边的无向有权图，定义最小代价为所连边权值的最大值，每次删除第 i 条边（只对该询问产生影响），记连通所有点的最小代价为 x_i，若无法连通则记作 -1，求
\frac{\sum_{i=1}^{m} x_i}{\sum_{i=1}^{m} [x_i \neq -1]}

可以现在原图跑最小生成树，然后对删除的边进行分类讨论：

若删除的边是非树边，那么不会对答案产生影响
否则就需要再剩下的边中找到权值最小的边使得整棵树重新连通

不难发现，对于一条非树边 (u_i,v_i,w_i)，当且仅当去掉的树边于树上从 u_i 到 v_i 的路径时，该条非树边可以使得整棵树重新连通，那么可以将 w_i 从小到大枚举更新答案即可

这里可以使用常数小~~码量大~~的树链剖分维护即可，时间复杂度为 \mathcal O(m \log m + m \log n)，其中 m \log m 为 Kruskal 跑最小生成树的时间复杂度， \log n 为单次树剖的时间复杂度

当然也可以用其他 STL 或者数据结构来维护

D

给定一个二维平面网格，有 n 个点，第 i 个点的坐标为 (x_i,y_i)，保证均为整数，由于二维平面网格的特殊性，故对于每一个长度为 1 的方格，只有长度为 1 个边以及长度为 \sqrt 2 对角线连线可走，多次询问，每次询问区间 [l,r] 的点两两之间距离的最大值

咕咕咕

Round 29 (11.18)

A

求
\left( \sum_{i=l}^{r} \left\lfloor \frac{2^i}{3} \right\rfloor \right) \bmod{10^9+7}
其中 l,r \leq 10^{18}

众所周知：

\sum_{i=0}^{N} x^i = \frac{x^{N+1}-1}{x-1}

不难发现，根据观察和上式可得：

\begin{aligned} \sum_{i=l}^{r} \left\lfloor \frac{2^i}{3} \right\rfloor &= \frac{1}{3}\sum_{i=l}^{r} \left( 2^i-2^i \bmod 3 \right) \\ &= \frac{2^{r+1}-2^{l}}{3} - \frac{1}{3} \sum_{i=l}^{r} \left( 2^i \bmod 3 \right) \\ \end{aligned}

而 2^i \bmod 3 的周期为 2,1,2,1,\dots，那么后面的 \sum_{i=l}^{r} (2^i \bmod 3) 拆成 \sum_{i=1}^{r} (2^i \bmod 3)-\sum_{i=1}^{l-1} (2^i \bmod 3) 随便弄一下就好

时间复杂度 \mathcal O(\log r)，其中 \log r 为快速幂的时间复杂度

B

给定一个长度为 m 的排列 b，以及给定一个长度为 n 的序列 a，每次遍历 a_1,a_2,\dots,a_n，进行 a_i \gets a_{b_i} 操作，已知 a_i 在值域 [1,m] \cap \mathbb Z 上等概率取值，求期望进行多少次操作使得所有的 a_i 变回原样，答案对 10^9+7 取模，1 \leq m \leq 100

神秘期望容斥 dp，反正笔者看了很久才知道题目在讲什么

注意到 b 是一个排列，那么操作 a_i \gets b_{a_i} 就是在环上走一步

考虑枚举所有的不同长度的环，注意到 m \leq 100，那么 1+2+\dots+14 > 100，故不同长度的环最多只有 13 种 ^\dag

设 a_1,a_2,\dots,a_n 所在的环长度分别为 l_1,l_2,\dots,l_n，那么要走的步数为 \operatorname{lcm}\lbrace l_1,l_2,\dots,l_n \rbrace

考虑状压枚举每一种长度的环以及对应出现的个数，计算每一个集合 T 的环长之和，记作 x_T

设出现的环长集合为 S，枚举所有的 T \subseteq S，那么出现的概率为 \left(\frac{x_T}{m}\right)^n，容斥系数为 (-1)^{|S|-|T|}

### C > 给定一个长度为 $n$ 的数列 $a$，可以进行无限次操作 $a_i \gets a_i \oplus a_{i-1}$，希望得到一个最大的 $m$，满足在序列 $b_1,b_2,\dots,b_m$，使得 $1 \leq b_1 < b_2 < \dots < b_m \leq n,a_{b_1}<a_{b_2}<\dots<a_{b_m}$，其中 $\oplus$ 表示按位异或咕咕咕 ### D > 有 $n$ 个人，第 $k$ 个人有三个属性 $e_k,i_k,\pi_k$，定义 $i$ 能看清 $j$ 当且仅当 $i$ 的所有属性**都不小于** $j$ 的所有属性，你希望第 $i$ 个人能看清第 $i-1$ 个人，可进行如下操作： > > - 消耗一单位 $A$，交换某两人的顺序 > - 消耗一单位 $B$，把某人的某个属性 $+1

注意：你不关心消耗多少单位 A，但希望最小化消耗 B

咕咕咕

Round 30 (11.19)

咕咕咕

Round 31 (11.20)

A

有 n 张牌，每张牌要么正面朝上，要么反面朝上，当翻转第 i 张牌时，花费 t_i 的代价，第 i+1,i+2,\dots,r_i 也会被翻转，求所有牌都是正面朝上的最小代价

显然每张牌最多被翻转一次，那么考虑从前往后扫一次，因为每张牌的翻转只会影响其后面的，那么当前牌为反面的话直接翻转即可，对后面的牌产生的翻转差分一下就好了，时间复杂度 \mathcal O(n)

B

给个 n 个长度为 m 的 01 串，你需要按顺序将每一行字符串编写出来，可以进行两种操作：

花费 c 的代价直接编写

花费 1 的代价复制前面编写过的一个串，对于每个不同的二进制位，修改也需要花费 1 个代价

求编写所有字符串花费的最小代价，1 \leq n \leq 10^6,\color{red}1 \leq m \leq 20

未知，反正用 01Trie 树 + 暴力无任何优化最大点 1052ms 冲过去了

注意到 m 很小，记前面变成 s 的最小代价为 f_s，每个字符串花费的代价上界为 \min \lbrace m+1,c \rbrace（除了第一个必须是 c）

不难发现 f_s 最多有 \mathcal O(m) 种取值，那么被更新的总次数为 \mathcal O(2^m m)，看了眼题解似乎是使用 bfs 或 dfs 更新相邻的状态，最多有 \mathcal O(m) 种相邻状态，故时间复杂度为 \mathcal O(2^m m^2)

C

定义一个正整数为对称数当且仅当这些数的数码是中心对称，求有多少对对称数 (x,y) 满足 x+y=N,1 \leq N \leq 10^{18}

咕咕咕

D

定义进行一次操作：x \gets (x + \operatorname{f}(x)) \bmod M，其中 \operatorname{f}(x) 表示 x 在十进制下最大的数码，给定 A，求对 A 进行 N-1 次操作后的值为多少，1 \leq A < M,1 \leq N,M \leq 10^{18}

咕咕咕

Round 32 (11.21)

A

给定 n 枚硬币，第 i 枚硬币面值为 a_i，特别地：

\exists 1 \leq i \leq n,a_i=1

\forall 1 \leq i < j \leq n,a_i \mid a_j

你可以从一个可以提供无限金额的 ATM 机查询，每次给定一个正整数 X，ATM 机将以最少的硬币支付你的金额，求确认每种面值对应的颜色所需查询的最小次数

对于最大的面值，显然可以用一个极大值来区分，对于 1 到 n-1 钦定 b_i=\frac{a_{i+1}}{a_i}，显然每次询问只能分配一个数 c_i \in [0,b_i) \cap \mathbb Z，能将 i,j 区分当且仅当存在一次询问，使得 c_i \neq c_j

将 b_i 从小到大排序，对于一个 b_i \leq x 的前缀，考虑到每一项都在 [0,x) 之间的 m 元组最多有 x^m 个，故长度 > x^m 则一定不能在 m 次询问内完成

显然是可以二分或者直接枚举 m，时间复杂度 \mathcal O(n \log n)，当然 m 很小也可以直接枚举，时间复杂度 \mathcal O(n^2)

当然还可以像某大神那样直接打表找规律，答案为

\left( \sum_{i=1}^{n} \log_2 \left\lfloor \frac{i}{b_i^\prime} \right\rfloor \right) + 1

其中 \forall i \in [1,n) \cap \mathbb Z,b_i=\frac{a_{i+1}}{a_i}+1,b_n=n+1,b^\prime 为 b 从小到大排序后

正确性待证，时间复杂度还是 \mathcal O(n \log n)，瓶颈在于排序

B

有 n 只狼，第 i 只狼初始在坐标 (x_i,y_i)，每次可以移动到 (x-1,y),(x+1,y),(x,y-1),(x,y+1) 之一，求在 m 轮移动后，移动到了同一网格顶点的方案数，答案对 10^9+7 取模，0 \leq |x_i|,|y_i|,m \leq 10^5

没看懂题解在干嘛

套路地，看到这种既有 x 又有 y 的就像给拆开维度分开计算，但对于原坐标系上还是太困难了

考虑旋转坐标轴，将 (x,y) 变成 (x+y,x-y)，那么每次移动就会变成 (x \plusmn 1,y \plusmn 1)，那这样就可以拆成 x,y 两维分开计算

钦定所有狼最终走到坐标 (x^\prime,y^\prime)，对于第 i 只狼，假设从 (x_i,y_i) \to (x^\prime,y^\prime) 移动了 k 次，先看 x_i \to x^\prime，那么就移动了 i 次 +1，k-i-x_i 次 -1，故 i-(k-i-x_i)=x^\prime，化简得 i=\frac{x^\prime-x_i+k}{2}，方案数为 k \choose \frac{x^\prime-x_i+k}{2}

同理可得 y_i \to y^\prime 的方案数为 k \choose \frac{y^\prime-y_i+k}{2}，那么所有狼移动的方案数为：

\sum_{x^\prime} \sum_{y^\prime} \prod_{i=1}^{n} {k \choose \frac{x^\prime-x_i+k}{2}} {k \choose \frac{y^\prime-y_i+k}{2}}

维度拆开处理，将乘式前移，得：

\left(\sum_{x^\prime} \prod_{i=1}^{n} {k \choose \frac{x^\prime-x_i+k}{2}} \right) \left(\sum_{y^\prime} \prod_{i=1}^{n} {k \choose \frac{y^\prime-y_i+k}{2}} \right)

时间复杂度 \mathcal O(nV)，其中 V 为 x^\prime,y^\prime 枚举的值域，通常为 4 \times 10^5 即 [-2 \times 10^5,2 \times 10^5]

C

洛谷 P11340 「COI 2019」TENIS

咕咕咕

D

定义一个正整数 n 是半完全幂，当且仅当存在正整数 a \geq 1,b>1 \text{ 和 } c>1，使得 a<b \text{ 且 } n=a \cdot b^c，给定正整数 L,R 求区间 [L,R] 中的半完全幂数量，1 \leq L \leq R \leq 8 \times 10^{16}

咕咕咕

Round 33 (11.22)

A

给定参数 a,b，定义 \operatorname{f}(x)=(x \oplus a)-b，其中 \oplus 为按位或，给定长度为 n 的序列 x，q 次询问，每次给定 a,b，求问是否存在一个 i \in [1,n)，满足 \operatorname{f}(x_i) \times \operatorname{f}(x_{i+1}) \leq 0，无解输出 -1

钦定 x \oplus a 最小和最大两个位置 p_1,p_2，那么无解只需转换为 \operatorname{f}(p_1) \times \operatorname{f}(p_2) > 0

那么剩下考虑分治求解，令 p_1,p_2 的中点为 mid，由 \operatorname{f}(p_1),\operatorname{f}(p_2) 异号得 \operatorname{f}(p_1),\operatorname{f}(mid) 和 \operatorname{f}(mid),\operatorname{f}(p_2) 必有一对异号，每次向着异号的那一半递归求解即可，时间复杂度 \mathcal O(\log n)

不难发现，求解 x \oplus a 最小和最大两个位置 p_1,p_2 可以使用 Trie 树，时间复杂度 \mathcal O((n+q)(\log n + \log V))

Fun Fact：最大点时限 4s，标程跑了 3s

B

咕咕咕

C

咕咕咕

D

咕咕咕

Round 34 (11.23)

A

给定一个长度为 n 的序列 a，q 次操作，每次操作分为两种：

1 x s t 给定非负整数 x 和两个正整数 s,t，对于每一个大于等于 x 的数先加 s 后乘 t，即 \forall a_v \geq x,a_v \gets t(a_v+s)

2 x s t 给定非负整数 x 和两个正整数 s,t，对于每一个小于等于 x 的数先减 s 后除以 t，并向零截断，即 \forall a_v \leq x,a_v \gets \operatorname{trunc}^\dag(\frac{a_v-s}{t})

求 q 次操作后序列 a 中有多少个数在区间 [L,R] 之间，即 L \leq a_i \leq R_i
\dag$：其中 $\operatorname{trunc}(y)$ 表示向零截断 $y$ 得到的整数，即舍弃小数部分，例如 $\operatorname{trunc}(11.4)=11,\operatorname{trunc}(-51.4)=-51

咕咕咕

B

咕咕咕

C

咕咕咕

D

咕咕咕

Round 35 (11.26)

GJ 数据有点水了

A

AT_abc245_d Polynomial division

有三个关于 x 的多项式 F(x),G(x),H(x)，钦定它们的长度分别为 N,M,K 令
\begin{aligned} F(x) &=a_0+a_1x+a_2x^2+\dots+a_{N-1}x^{N-1} \\ G(x) &=b_0+b_1x+b_2x^2+\dots+b_{M-1}x^{M-1} \\ H(x) &=c_0+c_1x+c_2x^2+\dots+c_{K-1}x^{K-1} \\ \end{aligned}
给定 M,K 以及 G(x),H(x) 的各项系数 b_{0 \dots M-1},c_{0 \dots K-1}，求 F(x) 的长度 N 以及各项系数 a_{0 \dots N-1}，M,K \leq 2 \times 10^3

大除法秒了，时间复杂度 \mathcal O(MK)

赛时代码：

#include<bits/stdc++.h>
#define il inline
using namespace std;
const int N=2e3+5;
int n,m,k,a[N],b[N],c[N];
template <typename T>
il void read(T &x)
{
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    x*=f;
}
int main()
{
    freopen("poly.in","r",stdin);
    freopen("poly.out","w",stdout);
    read(m);for(int i=1;i<=m;i++) read(b[i]);reverse(b+1,b+1+m);
    read(k);for(int i=1;i<=k;i++) read(c[i]);reverse(c+1,c+1+k);
    n=k-m+1;
    for(int i=1;i<=n;i++)
    {
        int tmp=c[i]/b[1];
        a[i]=tmp;
        for(int j=1;j<=m;j++)
            c[i+j-1]-=tmp*b[j];
    }
    printf("%d\n",n);
    for(int i=n;i;i--) printf("%d ",a[i]);
    return 0;
}

B

CF510D Fox And Jumping

给出 n 个撑杆，分别有 v_i 和 c_i。在一个无限长的一维网格，你可以选择花 c_i 的钱来购买撑杆 i 从此以后可以向左或向右跳 v_i 个单位。问你至少花多少元钱才能够跳到网格上全部位置。若不行，输出 -1。1 \leq n \leq 300,1 \leq v_i \leq 10^9，多测

赛时并没有跟题解写同一种做法

转换一下题意就会发现选出的 m 个杆必须要满足 \gcd \lbrace v_1,v_2,\dots,v_m \rbrace=1

n\leq 20
考虑指数级暴力，枚举每一根杆是否选择，时间复杂度 \mathcal O(T2^n)，期望得分 \texttt{40pts}
特殊性质 A：v_i \leq 30

考虑 01 背包 dp，f_x 表示选出的杆的最大公因数为 x 花费的最小值，枚举每一个 v_i 和 j，转移方程为 \forall 1 \leq i \leq n,f_{\gcd \lbrace v_i,j\rbrace}=\min_{j=1}^{v_{max}} \lbrace f_{\gcd \lbrace v_i,j\rbrace},f_j+c_i \rbrace，答案即为 f_1 时间复杂度 \mathcal O(T n v_{max})，其中 v_{max}=30，期望得分 \texttt{+20pts}
特殊性质 B：c_i=1

这档部分分笔者真不会，可能留给爆搜剪枝，但是这一部分有道原题 CF1043F Make It One，期望得分 \texttt{+20pts}
n \leq 300
话说回来这部分完全是从特殊性质 A 推来的，仍然是考虑 01 背包 dp，只不过将 f 数组换成用 map 来维护，转移方程为 \forall 1 \leq i \leq n,f_{\gcd \lbrace v_i,j\rbrace}=\min_{j \in S} \lbrace f_{\gcd \lbrace v_i,j\rbrace},f_j+c_i \rbrace，其中 S 为所有可以得到的最大公因数所组成集合，答案仍是 f_1 对于每个 v_i，最多只会有约 \log V 个因数，每次与原有的值进行 \gcd 操作，最多只会产生 \mathcal O(\log V) 的贡献，那么 n 个数最多只会产生 \mathcal O(n \log V) 个不同的质因数故时间复杂度 \mathcal O(T n^2 \log n\log V)，其中 V 为值域大小，n \log V 为状态数，\log n 为 map 查询的复杂度，若使用 unordered_map 可以使复杂度变成 \mathcal O(T n^2 \log V)，不过会带有较大常数，期望得分 \texttt{100pts} 题解做法：其实不难发现 10^9 以内的数，其不同的质因子最多只有 9 个，故状压可将复杂度降至 \mathcal O(T 2^9 n^2)

赛时代码（时间复杂度 \mathcal O(T n^2 \log n \log V) 的那个）：

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define il inline
using namespace std;
const int N=1e5+5,INF=0x3f3f3f3f;
int T,n,maxv,G,v[N],c[N];
int gcd(int a,int b)
{
    return !b?a:gcd(b,a%b);
}
map<int,int> dp;
void solve()
{
    dp.clear();
    for(int i=1;i<=n;i++)
        if(!dp[v[i]]) dp[v[i]]=c[i];
            else dp[v[i]]=min(dp[v[i]],c[i]);
    map<int,int>::iterator it;
    for(int i=1;i<=n;i++)
        for(it=dp.begin();it!=dp.end();it++)
        {
            int G=gcd(v[i],it->first);
            if(!dp[G]) dp[G]=it->second+c[i];
            else dp[G]=min(dp[G],it->second+c[i]);
        }
    printf("%d\n",!dp[1]?-1:dp[1]);
}
template <typename T>
il void read(T &x)
{
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    x*=f;
}
int main()
{
    freopen("jump.in","r",stdin);
    freopen("jump.out","w",stdout);
    read(T);
    while(T--)
    {
        read(n),G=0;
        for(int i=1;i<=n;i++)
            read(v[i]),G=gcd(G,v[i]);
        for(int i=1;i<=n;i++) read(c[i]);
        if(G^1) puts("-1");
            else solve();
    }
    return 0;
}

C

CF1553I Stairs

咕咕咕

D

咕咕咕

Round 36 (11.27)

A

给定一个大小为 n \times m 的地图，每次可以上下左右移动一格，花费 1 个单位的时间，也可以花费 t 个单位的时间移动到距离 ^\dag 该点不超过 k 的任意一个点，有障碍，求起点到终点花费的最短时间，1 \leq n,m \leq 2 \times 10^3,1 \leq k \leq 8
^\dag$ 上文的距离指的是曼哈顿距离，即两点 $(x_1,y_1),(x_2,y_2)$ 间的距离为 $|x_2-x_1|-|y_2-y_1|

很自然的想到用 Dijkstra 或者 bfs 求解

使用普通的 bfs / Dijkstra + 优先队列求解，时间复杂度为 \mathcal O(n m k^2 \log)，可能卡不过去

使用普通的无优化 bfs / Dijkstra 求解，时间复杂度为 \mathcal O(n m k^2)，注意特判 t<k 的情况

看了眼题解用了两个普通队列，应该是类似于 01 bfs 的思想，时间复杂度 \mathcal O(n m k^2)

剩下两个时间复杂度分别为 \mathcal O(n m k\log) 和 \mathcal O(n m k) 应该是对于花费 t 的代价只保留走 k 格，但是未知是否同样要特判 t<k 以及做法的正确性

究竟 \log 后面要套什么容我再想想，问题不是特别大，大抵是 \log (nm)

B

有一根长度为 n 的木板，第 i 段为 0 表示破损，1 表示正常，一个毛毛虫玩具，身体长度为 a，共 b 只脚，初始身体和脚都在最左边，每次可以：

将某一只脚移动若干距离，需要保证落脚点不能是破损的木板，同一地方不能有多只脚且不能改变脚的相对顺序

将身体移动若干距离，需要保证移动完之后所有脚都在身体下方

上述移动方式均花费 1 的代价，求身体和脚都移动到最右边的最小花费，无法完成输出 IMPOSSIBLE，1 \leq b \leq a \leq n \leq 3 \times 10^6

模拟贪心，容易发现:

身体能移动尽量往前移
脚能移动尽量往前移
身体不能移动时等脚从右到左依次移动玩再移动

随便开队列维护一下身体下方前 b 个非破损的地方，时间复杂度 \mathcal O(n)

C

咕咕咕

D

AT_arc063_d [ARC063F] すぬけ君の塗り絵 2

咕咕咕

Round 37 (11.28)

A

P6189 [NOI Online #1 入门组] 跑步 / 弱化版：P10955 正整数拆分

给定一个正整数 n，求其划分成若干个正整数之和的方案数，答案对 10^9+9 取模，1 \leq n \leq 10^5

未知，赛时用 \mathcal O(n^2) 的完全背包冲过去了

正解考虑分块：

当 x \leq \sqrt n 时，考虑用完全背包算法，时间复杂度 \mathcal O(n \sqrt n)
当 x > \sqrt n 时，考虑如下两种操作
- 在序列头加 1 个 1
- 给当前序列每一个数加 1
定义 dp_{i,j} 为 i 个元素，和为 j 的方案数，则
dp_{i,j}=dp_{i-1,j-1}+dp_{i,j-i}
这一部分时间复杂度 \mathcal O(n \sqrt n)

统计答案的时候将两部分的方案数相乘即可，总时间复杂度仍是 \mathcal O(n \sqrt n)

B

AT_nikkei2019_2_qual_d Shortest Path on a Line

有 n 个点，m 个区间，第 i 个区间为 [L_i,R_i]，可以花费 W_i 的代价在该区间中任意的 \forall L_i \leq i,j \leq R_i 的 (i,j) 连边，求点 1 到点 n 的最短路，1 \leq n,m \leq 3 \times 10^5

惊奇的发现题解区居然全是建图跑最短路，这怎么行，所以这一篇题解并没有跑任何最短路，而是使用了线段树优化 DP。

考虑将建边区间按右端点从小到大排序，每次以右端点为枚举编号，记作 x ，发现只会从 [1,x-1] 中的点转移过来，故这样对区间排序后不会存在后效性，故可以开始规划 DP。

将区间从小到大排序后，记第 i 个区间为 [L_i,R_i]，dp_x 表示从点 1 出发到达点 x 的最短距离，则

dp_{R_i}= \begin{cases} \min_{j=L_i}^{R_i-1} dp_j+W_i &, R_i \geq 2 \\ 0 &, R_i=1 \\ \end{cases}

这样做的时间复杂度为 \mathcal O(mn+m \log m)，那么就可以考虑优化一下复杂度

观察到 dp_{R_i} 需要快速查询 dp_{L_i,\dots,R_i-1} 的最小值，并且需要更新 dp_{R_i} 的值，故可以使用线段树区间查询最小值，单点修改即可，时间复杂度 \mathcal O(m \log m + m \log n)，其中 m \log m 为排序的时间复杂度，\log n 为线段树单次操作的时间复杂度，细节见代码

#include<bits/stdc++.h>
#define il inline
#define ls u<<1
#define rs u<<1|1
#define int long long
using namespace std;
const int N=3e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,m;
struct dat
{
    int L,R,W;
}a[N];
struct SGT
{
    int t[N<<2];
    void push_up(int u)
    {
        t[u]=min(t[ls],t[rs]);
    }
    void build(int u,int l,int r)
    {
        if(l==r) return t[u]=(l==1)?0:INF,void();
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        push_up(u);
    }
    void update(int u,int l,int r,int x,int k)
    {
        if(x==l&&r==x) return t[u]=k,void();
        int mid=(l+r)>>1;
        if(x<=mid) update(ls,l,mid,x,k);
            else update(rs,mid+1,r,x,k);
        push_up(u);
    }
    int query(int u,int l,int r,int x,int y)
    {
        if(x<=l&&r<=y) return t[u];
        int mid=(l+r)>>1,res=INF;
        if(x<=mid) res=min(res,query(ls,l,mid,x,y));
        if(y>mid) res=min(res,query(rs,mid+1,r,x,y));
        return res;
    }
}T;
template <typename T>
il void read(T &x)
{
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    x*=f;
}
signed main()
{
    freopen("city.in","r",stdin);
    freopen("city.out","w",stdout);
    read(n),read(m);
    T.build(1,1,n);
    for(int i=1;i<=m;i++)
        read(a[i].L),read(a[i].R),read(a[i].W);
    sort(a+1,a+1+m,[](dat a,dat b){return a.R<b.R;});
    for(int i=1;i<=m;i++)
    {
        if(a[i].L==a[i].R) continue;
        int pre=T.query(1,1,n,a[i].L,a[i].R-1);
        int now=T.query(1,1,n,a[i].R,a[i].R);
        if(pre+a[i].W<now) T.update(1,1,n,a[i].R,pre+a[i].W);
    }
    int ans=T.query(1,1,n,n,n);
    printf("%lld",ans==INF?-1:ans);
    return 0;
}

C

AT_arc069_d [ARC069F] Flags / 双倍经验：UVA1146 Now or later

有 n 个标志，需要插在一条直线上，第 i 个旗子可以选择插在 x_i 或者 y_i，最大化两旗子间的最小距离，1 \leq n \leq 10^4

考虑二分答案，二分一个距离 mid 作为两点间的最大距离，显然可将每个旗子的 x_i,y_i 拆成 01 状态表示其取或者不取：

x_i=1 \lor y_i=1 \implies x_i=0 \to y_i=1 \land x_i=1 \to y_i=0

使用 2-SAT 求解即可

但是这样连边是 \mathcal O(n^2) 的，考虑线段树优化建图

不难发现，若 x_i=1，则有区间 [x_i-mid,x-1]=0,[x+1,x_i+mid]=0，点到区间连边就可以用线段树来优化建图了，y_i=1 时同理

时间复杂度 \mathcal O(n \log n \log V)，其中 V 为 x_i,y_i 的值域，\log V 为二分的时间复杂度

D

有一棵含有 n 个结点的树，有两个人 Blice 和 Aob 要在上面进行一场游戏

指定一个起点 u，Blice 先手，Aob 后手，每次移动的距离需要大于上一次的，不能重复移动到同一点上，第一步移动的距离不受限制，不能移动者输，问 Blice 对于树上的每一个点作为起点，是否有必赢的策略，假设 Blice 和 Aob 都绝顶聪明，1 \leq n \leq 2 \times 10^5

神秘结论题

特殊性质 A：保证树是一条链

手玩发现，当起点为链的中点时先手才会输，否则先手肯定赢
特殊性质 B：保证树是一棵菊花

显然只有起点为中心时先手才会输

从特殊到一般，大胆猜测：只有树的直径上的中点（即树的中心）作为起点先手才会输

可以证明其他情况先手必赢的策略

当后手走完后，先手一定可以找到某条直径的关于该中心的对称点走过去，而在中心时两者交换

那么直接使用 dfs 求出树的直径即可，时间复杂度 \mathcal O(n)

Round 38 (11.28)

NOIP2024 前最后一场模拟赛，祝各位 NOIP2024 考生 RP++！