xcyle-medium

here

[TOC]

1. CF1609G - A Stroll Around the Matrix [Euclid]

题面

给定 $\{a_1,a_2,\cdots,a_n\}$ 和 $\{b_1,b_2,\cdots,b_m\}$，保证 $a,b$ 均凸（这里的凸定义为对于一个序列 $c$，其满足 $c_1<c_2$ 且 $c_i-c_{i-1}<c_{i+1}-c_i$），定义 $f(a,b)$ 的值为：有一个 $n\times m$ 的矩形，$(i,j)$ 的权值为 $a_i+b_j$，问从 $(1,1)$ 到 $(n,m)$ 的最短路径经过的格子权值和最小为多少

有 $q$ 次修改，每次给 $a$ 或 $b$ 的后 $k$ 位分别加上 $d,2d,\cdots,kd$，每次修改后你需要输出 $f(a,b)$

$2\le n\le100,2\le m\le10^5,1\le q\le10^5,1\le a_i,b_i\le10^{12},1\le d\le10^3$

题解

不难发现 $a$ 和 $b$ 一定一直都是凸的

考虑 $f(a,b)$ 是什么，如果我们把这两个数组差分，那么我们首先会有一个 $(n+m-1)(a_1+b_1)$ 的代价，接下来我们可以选择往哪个方向走，如果我们第 $i$ 步跨越的两个行/列差分为 $x$，那么会产生 $(n+m-1-i)x$ 的代价

因此，如果我们能够按从小到大的顺序走 $x$ 的话，一定是最优的，而由于差分数组递增，我们可以做到这一点

由于 $n$ 很小，我们可以将 $b$ 排好序，然后将 $a$ 插入到序列中，我们需要一个数据结构，支持区间加，查询第一个 $\le x$ 的数，以及查询区间和，这个可以用 平衡树/线段树+树状数组 完成

复杂度 $O(qn\log m)$

---

5. CF1617E - Christmas Chocolates [Euclid]

题面

数列 $a_1,a_2,\cdots,a_n$，定义 $f(x,y)$ 为：

你可以进行操作，一次操作可以选择一个 $k$ 使 $2^k\ge a_x$，并将 $a_x$ 变成 $2^k-a_x$

使 $a_x=a_y$ 的最小操作次数为 $f(x,y)$

对于所有 $i,j$，求 $f(a_i,a_j)$ 的最大值，输出最大值与此时的 $i,j$

$2\le n\le2\times10^5$

题解

我的做法

就硬手模。

考虑操作可逆。

我们可以发现，除非将一个数减成 0，否则这个数的 lowbit 一直不会变，我们将这些位删掉不考虑

进行两次操作相当于在这个数的最高位 1 前面任意添加一段 1，或者把最高的 1 段删掉一个前缀

转换到差分数组上相当于将第 $1$ 位反转以及第 $k$ 位翻转

那么如果 $\text{lowbit}(x)\neq\text{lowbit}(y)$，一定是将两个数都变成 0

否则，答案就是差分数组删掉 lcp 后 1 的个数之和

（是的，很抽象）

那么对于第一种情况，我们可以按 lowbit 分类，然后容易统计

对于第二种情况，我们可以对每种 lowbit 开一棵 trie，然后在树上统计

复杂度 $O(n\log a_i)$，空间复杂度 $O(n\log a_i)$

题解做法

如果 $x+y=2^k$ 那么就在 $(x,y)$ 之间连边，建出无向图

考虑对于任意 $x$，只有一个 $y$ 满足 $y<x,x+y=2^k$，所以这个图是一棵树

那么我们相当于要求这棵树上 $n$ 个点之间的最大距离，也就类似于树的直径

不难发现，这个树的深度只有 $\log a_i$

一种方法是只建 $n$ 个点到根（0） 路径上的点，这样只有 $O(n\log a_i)$ 个点，可以接受

或者用求最远点的方法求直径，算距离的时候暴力跳父亲，复杂度也是 $O(n\log a_i)$

---

9. CF1661F - Teleporters [Euclid]

题面

你有一个一维数轴，初始有 $n$ 个点，坐标为 $a_1,a_2,\cdots,a_n(1\le a_1<a_2<\cdots<a_n)$，并给定 $m\ge a_n$

