Difference between revisions of "2019 Multi-University,Nowcoder Day 4"

From EOJ Wiki
Jump to navigation Jump to search
 
(13 intermediate revisions by the same user not shown)
Line 6: Line 6:
  
 
Upsolved by Weaver_zhu. (-5)
 
Upsolved by Weaver_zhu. (-5)
 +
 +
题意:线性基求交模板题
 +
 +
题解:抄模板,然后线段树求逻辑取和,不用真的求出区间线性基,而是在递归查询里面搞,就能少个log
  
 
== Problem C ==
 
== Problem C ==
Line 43: Line 47:
 
题解:对 $x$ 的二进制表达式中的 $1$ 进行分类:
 
题解:对 $x$ 的二进制表达式中的 $1$ 进行分类:
  
二进制下每一位的权值 ${\rm} mod 3$ 只可能是 $1$ 或 $2$。我们令 $m$ 的二进制中权值为 $1$ 的 $1$ 的数量为 $cnt1(m)$,权值为 $2$ 的数量为 $cnt2(m)$。令 $cnt1(x)=p,cnt2(x)=q$:
+
二进制下每一位的权值 ${\rm mod} \; 3$ 只可能是 $1$ 或 $2$。我们令 $m$ 的二进制中权值为 $1$ 的 $1$ 的数量为 $cnt1(m)$,权值为 $2$ 的数量为 $cnt2(m)$。令 $cnt1(x)=p,cnt2(x)=q$:
  
我们考虑满足 $a_1\;{\rm or}\;a_2\;{\rm or}\dots{\rm or}\;a_n=y$,其中 $cnt1(y)\le p,cnt2(y) \le q$ 的情况数,我们可以枚举 $cnt1(a_i)$ 和 $cnt2(a_i)$。
+
我们考虑满足 $a_1\;{\rm or}\;a_2\;{\rm or}\dots{\rm or}\;a_n=y,cnt1(y)\le p,cnt2(y) \le q$ 的情况数,我们可以枚举 $cnt1(a_i)$ 和 $cnt2(a_i)$。
  
 
对于每一个 $a_i$,都满足两个限制条件:$cnt1(a_i) \le p,cnt2(a_i) \le q$ 和 $cnt1(a_i)+2 \cdot cnt2(a_i)\;{\rm mod }\;3=0$。因此,通过枚举 $i=cnt1(a_k),j=cnt2(a_k)$ 以及这些二进制位可能处在的位置,每一个 $a_k$ 可能的不同值的数量就是 $P(p,q)=\sum_{i=0}^p\sum_{j=0}^q C_{p}^{i} \cdot C_{q}^{j}(i+2\cdot j\;{\rm mod}\;3=0)$。
 
对于每一个 $a_i$,都满足两个限制条件:$cnt1(a_i) \le p,cnt2(a_i) \le q$ 和 $cnt1(a_i)+2 \cdot cnt2(a_i)\;{\rm mod }\;3=0$。因此,通过枚举 $i=cnt1(a_k),j=cnt2(a_k)$ 以及这些二进制位可能处在的位置,每一个 $a_k$ 可能的不同值的数量就是 $P(p,q)=\sum_{i=0}^p\sum_{j=0}^q C_{p}^{i} \cdot C_{q}^{j}(i+2\cdot j\;{\rm mod}\;3=0)$。
  
因此,满足 $a_1\;{\rm or}\;a_2\;{\rm or}\dots{\rm or}\;a_n=y$,其中 $cnt1(y)\le p,cnt2(y) \le q$ 的情况数就是 $P(p,q)^n$。而满足 $a_1\;{\rm or}\;a_2\;{\rm or}\dots{\rm or}\;a_n=x$ 的情况数 $ans(p,q)=P(p,q)^n-\sum_{i=0}^p\sum_{j=0}^q ans(i,j) ((i,j) \neq (p,q))$。
+
因此,满足 $a_1\;{\rm or}\;a_2\;{\rm or}\dots{\rm or}\;a_n=y,cnt1(y)\le p,cnt2(y) \le q$ 的情况数就是 $P(p,q)^n$。而满足 $a_1\;{\rm or}\;a_2\;{\rm or}\dots{\rm or}\;a_n=x$ 的情况数 $ans(p,q)=P(p,q)^n-\sum_{i=0}^p\sum_{j=0}^q ans(i,j) ((i,j) \neq (p,q))$。
  
 
逐个算出就 $ans(i,j)$ 能求得 $ans(p,q)$。
 
逐个算出就 $ans(i,j)$ 能求得 $ans(p,q)$。
Line 80: Line 84:
  
 
Upsolved by Kilo_5723.
 
