被坑了，O(log(n)^2) 的复杂度超时，暴力 O(n) 反而通过了。
零、背景
leetcode 的秋季个人赛我忘记参加了，团队赛就留意了下日期。
团队里两个队友本来都在美国。
下午三点开始比赛的时候，他们那边是凌晨十二点。
今年有一个回国了，但恰好今天要去参加婚礼。
于是团队赛只剩下两个人了。
有六道题，最终只做出前四道题，排名刚好跨进前百名。
最后一题想了一个O(n * log(n)^3)
复杂度的算法，总是超时。
最后换成O(n^2 log(n))
的暴力算法，结果通过了。
PS：由于周日要国庆调休加班，第 260 场比赛就不实时参加了，晚上我找个时间做一下。
一、开幕式焰火
题意：给一个二叉树，问二叉树中节点值组成集合后，集合的大小是多少。
思路：递归遍历二叉树，放进集合，输出集合大小即可。
通过者：队友网速快，先看的第一题，我便不看这道题了。
通过时间：0:02:01
PS：队友手速好快。
二、自行车炫技赛场
题意：给一个二维坐标，坐标有两个属性：高度和减速带。
相邻坐标之间移动时有个速度转移公式。
现在给一个起始坐标和速度，问在速度不为 0 的情况下，哪些坐标的速度可以到达 1。
思路：坐标大小为100*100
，根据公式可以知道最大速度为 200
。
坐标与速度组合最多有 100*100*200
个状态。
DFS 求出所有合法状态即可判断有多少个答案。
通过者：由于队友做的第一题，我便做的这道题题。
通过时间：0:23:14
三、志愿者调配
题意：给一个无向图和若干个操作，操作分三类。
操作1：顶点 x 的权重值减一半。
操作2：顶点 x 相邻顶点的权重值都加上顶点 x 的权重值。
操作3：顶点 x 相邻顶点的权重值都减去顶点 x 的权重值。
现在我们知道初始状态所有顶点的权重值之和，以及最终状态除了第一个顶点外其他顶点的权重值。
求初始状态每个顶点的权重值。
思路：假设最终状态第一个顶点的权重值为 x。
所有顶点都使用 a * x + b
的 <a, b>
二元组表示。
然后逆向遍历操作，并做逆向计算。
逆向操作1：顶点 X 的权重值翻倍。
逆向操作2：相邻顶点都减去。
逆向操作3：相邻顶点都加上。
最终可以得到初始状态所有顶点的二元组，求和后得到一个一元二次方程。
解方程可以计算出 x
的值。
初始状态所有顶点的公式都套入 X，即可计算出所有顶点的初始值。
小技巧：二元组可以封装为一个对象，并实现加法和减法，翻倍等价与加法。
struct Node{ll a, b; // a * x + bvoid Add(Node& o){a = a + o.a;b = b + o.b;}void Minute(Node& o){a = a - o.a;b = b - o.b;}};
通过者：队友
通过时间：0:34:51
四、入场安检
题意：有 n 个安监室，每个安监室可以容纳若干个人，这些人需要排队。
排队方式可能是队列的形式（先进先出），也可能是栈的形式（后进先出）。
现在问这些安监室如何选择排队方式，可以使得第 k 个人经过所有安监室后变成第一个人。
思路：题意的大概意思很容易理解，但是细节很难理解。
我有两处理解错题意了。
第一处是栈如何出队的。
假设一个安监室大小为 a，我理解为 a 个人先入栈，然后 a 个人在同时出栈。
结果是这 a 个人顺序反转。
第二处是最后那批人，没有把安监室填充满该怎么办。
我起初理解为不满时，按不满出栈或者出队。
三十分钟过去了，代码也敲完了，一测试，第一组测试数据没通过。
再反复读题意，发现题目增加了一个注意事项，最后那批人永远出不去。
而对于栈，看了题目提供的动图，发现每次只能出栈一个人。
这意味着栈中的人，除了最顶端的人，其他人永远都出不去了。
理解题意后，这道题反而非常简单了。
输入的位置为 K。
每经过一个房间，有两种选择，位置就拆分为两种状态。
房间个数为 200，意味着选择有 2^200
种路径。
每个房间最多容纳 200 人，总人数最多可能是 40001 人，位置状态也就是 4 万个。
储存一个房间每个状态的路径数，我们就可以计算出下个房间每个状态的路径数。
复杂度：O(200^3)
通过人：我做的这道题。
通过时间：1:24:32
五、无限棋局
题意：给一个五子棋的无限坐标棋盘，问接下来三步内（黑、白、黑），是否可以决出胜负。
如果可以输出胜者，否则输出平局。
思路：三步分别处理。
胜利点定义：一个位置放入棋子后，该颜色的棋子组成一条连续的线，且至少有 5 个。
第一步最简单，只要找到一个胜利点则认为胜利，复杂度O(n^2)
。
第二步比较简单，至少有两个胜利点，复杂度O(n^2)
。
第三步稍微复杂点，需要第一步填充某个坐标后，构造出至少两个胜利点。
构造胜利点的时候，分两种情况：连续构造与隔空构造。
连续构造比较好理解。
已经有一个三点成线了。
增加一个点，就是四点直线，两端就是两个必胜点。
隔空构造意味着增加一个点后某个必胜点并没有组成四点直线，而是一点与三点或者两点与两点。
六、环形闯关游戏
题意：给一个环形关卡，每个关卡有一个权重值。
起始状态有一个分数，可以任意选择一个关卡来挑战。
如果分数大于挑战关卡的权重值，分数可以与关卡的权重值合并得到新的分数。
然后挑战过的关卡的相邻关卡也可以进行挑战。
问起始状态的分数最低是多少时，依旧可以调整所有关卡。
思路：我很快就想到解决方法了。
首先是从高到底枚举 bit 位，判断组成的分数是否可以通过所有关卡。
例如假设处理到第 i 位，已经有前缀 preAns
了。
优先判断第 i 位为0时是否有答案，即判断 preAns + (1<<i) - 1
是否有答案。
如果有答案了，这个答案肯定比第 i 位为 1 时的答案更优。
枚举复杂度：O(log(n))
那得到一个分数后，怎么判断是否是答案呢？
我的方法依旧是枚举。
枚举起始位置为所有位置，判断是否有某个位置可以通过所有关卡。
枚举复杂度：O(n)
那得到起始位置和起始分数了，怎么判断是否可以通过关卡呢？
我的方法是通过线段树二分查找来解决。
每次尝试向左与向右，找到最远的区间最大值不大于当前分数位置。
如果有找到，再求区间 bit 或运算的结果，累计到当前分数上。
之后再次尝试向左与向右寻找是否可以走的更远。
复杂度：log(n)^2
综合复杂度：n log(N) log(n)^2
当然，这个线段树二分的方法看着很巧妙，但是最终超时了。
赛后看了有人没有使用线段树，直接暴力向左减一向右加一去寻找答案的。
暴力的复杂度是n^n log(N)
，试了下，然后竟然过了，坑呀。
赛后还看到有人使用并查集过的，后面有时间了研究下为啥可以使用并查集。
七、最后
这次比赛还不错吧。
第一题是签到题。
第二题是记忆化搜索。
第三题是计算题。
第四题是动态规划。
第五题是模拟题。
第六题是二分加其他数据结构体。
比赛的时候我没去看倒数第二题，真如队友所说，倒数第二题更简单吧。
加油，算法人。
《完》
-EOF-
题图：来自朋友圈。
上篇文章：线段树：权值？合并？动态开点？没听说过
长按二维码，一起成长学习
▲ 长按关注，天天成长
觉得有帮助可以点击好看与转发，谢谢！
