AtCoder Beginner Contest 341

比赛链接，官方题解

ID	Difficulty (0-5)	Topic	Status	Code
A	0	Brute Force	Solved	A.cpp
B	0	Greedy	Solved	B.cpp
C	0	Brute Force	Solved	C.cpp
D	1	Number Theory	Solved	D.cpp
E	2	Segment Tree	Solved	E.cpp
F	2	Knapsack	Solved	F.cpp
G	2	Convex Hull Trick	Solved	G.cpp

E - Alternating String

维护 01 数列，支持区间翻转，查询区间是否 01 交替。

线段树维护区间开头，结尾，是否01交替，懒标记支持区间操作。

F - Breakdown

给定无向图，每个点 $u$ 有点权 $w_u$ ，第 $i$ 个点上有 $a_i$ 个石子。

每轮行动，选择一个石子，假设其所在的点为 $u$ 。

从 $u$ 的邻居 $N(u)$ 中选一个子集 $S\subseteq N(u)$ ，满足 $\sum_{v\in S} w_v < w_u$ 。

将 $u$ 上石子数 $-1$ ， $S$ 中每个点 $v$ 上石子数 $+1$ 。

问可以最多行动多少轮。数据范围 $1\le n,m,w_u\le 5000$ 。

首先所有石子所在点的 $w$ 之和随着行动肯定是减小的，游戏会结束。

令 $f_u$ 表示 $u$ 上的一个石子可以使游戏进行多少轮，由于石子所在权值一定变小，所以移走就回不来，转移关系是DAG。将每条边由权值较小的点连向权值较大的点，跑拓扑排序 + 01 背包。

每条边只会被用来做一次背包，复杂度 $O(m\cdot \max w_u)$ 。

G - Highest Ratio

给定数列 $a_1,a_2,\dots,a_n$ ，对每个 $i\in{1,2,\dots,n}$ ，找一个 $j\in{i,i+1,\dots,n}$，最大化 $a_i,a_{i+1},\dots,a_j$ 的平均值。

预处理 $a$ 的前缀和数组 $sum$ 。容易发现所求
$$
ans_i=\arg\max_{i\le j\le n}\frac{sum_j-sum_{i-1}}{j-(i-1)}
$$
把 $(i, sum_i)$ 看作二维平面上的点，$f_i$ 其实就是从 $(i-1,sum_{i-1})$ 向后看，找一个点构成的直线斜率最大。

容易发现这条直线就是 $(i-1,sum_{i-1})$ 向后面的点集的凸包的切线。

单调栈维护上凸壳 + 凸壳上三分即可。复杂度 $O(n\log n)$ 。