来挖个坑。

以下按main上顺序。
另外吐槽一下波兰人的效率。这么久了还没放出英文题面……

Stage I

bar

translate:有一个长度为n的字符串,每一位只会是p或j。你需要取出一个子串S(从左到右或从右到左一个一个取出),使得不管是从左往右还是从右往左取,都保证每时每刻已取出的p的个数不小于j的个数。你需要最大化|S|。(鸣谢dzy在BZOJ上放的翻译)
solution: 从左往右从右往左各扫一遍求出每个p可以延伸到的最右和最左边界,然后线段树维护着扫一遍更新答案。

hot

translate:一棵树,求有多少个三元点组,使两两之间距离相等。
solution:我写的爆枚根的做法……据说有的点分治做法。太神了不会。
爆枚根的就很简单了吧。统计一下每个子树中每个深度的点有多少个然后算算就行。

klo

translate:有n种颜色的砖块,第i种颜色的砖块有a[i]个,你需要把他们放成一排,使得相邻两个砖块的颜色不相同,限定第一个砖块的颜色和最后一个砖块的颜色,请构造出一种合法的方案或判断无解。(鸣谢dzy在BZOJ上放的翻译)
solution:用过堆维护一下当前数量最多的一种颜色。每次放与前一个颜色不同的数量最多的一个。

kur

traslate: 给一个长度为n的序列a。每次询问一个区间,是否存在一个数在区间中出现的次数大于(r-l+1)/2。
solution: hzc集训队论文上讲了一种基于随机的做法。每次随机区间内一个数,如果区间内存在一个数的出现次数大于长度的一半,那么至少有的概率随机到它。那么随机20次,每次查询一下这个数在区间内出现的次数。如果20次都没有随机到那么就判断为不存在这样的数。但是这个做法太慢了在main上拿不了100分……
更神的做法见讨论区

waz

translate:一个3*n的棋盘上,有一条蛇在棋盘上。从蛇头到蛇尾刚好是1~3*n。现在你只知道某几个位置上的数,其他位置都不确定。构造出任意一组合法的蛇形图。保证有解。(鸣谢dzy在BZOJ上放的翻译)
solution:这题可做??

Stage II

kar

translate:n张卡片排成一列。每张正反两面有两个数。有m次交换,每次交换两个位置上的卡片。在每次交换后,求能否通过任意翻转卡片,使每张卡片朝上的面的数字单调不减。
solution:用线段树维护当前区间的左端点取正/反的数时,右端点能否取正/反的数。

prz

translate:有一排n个房屋,每个有一种颜色。共有k种颜色。其中有两个住着强盗,它们一定住在同一种颜色的房屋中。现在两个强盗分别向另一个强盗的方向走,它们会进某些路过的房屋抢劫。一直左边的强盗(住的房屋编号较小)抢了m个房屋,右边的强盗抢了l个房屋,给出两个强盗抢的房屋的颜色序列。要求两个强盗最后抢的房屋相同。求最后抢的房屋有多少种可能性。保证两个强盗最后一个抢的房屋的颜色相同。保证每个强盗的抢劫颜色序列中没有重复的颜色。
solution:首先请再看一次题目意思。
对一个最后抢的房屋i,我们只需要求出左边的强盗第一个抢的房屋最靠后的位置front,和右边的强盗第一个抢的房屋最靠前的位置back,那么只需要判断[1,front-1]和[back+1,n]中是否有同样的颜色,即可判断i是不是一个可行解。而front和back可以通过一遍预处理得出。考虑front:假设最后抢的访问颜色为c。我们从左向右扫描,每碰到一个不是c的房屋,就把它放入对应颜色的队列中。每碰到一个是c的房屋,依次向前更新每个抢劫的房屋的最后出现位置。然后得到当前位置的front。注意更新时一旦不能更新了就break。这样是O(n)的。而由于一个强盗不会抢两个同样颜色的房屋,所以这样是正确的。

sup

translate:给定一棵以1为根的n个节点的树。有Q个询问,每次询问给出一个k。我们有一个点的集合,初始的时候只有1这一个节点。每次操作,我们可以从集合中选出至多k个节点,把它们删去并把它们所有的子节点加入集合(指直接的子节点)。求最少多少次操作可以使集合为空。
solution:待填

