“科林明伦杯”哈尔滨理工大学第12届程序设计竞赛题解

A. 割韭菜

此题考查线段树，首先不难发现生长速度快的韭菜在整个过程中都会大于等于生长慢的韭菜的高度。这样按照生长速度排序后，数列永远单调。

在线段树上的区间维护以下值：

①最后一棵韭菜的高度$aa$

②上次收割日期$bb$

③总的韭菜高度和$cc$

④总的生长速度和**$dd$**

⑤收割标记$DD$和$BB$

查询时只需要判断区间的最后一棵韭菜的高度$aa$与$BB$的关系，结束，$a>Ba>B$时，若左儿子的则直接查询右区间，若左儿子的$a>Ba>B$直接加上右区间的贡献，继续查询左儿子即可。

复杂度：$O(nlogn)O(nlogn)$

B .抓球

签到题，q次取球为独立事件，每次取球的概率为$\frac{C(n,k)}{C(n+m,k)}\backslash frac\; \{C(n,k)\}\; \{C(n+m,k)\}$，所以答案为$(\frac{C(n,k)}{C(n+m,k)}{)}^q(\backslash frac\; \{C(n,k)\}\{C(n+m,k)\})^q$，注意快速幂，组合数，逆元的使用。

复杂度：$O(T\ast log(q))O(T*log(q))$

C .迷宫

定期重构，当我们手中要插入的点的个数小于一个阈值时，我们就直接暴力对每个点求一下曼哈顿距离就可以了，当大于阈值时一次性将手中的点全部拿出来$bfsbfs$，然后手中的点的个数清零就好了。

复杂度证明：假设阈值是E，那么插入的复杂度是$q\ast n\ast m\ast h\mathrm{/}Eq*n*m*h/E$,询问的复杂度是$q\ast Eq*E$，所以总的复杂度是$qnmh\mathrm{/}E+qEqnmh/E+qE$,根据均值不等式可知当$E=\sqrt{n\ast m\ast h}E=\backslash sqrt\{n*m*h\}$时理论复杂度最低。

复杂度：$O(q\ast \sqrt{n\ast m\ast h})O(q*\backslash sqrt\{n*m*h\})$

D. $gkgk$的爬山之旅

首先要维护出当前点能到达的点集合，以左侧为例，假设当前在i座山，存在这样一些满足条件的点集$j,kj,k$ 其中。注意到g数组是单调的，很显然我们从$i->k->ji->k->j$对答案的贡献是一样的, 因为$abs(g[i]-g[k])+abs(g[k]-g[j])abs(g[i]-g[k])+abs(g[k]-g[j])$ $=abs(g[i]-g[j])=\; abs(g[i]-g[j])$，考虑到走到k号点之后还可能会往右跳再回到$ii$号点，此时很明显走到$kk$的点的决策是最优的，此时我们只需要维护左右两侧第一个能到达点的位置。很明显可以用单调栈，但是要注意当有一段区间高度相同的点出现时，很明显最左/右侧的点是最优决策点，因为不能在这段相同的区间来回走。

由于要求出每一个点出发的答案，而这些点至多经过其他点一次，所以记忆化搜索即可。

复杂度: $O(n)O(n)$

E. $gkgk$的字符串

由于要保证相邻字符不相同，只需要贪心的向‘?’的位置填‘a’或‘b’或‘c’即可。

复杂度：$O(n)O(n)$

F. $gkgk$的树

本来要出一个树上的度数问题转化成网络流来解，后来验题的时候发现贪心也能过 (std假了)

贪心：$dfsdfs$的时候先考虑子树的影响即可，也可以优先从叶子节点开始处理。

复杂度：$O(n)O(n)$

网络流：把树看成二分图之后，可以建立S到col=1流量为k的边，col=2到T流量为k的边，跑完最大流之后流过的边就是剩余的边，答案就是$n-1-maxflown-1-maxflow$。(可以自己证明一下正确性)

复杂度：$O(n\ast \sqrt{n})O(n*\backslash sqrt\{n\})$

G. $gkgk$的数字游戏

要看出来题目中的公式是一个取模的过程，所以模拟一下就好。

复杂度：$O(T\ast log(max(n,m)))O(T*log(max(n,m)))$

H.进来DP 一种暴力的$dpdp$做法是令$f(i,j)f(i,j)$表示前$ii$个数组拿走$jj$个数的最大和，复杂度为$O(k\ast min(nk,{\sum }_{i=1}^{n}c[i]))O(k*min(nk,\backslash sum\_\{i=1\}^n\; c[i]))$ 但是注意到每个数组都是有序的，那么可以得到一个结论：在所有取了数的数组中，最多只有一个数组只拿走了一部分即。$b[i]b[i]$为第$ii$个数组拿走数字的个数 （证明：假设有两个数组$p,qp,q$分别拿走了那么此时我们将p数组少拿一个，q数组多拿一个，最后的结果一定不会变小）。

现在我们只需要枚举这个部分拿走的数组，然后对其他$(n-1)(n-1)$个数组跑01背包（以数组大小为权重，数组元素之和权值），得到$g(w)g(w)$为拿走w个数的最大和后。在枚举在这个数组拿走多少个和$g(w)g(w)$合并就可以。

暴力求解每个背包的复杂度为$O(n^{2}k+{\sum }_{i=1}^{n}c[i])O(n^2k+\backslash sum\_\{i=1\}^n\; c[i])$，但这过程中有很多的重复计算，一个常见的优化方式是使用分治来优化到$O(kn\log n)O(kn\backslash log\; n)$

把数组分成两半，在递归进入前半之前，把后半数组对$g(w)g(w)$数组的影响更新一下，然后在回溯时在取消此次修改。 这样一来，当我们的分治区间的长度为1时，我们就得到了其他数组进行01背包后的$g(w)g(w)$。 复杂度：$O(knlogn+{\sum }_{i=1}^{n}c[i])O(knlog\; n+\backslash sum\_\{i=1\}^nc[i])$

I.又AK了 想要总罚时最少，就要先写费时最少的题目。那么求出每道题的花费时间，从小到大排序在计算即可。 复杂度：$O(n\ast log(n))O(n*log(n))$

J.大数乘法

令$y={\sum }_{i=0}^{n}a[i]\ast 10^{i}y=\backslash sum\_\{i=0\}^\{n\}a[i]*10^i$ 那么$x^y={\prod }_{i=0}^n{x}^{a[i]\ast 10^i}={\prod }_{i=0}^n{x^{10^i}}^{a[i]}x^y=\backslash prod\_\{i=0\}^\{n\}x^\{a[i]*10^i\}=\backslash prod\_\{i=0\}^\{n\}\{\{x^\{10^i\}\}^\{a[i]\}\}$ 由于$0\le a[i]\le 90\backslash leq\; a[i]\backslash leq\; 9$ 所以只需预处理出$x^{10^i}\mathrm{\%}modx^\{10^i\}\backslash \%mod$的值然后对每一位暴力就可以了。 复杂度：$O(len(y)\ast 10)O(len(y)*10)$

K.蹦蹦炸弹 由于所有炸弹都在$xx$轴上，所以每次炸弹相遇只在相邻的两颗炸弹之间发生。那么我们把相邻两颗炸弹的相遇时间放进优先队列里，每次把堆顶的两颗炸弹删掉，然后找到这两颗炸弹左右两边的炸弹（set模拟或者并查集都可），把它们的相遇时间放进优先队列里不断模拟就好了。 复杂度：$O(n\ast log(n))O(n*log(n))$

L.NP-Hard 模拟,按位判断数字后求和比较就可以。 复杂度：$O(len(x))O(len(x))$