王清楚

2019-12-16 11:35 牛客运营

关注

【题解】＂新生赛＂长沙理工大学程序设计竞赛

A、Psycho-Pass

全场题，for一遍，然后计数器碰到1就++

B、happy card

一个 $\text{DP}$ 题，对于萌新来讲可以有的难度。
列出所有条件：人数 $\mathit n$ ，总的快乐牌 $\mathit{num}$ ，限制手牌 $\mathit m$
我们可以 $\text{DP}$ 的是：前 $\mathit i$ 个人在总牌数为 $\mathit j$ 的情况下，第 $\mathit i$ 个人拿 $\mathit k$ 张牌的最大幸福值。想想似乎和01背包有点儿类似，那么状态转移方程也就不难写出来了：

$\operatorname{dp}[i][j]=\max (\operatorname{dp}[i-1][j-k]+h[k], \operatorname{dp}[i][j])]$ 当然我们的第一维其实可以直接滚动掉的。。

其实算法还可以再进行时间的优化，将其化为 $n^2$ 算法。

实际上人数是一个无用条件，我们知道总的快乐牌数，那么人数一定会大于等于这个数。这种情况的所有必要条件就是：总的快乐牌 $\mathit{num}$ ，限制牌堆 $\mathit m$ ，那么可以化成以下情景：知道总的牌数 $\mathit{num}$ ，问在限制每堆最大牌数为 $\mathit m$ 时，堆成几堆牌能够使得快乐值最大。其方程式为：
$\operatorname{dp}[j]=\max (\operatorname{dp}[j], \operatorname{dp}[j-i]+\operatorname{h}[i])$ ;请大家自行思考原因。

C、7-教417

很简单地模拟一下即可，要求输出最小的数字，那么也就是说当 $\mathit 7$ 最多的时候该数字最小（长度短）。
我们直接 $\frac{n}{7}$ 就可以知道最多可以放几个 $\mathit 7$ 了，然后往下筛选符合条件的，即扣掉 $\mathit x$ 个 $\mathit 7$ 后的余值模 $\mathit 4$ 为 $\mathit 0$ 。最后把所有 $\mathit 4$ 放在前面， $\mathit 7$ 放在后面。

D、巫妖王的远征

也是比较裸的bfs，就是有些地方比较坑，也属于较简单的题目。我们可以先忽略休息时间，最后做个除法加上就好了。
这里需要注意的是传送门只能一对一，所以我们可以比较方便地使用结构体套map作为地图，用map记录传送门的对应关系，注意是双向的。
然后跑一遍bfs，在bfs中判断一下合法的队首是否存在传送门，然后在判断入队就好了。最后注意特判传送门直接从起点到达终点的情况。

E、括号匹配

这个很简单的，就是个简单的栈的理解运用，用 $\mathit {sum}$ 记录一个数据，在遇到’(‘则加一，遇到’)’则减一，在从前往后扫描的过程中， $\mathit {sum}$ 始终不为负数，并且扫描完成后 $\mathit {sum}$ 等于 $\mathit 0$ 输出 $\text{YES}$ 即可。

F、找朋友

裸的并查集的路径压缩或按秩合并

G、PC快脱单了

看起来也是有点唬人...不过打个表就是一眼题了，我们会发现这就是一个首相为2的斐波那契数列，推出式子：

$\operatorname{f}(i)=\operatorname{f}(i-1)+\operatorname{f}(i-2)$

证明过程如下：
我们用 $\operatorname{dp}[i][j]$ 表示第 $\mathit i$ 个位置放置 $\mathit j$ ，那么我们很容易得出状态转移方程：
$\operatorname{dp}[i][j]=\operatorname{dp}[i-1][k]$ 若 $\mathit j$ 为 $\mathit 0$ ，则 $\mathit k$ 可以为 $\mathit 0$ 或者 $\mathit 1$ ，若 $\mathit j$ 为 $\mathit 1$ ，则 $\mathit k$ 为 $\mathit 0$ ，

$\begin{aligned} 即：\mathrm{d} \mathrm{p}[\mathrm{i}][1] &=\mathrm{dp}[\mathrm{i}-1][0] \\ \mathrm{d} \mathrm{p}[\mathrm{i}][0] &=\mathrm{dp}[\mathrm{i}-1][1]+\mathrm{dp}[\mathrm{i}-1][0] \\即： \mathrm{dp}[\mathrm{i}][] &=\mathrm{dp}[\mathrm{i}-1][0]+\mathrm{dp}[\mathrm{i}-1][1]+\mathrm{dp}[\mathrm{i}-1][0] \\ &=\mathrm{dp}[\mathrm{i}-1][]+\mathrm{dp}[\mathrm{i}-2][1]+\mathrm{dp}[\mathrm{i}-2][0] \\ &=\mathrm{dp}[\mathrm{i}-1][]+\mathrm{dp}[\mathrm{i}-2][] \\ 证得：& \mathrm{dp}[\mathrm{i}]=\mathrm{dp}[\mathrm{i}-1]+\mathrm{dp}[\mathrm{i}-2] \end{aligned}$

