CF1695D2 Tree Queries (Hard Version) 做题记录

给定一棵无根树,有 nn 个顶点。在这棵树上有一个顶点 xx,你希望找到它。

要找到 xx,你可以进行 kk 次查询 v1,v2,vkv_1 , v_2 ,\ldots , v_k (其中 viv_i 是树中的各个顶点)。当你进行完所有查询后,你会得到 kk 个数字 d1,d2,dkd_1 , d_2 ,\ldots , d_k ,(did_iviv_ixx 之间的最短路径上的边数)。注意,您知道哪个距离对应于哪个查询。

请你求出最小的 kk ,使存在这样的一些查询 v1,v2,vkv_1 , v_2 ,\ldots , v_k ,让你总能找到唯一的一个节点 xx (无论 xx 是什么)。

注意,你不需要输出这些查询。

1n2×1051 \le n \le 2\times 10^5

阅读全文 »

CF1158C Permutation recovery 做题记录

有排列 pp,令 nxtinxt_ipip_i 右侧第一个大于 pip_i 的数的位置,若不存在则 nxti=n+1nxt_i=n+1

现在整个 ppnxtnxt 的一部分丢失了,请根据剩余的 nxtnxt,构造出一个符合情况的 pp,输出任意一解。

1n5×1051\le n\le 5\times 10^5

阅读全文 »

CF1166E The LCMs Must be Large 做题记录

有一个长度为 nnn<=104n<=10^4)的内容未知的序列,再给 mmm<=50m<=50)个限制,每个限制会给一个位置集合 SS,需要让 SS 中所有位置上的数的 lcm\operatorname{lcm} 严格大于序列里剩下的数的 lcm\operatorname{lcm},求是否存在一个这样的序列满足所有限制。存在一个序列输出 possible,否则输出 impossible

阅读全文 »

CF763B Timofey and rectangles 做题记录

平面上有 nn 个与坐标轴平行的矩形。矩形的所有边的长度都是奇数。矩形不能相交,但它们可以互相接触。

你要让每两个接触的矩形有不同的颜色。如果可以则输出 YES,并给出每个矩形图上的颜色([1,4]\in[1,4];如果不行输出NO

阅读全文 »

CF1332E Height All the Same 做题记录

最近,Alice 迷上了一款名为 Sirtet 的游戏。

在 Sirtet 中,玩家会得到一个 n×mn \times m 的网格。初始时,格 (i,j)(i, j) 上码放有 ai,ja_{i, j} 个方块。若两个格子有一条公共边,我们称这两个格子时相邻的。玩家可以进行以下两种操作:

  • 在两个相邻的格子上各码上一个方块。
  • 在一个格子上码上两个方块。

上述中所提到的所有方块都具有相同的高度。

玩家的目标是通过这些操作,使得所有的格子拥有同样的高度(也就是说,每个格子上堆放的方块数相同)。

然而,Alice 发现存在有某些初始局面,使得无论她采用什么策略,都无法达到目标。因此,她希望知道有多少初始局面,满足,

  • 对于所有的 1in1 \le i \le n1jm1 \le j \le mLai,jRL \le a_{i, j} \le R
  • 玩家可以通过执行这些操作,达到目标。

请帮助 Alice 解决这个问题。注意答案可能很大,请输出所求答案对 998244353998244353 取模的值。

阅读全文 »

CF675C Money Transfers 做题记录

nn 个整数排成一个环,每次可以选择一个 xx 并把环上相邻的某两个整数其中一个加上 xx,另一个减去 xx。求把所有整数都变成 00 的最小操作次数。

1n1051\le n\le 10^50ai1090\le |a_i|\le 10^9

阅读全文 »

CF1365F Swaps Again 做题记录

给出两个长度为 nn 的数列 a,ba,b,你需要判断能否在数次操作后使得 aabb 相同。

操作是指你可以选择一个 k(1kn2)k(1\le k\le\lfloor\frac n2\rfloor),之后交换 aa 的长度为 kk 的前缀和长度为 kk 的后缀。

例如对于 a={1,2,3,4,5,6}a=\{1,2,3,4,5,6\},选择 k=2k=2,那么交换后会得到 {5,6,3,4,1,2}\{5,6,3,4,1,2\}

1n5001\le n\le5001ai,bi1091\le a_i,b_i\le10^9

阅读全文 »

CF1370E Binary Subsequence Rotation 做题记录

给定两个长度为 nn0101aabb,要求串 aa 的任意子序列经过若干次“旋转”操作变为串 bb

对于一次“旋转操作”我们这样定义:

如果我们要旋转的序列为

c1,c2,c3,c4,c5...cnc_1,c_2,c_3,c_4,c_5...c_n

那么旋转之后的序列为 cn,c1,c2,c3,c4...cn1c_n,c_1,c_2,c_3,c_4...c_{n-1}

例如对于 s=1110100s=1110100

如果我们旋转的子序列的下标为 2,6,7{2,6,7}(从1开始)

那么旋转之后的串为 10101101010110

求至少进行多少次“旋转”操作,能够把串 aa 变成串 bb

n(1n106)n(1\le n\le 10^6)

阅读全文 »

CF1419E Decryption 做题记录

给定一个正整数 nn,将它的所有大于一的因数按照任意顺序排列在一个环上,你每次可以选择圈上相邻的两个数,在它们中间插入他们的最小公倍数,使得最后的环上不存在两个相邻且互质的数。你需要找到一个需要进行操作次数最少的排列。

4n1094 \le n \le 10^9

阅读全文 »

CF1479B2 Painting the Array II 做题记录

给定一个数组 aa, 你将将 aia_i 染为 bib_i 色, 其中 bb 是由你指定的一个 01 数组. 将 aa 数组中被染成 0 色的数字取出来并依在 aa 中出现的顺序排列, 组成数组 a(0)a^{(0)}. 同理, 将 aa 数组中被染成 1 色的数字取出来并依在 aa 中出现的顺序排列, 组成数组 a(1)a^{(1)}. 我们定义 seg(c)seg(c) 是一个正整数, 其中 cc 是一个数组, seg(c)seg(c) 的值为在我们将 cc 中相邻的所有相同元素合并后, cc 数组的大小. 例如, seg([1,1,4,5,1,4])=[1,4,5,1,4]=5seg([1, 1, 4, 5, 1, 4]) = |[1, 4, 5, 1, 4]|=5. 最小化 seg(a(0))+seg(a(1))seg(a^{(0)})+seg(a^{(1)})
1n1051\leq n\leq 10^51ain1\le a_i\le n

阅读全文 »