如果两个点坐标分别为 $x,y$，那么你从 $x$ 走到 $y$ 需要 $(x-y)^2$ 的代价

问你最少要添加多少个点使得从 $0$ 到 $a_n$ 的最小代价 $\le m$

注：只能添加整点

$1\le n\le2\times10^5,a_i\le10^9,m\le10^{18}$

题解

如果我们加点，我们按照 $a$ 将数轴分成若干个部分，那么每个部分里加的点一定尽量平均分

令 $cal(x,k)$ 表示一个长为 $x$ 的区间分为 $k$ 个部分的最小代价

那么有一个显然的贪心，我们每次找到 $cal(x,y)-cal(x,y+1)$ 最大的区间将其加一个点，直到总代价 $\le m$

但是这样复杂度太大了。

我们考虑优化，推一下贡献式子可以发现如果 $\lfloor\frac xy\rfloor$ 一定的时候每次加一个点产生的贡献也一定

因此，我们从堆中找到一个点后，可以直接取到 $\lfloor\frac xy\rfloor$ 改变为止，这样最多只会有 $O(n\sqrt{a_i})$ 种不同的状态

总复杂度 $O(n\sqrt{a_i}\log n)$

---

11. CF1672H - Zigu Zagu [Euclid/Keter]

题面

对于一个 01 串 $s$，定义 $f(s)$ 为：

一次操作可以删掉一个 01 交替的子串，剩下两部分拼起来，$f(s)$ 为将其删空的最少操作次数

给定一个长为 $n$ 的 01 串 $a$，$q$ 次询问，每次给定 $l,r$，询问 $f(a[l:r])$

$1\le n,q\le2\times10^5$

题解

一次操作我们一定是删除一段极长的交替段，那么这个交替段两端一定满足 $a_{l-1}=a_l,a_r=a_{r+1}$，接着 $a_{l-1}$ 和 $a_{r+1}$ 会合到一起

那么我们考虑满足 $a_i=a_{i+1}$ 的数量 $x$，如果 $a_{l-1}=a_{r+1}$，进行 $[l,r]$ 操作会让 $x$ 减 $1$，否则会让 $x$ 减 $2$

也就是说，我们把所有满足 $a_i=a_{i+1}$ 的都提出来，如果有 $=0$ 和 $=1$ 的相邻，那我们可以把这两个同时消掉，否则我们只能对每个单独消

我们发现，如果同时存在 $=0$ 的 $=1$ 的，那么必定存在一个位置 $=0$ 的和 $=1$ 的相邻，因此答案是 $[l,r]$ 内相邻的 0 和相邻的 1 的个数的最大值

复杂度 $O(n+q)$

---

12. CF1673F - Anti-Theft Road Planning [Euclid]

题面

交互题。

给定 $n\times n$ 的矩形，$(i,j)$ 与 $(i+1,j)$ 之间有无向边相连，$(i,j)$ 与 $(i,j+1)$ 之间有边相连，你需要给每条边赋一个非负权值，使得边权总和不超过 $48000$

接下来，有一个人在这个矩形上走路，初始在 $(1,1)$，这个人会移动 $k$ 次（移动的过程会影响之后的询问），每次会经过若干条边，交互库会给你这些边的边权异或和，你需要输出这个人到了哪个点，注意询问之间不互相独立

$2\le n\le32,1\le k\le1024$

题解

我们从 $0$ 开始数数。

有一种显然的想法是我们将 $(u,v)$ 与 $(w,x)$ 之间的边权设为 $(un+v)\oplus(wn+x)$，这样一条路径的权值一定是起点异或终点，但是这样边权和超过了 $48000$

我们不妨考虑一下优化，一种优化的方式是将 $un+v$ 替换为一个 $0\sim n^2-1$ 的排列 $id_{u,v}$

边权和只和相邻数的异或和有关，我们需要让这个数字尽量小，不难联想到格雷码

我们令 $id_{u,v}$ 后 $5$ 位为 $u$ 的格雷码，前 $5$ 位为 $v$ 的格雷码，但是这样前 $5$ 位产生的代价仍然过大

因此，我们令 $id_{u,v}$ 的 $1,3,5,7,9$ 位为 $u$ 的格雷码，$0,2,4,6,8$ 位为 $v$ 的格雷码，这样估计下来是：

