CF1225F Tree Factory 做题记录

你需要一棵 nn 个节点的有根树,节点编号为 [0,1,...,n1][0,1,...,n-1],其中 00 是根节点,且对于任何非根节点 vv,它的父节点的标号 p(v)p(v) 要比它的标号 vv 要小。

工厂里所有的树都是用竹子做的(可能不准确但不影响题意理解),这种竹子是有根的树,且每个节点只有一个子节点(除了叶子节点没有子节点),也就是说,它是直线形的。加工前,竹子的顶点可以随意标注。

要加工竹子为一棵树,可以进行这样的操作:选择任意一个不是根节点且父节点也不是根节点的节点 vv,将它的父节点变成原先父节点的父节点即 p(p(v))p(p(v)),而其它节点的父节点都保持不变,vv 的子树也不会改变。

效率是至关重要的,所以在加工出所需要的树的前提下你应当最小化操作数。现在请你构造任何最优的操作序列以生成所需要的树

注意:加工出的结果树的标签必须和所需要的树的标签一致,即根节点标签相同,其它所有具有相同标签的子节点 vv,其父节点标签p(v)p(v)也应相同。

数据保证任何输入都至少有一种可行的方案,且最优操作序列最多包含 10610^6 个操作。

2n1052\le n\le 10^5

阅读全文 »

CF794G Replace All 做题记录

给两个包含 A,B,? 的串,? 可以填 AB,求所有情况下下面这个东西的和,对 109+710^9+7 取模:

  • 统计有多少对长度 n\le n0101(S,T)(S,T) 使得把所有 A 换成 SSB 换成 TT 后两个串相等;

两个串的长度 3×105\le 3\times 10^5
为了方便,设 a=n,b=m|a|=n,|b|=m,原来的 nn 设为 kk

阅读全文 »

CF618F Double Knapsack 做题记录

给你两个可重集 A,BA, BA,BA, B 的元素个数都为 nn,它们中每个元素的大小 x[1,n]x\in [1,n]。请你分别找出 AA 的一个子集和 B$ 的一个子集,使得它们中的元素之和相等。输出方案。

1n1061\le n\leq 10^6

阅读全文 »

AT_arc148_d [ARC148D] mod M Game 做题记录

场上 2N2N 个整数, Alice,Bob 轮流取数, Alice 先手,如果最终 Alice 取出数的和取模 MM 和 Bob 取出来数的和相等,那么 Bob 获胜,否则 Alice 获胜。

两个人绝对聪明,求哪个人会获胜。

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 2M1092 \leq M \leq 10^9
  • 0AiM10 \leq A_i \leq M - 1
阅读全文 »