给定一棵无根树,有 个顶点。在这棵树上有一个顶点 ,你希望找到它。
要找到 ,你可以进行 次查询 (其中 是树中的各个顶点)。当你进行完所有查询后,你会得到 个数字 ,( 是 和 之间的最短路径上的边数)。注意,您知道哪个距离对应于哪个查询。
请你求出最小的 ,使存在这样的一些查询 ,让你总能找到唯一的一个节点 (无论 是什么)。
注意,你不需要输出这些查询。
。
CF1158C Permutation recovery 做题记录
有排列 p,令 nxti 为 pi 右侧第一个大于 pi 的数的位置,若不存在则 nxti=n+1。
现在整个 p 和 nxt 的一部分丢失了,请根据剩余的 nxt,构造出一个符合情况的 p,输出任意一解。
1≤n≤5×105。
CF1166E The LCMs Must be Large 做题记录
有一个长度为 n(n<=104)的内容未知的序列,再给 m(m<=50)个限制,每个限制会给一个位置集合 S,需要让 S 中所有位置上的数的 lcm 严格大于序列里剩下的数的 lcm,求是否存在一个这样的序列满足所有限制。存在一个序列输出
possible
,否则输出impossible
。
CF763B Timofey and rectangles 做题记录
平面上有 n 个与坐标轴平行的矩形。矩形的所有边的长度都是奇数。矩形不能相交,但它们可以互相接触。
你要让每两个接触的矩形有不同的颜色。如果可以则输出
YES
,并给出每个矩形图上的颜色(∈[1,4];如果不行输出NO
。
CF1332E Height All the Same 做题记录
最近,Alice 迷上了一款名为 Sirtet 的游戏。
在 Sirtet 中,玩家会得到一个 n×m 的网格。初始时,格 (i,j) 上码放有 ai,j 个方块。若两个格子有一条公共边,我们称这两个格子时相邻的。玩家可以进行以下两种操作:
- 在两个相邻的格子上各码上一个方块。
- 在一个格子上码上两个方块。
上述中所提到的所有方块都具有相同的高度。
玩家的目标是通过这些操作,使得所有的格子拥有同样的高度(也就是说,每个格子上堆放的方块数相同)。
然而,Alice 发现存在有某些初始局面,使得无论她采用什么策略,都无法达到目标。因此,她希望知道有多少初始局面,满足,
- 对于所有的 1≤i≤n,1≤j≤m,L≤ai,j≤R。
- 玩家可以通过执行这些操作,达到目标。
请帮助 Alice 解决这个问题。注意答案可能很大,请输出所求答案对 998244353 取模的值。
CF675C Money Transfers 做题记录
n 个整数排成一个环,每次可以选择一个 x 并把环上相邻的某两个整数其中一个加上 x,另一个减去 x。求把所有整数都变成 0 的最小操作次数。
1≤n≤105,0≤∣ai∣≤109。
CF1365F Swaps Again 做题记录
给出两个长度为 n 的数列 a,b,你需要判断能否在数次操作后使得 a 与 b 相同。
操作是指你可以选择一个 k(1≤k≤⌊2n⌋),之后交换 a 的长度为 k 的前缀和长度为 k 的后缀。
例如对于 a={1,2,3,4,5,6},选择 k=2,那么交换后会得到 {5,6,3,4,1,2}。
1≤n≤500,1≤ai,bi≤109。
CF1370E Binary Subsequence Rotation 做题记录
给定两个长度为 n 的 01 串 a 和 b,要求串 a 的任意子序列经过若干次“旋转”操作变为串 b。
对于一次“旋转操作”我们这样定义:
如果我们要旋转的序列为
c1,c2,c3,c4,c5...cn
那么旋转之后的序列为 cn,c1,c2,c3,c4...cn−1
例如对于 s=1110100
如果我们旋转的子序列的下标为 2,6,7(从1开始)
那么旋转之后的串为 1010110
求至少进行多少次“旋转”操作,能够把串 a 变成串 b
n(1≤n≤106)。
CF1419E Decryption 做题记录
给定一个正整数 n,将它的所有大于一的因数按照任意顺序排列在一个环上,你每次可以选择圈上相邻的两个数,在它们中间插入他们的最小公倍数,使得最后的环上不存在两个相邻且互质的数。你需要找到一个需要进行操作次数最少的排列。
4≤n≤109。
CF1479B2 Painting the Array II 做题记录
给定一个数组 a, 你将将 ai 染为 bi 色, 其中 b 是由你指定的一个 01 数组. 将 a 数组中被染成 0 色的数字取出来并依在 a 中出现的顺序排列, 组成数组 a(0). 同理, 将 a 数组中被染成 1 色的数字取出来并依在 a 中出现的顺序排列, 组成数组 a(1). 我们定义 seg(c) 是一个正整数, 其中 c 是一个数组, seg(c) 的值为在我们将 c 中相邻的所有相同元素合并后, c 数组的大小. 例如, seg([1,1,4,5,1,4])=∣[1,4,5,1,4]∣=5. 最小化 seg(a(0))+seg(a(1))。
1≤n≤105,1≤ai≤n。