JAG Practice Contest for ACM-ICPC Asia Regional 2016 部分题解

这场的题目质量挺高的,学习了一些新的姿势。

A – Best Matched Pair

给出n个数字,任意两个数字可以乘积,求乘积最大并且乘积结果是连续递增的数字的一个解。例如1234是连续递增的数字,但135不是。
用set xjb预处理出这些连续递增的数字,然后暴力n ^ 2去匹配set。

B – Help the Princess!

一个n * m的地图,有个若干坏蛋和主角,主角需要到达出口才能得救,主角和坏蛋没秒都可以选择往四周走或者停留不动,求主句是否存在一条路径到达出口,这条路径无论坏蛋怎么走都无法阻断!
很简单,先用坏蛋去bfs出到每个位置的最小时间,然后在bfs主角,主句所走的没步的时间都需要<之前bfs的最小时间。

C – We Don’t Wanna Work!

有一个公司,开始时有n个员工,这个公司比较奇葩只会有%20的人工作(%20下去整),现在有一些员工的加入和删除,对于加入或者删除操作需要输出:1.当前加入的员工的状态:工作or部工作;2.其他员工若有变化需要输出他现在的状态:工作or部工作。
思路很简单,用一颗splay模拟一下题意就好了。

D – Parentheses

构造出()这样的括号序列,使得这个序列最短并且变化成合法括号序列的最短步奏要准确的等于n。步奏:选择任意两个相邻的位置交换!
分析容易发现))))(((((这样左边全是)右边全是(的序列需要的最短步奏在同长度的序列中是最大的,因此我们锁定步奏的这个序列,对于每个序列如何求它的最短步奏?这个可以贪心,从左往右找第一个不匹配的括号然后从后面找一个最近能够匹配的括号一直交换到这个括号的旁边!于是你会发现)))((( => )())((,是不是发现删除前两个就变成了))((,那么很容发现对于最大步奏的序列是存在递推关系的,f[n] = f[n – 2] + n / 2(n是偶数)。那么我们就可以快速找到第一个f[i]>=n,那么构造的串的长度就锁定在了i了。接下来就是构造长度i并且变成合法括号序列最短步奏是n的串。这个其实容易发现只需要将)()))(((这样的序列的第二符号'(‘换到第f[i] – n + 1个位置即可(下标1开始算)

E – Similarity of Subtrees

计算一棵树有多少棵树同构,同构的定义:S(T, d)表示T为根,深度是d点个数,那么T 同构与T’当且仅当对于所有的d,都有S(T, d) = S(T’, d)
我们可以根据树的多项式表示做双hash,然后同hash值的统计即可。

F – Escape from the Hell

N天,这个人要从地面网上爬L的长度,有N瓶饮料,每天只能喝一瓶,第i瓶饮料喝了白天可以爬Ai,晚上会掉下Bi。有另外一个人在追你,他只会晚上爬,并且第i天会爬Ci。可以自己选择和饮料的顺序,求最少需要几天并且不被追上爬到L以上。
令Di = Ai – Bi,然后Di从大到小排序,Fi = Fi-1 + Di, Gi = Gi-1 + Ci。然后暴力的枚举最后一天喝什么饮料,加入喝t饮料,那么对于删除Dt后,在序列中找到第一最小的x,是的Fx >= L – At 并且 Fi > Gi (i <= x)。我们可以二分这个x,然后判断是否合法,合法的判断方法:对于Fi – Gi,和Fi – Gi-1分别建立两颗线段树,只需要判断[1, x]中的最小值是否>0即可,判断的是否需要分两个线段树合并最小值。之所以用两颗线段树是为了处理某个点被删除后的情况,因为我们无法动态的维护序列,这里可以仔细想想,这是一个小技巧。

A:

 

B:

 

C:

 

D:

 

E:

 

F:

 

LEAVE A COMMENT