Difference between revisions of "2019 Multi-University,Nowcoder Day 4"
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
Line 51: | Line 51: | ||
而 $m$ 所在的块,左半边 $[x,m]$ 合成一块显然成立,右半边 $[m+1,y]$ ,需要按照上面的要求不断的裂开。 | 而 $m$ 所在的块,左半边 $[x,m]$ 合成一块显然成立,右半边 $[m+1,y]$ ,需要按照上面的要求不断的裂开。 | ||
− | 维护这个块的归并可以用 treap | + | 维护这个块的归并可以用 treap ,我们用权值来表示坐标,对于每一块的开头一定是连续一段的 max ,再维护一个区间 max 就可以了。 |
== Problem G == | == Problem G == |
Revision as of 15:51, 27 July 2019
Problem A
Solved by Weaver_zhu. 01:43:34 (+)
Problem B
Upsolved by Weaver_zhu. (-5)
Problem C
Solved by Kilo_5723. 03:23:47 (+2)
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)
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
Unsolved.
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)
Problem K
Solved by Xiejiadong. 00:19:37 (+)
题意:求字符串的子串中有多少 $300$ 的倍数。
题解:$300$ 的倍数就是末尾有两个 $0$ ,前面的数字和是 $3$ 的倍数就好了。
我们把当前数字后面跟着两个 $0$ 的位置称为有效的结束位置,把所有的有效结束位置的前缀和模 $3$ 扔进 map 。
然后枚举开头,判断有多少同值的有效结尾就好了。
还需要特判一个 $0$ 和两个连续 $0$ 的情况。