zerol edited 6 年,9 月前
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)$ 。
你再好好算算 $1$ 到 $n$ 的路径有几条。虽说对于每个较小顶点有三条边连向它,但每一层的选择不是独立的,所以不能简单地相乘。(比如相邻两层不能同时选 2i+1->2(i+1)。)
顺便说一下,你这个构造明显没楼下那个斐波那契数列的好。