ABC267 solution

https://atcoder.jp/contests/abc267/

Problem A.

题目描述

输入一个表示星期的英文字符串，输出：还有多少天到星期六？

solution

依题意模拟。\(O(1)\)。

Problem B.

题目描述

Robin 有十个小球，如图排列成这样，然后 Robin 将一些球击飞了，他告诉你哪些球被击飞，然后问你一下这两个条件是否都满足：

1 号球被击飞。
存在两个不同的列（图中用虚线分割成七列），满足这两列分别还有至少一个球没被击飞，它们中间有一列球全部被击飞。

solution

依题意模拟。\(O(1)\)。

Problem C.

题目描述

Robin 给你数列 \(a\) 和正整数 \(m\)，然后定义长度为 \(m\) 的数列 \(b\) 的价值 \(f(b)\) 为 \(\sum_{i=1}^mi\cdot b_i\)，然后 Robin 要求你求出一个 \(a\) 的连续子序列，使得这个连续子序列的长度为 \(m\) 且价值 \(f\) 最大。

solution

观察到我们可以枚举所有的长度为 \(m\) 的连续段，只有 \(O(n)\) 个，且已知 \(i\) 开始的连续段，那么 \(i+1\) 开始的连续段的价值是可以轻易计算的。

\(f([i+1,i+m])=f([i,i+m-1])+(m+1)a_{i+m}-\sum_{j=i}^{i+m}a_i.\)

使用前缀和优化。\(O(n)\)。

Problem D.

背包。设 \(f_{i,j}\) 表示前 \(i\) 个数字已经选出 \(j\) 个数作为子序列的前 \(j\) 个数。

\(f_{i,j}=\max(f_{i-1,j},f_{i-1,j-1}+a_i\cdot j)\)。\(O(n^2)\)。

Problem E.

考虑每次贪心选出代价最小的节点删除。删除了这个节点之后，动态维护一下其他点的删除代价，然后重复这个过程。明显这样是最优的，因为考虑二分答案的时候，每次拿出 \(\leq mid\) 代价的节点，实际上拿出这些节点的顺序是无所谓的，且只会使得其他点的代价尽可能小，所以不需要二分答案而是直接贪心。

线段树或者二叉堆维护。\(O(n\log n)\)。

Problem F.

考虑求出每个点能到达的最远点，如果 \(k\) 超出这个范围则必然无解，否则在它到最远点的路径上任意截取 \(k\) 条边，取出向最远点走 \(k\) 条边到达的点。

使用换根 DP 求出最远点，使用倍增 LCA 求出树上 \(k\) 级祖先（查询一条链上走 \(k\) 步等价于从某个端点向上跳祖先）。\(O(n\log n)\)。

Problem G.

题目等价于重排 \(a_i\) 后恰好有 \(n-k\) 个极长严格递增子段，不妨消除相同数字影响（\(ans_0=\prod_i(\sum_j[a_j=i])!\)），并使得 \(k:=n-k\)。

考虑插入 DP，设 \(f_{i-1,j}\) 表示已经考虑了 \(<i\) 的数字，当前有 \(j\) 个极长上升连续段，设 \(<i\) 的数字实际上有 \(s\) 个。然后考虑插入 \(i\)，情况分为三类：

插在某个连续段后面，不影响段数。
插在某个数字前面，不能是连续段开头的前面（除了最开头的前面），一共 \(s-j+1\) 个位置，增加段数。
插在第一类的后面使他重复，增加段数。

设 \(c_1,c_2,c_3\) 分别是三类的个数，那么方案数是 \(\binom{j}{c_1}f(c_2,s-j+1)f(c_3,c_1)\)，其中 \(f(n,m)=\binom{n+m-1}{m-1}\) 表示 \(n\) 个无标号小球放进 \(m\) 个有标号盒子的方案数。然后 \(\sum_{c_2+c_3=a_i-c_1}f(c_2,s-j+1)f(c_3,c_1)\) 是可以范德蒙德卷积的，证明过程完全一致，可以直接写成 \(f(c_2+c_3=a_i-c_1,s-j+1+c_1)\)，然后暴力枚举状态和 \(c_1\) 进行转移即可。\(O(n^2)\)。