H、亚丝娜sama

在原来射出的时间基础上加上 $\mathit m$ ，然后做一个前缀和就完事了。

I、洛克王国之域外大逃杀

实际上这题也是很简单，只不过代码量比纯签到题多了一点所以才放到了中等题中...

我们可以先只考虑暴力，也就是先20遍bfs遍历所有的魔物，然后在地图上记录一下每个魔物抵达的时间和该时间点的最大攻击。

接下来由于最多只有两个宠物，我们跑4次bfs就好了，洛克到1号宠物再到2号，洛克到2号再到1号。于是这题就愉快的暴力掉了4000ms+。然后就是考虑优化了。

其实也不需要优化太多，我们可以将所有魔物全部放进队列中一起跑，然后稍微剪个枝就可以过了。我们知道如果一个魔物后抵达A，而它的攻击又弱于或者等于前一个抵达的魔物，那么我们就可以将这个状态给舍弃掉了。1500ms

当然其实还可以再优化的，考虑到没有障碍物的情况，我们可以利用曼哈顿距离做一下操作，我们可以两个队列同时跑，这样我们的宠物能否到达判断就不需要对每个魔物的到达时间和攻击判断，只需要对比一下最大ATK就好了，魔物的队列和之前一样的优化一下就好了，宠物的话利用曼哈顿距离搞搞和之前的写法差别不大。

J、jcc爱踢球

由于每轮都是偶数只队伍，那么这就相当于一颗满二叉树了，我们经常看电视的时候每次比赛都基本会出现树状图。
我们每次只记录叶节点的编号（假设为 $\mathit i$ ），那么下一次的新叶节点编号（即旧叶节点的父亲）为 $\frac{(i+1)}{2}$ 如图所示：

那么他们相遇也就是父节点相同的时候，而每找一次父节点计数器加一，则最后的计数器的值(记为 $\mathit S$ )就是树的深度-1，也是比赛是场数，最后如果 $2^S$ 为总的队伍数，则说明决赛相遇。

K、QAQ

此题看起来复杂，但打个表就会发现是个一眼题...
公式由于(i%2)的存在，所以我们只需要计算 $\mathit i$ 为奇数的情况就好了。
那么打个奇数的表就会发现:

$f(i, j)=\left\{\begin{array}{l}{1, i=1+4 k(k=0,1 \ldots)} \\ {01 交错, i=3+4 k(k=0,1 \ldots)}\end{array}\right.$

那么此题就结束了。

证明如下：

记 $f(\mathit x,\mathit y)$ 为 $\mathit x$ 到 $\mathit y$ 的所有整数的异或值。
对 $f(2^k, 2^{k+1} -1)$ (注意文章中的xor 表示“异或”，or 表示“或”)：
$2^k$ 到 $2^{k+1} -1$ 这 $2^k$ 个数，最高位（+k位）的1个数为 $2^k$ ，
若 $k \geq 1$ ，则 $2^k$ 为偶数，将这 $2^k$ 个数的最高位(+k位)去掉，异或值不变。
因而 $f(2^k, 2^{k+1} -1) = f(2^k - 2^k, 2^{k+1} -1 -2^k) = f(0, 2^k -1)$
因而 $f(0, 2^{k+1} -1) = f(0, 2^k -1) \ xor \ f(2^k, 2^{k+1} -1) = 0 (k \geq 1)$
即 $f(0, 2^k - 1) = 0 (k \geq 2)$

对 $f(0, n)\ (n \geq 4)$ 设 $\mathit n$ 的最高位1是在+k位 $(k \geq 2)$ ，
$f(0, n) = f(0, 2^k - 1) \ xor \ f(2^k, n) = f(2^k, n)$
对 $2^k$ 到 $\mathit n$ 这 $n+1-2^k$ 个数，最高位(+k位)共有 $m = n+1-2^k$ 个1,去除最高位的1
当 $\mathit n$ 为奇数时， $\mathit m$ 是偶数，因而 $f(0, n) = f(2^k, n) = f(0, n - 2^k)$
由于 $n - 2^k$ 与 $\mathit n$ 同奇偶，递推上面的公式，可得： $f(0, n) = f(0, n \% 4)$
当 $n \% 4 == 1$ 时， $\operatorname f(0, n) = \operatorname f(0, 1) = 1$
当 $n \% 4 == 3$ 时， $\operatorname f(0, n) = \operatorname f(0, 3) = 0$

L、这是最难的题

这个题可能就不是那么签到了，需要转一个弯。
我们先对装备的数量排个序，记录一下排序后的前缀和，二分答案记为 $\mathit x$ ，检查答案 $\mathit x$ 的时候从后往前遍历，比 $\mathit x$ 大的数是一定满足分配的，
当比 $\mathit x$ 小的时候，我们用此时的前缀和除一下 $\mathit x$ 其值记为 $\mathit s$ ，如果 $\mathit s$ 与之前比 $\mathit x$ 大的种类数量的和大于等于 $\mathit m$ ，则改答案为可行答案，继续二分。请大家自行证明其正确性。