你需要一棵 个节点的有根树,节点编号为 ,其中 是根节点,且对于任何非根节点 ,它的父节点的标号 要比它的标号 要小。
工厂里所有的树都是用竹子做的(可能不准确但不影响题意理解),这种竹子是有根的树,且每个节点只有一个子节点(除了叶子节点没有子节点),也就是说,它是直线形的。加工前,竹子的顶点可以随意标注。
要加工竹子为一棵树,可以进行这样的操作:选择任意一个不是根节点且父节点也不是根节点的节点 ,将它的父节点变成原先父节点的父节点即 ,而其它节点的父节点都保持不变, 的子树也不会改变。
效率是至关重要的,所以在加工出所需要的树的前提下你应当最小化操作数。现在请你构造任何最优的操作序列以生成所需要的树
注意:加工出的结果树的标签必须和所需要的树的标签一致,即根节点标签相同,其它所有具有相同标签的子节点 ,其父节点标签也应相同。
数据保证任何输入都至少有一种可行的方案,且最优操作序列最多包含 个操作。
。
CF618F Double Knapsack 做题记录
给你两个可重集 A,B,A,B 的元素个数都为 n,它们中每个元素的大小 x∈[1,n]。请你分别找出 A 的一个子集和 B$ 的一个子集,使得它们中的元素之和相等。输出方案。
1≤n≤106。
CF351E Jeff and Permutation 做题记录
给出数组 a ,你可以改变每个数的正负,求逆序对数最少是多少。
1≤n≤2000,∣ai∣≤105。
AT_arc148_d [ARC148D] mod M Game 做题记录
场上 2N 个整数, Alice,Bob 轮流取数, Alice 先手,如果最终 Alice 取出数的和取模 M 和 Bob 取出来数的和相等,那么 Bob 获胜,否则 Alice 获胜。
两个人绝对聪明,求哪个人会获胜。
- 1≤N≤2×105
- 2≤M≤109
- 0≤Ai≤M−1
0%