2018.1 月赛题解

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.

出题人:其实这题跟一道上古 TC 题撞了,不过是出完了才发现的。。。

E 没用的函数

By zerol.

F 最小 OR 路径

By zerol.

Easy

Hard

Comments

gymgym1212

之前打错了

题解里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(逃

zerol

你再好好算算 $1$ 到 $n$ 的路径有几条。虽说对于每个较小顶点有三条边连向它,但每一层的选择不是独立的,所以不能简单地相乘。(比如相邻两层不能同时选 2i+1->2(i+1)。)

顺便说一下,你这个构造明显没楼下那个斐波那契数列的好。

啊诡是校草呀

C可以到Fib(49)吧

ultmaster

在随机情况下这种构造应该足够好。

啊诡是校草呀

对 我没有算中间的剪枝。。。

zerol

你说的是 $k$ 连 $k+1$ 和 $k+2$ 吧,这样 $1$ 到 $n$ 的路径确实有那么多,但最短路径长度是 25。因为搜索有剪枝,所以要计算的是起点出发长度不超过最短路径长度的路径的长度和。(spj 读入后将边的顺序 shuffle 过了。)

Nasaos

讲道理B题2e4的数据是不是有点坑,没敢暴力

ultmaster

有经验的(被青岛坑过的)都知道 strcmp 超快。

annie2212

顶一个,
话说有标程吗? 我想对拍看看F1直接 dijkstra 最短路为什么不行.

Wss

A -> C
B -> C
C -> D

从A到C权值为 011
从B到C权值为 101
从C到D权值为 101
那么最后到D的答案应该是101,可见并不满足贪心性质

UoA_ZQC

显然不满足贪心性质啊

UoA_ZQC

请问C题为什么不是$2^{24}$?

zerol

$n$ 的确有点小。超时成功是因为 spj 判断时间的常数有点大。

UoA_ZQC

讲道理$2^{24}*24$并不是那么大啊。。建议增大$n$的限制。

zerol

已更正