「Macau 20 K」Candy Ads

2024-03-26

主办方将在一个二维平面中投放广告。共有 nn 个广告可被投放,其中每个广告的都是左上角为 (xi,yi)(x_i,y_i)w×hw\times h 矩形且出现时间为 [li,ri][l_i,r_i]。同一时间内,任意两个被投放的广告不能有重叠面积。此外还有 mm 条限制 (ui,vi)(u_i,v_i) 表示在广告 uiu_i 和广告 viv_i 中至少选择投放一条。判断是否存在一组合法的投放方案,如果存在的话给出方案。

1n5×1041\le n\le 5\times 10^41m1051\le m\le 10^51w,h,xi,yi,li,ri20001\le w,h,x_i,y_i,l_i,r_i \le 2000

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

给定 nn{ci}i=0n\{c_{i}\}_{i=0}^n,表示 n+1n+1 条限制形如对于 f(x)f(x) 满足 1f(i)ci1 \leq f(i) \leq c_i 对于所有 0in0\le i\le n

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

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

0n60\le n\le 61ci1091\le c_i\le 10^9

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 两两不同。