牛客寒假算法基础集训营5 题解

A 炫酷双截棍

如果只有一根木条，显然答案就是一个圆弧。

当有两根木条的时候，问题等价于在这个圆弧上任一点放置木条2。

显然可以发现可以到达的位置是一个圆环或者一个圆（当且仅当）。

B 炫酷五子棋

五子棋只需要计算同方向连续的五个子即可。

所以对于每次落子，我们只需要知道其4个方向(双向)连续的子数（只需要查找至多4*8个位置是否存在即可）。

需要利用一些简单的剪枝降低这个查找次数（比如遇到五子即退出，比如遇到不连续则continue之类）。

通过以上优化，使用set< pair<int,int> >来存放也不会超时。

否则可能需要一定的优化才行。

时间复杂度（使用平衡树比如set）或O(M)（如果使用哈希表的话）

C 炫酷迷宫

比如4*4，K=10的时候，很容易构造出：

....

xxx.

.xx.

....

于是得到了一种绕圈的想法。

但是在比如5*2，K=7中，绕圈法又遇到了阻碍，不如直走换边法，即

.x...

...x.

将这两种方法合并起来，即可以得到一种看起来还不错的解法。

D 炫酷路途

因为，一些人看到这个应该直接就状压了，题目放过了这种做法。

但事实上，我们可以将所有额外连边的点再加上起点终点构成一张单独的图。

根据题目数据范围，上述最多一共只有32个点。

随后计算这些点两两间的距离并求起点到终点最短路即可。（因为是有向图，非常好求）

P.S : G++编译环境中，__builtin_popcount(unsigned int)可以$O(1)$计算二进制中该数字1的个数。

时间复杂度

E 炫酷划线 数据已加强

题意转化为：读入一些区间，输出直到有区间交叉的第一个位置。

正经解法：

考虑线段树维护最小值。将左端点值赋值在右端点下标，查询左闭右开内最小值是否小于左端点。

随意解法：

树状数组哈希即可，具体的做法是对于每次连线，随机一个足够随机的值s，然后在首尾分别加上s和减去s，每次查询连线的区间是否和为0即可。

如果和不为0，说明有线交叉了。

时间复杂度

F 炫酷回文

引理：如果一个子矩形的字符串可以单独重组成为回文串，那么其出现奇数个的字符至多只有一个。

考虑状压数字的每一位，第i位为1表示i出现次数为奇数次。

基于上面的引理，我们可以从左到右维护矩形前缀异或和。

当子矩形异或和的二进制表示只有1个或者0个1位时，该子矩形能单独重组成为回文串。

具体做法类似于求前缀和满足条件的计数，将第一行、第二行和两行一起三种情况分开即可。

设可以选用的字符大小集为S，时间复杂度为O(S*N)或（不同的实现方法）

G 炫酷数字

该题目可以直接打表，甚至可以OEIS。

根据唯一分解定理，如果一个数n可以表示成

那么n的因数的个数为

所以可以通过类似调和级数的方法求解。

或者扩展埃式筛法之类也可。

H 炫酷雪花

首先，蹦蹦跳跳的次数是可以直接贪心求得的（选取尽可能冷的时间起来蹦蹦跳跳即可）。

记蹦蹦跳跳的次数为ans。

输出字典序最小的方案，这需要认真思考。

我们可以用动态规划的方式求解（这里方案很多，我任选一种）：

定义状态表示在第i~n秒钟站起来抖j次能获得的最小寒冷度。

可以得到动态转移方程

有了这个数组，我们就可以从第1位判定是否必须站起来蹦蹦跳跳了。

呃，假设我们现在判定第i个时间，记之前受到过sum点寒冷，之前跳过ans-j下，有以下判断：

• 时，我们还可以坚持第i个时间不跳，。

• 时，我们就被迫要站起来蹦蹦跳跳了，sum不变，跳过的次数++。

由上，我们就可以得到最终的答案了，时间复杂度

I 炫酷镜子

注意到固定转向的镜子没有办法汇聚，也就没有办法卡掉模拟光线。

直接模拟即可，或者使用并查集或者记忆化搜索也可。

时间复杂度O(NM)

J 炫酷数学

考虑每一位，只有在(0,0)(0,1)(1,0)的三种情况时满足条件。