QOJ_News的博客

博客

2021 牛客多校 部分题目

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

flower 加训

1C

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

$N \leq 100\,000$

1G

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

$N \leq 100\,000$

2A

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

$n \leq 10^5$

2H

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

求连续翻转 $k$ 次的方案数

$n,k \leq 6 \times 10^5$

2L

给定 $n$ 个人之间的好友关系,每次单点增加一个人的步数

求每个人在自己列表里保持冠军的时间

3A

怎么模拟赛做了?

典中典猜数可以撒谎的题

不写了。

3D

怎么模拟赛做了?

3H

Thx so much huahua

https://loj.ac/p/6786

本题大致为 #2389. 「SHOI2007」书柜的尺寸 加强版,为减少无意义提交,题意略有不同.

千寻、眠雪给了你 $n$ 个「书本」,每个「书本」有四个「属性」$a_i,b_i,c_i,d_i$.

形式化地来说,你需要将「书本」划分为三个非空集合 $S_1,S_2,S_3$,最小化目标函数 $\mathbf{\Xi}$,定义为:

$$ \mathbf{\Xi}=\left(\max_{x=1}^3\max_{i\in S_x}a_i\right)\times\left(\sum_{x=1}^3\max_{i\in S_x}b_i\right)\times\left(\max_{x=1}^3\sum_{i\in S_x}c_i\right)\times\left(\sum_{x=1}^3\sum_{i\in S_x}d_i\right) $$

求出目标函数的最小可能值.

对于所有数据,$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

???

评论

暂无评论

发表评论

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