jiangly的博客

博客

The 3rd Universal Cup. Stage 6: Osijek 题解

2024-08-11 21:35:44 By jiangly

A. Coprime Array

注意到我们只关心 smodx 的值(答案绝对值要求在 109 以内,但是任何一组解都可以通过调整符合这个范围,所以可以忽略这个限制),将 x 分解后,只需要求出每个 pk 的解,就能通过 CRT 合并出 x 的解。

显然答案等于 1 当且仅当 gcd(s,x)=1

剩下的情况,除了 s 是奇数且 x 是偶数的情况,都能构造出长度为 2 的解。

s 是奇数且 x 是偶数的情况可以先分出一个 1,因此可以构造出长度为 3 的解。

实现时其实可以利用随机避免分解和 CRT,随机到一个解的概率至少是 p|xmax{1,p2}p

B. Square Locator

因为点 Ay 轴上,所以点 A 的坐标可以直接算出。枚举 ABCD 是逆时针还是顺时针,设点 B 的坐标是 (x,y),则可以通过点 B 和点 C 到原点的距离列出两个方程,从而直接解出 x,y 并判断。

C. -is-this-bitset-

对于深度 d11 的点 i,将 ai 设为 220d。因为树是二叉树,所以至多改变 2121=4095 个点的 ai

改变之后,每条链上的前 12 个点就可以凑出 [0,221) 中所有 29=512 的倍数。因此对于 d>11 的点,只需要考虑模 512 的每种余数能凑出的最小的数,可以在 O(512) 的时间 DP 求出。

为了进一步减小空间消耗,注意到每条链上 DP 的改变量不会超过 max{bi}<221,因此只需记录 DP 数组发生的改变,回溯时撤销即可。

V=max{bi},k=5000,则时间复杂度为 O(nV/k),空间复杂度为 O(n+V)

D. Cycle Game

我们认为最外圈边界都是白格子,则存在一个内部非空的环当且仅当存在一个格子,将这个格子视为白格子后白格子的八连通块至少有两个(即存在一个白格子和边界不连通)。

加入一个黑格子后,如果存在这样的格子,那么其中的一个一定与新加入的格子相邻。因此只需使用线段树分治和可撤销并查集维护连通性,在每个时刻枚举周围的所有格子并判断这次操作是否应该进行。

时间复杂度 O(nmlog2(nm))

E. Sum of Squares

F. Alternating Cycle

G. Touching Grass

如果询问的是直线,则问题可以转化为直线和点集的上凸包是否相交,只需在凸包上二分。

线段询问可以通过线段树转化为直线询问,即按 x 排序建线段树,对线段树上的每个区间都求凸包。

这样的空间复杂度是 O(nlogn+m),采用类似分治的方式离线回答询问可以优化为 O(n+m)

将线段按斜率排序后可以避免二分,改用双指针,总时间复杂度 O((n+m)logn)

H. Game Design

ipi 连边,可以看作每个点入度和出度都是 1 的有向图。设 f(i,j) 为考虑前 i 个点,有 j 条入边和出边的另一端还未确定(大于 i)。

考虑 i 的连边,有如下四种转移。

  • 入边和出边都向后,转移到 j+1,方案数 1
  • 入边向后,出边向前,转移到 j,方案数 j
  • 入边向前,出边向后,要求 si=1,转移到 j,方案数 j
  • 入边和出边都向前,要求 si=1,转移到 j1,方案数 j2

时间复杂度 O(n2)

I. Geometry Hacking

J. Non-Interactive Nim

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。