QOJ_News的博客

博客

2021 牛客多校 部分题目

2022-06-13 00:40:41 By QOJ_News

flower 加训

1C

给一个带点权的树,你可以删去树上一个点,最小化所有子树最长上升子序列的长度最大值 。

N100000

1G

给定序列 A,B,需要交换恰好 k 次 A 中两个不同的数,使得 A,B 每个位置的绝对差值和最大。

N100000

2A

给定一个序列,求所有子区间,满足排序后是等差数列的个数

n105

2H

给定一个长度为 n 的01串,每次翻转一个两端为1的交替段

求连续翻转 k 次的方案数

n,k6×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\leq6001\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

给定序列 AQ 次询问,每次给定 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

???

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。