CF573E Bear and Bowling 题解
Description 给定一个长度为 nnn 的序列 a1…na_{1\dots n}a1…n。 你要求一个 aaa 的子序列 b1…mb_{1\dots m}b1…m（可以为空），使得 ∑i=1mibi\sum_{i=1}^m ib_i∑i=1mibi 的值最大。 n≤105n \le 10^5n≤105，∣ai∣≤107|a_i| \le 10^7∣ai∣≤107。 Sol
CF571E Geometric Progressions 题解
Description 给定 nnn 以及 nnn 个正整数对 ai,bia_i, b_iai,bi。 第 iii 对 ai,bia_i, b_iai,bi 确定了一个序列 {ai,aibi,aibi2,aibi3,…}\{a_i, a_i b_i, a_i b_i^2, a_i b_i^3, \ldots \}{ai,aibi,aibi2,aibi3,…}。 询问最小的
CF568E Longest Increasing Subsequence 题解
Description 给定一个长度为 nnn 的有 kkk 个空缺的序列。 你有 mmm 个数可以用于填补空缺。 要求最大化最长上升子序列的长度。 n,m≤105n, m \le 10^5n,m≤105，k≤103k \le 10^3k≤103。 Solution 容易发现只需要先构造出 LIS 上的位置的值，对于其余未填位置随便填，所以构造 LIS 时就不需要考虑出现重复的问题。 考虑先求
CF566E Restoring Map 题解
Description 有一棵 nnn 个点的树，你不知道这棵树的边是怎么连的。 你得到了 nnn 条关于每个点信息，每条信息记录了距离某一个点 ≤2\le 2≤2 的所有点。 但你不知道每条信息具体是哪个点的。 你需要构造一棵满足这些信息的树。 n≤103n \le 10^3n≤103。 Solution 首先可以发现如果存在一条路径 x−u−v−yx-u-v-yx−u−v−y，那么 x,y
CF566C Logistical Questions 题解
Description 一棵 nnn 个节点的树，点有点权，边有边权。 两点间的距离定义为两点间边权和的 32\frac 3223 次方。 求这棵树的带权重心。 n≤2×105n \le 2 \times 10^5n≤2×105。 Solution 不妨设 d(i,j)=dist(i,j)1.5d(i,j)=dist(i,j)^{1.5}d(i,j)=dist(i,j)1.5，考虑找到一个最
CF553E Kyoya and Train 题解
Description 给定一张 nnn 个点 mmm 条边的无重边无自环的有向图，你要从 111 号点到 nnn 号点去。 如果你在 ttt 时刻之后到达 nnn 号点，你要交 xxx 元的罚款。 每条边从 aia_iai 到 bib_ibi，走过它需要花费 cic_ici 元，多次走过同一条边需要多次花费。 走过每条边所需的时间是随机的，对于 k∈[1,t]k \in [1,t]k∈[
CF538H Summer Dichotomy 题解
Description 有 TTT 名学生，你要从中选出至少 ttt 人，并将选出的人分成两组，可以有某一组是空的。 有 nnn 名老师，每名老师要被分配到两个小组之一，对于第 iii 名老师，要求所在的小组中的学生人数 ∈[li,ri]\in [l_i, r_i]∈[li,ri]。 此外，有 mmm 对老师不能在同一个小组中。 你需要判断能否满足所有要求，如果可以，请给出一种方案。 t≤T
CF538G Berserk Robot 题解
Description 有一个机器人，第 000 秒时在 (0,0)(0,0)(0,0) 位置。 机器人会循环执行一个长度为 lll 的指令序列，每秒执行一个指令。 指令有 ULDR 四种，分别代表向上/左/下/右移动一格。 你不知道这个指令序列具体是什么，但是你知道 nnn 条信息，第 iii 条信息为「第 tit_iti 秒时机器人在 (xi,yi)(x_i,y_i)(xi,yi)」，