======AtCoder Beginner Contest 176======

=====A - Takoyaki =====

====题目大意====

给 $n,x,t$ ,问 $n/x$ 取上整乘 $t$.

====解题思路====

模拟

=====B - Multiple of 9=====

====题目大意====

给定一个长为 $n \le 2e5$ 的数，问其是否是9的倍数。

====解题思路====

每位的数相加看能否整除9即可。

=====C - Step=====

====题目大意====

给定长为 $n \le 2e5$ 的数组。允许给每个数任意加值，问最少加多少使数组非减。

====解题思路====

原本非减就不管，否则加到和前一个数一样大即可。

=====D - Wizard in Maze=====

====题目大意====

给定 $H×W ，H，W \le 1000$ 的一张图，图上有一些不能走的点，支持两种操作，一是走相邻的格子不消耗步数，二是在周围 $5×5$ 的格子内任意移动并消耗一个步数，问最少多少步能够从一点到另一点。

====解题思路====

本题图的范围较大，我们不能直接用SPFA解决，而需要通过一次dfs和并查集处理出连通块，再通过bfs得出结果。


=====E - Bomber =====

====题目大意====

在一张 $H×W ，H、W \le 3e5$ 的图上，给定一些点 $(n \le min(H×W,3e5))$，问选定一行一列最多能覆盖多少个点。

====解题思路====

我们显然可以处理出覆盖点最多的行和列，然后依次枚举检查它们交叉的点处有没有点即可，由于点的个数有限，这个检查是符合复杂度的。

=====F - Brave Chain=====

====题目大意====

给长度为3n（$n\le 2000$）的序列，每个数都是1到n。每次从前五个里挑三个删除，若这三个数相等，则结果加一。最后剩下的三个若相等，结果也加一。问最终答案的最大值。

====解题思路====

首先最朴素的思想，是枚举前一次剩下的结果，复杂度$O(n^3)$。随后，发现每次转移的结果，要么是原先的两个，要么是原先的一个加之后的三个中的一个，要么是三个中的两个。后两种一共O(n)种情况，记录一下所有剩余情况的最大mx和所有剩余的里有i的最大$f_i$即可。第一种除非三个全相等，否则结果不变。可以证明，三个全相等时，最优情况一定是删这三个。因此可以单独再用一个数cnt记录这个即可。最终答案为$cnt+max\{mx,dp[a[3n]][a[3n]]\}$。