「Macau 21 J」Colorful Tree

2023-11-08

维护一个点有颜色的树,一开始只有一个编号为 11 的节点,颜色为 CC,要求支持以下操作 qq 次:

  1. 给定 x,c,dx,c,d,添加一个编号为 n+1n+1 颜色为 cc 的节点,向点 xx 连一条长度为 dd 的边
  2. 给定 x,cx,c,将点 xx 的颜色变成 cc

在每次操作后,你都需要在树上选两个颜色不同的点并最大化他们之间最短简单路径的长度,并输出这个长度。

1q5×1051\le q\le 5 \times 10^5

2021-01-21

定义一个排列 PP 上的操作 (t,S)(t,S) 为:

  1. 有两个空序列 AABB
  2. 枚举 Si=1S_i=1 的每个 ii:如果 PiP_i 是偶数,则将其放到 AA 的末尾;否则放到 BB 的末尾;
  3. 如果 t=0t=0 则令 C=ABC=\overline{AB},否则令 C=BAC=\overline{BA}
  4. 枚举 Si=1S_i=1 的每个 ii:将 PiP_i 替换为 CC 的开头元素,删去 CC 的开头元素。

现给定排列 PP,要求使用至多 3030 次如上操作,使 PP 从小到大排序,注意你不需要最小化操作次数。

1n150001\le n\le 15000

2020-10-04

给定 nnc0nc_{0\ldots n},表示限制形如对于 0in0 \leq i \leq n 都满足 1f(i)ci1 \leq f(i) \leq c_i

其中 f(x)=i=0naixif(x) = \sum_{i=0}^{n} a_i x^i,其中 a0na_{0 \ldots n} 都是整数,即 f(x)f(x) 是一个不超过 nn 次的整系数多项式。

问满足限制的 f(x)f(x) 有多少个,答案对 998244353998244353 取模。

2020-09-17

用三元组 (a,d,n)(a,d,n) 表示长度为 nn 的递增等差正整数序列 {a,a+d,a+2da+(n1)d}\{a, a+d, a+2d \ldots a+(n-1)d\}。给定 (a,d,n)(a,d,n),要求构造 (b,e,n)(b,e,n) 满足:

  • b,e<264b,e < 2^{64},且是正整数
  • 对于所有 0i<n0 \leq i < na+ida+id 的十进制表示是 Fb+ieF_{b+ie} 的十进制表示的后 1818 位的子串(如果没有 1818 位自动补前导零)。其中 FiF_i 是指斐波那契数列的第 ii 项。

1a+(n1)d1061 \leq a+(n-1)d \leq 10^6

2020-09-15

一个大小为 nn 的集合 {ai}i=1n\{a_i\}_{i=1}^n,每次可以选择 (i,j,k)(i,j,k),若 aiaja_i \mid a_jaiaka_i \mid a_k,可以将 aka_k 删去。

求能删除最多数的删除序列数,删除序列定义为对于一个三元组 (i,j,k)(i,j,k),每次删数把 aka_k 加入到删除序列中。

1ai,n601 \leq a_i, n \leq 60,保证 aia_i 两两不同。

2020-08-31

给定一张 nn 个点的树或基环树,树上的每条边 (ui,vi,wi)(u_i, v_i, w_i) 代表 (ui,vi)(u_i, v_i) 间有 wiw_i 道路相连。

你需要统计有多少种从任意点出发的本质不同路径,使得经过所有道路恰好一次。

路径可以认为是一个从某个点出发,由经过道路编号和方向组成的序列。两条路线被认为是相同的当且仅当两序列相同,或更换起始边后两序列相同。

n,wi1000n, w_i \leq 1000