Codeforces Round #719 题解

A. Do Not Be Distracted!

给你一个字符串，问你这个字符串的字母是不是连续的。

扫一遍。每发现一个字母，就直接把连续的相同字母都跳过，然后标记这个字母已经不会再出现了。如果后面再出现就输出NO。

定义美的数：这个数里面的数字都一样。给你一个n，问你从1到n里有多少个美的数。

从1-9依次构建出9位以内的美的数，统计其中小于n的个数。

给你一个$n\times n$的棋盘，让你把1到$n^2$放到棋盘里。要求相邻两个格子的值的差不能为1。问你怎么构建。

对角线斜着构建。以$n=5$为例：

给你一个长度为$n$的数组$a$，问你其中有多少对$i,j$使得$a_j - a_i = j - i$.

变换一下等式，得到$a_j - j = a_i - i$。于是扫一遍，计算出所有$a_x - x$出现的次数。然后$C_n^2$即可。

算是一个思维题。其实就是看有多少羊往左，有多少羊往右。

经典二分。不断查询$[1,mid]$的值。但hard version里要改值会导致之前的查询的结果要统一加一。因此立刻想到线段树维护一下。

这个题我之前见过。就是从起点和终点BFS一次之后，再考虑传送门的问题。我记得之前好像也是上来就想Dijkstra结果挂了。