Description 有一个供 KKK 个玩家玩的棋盘游戏。该游戏的棋盘由 NNN 个编号从 1 到 NNN 的单元格和 MMM 条编号从 1 到 MMM 的路径组成，其中路径 jjj（1≤j≤M1 ≤ j ≤ M1≤j≤M）双向连接着单元格 UjU_jUj​ 和 VjV_jVj​。 棋盘上有两种类型的单元格：重新激活单元格和停止单元格。 这些信息由长度为 NNN 的字符串 SSS 给出，SS

Description 这是一道交互题。 Tomislav 在睡梦中想到了一个问题：给定两棵大小为 NNN 的树，树上的节点按 1∼N1\sim N1∼N 分别编号，树则分别编号为树 111，树 222，树有边权，但是边权被隐藏了起来。 Tomislav 需要向交互库提供一个大小为 KKK 的编号的子集 SSS，在选择了这个集合后，小 C 可以问 QQQ 个格式为 (a,b)(a,b)(a,b)

Description 给定一个长度为 nnn 的整数序列 a1∼ana_1\sim a_na1​∼an​，其中的元素两两互不相等。 有 qqq 个询问，每个询问给定一个区间 [l,r][l,r][l,r]，你要选择三个下标 i,j,k∈[l,r]i,j,k\in[l,r]i,j,k∈[l,r] 满足 i≠j,j≠k,k≠ii\neq j,j\neq k,k\neq ii=j,j=k,k=

用处：树上/序列的计数/最优化 dp 的优化方法，要求支持单点修改和可合并性。 做法：用矩阵维护 dp，同时在树上树链剖分，修改时跳重链时用线段树维护矩阵，由于轻儿子只会跳 O(log⁡n)O(\log n)O(logn) 次，所以轻儿子暴力跳即可。 12345678910111213141516171819202122232425262728293031323334353637383940414

Description 今天是 YQH 的生日，她得到了一个 1∼n1\sim n1∼n 的排列作为礼物。 YQH 是一个有强迫症的女孩子，她希望把这个排列从小到大排序，具体的，她可以进行这样的操作： 把 [1,n][1,n][1,n] 分成若干个区间，假如是 mmm 段，依次为 [l1,r1],[l2,r2],…,[lm,rm][l_1,r_1],[l_2,r_2],\dots,[l_m,

Description 给 nnn 点 mmm 边的无向图，LLL，sss，ttt。 修改 mmm 条边中边为 000 的边，使满足 s,ts,ts,t 的最短路长度是 LLL，且输出答案的时候边为 000 的边的权值必须在 [1,1018][1,10^{18}][1,1018] 内。 Solution 考虑怎么判有无解。 容易发现将所有未知边边权设为 101810^{18}1018，如果最短

Description 给定一张 nnn 个点的无向图，初始没有边。 依次加入 mmm 条带权的边，每次加入后询问是否存在一个边集，满足每个点的度数均为奇数。 若存在，则还需要最小化边集中的最大边权。 n≤105n \le 10^5n≤105，m≤3×105m \le 3 \times 10^5m≤3×105。 Solution 考虑给定一个图，怎么判断这个图存在一个边集满足条件。 结论是这个

Description 你用销售机器人的利润雇佣了一名助手，现在你准备好去拿走装有 CEOI 奖章的保险箱了。 保险箱位于一所由 nnn 个房间所组成的大学建筑内，这些房间由 n−1n-1n−1 扇门连接。每个房间都可以从其他任何房间到达，且每个房间最多与 333 扇门相连。 你和你的助手都有描述建筑物内房间相连情况的平面图，但是你们两个各自拥有的平面图虽然描述了相同的房间结构布局，但是房间和门

Description 有 nnn 个机器人排成一排，第 iii 个机器人的购买价是 aia_iai​ 欧元，卖出价是 bib_ibi​ 欧元。 给定 1≤k≤n1\le k\le n1≤k≤n，你需要购买一段长度至少为 kkk 的区间中所有的机器人，然后选择其中的恰好 kkk 个机器人来卖出。 你需要求出： 你能够得到的最大收益； 在收益最大化的前提下，哪些机器人可以在某种最优方案中被卖出。

Description 今年 CEOI 的开幕式上有一场精彩的火炬表演。表演者们站成一排，从 111 开始从左往右编号。每个表演者举着一根火炬，初始只有一个举着点燃的火炬的表演者。 表演分为 QQQ 幕。在第 aaa 幕开始之前，要么 pa>0p_a > 0pa​>0 个表演者从右侧加入表演，他们的火炬是熄灭的；要么最右侧 pa>0p_a > 0pa​>0 个