之前打错了
题解里C题复杂度为2的24次方，这个做法不太保险啊。
给个我的感觉稳得一匹的解法：
第0层放1，1->2,1->3. 连两条边。
第i(1~24) 层开始放 2i,2i+1,然后 2i+1->2i，当i不是第24层的时候，2i+1->2(i+1)，2i->2(i+1),2i->2(i+1)+1。
这样一共有25层（从0开始），其中下面的 2~24层中较小的那个点都有三条边连向它。复杂度至少是3的23次方。
2的24次方：16777216
3的23次方：94143178827（逃
2018.1 月赛题解
zerol edited 6 年，3 月前
A 石头剪刀布的套路
By ultmaster.
既然你可以预测对方下回合出什么，那不就稳赢了？
B. 最大的子串
By ultmaster.
实质上是要求一个小数 0.xxxxx 最大。我们发现，字典序肯定是骗人的；当不考虑长度的限制时，肯定是越长越好。所以只需要考虑 $s[1..n], s[2..n], \ldots, s[n..n]$ 这 $n$ 个子串即可。
小数的大小其实跟字典序是等价的。所以其实就是求这些子串当中字典序最大的那一个。
有一个问题是后面有 $0$ 结尾的时候，要把 $0$ 去掉，不然就违反了长度的规定。有一个坑是如果全是 $0$，不能全去了，必须要留一个 $0$。
C 我决不会 TLE
By zerol.
本题根据真实事件改编。
给出一种解法。在 1 和 n 之间加入 24 个中间层，每层两个顶点，前一层的顶点与后一层的顶点连边。在这种情况下，1 到 n 的最短路条数有 $2^{24}$ 种，搜索显然会超时(好像并不显然)。
补充：如果考虑最坏情况，那么一开始找到的就是最短路，后面搜索的深度就不会超过这条最短路的长度。如果考虑最好情况，那就是所有路径的长度和。spj 中对边的顺序进行了打乱，所以复杂度很难到达最坏情况。
D. 华生的围栏
By ultmaster.
- 小于 $3$ 是无解的。
- 对于偶数的情况，只要构造一个长为 $\frac{C}{2}-1$，宽为 $1$ 的长方形即可。
- 奇数是无解的，证明如下：如果存在一个周长为奇数的多边形，我们可以将每一条不跟坐标轴平行的边 $(x_1,y_1)-(x_2,y_2)$ ($x_1 \ne x_2, y_1 \ne y_2$) 替换成对应的折线 $(x_1,y_1)-(x_1,y_2)-(x_2,y_2)$，可以保证做这样的替换后原图周长的奇偶性不变（因为 $a^2+b^2=c^2$ 必然有 $a+b \equiv c \pmod 2$）。现在多边形的所有边都与坐标轴平行，且是一个封闭图形。所以考虑从一个顶点出发，绕个多边形走一圈，每一步向上都有向下的对应，每一步向左都有向右的对应。这样多边形的周长一定是偶数。矛盾。
出题人：其实这题跟一道上古 TC 题撞了，不过是出完了才发现的。。。
E 没用的函数
By zerol.
- 如果固定右端点，扩展左端点，那么 gcd 的值最多变化 $logC$ 次（C 为数列中最大的可能值，因为 gcd 每次至少减少一半），而且从左到右 gcd 值是单调递增的。
- 如果右端新加入一个点，那个将原来的每一段的 gcd 都对于新的数取 gcd，再进行去重就能得到新的 gcd 的分段信息。
- 对于每一段，需要求区间最大值，用ST表或者线段树预处理一下即可。
- 复杂度 $O(nlogn)$ 。
F 最小 OR 路径
By zerol.
Easy
- dp[u][k] 表示到结点 u 的代价为 k 的方案是否存在，然后在图上转移（dfs 一下就好了）。
- 可以枚举所有可能的答案，判断连通性。但是如果你想到了这一点，那么 HARD 一定也不在话下。
Hard
- 假设答案的二进制位全是 1，然后从高位到低位考虑，如果将该位置为 0 不破坏连通性的话就置为 0，这样肯定最优。
- 判断连通性可以用 并查集 或者 搜索，反正 $O(M)$ 就行。
- 复杂度 $O(63M)$ 。
Comments
gymgym1212
你再好好算算 $1$ 到 $n$ 的路径有几条。虽说对于每个较小顶点有三条边连向它，但每一层的选择不是独立的，所以不能简单地相乘。（比如相邻两层不能同时选 2i+1->2(i+1)。）
顺便说一下，你这个构造明显没楼下那个斐波那契数列的好。