竞赛讨论区 > 【题解】牛客CSP-S提高组赛前集训营5
头像
溴溴溴
编辑于 2019-11-11 11:28
+ 关注

【题解】牛客CSP-S提高组赛前集训营5

A-无形的博弈

暴力做法

枚举每个状态。暴力搜索。

100分

输出。证明如下:

对于一个串,设有一个指针初始指向0,那么往右旋转就是指针往右移。每次操作这个指针指向的数。

神J的策略如下:

定义一轮为这个指针走完一圈,那么在每一轮里,

神J每次能变成0就变成0,如果神树大人把一个0变成1了那么在这一轮内什么都不做。

发现若把这个串视作一个二进制数那么这个二进制数一定在增加。

所以对于所有串都是神J必胜。

B-十二桥问题

24分
注意到有,直接一遍最短路跑过去跑回来即可。

40-70分
为了获得更多的分数,一个很朴实的想法是定义状态为(当前位置,访问过的大桥),即定义数组dist[pos][status]的意义为当前在位置pos,利用二进制状压维护status。通过最短路可以直接跑出答案,大概可以获得分。

100分
正解也很容易想到,我们注意到条边相连的点,再加上起点是最重要的点了,其他的点都无关紧要。我们可以想办法建立一张只有这个点的小图,然后跑上述状压方法的最短路得到答案。

构造这张小图,最简单的方法当然是基于这个点分别跑一遍最短路。其实只要跑次最短路就好了。

具体的构造方法是在这个小图中,先连接所有大桥。然后对于其中任意两点都通过在原图上跑最短路的方法得到距离(不用考虑是否经过大桥),并在小图上连接。然后用类似旅行商问题的方法(只是这次变成了经过某些边时改变状态)直接跑即可。

总时间复杂度

p.s: 卡SPFA的数据是利用CYaRon构造的。

C-神J上树

30分

使用Floyd,复杂度为

100分

路径只能是从上往下走。可以发现从s到t途中经过的点的编号一定是一个单调递减的序列。

接下来的问题就是如何快速算这个序列了。

考虑树剖,把问题转化为个在序列上的问题。在序列上,这个问题可以用单调栈解决。

所以将询问离线(在线也可以),然后对于每条重链用单调栈从下到上扫一遍。复杂度。标程写的,不过常数非常小。

如果只实现序列上的问题可以得到70分。

不要再问我是谁了。

A的标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41725858&scrollToDetail=1
B的标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41736673&scrollToDetail=1
C的标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41725752&scrollToDetail=1

全部评论

(21) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