【Gym-102331】300iq Contest 2

好,开始补坑。

这场打得实在有点问题,中途我去体测,廷廷又要提前回家,实际打的时间都没多少。。。

A Apollonian Network

B Bitwise Xor

题意:有$n$个数,给出一个数$x$,询问满足任意两个数异或和大于等于$x$的子序列的数量。

数据范围:$1\leq n\leq 300000,0\leq x,a_i\leq 2^{60}-1$

做法:一个子序列内添加进去一个新的数需要满足这个子序列的其他数和这个数的异或和都大于等于$x$,即只要找到最小的异或和大于等于$x$即可。于是每次添加一个数的时候在线段树上查找一下即可,复杂度$O(60n)$。

C Counting Cactus

D Determinant

E Easy Win

F Fast Spanning Tree

G Grammarly

题意:给出一个长度为$n$的串$s$,若$a,b\in s\ and\ b\in a\ and\ |b|+1=|a|$,则由$a$连一条边向$b$,求从$s$出发的简单路径数,答案模$99824453$。

数据范围:$1\leq n\leq 300000$。

做法:如果没有重复的字符,则答案显然为$2^n-1$。于是对极长重复字符段组合数容斥一下即可,复杂度是$O(n)$。

H Honorable Mention

I Interactive Vertex

题意:给出一棵$n$个点的树,其中有一个关键点$A$。交互,每次你可以给出类似$?\ k\ x\ y_1\ y_2\ …\ y_k$的询问,返回$dis(A,x)\geq min(dis(A,y_i))$的$bool$值,要求交互次数不超过$4\lceil log_2n\rceil$。

数据范围:$1\leq n\leq 200000$。

做法:首先对于每个连通块,你可以暴力判断关键点在哪个连通块。这里的判断即是每次拿走一半大小的子树判一判,如果在这一半里,就递归进去继续做,如果不在,那么就继续做。如果都不在,说明当前枚举的连通块的根就是答案。然而这样做交互次数和时间复杂度都有点小炸,那你就点分优化一下这个过程,保证了交互次数和复杂度。

J Jiry Matchings

K K-pop Strings

题意:定义一个串重复两次后的串为$tandem$。给出一个$k$,定义一个长度为$n$的串合法当且仅当其中最长$tandem$长度小于$n-k$,求长度为$n$的合法串的数量。

数据范围:$1\leq n\leq 100,0\leq k\leq 16$。

做法:神奇的暴力题。

我们先预处理出所有合法的长度及其位置,是否合法利用并查集维护相同的串的连通性即可。然后呢,直接暴搜所有合法长度和位置,一旦搜出不合法串就退出,并查集带撤销即可。这样复杂度显然错的,然后你$rand\ shuffle$一样所有合法长度及其位置,就能过了。好玄学啊。