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