牛客暑期多校训练3

来自PC Wiki
跳到导航 跳到搜索

Records

Contest

Solutions

A

每个点随机一个值,我们可以通过集合异或是否相等判断集合是否相等.

考虑如何维护这个异或,我们把点按度数分块,小点可以每次现场查询每条边(使用BIT支持查询这条边是否存在).

大点则在每次修改操作时维护值,可以按顺序记录大点的连边编号以及对应的点的随机值,每次修改相当于将大点的答案异或上一个区间的异或值.

B

签到题,子序列就是01个数的较小值乘2,子串就把0当-1,用前缀和算区间和为0的最长区间即可.

C

D

显然p=2或5时答案为0

根据费马小定理可知$$i^j$$在$$mod\ (p-1)$$意义下仍成立

寻找最小循环节x使得$$A(x)\ mod\ p=0$$,而$$A(n)=1111...=\frac {10^n-1} 9=0(mod\ p)$$,所以循环节x一定是$$\phi(9p)$$的约数,暴力枚举可得x

计算答案时固定j,计算出对应的乘积pr后用n去整除

指数最大30,所以j大于30时值可以直接计算

E

F

G

对于序列a来说,若$$\max_{1\leq i \leq n}\{a_i\} \leq \frac 1 2 ×\sum^n_{i=1}a_i$$,则必胜,否则必败

考虑枚举每个ai作为最大值,先向左扩展,然后向右扩展时利用单调窗口,由于每个点被扩展时都相当于翻倍所以被扩展次数不超过log w次

复杂度$$O(n\log w)$$

H

I

参照题解.

J

我们考虑数组其实是有序的,排序的依据是每个Block最近一次出现的时间.

利用Set维护这个东西即可.