刷题记录:Codeforces Round #719 (Div. 3)

Codeforces Round #719 (Div. 3)

20210703。网址:https://codeforces.com/contest/1520。

没错,我是个做div3的蒟蒻……

A

大水题。

B

所有数位都一样的数是【ordinary数】(如1,22,333)。给一个数n,问小于等于n的【ordinary数】有多少。

直接用一个数组记录【ordinary数】,然后以n为key对数组进行二分搜索,返回的下标就是答案。二分搜索:STL的lower/upper_bound。

怎么得到这个数组呢?数组长这个样子,1-9,11-99,111-999。1-9先初始化好,11-99可以由1-9得到,111-999进而用11-99得到。a[i]=a[i-9]*10+i%9+1,差不多这样的形式。

C

给一个n,用1到n*n的所有数,构造n*n的“不相邻矩阵”(就是,对于相邻的cell,数值不相邻)。

数值的相邻就是只差1。比如说,“1 2”“2 1”是相邻的,“1 3”“4 1”就不是相邻的。

如果可以构造出来,就输出这个矩阵。如果不能,就输出-1。

发现1可以(输出就是1),2不行。然后对于n≥3时,可以这样构造:

\[\begin{matrix} 1 & n+1 & \cdots & (n-1)n+1\\ (n-1)n+2 & 2 & \cdots & (n-2)n+2\\ \vdots & \vdots & \ddots & \vdots \\ n+(n-1) & 2n+(n-1) & \cdots & n-1 \end{matrix} \]

错位一下。

D

我们有一个n个整数的数组,统计一种pair的个数。

什么样的pair呢?i<j且a_j-a_i=j-i。

这个我一开始居然没想到怎么做……其实很简单。

\[a_j-a_i=j-i \\ a_j-j=a_i-i \]

就是这样!读入的时候就记录a[i]-i,然后对这个一通排序,对所有相等的值算一个\(C_n^2\)组合数,求和就ok了。

好像需要long long。

E

有点像华容道,只不过是1维的。

n个位置,每一个位置有物品/空着,移动物品多少次可以使所有物品聚在一起?

移动物品一次:把【一个】物品移动【一个位置】。

分析一下:

假设现在有两堆物品,左边一堆共a个物品,右边一堆共b个物品,它们之间距离是l。我们要把它们移成一堆。左边一堆往右移x,右边一堆往左移y,cost是ax+by,其中x+y=l。为了让cost更小,我们会让物品更少的那一堆移动,物品更多的堆原地不动。

想想一个坐标把这n个位置分成两半,我们把这个坐标叫做分割线。【分割线两侧的物品一定会分别聚成两堆】。因为它们最终要聚成一堆,如果最终这一堆物品的中心在左边,那么左边的物品围绕这个中心聚起来,右边的物品迁徙到紧靠分割线。最终物品中心在右边也是一样。不过这是感性的想法,(也不想去严格证明)。

所以,如果分割线两侧物品数量相等呢?分割线两侧的两堆物品数量相等,意味着哪一堆移动都无所谓,为什么不两堆一块移,一起向分割线聚拢呢?此时我们意识到,这样的分割线就是最终物品堆的中心!

所以,第一步把序列扫一遍确定物品个数,第二步把序列再扫一遍确定分割线位置。然后,对于左边的每一个物品,一个一个移动到中间并记录次数,右边也是如此。

F

读题读了半天……

有一个只有01的数组,我们要找第k个0的位置。我们可以发起询问,格式是“[l,r]的总和是多少”,通过简单处理就可以得到“[l,r]内有多少个0”的信息。

我们有t个询问,每个询问给出一个k,问第k个0的位置。并且,对于每一个被询问的0,我们找到它之后,它都会变成1。

举个例子:000。第一个0的位置是1,(然后0->1,变成100),再问第一个0的位置就是2了。

对于每一个询问,我们都二分搜索来找。为了问尽可能少的次数,我们记忆化搜索。维护一个数组dp,dp[i]表示[1,i]中有多少个0。(因为发现空间不够开二维dp数组。)

正确性:问“[l,r]中多少个0”的时候,第一种情况:l=1,得到的就是dp[r];第二种情况:l不是1,此时我们已经搜过l之前的位置,发现[1,l-1]并没有那么多0,所以转而搜l后面的位置,所以dp[l-1]已经被算过,【[l,r]中0的个数】=dp[r]-dp[l-1],可以顺利得到dp[r]。

询问结束后0->1的处理:操作dp数组,for i从pos到n做--dp[i],如果dp[i]已经被算过。

G

在一个地图里从左上角跑到右下角。地图的每一个位置是障碍(-1),空地(0),传送器(大于0的整数cost)。可以从一个传送器瞬移到另一个传送器,代价是两个传送器的cost相加。

首先明确一个事情。如果我们要用传送器,肯定只传送1次。我们从A传送到B,然后几经辗转跑到C再传送到D,B的代价、C的代价、B跑到C的代价都大于0,所以为什么不直接从A传送到D呢?

明确了这个之后,就好办多了!最优路线只可能有两种,要不是直接跑,要不是中间传送一次。

对于传送的方案,从左上角开始用bfs算【每一个传送器离左上角的距离+传送器本身cost】然后选值最小的,从右下角开始用bfs算【每一个传送器离右下角的距离+传送器本身cost】然后选值最小的,相加。

对于直接跑的方案,直接从左上角bfs到右下角。

上一篇:使用F021_API_F2837xD_FPU32.lib 库函数遇到的问题 warning #10068-D: no matching section


下一篇:python学习笔记之读取配置文件