$32(2^4\times(2^0+2^1)+2^3\times(2^2+2^3)+2^2\times(2^4+2^5)+2^1\times(2^6+2^7)+2^0\times(2^8+2^9))=47616$

复杂度 $O(n^2)$

---

13. Lenient Vertex Cover [Euclid]

题面

一张 $n$ 个点，$m$ 条边的无向图，求一个点集，使得任意一条边都有一个端点在点集中，并且最多只有一条边两个端点都在点集中

给出构造或返回无解

$1\le n,m\le10^6$

题解

CF19E。

---

14. CF1865C - Bring Balance [Euclid/Keter]

题面

给定一个由 $n$ 个左括号和 $n$ 个右括号组成的括号序列 $s$，每次操作可以将其中的一个子串 reverse，问最少进行多少次操作使得 $s$ 变为合法括号串

$1\le n\le10^5$

题解

我不理解，暂且认定为魔法。

你通过魔法得知了一种操作方式，这种操作方式叫：找到前缀和最大的下标 $mx$，操作区间 $[1,mx],[mx+1,2n]$

这种操作方式的正确性是可以证明的：设前缀和为 $a_i$，对于 $[1,mx]$ 中的位置 $i$，新的前缀和为 $a_{mx}-a_{i-1}$，这是非负的；对于 $[mx+1,2n]$ 中的位置 $i$，新的前缀和为 $a_{mx}+a_{n+1}-a_{i-1}=a_{mx}-a_{i-1}$，这是非负的，因此操作方式成立

那么步数最多为 $2$，我们需要判断步数是否为 $0$ 或 $1$

$0$ 是好判的，考虑怎么判 $1$

设我们唯一一步操作的是 $[L,R]$，显然 $[L,R]$ 一定要包含所有前缀和为负的下标

我们设 $l_0$ 表示第一个前缀和为负的下标，$r_0$ 表示最后一个前缀和为负的下标

令 $L_1$ 表示 $[0,l_0-1]$ 中前缀和最大的下标，$R_1$ 表示 $[r_0+1,2n]$ 中前缀和最大的下标

我们可以说明：如果存在 $(L,R]$ 操作一步可行，那么 $(L_1,R_1]$ 也一定可以

根据 $l_0,r_0$ 的定义，未在操作区间内的点一定满足限制

根据已知，我们有 $a_R-a_{i-1}+a_L\ge0(LR$，那么根据 $l_0,r_0$ 的定义一定有 $a_i\ge0$，根据 $L_1,R_1$ 的定义一定有 $a_{L_1}-a_{i-1}\ge0$ 或 $a_{R_1}-a_{i-1}\ge0$，而若 $L<i\le R$，那么由于 $a_{R_1}\ge a_R,a_{l_1}\ge a_L$，一定满足 $a_{R_1}-a_{i-1}+a_{L_1}\ge0$，得证。

判断输出即可，复杂度 $O(n)$

---

15. CF1687C - Sanae and Giant Robot [Euclid]

题面

给定长为 $n$ 的序列 $a$ 和 $b$，以及 $m$ 个区间 $[l_i,r_i]$，你需要进行若干次操作，将 $a$ 变为 $b$，每次操作选择一个 $[l_i,r_i]$，使得这段区间内 $a$ 的和等于 $b$ 的和，然后将 $a$ 中这段区间替换为 $b$ 中这段区间

问是否可以完成

$2\le n\le2\times10^5,1\le m\le2\times10^5$

题解

令 $c_i$ 为 $a_i-b_i$ 的前缀和，那么题目转化为有 $m$ 个数对 $(x_i,y_i)$，每次操作如果 $c_{x_i}=c_{y_i}$，那么我们可以把 $[x_i,y_i]$ 内的所有 $c$ 全部赋值为 $c_{x_i}$

由于我们最后需要全变为 $0$，所以每步操作一定是选择一个两边都是 $0$ 的数对，不难发现这样如果有解则一定能够找到解

那么我们考虑快速模拟这个过程，我们用一个队列依次考虑值变为 $0$ 的下标，初始把所有值为 $0$ 的下标入队

找到一个下标时，我们找有一个数与其相等的所有数对，判断是否能够操作，如果能，我们直接用暴力+并查集更新 $c$ 的值

复杂度 $O(m\alpha(n))$

---