flower 加训
1C
给一个带点权的树,你可以删去树上一个点,最小化所有子树最长上升子序列的长度最大值 。
N≤100000
1G
给定序列 A,B,需要交换恰好 k 次 A 中两个不同的数,使得 A,B 每个位置的绝对差值和最大。
N≤100000
2A
给定一个序列,求所有子区间,满足排序后是等差数列的个数
n≤105
2H
给定一个长度为 n 的01串,每次翻转一个两端为1的交替段
求连续翻转 k 次的方案数
n,k≤6×105
2L
给定 n 个人之间的好友关系,每次单点增加一个人的步数
求每个人在自己列表里保持冠军的时间
3A
怎么模拟赛做了?
典中典猜数可以撒谎的题
不写了。
3D
怎么模拟赛做了?
3H
Thx so much huahua
https://loj.ac/p/6786
本题大致为 #2389. 「SHOI2007」书柜的尺寸 加强版,为减少无意义提交,题意略有不同.
千寻、眠雪给了你 n 个「书本」,每个「书本」有四个「属性」ai,bi,ci,di.
形式化地来说,你需要将「书本」划分为三个非空集合 S1,S2,S3,最小化目标函数 Ξ,定义为:
Ξ=(max
求出目标函数的最小可能值.
对于所有数据,1\leq n\leq600,1\leq a_i,b_i,c_i,d_i\leq10^9,\max c_i\leq70,\sum c_i\leq1\times10^4.
4A
有 n 个课程, 每门课有学分 (范围 1...5), 且每门课都可以选无数次, 现在求选了恰好 w 学分的方案数
题目还会给出一个培养方案 : 一个 n 个点的有根树, 每个限制是x的子树里的课的学分总和至少为 c[x].
1 \leq n \leq 100, 1 \leq Q \leq 10, 0 \leq c_i \leq 150, 0 \leq w_i \leq 10^8
4D
这不是五年前的CF题?
5A
给一张仙人掌。
Q 次询问,每次给定 c_i, d_i, l_i,找点 x 使得存在 c \to d 的最短路经过 x 且存在 c \to l 的最短路径过 x。若有多个,选与 x 距离最远的,若还有多个,选编号最小的。
N,Q \leq 10^5。
5F
错题,做法假了
5I
给定序列 A,Q 次询问,每次给定 l, r, k,计算
\sum_{i=0}^{k-1} f(A_{l-i},\cdots, A_l, A_{l+1},\cdots, A_r, \cdots, A_{r+i}) \times (n+1)^i \pmod {998244353}
其中 f(S) = \max\{ len \mid \exists x, \forall u \in \{x, x+1,\cdots, x+len-1\}, u \in S \}
1 \leq N,Q \leq 10^5, \sum k \leq 10^7
6A
几何不做
6B
给你一张图𝐺,每条边有一个出现概率𝑃_𝑖,求生成树个数的期望
特别地,𝑃_𝑖会随着天数变化 P_i(t) = q_i + (p_i-q_i)a^{-(t-1)}
你需要求出第1至第𝑇天内答案的和
1 \leq n \leq 300, 1 \leq T_i\leq 10^8, p_i \not\equiv q_i \pmod {998244353}
6E
题意
给出一棵树,最开始只有一个根结点,编号为 1,有颜色 𝑐。要求 在线 完成 𝑚 次操作,每次操作是以下两种之一
给结点 𝑢 加一个叶结点 𝑛+1,颜色为 𝑐。
询问以 𝑢 为根的子树中颜色为 𝑐 的结点的个数。
m \leq 5 \times 10^5
6J
𝑛个点,𝑚条边的简单无向联通图,每个点一个权值 𝑎_𝑖;
一个连通块的贡献:(−1)^\text{块内点数}⋅∑𝑎_𝑖 [\text{点 𝑖 在该连通块内}];
可任意删除一些边,求连通块贡献之和最大是多少。
1≤𝑛,𝑚≤10^6, 1≤𝑎_𝑖≤10^9
6K
???