「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

2023-11-06

大一新生的第一次 ICPC 区域赛。

选赛站的时候本打算咨询一下“懂行”的前辈,可惜对面迟迟不回我,就根据期中考时间胡乱选了赛站,选完才知道南京高手云集。

出发的时候已经把期望拉到最低——能稳住金牌就好。这两天虽有许多遗憾,但结果意料之外的不错,算是一个比较“华丽”的开局了(对应比赛 K 题名称——华丽收场)。

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