Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2) 题解

Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2) 题解

A

只需要判断\(a\)\(b\)的奇偶性即可,和\(a\)是否等于\(b\)

B

枚举两种奇偶排列情况,求一边逆序对数即可。

C

将‘(‘看作\(+\),‘)‘看作-。

枚举左端点和右端点属于的块,解一个不等式即可。

D

首先一个\(and\)\(or\)操作可以变成\(+\)\(xor\)

看成\(+\)的话,只需要知道前三个中两两的和,和后面相邻位置的和即可。

E

\(c[i]=a[i]-b[i]\)。看成差分序列即可。

F

\(dp_{i,mask}\)表示只考虑\(mask\)里的点,\(i\)能到大\(mask\)里所有点的概率。

\(dp_{i,mask}=1-\sum_{t\subset mask,i\in t}dp_{i,t}\times G(mask-t,t)\)

其中\(G(A,B)=\sum_{x\in A}\sum_{y\in B}p[x][y]\)

\(G\)可以用哈希表存。时间复杂度为\(O(n3^n)\)

G

倒着考虑,并查集维护联通信息。

首先只相差一位可以让人想到“格雷码”。对于任意一段\([x2^k,(x+1)2^k-1]\)都是联通的,也就是对应线段树上的一个节点。

考虑将大段分成一些极长满足上述条件的小段。对于每一个小段可以枚举哪一位不同,然后用set连边。

时间复杂度\(O(MN^2\log M)\),需要卡常。

做法2:

可以发现任意一端:

  • \([x2^k,z](z\leq (x+1)2^k-1)\)
  • \([z,(x+1)2^k-1],(z\geq x2^k)\)

都是联通的。所以可以将一个大段分成\(2\)个小段。

考虑上述连边过程,实际可以做得更优。

考虑将所有原始区间和修改一位的区间做一遍\(two-pointers\),将边预处理即可。

时间复杂度为\(O(NM)\)

H

正解是拟阵交……

不过也可以模拟退火。

第一种做法:

先随机一个生成树,然后随机调整边,可能不是很优,不过需要调参也能过。

做法2

首先前\(k\)个点的生成图个数可以\(O(\exp(k))\)枚举。

可以随机前\(k\)个点和后\(k\)个点之间的边。

然后贪心构造。

正确性比第一个做法高许多。感觉第一个每次只能随机一棵生成树,而做法二每次随机了\(O(exp(k))\)个生成树。

Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2) 题解

上一篇:浅析exports和module.exports的理解


下一篇:Redis--数据类型