pta

translate:有n棵树排成一排,每棵树有个高度。有一只鸟一开始在1号树上,它要到n号树上去。它一次最多只能飞过k棵树。如果它一次飞行中到达的树比开始的树高或相等,那么它会变累。求它至少要变累多少次。共Q个询问,每次单独给出k。
solution:由于Q很小,那么对每次询问用单调队列维护DP求解即可。用单调队列取到dp值最小,如果dp值相同取树高最大。

raj

translate:给定一个DAG。求删掉一个点,使图中的最长路最短。
solution:待填

Stage III

far

translate:给定一棵树,我们从1号点出发按某种顺序遍历整棵树后回到1号点。走过每条边的时间是1。每个点有一个给出的权值,设每个点第一次到达的时间是。求一种遍历顺序使尽可能小。其中1号点的特殊,为最后一次回到1号点的时间。
solution:DP。设表示遍历以i为根的子树后又回到i的时间。表示在遍历i的子树后,最小的。显然为子树大小的两倍减1.当求出了i的所有子节点j的时,我们按排序后依次计算对的贡献即可。可以用调整法证明这样贪心最优。注意还要考虑为最大值的情况。最后再特殊判断1号点的时间即可。

doo

translate:一个环上有N个点。相邻两两之间有一个距离。现在给出一个d,每次飞行不能超过d的距离,从任意一个点开始,最少要停几次能够回到原点。(只能沿顺时针飞)
solution:这题第一大特点是卡空间(24MB),第二大特点是卡时间()。你们感受一下……
我们把环拆成链并看作两倍长度,假设我们已经得到了从每个点走不超过d最远能够到哪一个点,那么我们的问题就是:对每一个点i,求出它要走多少步才能走到一个编号大于或等于i+n的点上?这个问题可以用类似于并查集的东西均摊的搞出来……求每个点能到的点可以用单调性的搞出来……那么复杂度大概就是。唯一的问题是,我们不能开太大的数组(6个N的数组就会MLE),所以要精确地开空间……然后还要玩好常数……

mro

translate:给一棵树,其中一条边有一只食蚁兽。有g次蚂蚁来这里,每次会在每个叶节点上出现m只蚂蚁,每一群蚂蚁分别行动。如果一群m只的蚂蚁当前面对有d条路(不算经过过的路),那么每一条路会有只蚂蚁走过去,剩下来的会自杀。而如果一群蚂蚁经过食蚁兽在的边时恰好有k只,那么食蚁兽会把它们吃掉。现在问食蚁兽总共能吃掉多少只蚂蚁。
solution:由于整除是可以合并的……那么我们把有食蚁兽的边断掉,求出每个点要经过这一条边的话需要除掉的值,然后排个序每次询问二分即可。

tur

translate:给定一个任意简单路径长度不超过10的无向图,求其最小点权覆盖集。
solution:待填

lam

translate:有n盏灯,每盏灯有一个照亮角度。(所有灯的角度和方向都相同。)现在按1-n的顺序依次点亮每盏灯,而每盏灯有一个值x,当它被x盏灯照亮的时候也会亮起。求每盏灯第一次亮起的时候是在点亮第几盏灯的时候。
solution:待填

pan

translate:n组询问。每组询问给出,求一组满足,且最大。输出最大的gcd。
solution:我们即需要求一个v,使。那么v只有个取值,暴力即可。(常数要写的很好很好才能拿100 TUT)

zal

translate:有n辆火车,两个车站。两个车站间只有需要时间为s的单向道路,即道路上同时只能向一个方向走(如果有1->2的火车在行驶,就不能有2->1的火车在行驶)。现在n辆火车每辆在一个特定的时间到达1号车站,每辆都需要从1到2,再从2到1。每个车站同一时刻只能有一辆车离开。求方案使最晚回到1的一辆车尽量早。
solution:DP。表示前i辆最早什么时候能回到1。转移是枚举几辆火车一起过去再一起回来。用两个堆搞搞即可。

Comments

comments powered by Disqus