ABC428

C

https://atcoder.jp/contests/abc428/tasks/abc428_c #前缀和 #括号匹配

合法括号的处理办法：

1. （ ） 括号的数量要相等
2. 序列中的(的数量一定要大于等于 )

这可以把括号抽象为数字，( 代表 1， ) 代表 -1

这样，一个合法的括号就可以用下面的数学语言来表达

1. 和为 0
2. 过程中前缀和大于等于 0

所以我们在处理序列的时候维护两个值即可，一个是最小前缀和，另一个是当前前缀和

D

https://atcoder.jp/contests/abc428/tasks/abc428_d #数论 #十进制拼接 #前缀和 #logn

Let z be the string obtained by interpreting x,y in decimal notation as strings and concatenating them in this order. Let f(x,y) be the value when z is interpreted as an integer in decimal notation.

$f(3, 14)=314$

类似这样的拼接，用字符串进行转化非常麻烦，可以直接用 int 表示，把 $y$ 的十进制位数设为 $d$

那么就有

$f(x, y)=x\times 10^d + y$

这个表示同时还可以解决一个问题，也就是上下限区间的问题，我们可以通过这个直接计算出所有连续的可能的取值的上下限，不仅如此，这个区间的我们可以通过枚举 d 来获得，而 d 的取值范围非常小

这里还有一个比较显然的小结论，也就是，在区间 l~r 中，到底有多少的完全平方数？ 答案是 $\sqrt{ r } - \sqrt{ l -1 }$ #数学小知识

E

https://atcoder.jp/contests/abc428/tasks/abc428_e #树的直径 #bfs #树 #最长路径

这里有一个小结论，在一个树形结构中，对于任意节点 $u$，距离它最远的节点 $v$，一定满足 $v$ 是树直径的两个端点之一

所以，对于树上每一个点，离这个点最远的点一定是树的直径的两个点之间的一个

那么，我们可以先找出树的直径的两个端点，再计算每一个点到这两个点的距离，最后把去这两个距离中的最大值，这个值就是我们需要的最大距离，对应的点就是符合题意的点

找这个两个点 x，y 可以通过 bfs 来实现

先对任意一个点进行 bfs，找到 x，然后再对 x bfs 找到 y，再对 y bfs，即可获得 x 和 y 到任意一个点的距离，最后遍历输出答案即可