牛客挑战赛68题解

Problem A

给出正整数$nn$，求最小的正整数$kk$，使得对于$i=1i=1$至$nn$，$k!k!$均为$ii$的倍数。

$n\le 1e9n\; \backslash leq\; 1e9$，数据组数$T\le 1e4T\; \backslash leq\; 1e4$

Solution： 记$f(n)f(n)$的值为小于等于$nn$中最大的质数。 显然的必有$kk$ $>=>=$ $f(n)f(n)$。我们指出： $n=1n=1$ or $n=4,k=nn=4,k=n$; $elseelse$ $k=f(n)k=f(n)$； 该结论可以由打表观察得到，证明由伯特兰－切比雪夫定理结合对$k\mathrm{！}k！$素因子幂次的估计即可得到。

现在我们思考如何得到f(n)。熟知的素数间距是O(logn)的,而事实上在$1e91e9$的范围中素数间距不超过$300300$。 故对于n，由n出发从大到小的对于每个数进行$MRMR$素性检测，$lognlogn$次即可得到答案。 总时间复杂度$O(300\ast T\ast \log n)O(300*T*\; \backslash log\; n)$。或者预处理出所有小于等于sqrt(n)的素数进行枚举也可以通过本题。直接暴力$sqrt(n)sqrt(n)$的枚举不能通过。 注意：本题的$nn$较小，所以不会爆long long也更没必要使用龟速乘。如果你使用了带龟速乘的$MRMR$板子，自然无法通过。

Problem B

$nn$个正整数$a_{1}a\_1$至$a_{n}a\_n$,两两不同。判断是否存在，使得存在一个圆外切四边形，其四条边长度分别为$a_x\mathrm{，}{a}_y\mathrm{，}{a}_{z}a\_x，a\_y，a\_z$和$a_{w}a\_w$。

圆外切四边形定义见：https://zh.m.wikipedia.org/wiki/%E5%9C%86%E5%A4%96%E5%88%87%E5%9B%9B%E8%BE%B9%E5%BD%A2

$4\le n\le 100000,a_i\le 20000004\; \backslash leq\; n\; \backslash leq\; 100000,\; a\_i\; \backslash leq\; 2000000$

输出YES or NO

Solution: 手玩或者由切线性质可得，一个凸四边形是圆外切四边形当且仅当该四边形的对边之和相等。故问题转化为所给数列中是否存在四个不同的数 $a\mathrm{，}b\mathrm{，}c\mathrm{，}da，b，c，d$使得$a+b=c+da+b=c+d$ 。这是抽屉原理经典模型，暴力枚举即可。时间复杂度$O(\max (a_i))O(\; \backslash max\; (a\_i))$。作为签到题，为了让大家有一个友好的参赛体验，FFT也可以通过。

Problem C

给一个$nn$个点的简单无向图，点$ii$有点权$a_{i}a\_i$，点$ii$与点$jj$之间的连边（如果存在）有边权$e_{ij}e\_\{ij\}$。定义一条路径的花费是该路径上的点权之和以及边权之和的乘积。求花费最小的回路。

$1\le n\le 20,1\le a_i\le 1e6,1\le e_{ij}\le 1e61\; \backslash le\; n\; \backslash le\; 20,\; 1\; \backslash le\; a\_i\; \backslash le\; 1e6,\; 1\; \backslash le\; e\_\{ij\}\; \backslash le\; 1e6$

Solution:

看点的数量（$n\le 20n\backslash le20$）应该能想到状压DP。首先想到用 $f[st][i]f[st][i]$ 表示经过点集 $stst$且最后一个点是 $ii$ 的最小边权和，可以算花费最小的路径。由于环的起点可以是该环中任意一个点，只需指定点集 $stst$ 中的某一个点为起点（如 $stst$ 中最小的点）进行上述===即可，时间复杂度 $O(n^2{2}^n)O(n^22^n)$。

Problem D

在一个$1\ast (2\ast n+1)1*(2*n+1)$的方格表上，A和B做游戏。初始状态下有些格为黑色，其他的格里则为白色。初始状态将由一个长为$2\ast n+12*n+1$的01字符串给出。

A，B两人轮流执行以下两种操作之一，A先手：

1. 将一个白色格子染黑。
2. 将一个黑色格子染白，并且将该格子左侧最近的白色格子和该格子右侧最近的白色格子染黑。（若存在）

如果某次某玩家操作之后，当前方格表的黑白染色状态跟之前游戏的某一时刻的方格表的黑白染色状态重复（包括初始状态），则该玩家输掉游戏。问谁有必胜策略。

$n\le 100000n\; \backslash leq\; 100000$

Solution：

Part1

首先我们注意到，黑色格子数$>=2\ast n>=2*n$时，共有$2\ast n+22*n+2$个不同状态($2\ast n+12*n+1$种$2\ast n2*n$个黑格状态以及一个全黑格状态)，且这$2\ast n+22*n+2$状态可以互相转换，并且不能转换到其他黑色格子数的状态了。所以：

1，当初始状态黑格$>=2\ast n>=2*n$时，先手必胜。

2，否则注意到一但有人操作后黑格$>=2\ast n>=2*n$，他便必败。故双方均要保证自己操作后黑格数仍然小于等于$2\ast n-12*n-1$。 下面继续对该种情况进行讨论。

Part2

我们给方格表从左到右编号$11$到$2\ast n+12*n+1$. 记f(S)的值为当染色状态为S下所有白格的编号的和

首先我们指出该种情况下：S为必败状态当且仅当f(S)是2*n+2的倍数，分析与证明见下： (该结论也可以对于较小的n进行状压dp发掘所有的必胜态后找规律得出)