Upsolved by Kilo_5723.
 +
 +
题意:题目给出三个随机数生成器,每个以一个 $[0,10^9]$ 的数为种子生成一个长度为 $2000$ 的随机 $0/1$ 序列,现在给定 $1000$ 个长度为 $2000$ 的二进制串,询问分别是哪个生成器产生的。
 +
 +
题解:令三个生成器以 $seed$ 为种子生成的序列分别为 $gen_0(seed),gen_1(seed),gen_2(seed)$,第 $i$ 位分别为 $gen_0(seed)[i],gen_1(seed)[i],gen_2(seed)[i]$,对于三个生成器,分别找规律。
 +
 +
我们发现,对任意的 $gen2(a),gen2(b)$,都有 $gen2(a \;{\rm xor} \; b)[i]=gen2(a)[i]\;{\rm xor} \; gen2(b)[i]$。因此,对任意的 $seed$,$gen_2(seed)$ 都是 $gen_2(2^i)(0 \le i <30)$ 的线性组合,预处理 $gen_2(2^i)$ 后用线性基就能判断二进制串是否由 $gen_2$ 生成。
 +
 +
$gen_0$ 是输出当前 $seed$ 的第 $28$ 位二进制位,并用当前 $seed$ 映射出下一个 $seed$($seed'=214013 \cdot seed +2531011\; {\rm mod} \;2^{28}$)。经过实验,我们发现 $seed$ 变化的周期是 $2^{28}$。也就是说,一个由 $gen_0$ 生成的二进制串,一定是一个长度为 $2^{28}$ 的 $0/1$ 二进制串的长度为 $2000$ 的子串。我们令这个长度为 $2^{28}$ 的串为原串。
 +
 +
根据模拟结果,我们发现,一个长度为 $2000$ 的二进制串含有一个特定子串,在长度超过 $20$ 后几乎是不可能事件。因此,我们只要每隔 $1024$ 位选出原串的 $64$ 位单位串,就能保证每个长度为 $2000$ 的子串都包含至少一个单位串,同时含有这样单位串的长为 $2000$ 的串一定由 $gen_0$ 生成。这样的单位串的数量约为 $2 \cdot 10^5$。要判断一个串是否由 $gen_0$ 生成,只要对其每一个 $64$ 位子串查看其是否为单位串即可。如果都不是,则肯定不由 $gen_0$ 生成,否则则有极大概率由 $gen_0$ 生成。
 +
 +
同时,由于 $gen_0$ 的映射由模意义下的乘法和加法构成,我们可以算出 $seed$ 映射 $1024$ 次之后的值为 $108253185 \cdot seed + 238953472\; {\rm mod} \;2^{28}$,极大加速了预处理单位串的速度。
 +
 +
在判断完不由 $gen_2$ 和 $gen_0$ 生成之后,就只可能由 $gen_1$ 生成了。
  
 
== Problem I ==
 
== Problem I ==
Line 98: Line 116:
  
 
Solved by Kilo_5723. 01:39:30 (+3)
 
Solved by Kilo_5723. 01:39:30 (+3)
 +
 +
题意:给定一个无向图,可以将其中的 $k$ 条边的长度设为 $0$,求最短路。
 +
 +
题解:拆点建图。将图复制出 $k+1$ 层,对每一条边添加一条从第 $i$ 层通往 $i+1$ 层的长度为 $0$ 的复制,到每一层的终点的最短路的最小值就是答案。
  
 
== Problem K ==
 
== Problem K ==

Latest revision as of 09:00, 29 July 2019

Problem A

Solved by Weaver_zhu. 01:43:34 (+)

Problem B

Upsolved by Weaver_zhu. (-5)

题意:线性基求交模板题

题解:抄模板,然后线段树求逻辑取和,不用真的求出区间线性基,而是在递归查询里面搞,就能少个log

Problem C

Solved by Kilo_5723. 03:23:47 (+2)

题意:给定两个序列 $\{a_n\},\{b_n\}$,求出 $max_{1 \le l \le r \le n}(min(a_{l\dots r}) \cdot sum(b_{l \dots r}))$。

题解:考虑枚举 $a_i$ 作为区间最小值的所有情况。我们发现,如果从大到小将每个 $a_i$ 插入,那以 $a_i$ 作为区间最小值的区间 $[l,r]$ 肯定是包含 $a_i$ 的,$a_i$ 附近已经插入的连续点构成的段落。

考虑维护区间左/右端开始的和极大/极小的 $b_i$ 连续段落和以及区间和,我们发现,每次插入一个 $a_i$,只要查看 $i-1,i+1$ 是不是区间的左右端点,如果是,则将答案根据 $a_i$ 的正负加上 $a_i \cdot$ 左/右端开始的和极大/极小的 $b_i$ 连续段落和,并且将左右的区间和 $[i,i]$ 合并即可。合并的操作是 $O(1)$ 的。

Problem D

Solved by Xiejiadong. 01:23:59 (+)

题意:求最小数量的三的倍数的数,使得他们位或的结果是 $a$ 。

题解:大力分类讨论。我们可以发现二进制下,每一位模 $3$ 是 $1,2,1,2,\cdots $

我们不妨从总和下手:

  • 总和是 $3$ 的倍数,直接输出;
  • 总和是 $3$ 的倍数多 $1$ ,如果有 $1$ 去掉 $1$ 或者去掉两个 $2$ ,然后去掉的数考虑用 $1,1$ 或者 $2$ 去组成三的倍数,可以证明一定存在;
  • 总和是 $3$ 的倍数多 $2$ ,如果有 $2$ 去掉 $2$ 或者去掉两个 $1$ ,然后去掉的数考虑用 $2,2$ 或者 $1$ 去组成三的倍数,可以证明一定存在。

所以发现其实最多只有两个数就能搞出来了。

Problem E

Solved by Kilo_5723. 04:02:11 (+1)

题意:求满足 $a_1\;{\rm or}\;a_2\;{\rm or}\dots{\rm or}\;a_n=x$ 的序列 ${a_n}$ 的数量,其中 ${\rm or}$ 是二进制下的或运算。

题解:对 $x$ 的二进制表达式中的 $1$ 进行分类:

二进制下每一位的权值 ${\rm mod} \; 3$ 只可能是 $1$ 或 $2$。我们令 $m$ 的二进制中权值为 $1$ 的 $1$ 的数量为 $cnt1(m)$,权值为 $2$ 的数量为 $cnt2(m)$。令 $cnt1(x)=p,cnt2(x)=q$:

我们考虑满足 $a_1\;{\rm or}\;a_2\;{\rm or}\dots{\rm or}\;a_n=y,cnt1(y)\le p,cnt2(y) \le q$ 的情况数,我们可以枚举 $cnt1(a_i)$ 和 $cnt2(a_i)$。

对于每一个 $a_i$,都满足两个限制条件:$cnt1(a_i) \le p,cnt2(a_i) \le q$ 和 $cnt1(a_i)+2 \cdot cnt2(a_i)\;{\rm mod }\;3=0$。因此,通过枚举 $i=cnt1(a_k),j=cnt2(a_k)$ 以及这些二进制位可能处在的位置,每一个 $a_k$ 可能的不同值的数量就是 $P(p,q)=\sum_{i=0}^p\sum_{j=0}^q C_{p}^{i} \cdot C_{q}^{j}(i+2\cdot j\;{\rm mod}\;3=0)$。

因此,满足 $a_1\;{\rm or}\;a_2\;{\rm or}\dots{\rm or}\;a_n=y,cnt1(y)\le p,cnt2(y) \le q$ 的情况数就是 $P(p,q)^n$。而满足 $a_1\;{\rm or}\;a_2\;{\rm or}\dots{\rm or}\;a_n=x$ 的情况数 $ans(p,q)=P(p,q)^n-\sum_{i=0}^p\sum_{j=0}^q ans(i,j) ((i,j) \neq (p,q))$。

逐个算出就 $ans(i,j)$ 能求得 $ans(p,q)$。

Problem F

Upsolved by Xiejiadong.

题意:要求支持两个操作:

  • 对于区间 $[1,r]$ 类归并(本身是没有顺序的)
  • 询问某一个位置上的数

题解:

可以发现 merge 函数的规律,我们可以把两个需要归并的数列分块,每一块的第一个数都是最大值,之后连续的 $\le $ 他的数都在同一块,因为一旦第一个数比下面一个数列小了,这一整块都会被放入最后的数列的连续位置。

于是就考虑维护这些块,对于右端点 $r$ 所在的块,我们可以直接裂为 $[x,r],[r+1,y]$ ,在处理完 $[1,r]$ 的归并以后再合并 $[1,r],[r+1,y]$ 即可。

而 $m$ 所在的块,左半边 $[x,m]$ 合成一块显然成立,右半边 $[m+1,y]$ ,需要按照上面的要求不断的裂开。

维护这个块的归并可以用 treap ,我们用权值来表示坐标,对于每一块的开头一定是连续一段的 max ,再维护一个区间 max 就可以了。

Problem G

Unsolved.

Problem H

Upsolved by Kilo_5723.

题意:题目给出三个随机数生成器,每个以一个 $[0,10^9]$ 的数为种子生成一个长度为 $2000$ 的随机 $0/1$ 序列,现在给定 $1000$ 个长度为 $2000$ 的二进制串,询问分别是哪个生成器产生的。

题解:令三个生成器以 $seed$ 为种子生成的序列分别为 $gen_0(seed),gen_1(seed),gen_2(seed)$,第 $i$ 位分别为 $gen_0(seed)[i],gen_1(seed)[i],gen_2(seed)[i]$,对于三个生成器,分别找规律。

我们发现,对任意的 $gen2(a),gen2(b)$,都有 $gen2(a \;{\rm xor} \; b)[i]=gen2(a)[i]\;{\rm xor} \; gen2(b)[i]$。因此,对任意的 $seed$,$gen_2(seed)$ 都是 $gen_2(2^i)(0 \le i <30)$ 的线性组合,预处理 $gen_2(2^i)$ 后用线性基就能判断二进制串是否由 $gen_2$ 生成。

$gen_0$ 是输出当前 $seed$ 的第 $28$ 位二进制位,并用当前 $seed$ 映射出下一个 $seed$($seed'=214013 \cdot seed +2531011\; {\rm mod} \;2^{28}$)。经过实验,我们发现 $seed$ 变化的周期是 $2^{28}$。也就是说,一个由 $gen_0$ 生成的二进制串,一定是一个长度为 $2^{28}$ 的 $0/1$ 二进制串的长度为 $2000$ 的子串。我们令这个长度为 $2^{28}$ 的串为原串。

根据模拟结果,我们发现,一个长度为 $2000$ 的二进制串含有一个特定子串,在长度超过 $20$ 后几乎是不可能事件。因此,我们只要每隔 $1024$ 位选出原串的 $64$ 位单位串,就能保证每个长度为 $2000$ 的子串都包含至少一个单位串,同时含有这样单位串的长为 $2000$ 的串一定由 $gen_0$ 生成。这样的单位串的数量约为 $2 \cdot 10^5$。要判断一个串是否由 $gen_0$ 生成,只要对其每一个 $64$ 位子串查看其是否为单位串即可。如果都不是,则肯定不由 $gen_0$ 生成,否则则有极大概率由 $gen_0$ 生成。

同时,由于 $gen_0$ 的映射由模意义下的乘法和加法构成,我们可以算出 $seed$ 映射 $1024$ 次之后的值为 $108253185 \cdot seed + 238953472\; {\rm mod} \;2^{28}$,极大加速了预处理单位串的速度。

在判断完不由 $gen_2$ 和 $gen_0$ 生成之后,就只可能由 $gen_1$ 生成了。

Problem I

Solved by Xiejiadong. 02:47:24 (+1)

题意:求本质不同的字符串个数,正串和反串相同的串只算一个。

题解:考虑一下就不难想到,正串、反串分别插入 SAM 算一算就好了。但是发现回文串会重复计数。

我们不妨假设有 $x$ 个回文串,有 $y$ 个串的正串和反串是不相同的,有 $z$ 个串的正串和反串是相同的(不包括回文串)。

于是有,正串插入 SAM 后本质不同的串有 $x+y+z$ ,反串也插入以后,本质不同的串有 $x+2y+z$ ,减一减就能得到 $y$ 。

本质不同的回文串个数,建一下 PAM ,结点个数就是了,于是 $z$ 也算出来了,答案显然就是 $x+y+ \frac{z}{2}$ 。

Problem J

Solved by Kilo_5723. 01:39:30 (+3)

题意:给定一个无向图,可以将其中的 $k$ 条边的长度设为 $0$,求最短路。

题解:拆点建图。将图复制出 $k+1$ 层,对每一条边添加一条从第 $i$ 层通往 $i+1$ 层的长度为 $0$ 的复制,到每一层的终点的最短路的最小值就是答案。

Problem K

Solved by Xiejiadong. 00:19:37 (+)

题意:求字符串的子串中有多少 $300$ 的倍数。

题解:$300$ 的倍数就是末尾有两个 $0$ ,前面的数字和是 $3$ 的倍数就好了。

我们把当前数字后面跟着两个 $0$ 的位置称为有效的结束位置,把所有的有效结束位置的前缀和模 $3$ 扔进 map 。

然后枚举开头,判断有多少同值的有效结尾就好了。

还需要特判一个 $0$ 和两个连续 $0$ 的情况。