百度之星 2024 题目整理 && 游记
Register_int
·
·
生活·游记
Day 0
晚上是热身赛。
A
给定 n，求有多少个长度为 n 的小写字母字符串，满足 shs 不相交地出现了至少三次。n\le 10^6。
B
给定 n,m,k。求有多少种给 n\times m 格子染成黑白色的方案，使得任意两行或两列完全相同或完全不同。n,m\le 10^7,k\le n\times m。
C
给定 n,m 与数组 s_i,v_i，表示第 i 个元素从第 s_i 秒开始每秒产生 v_i 的贡献。现在可以去掉恰好一个元素，求总贡献 \ge m 的最大时间。n,m\le 2\times10^5。
你说得对，但是我 A 题一眼二项式反演开始推柿子，推不出来遂跳过。发现 B 是黄题后开始写写写写写调调调调调，最后在距离比赛结束 10 min 时发现 k 没开 long long。
赛后问了同学发现 A 可以直接 dp_{i,0/1/2/3,0/1/2}。唉这个状态打啥决赛。加睡。
Day 1
A
给定 n,a_{1\sim n},b_{1\sim n,1\sim n}。定义三元组 (i,j,k) 的权值为 \max\{a_i,a_j,a_k,b_{i,j},b_{j,k},b_{i,k},b_{i,j}\times b_{j,k}\times b_{i,k}\}，求将 1\sim n 划分成若干个三元组的最大权值和。n\le 21，3\mid n。
B
给定一个二进制数，求它 \times21 的值。长度 \le 10^3。
C
平面直角坐标系上 n 个位置 (x_i,y_i) 有障碍，每次上下左右走一格，走到障碍上耗费 1 的体力。求 (x_1,y_1) 到 x_2,y_2 的最小体力。1\le x_i,y_i\le 10^3，n\le 5\times10^4。
D
给定长度为 n 的环形大写字母字符串 s 和环形数组 a。定义一个区间的权值如下：
- 按顺序将区间中的字符弹入栈内，若栈内有相同字符则不断弹栈。权值为最后栈内剩下字符对应的 a_i 之和。
### E
给定 $n,k,d$ 和数组 $h_{1\sim n}$。定义一个段合法，当且仅当其能划分为 $k$ 个连续段，每段内极差不超过 $d$。求出：
1. 确定 $k$ 时，让原序列合法的最小的 $d'$。
2. 确定 $d$ 时，让原序列合法的最小的 $k'$。
3. 确定 $k,d$ 时，原序列的最长合法子段。
$k\le n\le5\times10^5$。
### F
给定长度为 $n$ 的序列 $a$，求有多少个子序列是单峰的。$n\le 10^6$。
### G
给定 $n$ 个点的带权树、$k$ 和长度为 $m$ 的序列 $a$。你可以 $k$ 次将树上一条边的边权除以二下取整，求 $1\to a_1\to a_2\to\cdots\to a_m\to1$ 这条路径权值的最小值。$m\le n\le10^5,w\le 10^8,k\le 10^9$。
### H
给定 $n$ 个区间 $[l_i,r_i]$，左端点单调递增。$q$ 次询问 $L,R$，先只保留 长度在 $[L,R]$ 的区间，再将相交的区间两两连边，求最小点覆盖。$n,q\le 2\times10^5
I
给定 n 个点的带权树与长度为 m 的序列 w。你可以在树上新连接 m 条边，边权分别为 w_1,w_2,\cdots,w_m。之后在树上找一个路径，使得：
- 从 1 出发，从 1 结束。
- 每条树边至少经过了一次，每条非树边最多经过一次。
求路径权值最小值。n\le 10^5,m\le 100。
J
平面上有 n 个椭圆 \frac{(x-x_i)^2}{a^2}+\frac{(y-y_i)^2}{b^2}=1。给定 a，求最大的 b 使得所有椭圆均不交。n\le 10^5。
K
有 k 种物品，每种有 c_i 个。现有 n=\sum c_i 个商店，你在第 i 个商店可以以 a_{i,j} 的价格出售一个第 j 个物品。每个商店只能恰好出售一个物品，最大化总价格。n\le 10^5,k\le 5。
L
忘了。有记得的哥们可以戳我一下。
游记部分。
唐了，铁了。嗯？铜了？哇！银了！
明年再来。