牛客杂题选做.
牛客练习赛138
F
逆天F构造…
构造一个[1,n]的排列使其构成的环满足任意两项之间差是奇质数.
结果告诉我只需要找到 $p+q=n$ 且 $p,q$ 都是奇质数的一对,然后就可以 [1,1+p,1+2p%n,…] .
最后用哥德巴赫猜想变种证明的,真神秘.
G
对于给定的 $n,k$ 计算
这个题乍一看无从下手,再一看k只有 $100$ 而n有1e7.
首先考虑特殊情况:k=1,这就是 $2^{n}-1$ .
对于k=2有
考虑二项式定理,上面就是 $(x+1)^n$ 的 $x$ 项的系数.
于是对于更普遍的情况,有:
答案是 $x$ 的系数.
为什么模 $(x^k-1)$ 而不是模 $(x^k)$ ?
因为前者可以让 $x^k\equiv 1$ (也就是变成了循环多项式环)而后者会让 $x^k,x^{k+1},…\equiv 0$ 也就是多项式高位全部丢掉了.
最后对n套一个快速幂就能算出来答案了,复杂度 $O(T\log nk^2)$ .
某个典1
你有一个数列,每次可以选最大的几个数让他们-1,求你最多能做多少次操作.
这个题的结论是:对于两个元素,公式如下(假设 $a_1$ 是数列 $a$ 中最大的元素):
对于三个元素,可以做拓展如下:
四个元素同理:
河南萌新3
随便整一场河南萌新赛看看什么样.
A
给一个数列,求长度至少为l的连续子串的最大平均值.
二分答案,然后对数列减掉答案剩下的东西做一个前缀和,然后根据前缀和的原理取前缀min直接检查即可.
C
给一棵树,要你对每个点算出除了该节点子树和该节点到根节点1的简单路径之外所有节点的gcd(如下图5的答案就是dat[4],2的ans是0),1e5.1
2
31-3-2-4
|
5
研究树的好题:我们在dfs的时候发现,这一个点的gcd会被切成两部分:dfs前面和dfs后面的,所以考虑拼起来:
首先维护dfs顺序,发现答案是退出dfs节点的gcd.
所以直接正着dfs一遍,再倒着dfs一遍即可.
D
选一个点之前必须选路上的所有父节点,其实就是裸的前置条件背包(好好复习背包九讲)
I
给两个数组ab代表两个环,上面的可以旋转,问你最大能匹配上多少个.
拆贡献:对于每一个数字枚举在b中出现哪些,意味着在这些点会有贡献,贡献最后加一起取max即可.
J
第一次随机选,然后在同一行选一个,然后再在上一个元素同一列选一个…直到最后选无可选,问是否存在一个方式使选出来的元素抑或和不是0.
以 每行每列 为元素建边,上述选点方式可以被抽象成在图上找简单环.
然后使用带权并查集维护即可.由于抑或和是可撤销的,所以维护节点到根节点的抑或和,然后直接抑或即可.
时刻 记得边权维护的是”当前根节点”到该点的权值,即使实际上根节点不是这个,比如1->2->3,1的实际根节点假设是2,那么只维护1到2的信息,在查询1的根节点时发现不是2的时候要及时更新,递归解决.
M
给两个数列ab,可以任选下标i,问最大的sum ai=sum bi的sum ai是多少.(n1e4,ab都是1e4)
其实就是一个背包,val是他俩相减,w是a(或者b),最后答案就是0点的最大值.
回顾:背包问题可以把数组初始化成-inf(极小值)让背包操作只对某个单独的点生效…