Namomo Winter Camp 3¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 13/65 | 7 | 10 | 11 |
A¶
upsolved by
题意¶
题解¶
B¶
upsolved by
题意¶
题解¶
C¶
solved by 2sozx JJLeo
题意¶
公司里面的人按勤奋值从大到小排序（相同的话后加入的人排在前面），前 20% （向下取整）的人勤奋工作，剩下的人都摸鱼，现在有一系列员工加入和离开公司的事件，输出所有工作状态发生转换的员工和他的新工作状态。
题解¶
先用 set 进行了究极带模拟，未知 bug，寄。
之后使用了 FHQTreap 进行模拟，成功大炮打苍蝇。
好写的正解是开两个堆，分别存勤奋工作的人和摸鱼的人，前者堆顶存最不勤奋的，后者堆顶存最勤奋的，来回弹即可。
D¶
solved by JJLeo
题意¶
构造一个括号序列，使得至少交换相邻两个字符 \(A\) 次才能将其变为合法括号序，且恰好交换 \(A\) 次是可以的。要求输出最短的字符串，如果有多个字符串满足条件，输出字典序最短的那个。(\(1 \leq A \leq 10^9\))
题解¶
找到最短的 \(n\) 满足 \(\dfrac{n(n+1)}{2} \ge A\)，先构造出 \(\underbrace{))\cdots))}_{n}\underbrace{((\cdots((}_{n}\)，再将其交换 \(\dfrac{n(n+1)}{2} - A\) 次即可，因为要字典序最小，优先将最左边的未到最终位置的左括号向左移动即可，最终的合法括号序为 \(n\) 个连续的 \(()\)。
E¶
solved by JJLeo
题意¶
给出一颗树，问有多少对子树，每种深度的节点数量相同。
题解¶
哈希即可。
F¶
upsolved by
题意¶
题解¶
G¶
upsolved by
题意¶
题解¶
H¶
upsolved by
题意¶
题解¶
I¶
upsolved by JJLeo
题意¶
有一个未知的长度为 \(n\) 的序列 \(a_1,a_2,\cdots,a_n\)。满足 \(a_i = [i < x]\)，其中 \(x\) 等概率分布于 \([1,n]\) 的每个整数。
你可以每次选择至多 \(m\) 个下标，同时获得序列中对应位置的数，如果其中有 \(x\) 个数为 \(0\)，则你需花费 \(t_x\) 的代价，求最优操作下知晓 \(x\) 所花费代价期望的最小值。(\(1 \le n \le 1000\)，\(1 \le m \le 30\))
题解¶
设 \(g_i\) 为对于长度为 \(i\) 的序列，知晓 \(x\) 所花费代价期望的最小值，所求答案即为 \(g_n\)。
显然有 \(g_1=0\)，当 \(i > 1\) 时，可以枚举分界点，进而转化为一系列子问题： $$ g_i = \min_{i>x_1>x_2>\cdots>x_k\ge1,1\le k \le m} \left[ \frac{i-x_1}{i}(g_{i-x_1}+t_0) + \frac{x_1-x_2}{i}(g_{x_1-x_2}+t_1) + \cdots + \frac{x_k}{i}(g_{x_k}+t_k) \right] $$ 但直接去枚举这些分界点会 TLE，因此还需要一个 dp，设：
则有如下转移：
时间复杂度为 \(O(n^2m)\)。
J¶
upsolved by JJLeo
题意¶
给定 \(n\) 个由 \(0\) 到 \(9\) 这十个数字以及 \(+,-,\times\) 三种运算符组成的字符串 \(s_i\)，将每个串重复 \(r_i\) 次，再将这 \(n\) 个串依次拼在一起，保证最终得到的字符串是一个合法的表达式，求这个表达式的值对 \(10^9+7\) 取模的结果。(\(1 \le n \le 10^4\)，\(1 \le |s_i| \le 10\)，\(1 \le r_i \le 10^9\))
题解¶
表达式一定是形如多个数乘积（可能为负）的和。
可以维护三个值，除了最后一个乘积外的和 \(x\)，最后一个乘积 \(y\)，以及最后一个乘积中除了最后一个数外的乘积 \(z\)。添加一个数字或是三种符号都可以用一个矩阵右乘行向量 \(\begin{pmatrix}x & y & z & 1\end{pmatrix}\) 来表示。
-
添加一个数字 \(d\)： $$ \begin{pmatrix} 1 & 0 & 0 & 0 \newline 0 & 10 & 0 & 0 \newline 0 & d & 1 & 0 \newline 0 & 0 & 0 & 1 \end{pmatrix} $$
-
添加一个加号： $$ \begin{pmatrix} 1 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 \newline 0 & 0 & 0 & 0 \newline 0 & 0 & 1 & 1 \end{pmatrix} $$
-
添加一个减号： $$ \begin{pmatrix} 1 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 \newline 0 & 0 & 0 & 0 \newline 0 & 0 & -1 & 1 \end{pmatrix} $$
-
添加一个乘号： $$ \begin{pmatrix} 1 & 0 & 0 & 0 \newline 0 & 0 & 1 & 0 \newline 0 & 0 & 0 & 0 \newline 0 & 0 & 0 & 1 \end{pmatrix} $$
使用矩阵快速幂即可快速算出答案，时间复杂度为 \(O(64n\log r_i)\)。
K¶
upsolved by JJLeo
题意¶
给出一颗 \(n\) 个点带边权和点权的树，每经过一个点可以获得等于该点点权的油量，每经过一条边时所拥有的油量不能少于该边的边权，不能重复经过一个点，出发点任意，问最多经过多少个点。(\(1 \le n \le 10^5\))
题解¶
点分治，考虑如何统计一条链是否合法：
上行的路径合法等价于任意一段后缀均非负，等价于当前的和减去前缀最大值非负。
下行的路径合法等价于任意一段不算最后一个点的前缀均非负，维护不算最后一个点的前缀最小值即可。
（前缀指从分治中心到某个点的所有点权减去边权的值，后缀指从当前点往上到某个点的所有点权减去边权的值）
可以将所有下行的路径加上分治中心那个点一起算上得到所有匹配的上行路径至少还要剩多少油才可行，使用 set 维护一个单调栈，保证所需油量随着点数单增，插入时如果合法则不断弹后继的点即可。
总时间复杂度 \(O(n \log ^2 n)\)。