Codeforces Round #719 题解

A. Do Not Be Distracted!

题意

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

题解

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

代码

Submission #115214999 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. Ordinary Numbers

题意

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

题解

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

代码

Submission #115220496 - Codeforces
Codeforces. Programming competitions and contests, programming community

C. Not Adjacent Matrix

题意

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

题解

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

代码

Submission #115233844 - Codeforces
Codeforces. Programming competitions and contests, programming community

D. Same Differences

题意

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

题解

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

代码

Submission #115239792 - Codeforces
Codeforces. Programming competitions and contests, programming community

E. Arranging The Sheep

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

Codeforces Round #719 Arranging The Sheep - 排序
题意给你一个长度为n的字符串,其中*表示羊,.表示空位。每次只能把羊往左或右移一位,且目标位置得是空位。问最小移几步。

F. Guess the K-th Zero (Easy/Hard Version)

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

Codeforces Round #719 Guess the K-th Zero (Hard version) - 线段树
题意交互式问题。有一个长度是$n$的由0和1构成数组。现在你每次可以查询任意区间的和。现在有$t$个提问,每个问题要你通过若干次查询后得出其中第$k$各0的位置。且每个提问之后,会把结果位置的0变为1。

G. To Go Or Not To Go?

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

Codeforces Round #719 To Go Or Not To Go? - BFS
题意给你一张$n\times m$的地图,从$(1,1)$出发,要走到$(n,m)$。每次向相邻格子走一步的开销是$w$。图上有传送门,从传送门传送的开销是$map[x_1][y_1]+map[x_2][y_2]$。问你最小开销是多少。