• 周六. 8月 20th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

Harbour.Space Scholarship Contest 2021-2022 (Div. 1 + Div. 2) Editorial题解

admin

11月 28, 2021

A

略,发现只有当末尾为9时才满足条件..

B

简单模拟,注意数组大小!!!

C

简单模拟。

D

比较暴力的一个做法就是每次找一个开始匹配的起始点,然后每次不同时向后跳2就行了。
注意这里最后还要判断一下剩下的串的个数是不是偶数!!!复杂度应该是(O(n^2))但水过了就是水过了…

E

好题!起码对我来说是这样的,学到了许多的知识…
首先我们先将所有的数字减1,将一个排列位置上的数和它的标号都减一。例如:(n=4)(p[0]=0,p[1]=1,p[2]=2,p[3]=3.)这是一个排列。或者打乱一下,(p[0]=2,p[1]=3,p[2]=0,p[3]=1),这也是一个排列,反正我们就是要将数和位置数都减一。为什么这样做呢,因为像这样的整体移动,往往和对n取模有关,例如当(k=2)时,数组变成(p[0]=2,p[1]=3,p[2]=0,p[3]=1),我们发现对于(>=k+1)的数下标为i的就变成了(i-k),这个很好想,毕竟他们就是从原来的数被迫向后推了(k)。对于前(k)个数我们找一下规律,(p[0]=2=n-1-(k-1)=n-k,p[1]=3=n-k+1),同理可推得(p[i]=n-k+i,p[i]=i-k+n),发现和(i-k)的形式就多了一个(n),怎么办,我们取模啊,于是就有了(p[i]≡i-k)(%n),也就是说对于一个k,我们就能知道了其序列应该满足上式。之后考率给定一个k我们怎么用最少的次数将它还原成目标数列(b[i]),一个做法就是用图论的知识,环图,我们将p[i]向b[i]连边。意思是在p[i]序列中p[i]要和b[i]交换。考虑这样做后整个图一定是若干个环,对于每个环我们要花费环中元素的个数-1的次数才能将环中的数都还原。这样之后我们总的还原次数就是n-环的个数。好了,结束了…
不对啊,难道我们要对每一个k都做一下上述找环的过程吗?这个过程不是(O(n^2))的吗?
考虑题中给的(mleq frac{n}{3})有何用意,我们考虑一个能够用m次交换就能成功的排列,那么其最多有2m个数是乱序的,那么也就是说这个排列最少有n-2m个数是在自己本来位置上的。我们可以用一个数组(cnt_i)表示(k=i)在自己正确的位置上的数的个数。
考虑(k=0,1,…,n-1)这n个排列是各不相同,也就是说对于(k1!=k2,p_{k1}[i]!=p_{k2}[i])这样的话由于目标序列只有一个,所以每个位置只会在其中的一个k中是正确的,在其他的位置都不正确,即(sum{cnt_i}=n)。这样的话我们只需要在目标序列上找到其对应正确位置的k值,之后我们只用检查满足要求的k值,等等这样的k值一共有多少个,(frac{n}{n-frac{2n}{3}})那不是3吗?
也就是说说最多有3个k值需要我们去找环,放心食用.

F

未完待续…

发表回复

您的电子邮箱地址不会被公开。