2017ACM萧山训练第1场(NEERC 2016)

2017年8月7日5750

队友做的题目我并不是非常懂。。。

A.[Neerc2016]Abbreviation

字符串模拟

E.[Neerc2016]Expect to Wait

如果对于等待的人数维护一个关于时间的前缀和

那么我们就得到了一个很长的前缀和序列,我们注意到初始车辆为 x,实际上就是询问这个序列大于 x 的前缀和的和

那么对于时间离散化以后,就是询问大于 x 的段的加权和

对所有的段从小到大排序,依次处理

G.[Neerc2016]Game on Graph

第二个人先手的状态的一个后继被确定不是平局,则这个状态不是平局

第一个人先手的某个状态的所有后继都不是平局,则这个状态不是平局

从出度为0的点开始拓扑排序,剩下的点都是平局状态

类似地,确定不是平局的所有状态的胜负

剩下无法确定的点一定是第一个人必胜,第二个人必败,因为第二个人宁愿输也不平局

H.[Neerc2016]Hard Refactoring

模拟

J:Jenga Boom

对于每一层,维护一下最两侧的木块,以及本层木块的数量与重心

每次移除一块积木时,从上往下考虑每一层 x

对于比 x 更高的那些层,若奇偶性与 x 相同,则第 i 块木块重心在 i,否则设其重心在(n + 1) / 2

计算这些层的重心是否在 (mn_x – 0.5, mx_x + 0.5)这个范围内

L:List of Primes

发现用到的质数不会太多,质数和小于1500时总长4*10^18

M.Mole Tunnels

在一棵满二叉树上模拟费用流

维护每个子树内离根最近的可流出的结点,每次流入量加一时,依次查询它的所有祖先,找到一个离它最近的结点,然后把整条路径的所有信息暴力更新一下

维护的时候要记录每条边两个方向的退流