第十三届北京师范大学程序设计竞赛决赛——题解

比赛题目链接：第十三届北京师范大学程序设计竞赛决赛（校外同步赛）

A Araleii & Bill的冠名权争夺战之登顶校赛

从题意中不难想到，由于戴上帽子后不允许有任何信息交换，所以无论采取什么策略，答对颜色的人数期望不会发生改变，即为N/M。设i个人答对的概率为Pi，可得1*P1+2*P2+…+N*PN=N/M。那么令P1=P2=…=PN-1=0，此时PN最大，等于1/M。

下面证明PN可以达到1/M。构造一种策略，使N个粉丝要么全对，要么全错。把i个颜色的帽子依次编号，第一种颜色为0，第二种颜色为1，…，第M种颜色为M-1。显然，所有帽子的编号和对M取模的结果在0~M-1上等概率分布。那么策略可以是令帽子编号和可以被M整除等等。

B 神奇的身高

构造序列b，b[i]=a[i]-i，求b大于0的LIS即可。

C Attack on Titan

对于每一个村庄和泰坦记录一个二进制数表示在第i条河的哪一边，然后对每个村庄查询是否有泰坦和该村庄处于同一位置即可。

D 超级线段树

倒着扫描操作，用并查集记录每个点最右边没有被执行过操作的点即可。

E rating计算

直接模拟，注意下上下界就可以了。

F 进化之地(Evoland)

此题可以暴力广搜，从起点开始搜，mode=2D，把遇到的所有@压入起点队列，然后再依次以@为起点，搜全图，此时mode=3D,然后这样逐次2D3D2D间隔着搜下去。每个@只搜一遍。

因为每层在搜的时候遇到@时除了加入队列，也会当作通路继续搜下去，所以实际考虑到了@的切换和不切换。

处理的时候记得把起点0也作为通路。

另外一个简单的写法是把每个@和终点作为两个连同的节点，距离为0，分别代表2D模式和3D模式，起点也作为1个点，总共最多13*2+1=27个点，然后通过搜索找到同一模式下任意两点之间的最短路，作为他们之间的距离。然后在这个网络上从起点到终点（两个模式的点任选一个就好）做一下最短路。

G 贪心

二分最终答案s，按ai+bi*s排序，验证能否选出s个即可。

H 简单的传球游戏

记f[i][0]表示i次传球后在1号的方案数，f[i][1]表示i次传球后不在1号的方案数，则f[i][0]=f[i-1][1]*(k-1)，f[i][1]=f[i-1][0]+f[i-1][1]*(k-2)。之后矩阵快速幂或求解通项公式均可。

I 打怪兽

区间DP，将时间离散化，dp[i][j]表示将出现时间在i到j之间的怪兽全部消灭的最小消耗。转移时枚举区间中距离最远的怪兽在什么时间打即可。

J 最长上升子序列

构造AC自动机，显然一个串经过的节点或它们fail指针指到的节点都是这个串的子串，以这个串为结尾的LIS就需要找到这些节点的最大值。那么可以构建fail树，按dfs序构造线段树维护最值即可。