1，注意到在双方均保证自己操作后黑格数小于等于2*n-1的前提下，每次操作后要么黑格子个数增加，要么方格表最左侧的白格与最右侧的白格子的距离递增，故此时所有的局面均不同。故我们可以忽略“局面不重复”的制约。

原问题等价于AB轮流操作，谁先使黑格数目大于等于$2\ast n2*n$者输。

对于某个局面下，该玩家恰有$2\ast n+12*n+1$种不同的操作方式(即对每个$2\ast n+12*n+1$格子分别操作)。

观察这$2\ast n+12*n+1$种操作对f(S)的变化，发现：对于位置$ii$若其为白色，对其操作有：$f(S\mathrm{’})-=if(S’)-=i$;

对于某个极长的连续黑色格子段$i\mathrm{，}i+1\mathrm{，}\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{，}ji，i+1，...，j$发现对其中的位置操作有$f(S\mathrm{’})-=i+j-kf(S’)-=i+j-k$；

所以这$2\ast n+12*n+1$种操作对$f(S)f(S)$的变化量是$11$到$2\ast n+12*n+1$的一个排列。即问题转化为每次玩家可以选择一个$11$到$2\ast n+12*n+1$的$ii$减到$f(S)f(S)$上面。这就和经典的博弈模型相似了。

最后我们再分析最终必输态$S_{0}S\_0$，即有$2\ast n2*n$个格子为黑色的情况下f$(S_0)(S\_0)$的特征，此时$f(S_0)=if(S\_0)\; =i$。其中$i=1,2,\mathrm{.}\mathrm{.}2\ast n+1i=1,2,..2*n+1$。即若某位玩家操作完之后，有,他便必输。现在我们就转化成了经典模型。

发现对每个必输态都有$f(S_{0}f(S\_0$)不是$(2\ast n+2)(2*n+2)$的倍数。这是因为若某个玩家可以一直维持在他操作后$f(S)f(S)$模$2\ast n+22*n+2$余$00$,则他永远不会进入必输态。而每次某玩家又是任选$11$到$2\ast n+12*n+1$中任何一个数减在$f(S)f(S)$上，说明当且仅当轮到他操作时$f(S)f(S)$模$2\ast n+22*n+2$余$00$他才必输。否则他均可以使得他操作后$f(S^{\mathrm{\prime }})f(S\text{'})$模$2\ast n+22*n+2$余$00$然后一直维持这个状态。这样我们就证明了结论。

综上只需对题目的01串扫一遍即可，时间复杂度$O(n)O(n)$。

作者：superguymj 链接：https://ac.nowcoder.com/discuss/1160431?type=101&order=0&pos=7&page=1&channel=-1&source_id=1 来源：牛客网

E. 首先二分答案，紧接着贪心划分字符串。考虑这样一个子问题，给定一个字符串，求它的val是多少。可以建pam，将每个回文串的right集合的最大最小值处理出来，将其之间的所有w值+1。因此可以线性求出一个字符串的val值。 那么我们只需要二分每次划分的长度即可。

F. 对括号序列建立猫树。每个分治区间的括号匹配形成了一颗树结构。修改操作为修改某个点的值，询问操作为查询树链的最大值。 作者：superguymj 链接：https://ac.nowcoder.com/discuss/1160431?type=101&order=0&pos=8&page=1&channel=-1&source_id=1 来源：牛客网

F题解补充：

做法一：

题目怎么说，你就怎么写。（O(n^2)）

做法二：

每只括号都能存活。直接用线段树维护区间最大值。（O(nlogn)）

做法三：

存活的括号一定是原序列中连续的一段。直接用线段树维护区间最大值。(O(nlogn))

做法四：

如果已知[l,r]的存活括号序列，将l±1或将r±1都只会增加或减少一直存活的括号（O(1)）。所以可以使用莫队算法，用双端队列维护存活括号，用值域分块维护最大值（O(m√n)）。如果用堆维护最大值则不能获得全部分数。

做法五：

直接上线段树，每个节点维护区间存活括号以及1类括号的后缀最大攻击力和0类括号的前缀最大攻击力。因为每只括号最多出现在logn个区间内，所以建树的复杂度为O(nlogn)。查询需遍历O(logn)个区间，O(1)合并区间信息。故总复杂度为O((n+m)logn)。

做法六：

在做法五的基础上，每个节点再开一棵线段树维护存活括号的攻击力。建树O（nlog^2n），查询O（mlog^2n）。

做法七：

单独考虑1类括号。令f[i]为区间[1,i]中的1类括号数-0类括号数。括号i在区间[l,r]中能存活(i∈[l,r])当且仅当f[i]>f[l-1]且不存在一个j∈[l,i)满足f[j]=f[i]。也即每个区间的存活括号中不存在f值相等的。树套树外层以位置为下标，内层以f值为下标(内层线段树需动态开点)，维护区间存活括号的攻击力以及区间最大f值（建树O(nlog^2n)）。查询开始时，令minf=f[l-1]+1，从左到右遍历每个需要遍历的区间，查询[minf,+∞)的存活括号的攻击力，并将minf改为区间maxf+1。0类括号同理。查询复杂度为（O(nlog^2n)）。

做法八：

将01序列视为一段dfs序。0为入栈，1为出栈。一段01序列则表示树上的一条链。本题操作即为修改树结点权值和查询树链最大权值。树链剖分即可。（O(nlog^2n)）

反思：

做法七中的f[i]实际上是做法八中的树结点的深度。因此，树上的一条链其实可以转化为dfs序和深度的二维平面上同一深度中dfs序最靠前/靠后的结点的集合（虽然这似乎没什么用。实测做法七的常数是做法八的两倍）。