ABC267总结

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16653808.html

比赛链接

比赛情况

AC：6 / 8

题目分析

A（语法入门）

打表周一到周五即可

B（基础算法）

按照题意计算即可

假如1号球没倒，则非法

否则分别找最左和最右分别没倒的列，判断中间是否有一列全倒了

上图中红色列代表最左没倒，蓝色列代表最右没倒，黄色列打表中间全倒了的

C（简单模拟）

考虑区间整体右移的变化，假设末尾为 $i$，如下图所示：

显然红色部分没了，黄色部分各少一个，蓝色部分多 $m$ 个

前缀和预处理一下，$f_i=f_{i-1}+S_{i-1}-S_{i-m-1}+a_i\times m$

答案为 $\max_{i=m}^nf_i$

D（基础DP）

设 $dp(i,j)$ 为前 $i$ 个数选 $j$ 个的最小代价

显然，枚举当前数选或不选

1. 选：$dp(i, j)=dp(i-1, j-1)+a_i\times j$
2. 不选：$dp(i, j)=dp(i-1, j)$

答案即为 $dp(n,m)$

E（图论+二分）

显然，最大的最小，二分最大值

把符合条件的放进队里，然后使和其相连的减去，如果符合条件再丢进队里

如果所有数最后都符合条件则可行

F（树的直径+树上倍增）

显然，离一个点最远的点一定是树直径的两端点之一（求树直径两遍dfs做法时已证）

而离这个点越远显然机会更多

所以先求树直径，然后以树直径两端点建树，每个询问 $u$ 分别在这两颗树上找第 $k$ 个父节点，这个过程可以用树上倍增实现