21st Polish Olympiad in Informatics

【开坑日期2017/6/20】

我已经做了12/15


Salad Bar 很容易观察到符合条件的前缀和应满足s_{l-1}\leq s[k]\leq s[r],那么利用前后绝对值之差不超过一的原理,可以在O(n)的时间复杂度内求出每个点的下一个点作为起始点向右能走多远,作为右端点向左能走多远,然后就变成最大化R-L+1,要满足L[R]\leq L,R\leq R[L],用一个树状数组和two pointers维护即可。

Ant Colony 简单树dp,利用bfs统计即可,特判爆long long的情况。

Hotels 我一开始naive了。。以为统计下总数然后算组合数就行,实际上会因为某三个数的lca不是根而导致GG,那怎么做呢?不妨枚举中点,然后对他的每个子树统计,然后合并在一起,这样就不会重复了。

Bricks 简单贪心,但是有一个问题就是,如果数量相同怎么办?如果两个中有一个,是末尾结束的,我们肯定希望先用这个,这样就会减少末尾重复的可能性。然后要用快速读入才能卡到100分。。。

Cuoriers 主席树简单应用

Cards Orz线段树分治处理查询,大概就我这个蒟蒻不会QAQ,每个点维护左边的牌,是用较小的/较大的,延伸到右端,在尽量使他最小的情况下,是较小的还是较大的还是不存在该方案,然后每次查询直接合并下就行了,时间复杂度O(n\log n)

Criminals 我们枚举相遇点,考虑怎么去验证,贪心的来说,我们希望保存每个点左边最靠右的某个点xx到这个点之间能凑出一个完整的小偷A的序列。右边同理。这样问题等价于判断[1,x][y,n]之间是否有同色的数,考虑到之前预处理出来的那个东西有单调性,直接做就行了。

Supercomputer 神结论题,对于一个k,答案就是max\begin{Bmatrix}i+\left \lceil \frac{s[i]}{k} \right \rceil\end{Bmatrix},以i为斜率,跑出凸壳,在凸壳上二分即可。

Little Bird 直接单调队列优化dp即可

Rally 神题,我们需要最小化整张图的最长链,那么如何去求整张图的最长链呢?建立源汇,源连向所有点,所有点连向汇,那么源到汇的最长路就是整张图的最长链。那么考虑如何支持删除操作,对每个边拉出来考虑,记源到i的最长链为f[i],记i到汇的最长链为g[i],那么这条边就可以表示为f[u]+g[v]-1,也就是代表了一条最长链,整张图的割集一定涵盖了最长链的代表边,所以只要能在删点之后,快速知道这张图的任意一个割集即可。这个可以按照拓扑序删除,再加入这个点之前,这个点的出边显然都不在这个图内,然后考虑把这个点的入边以及他到汇的边全删,那么此时此刻显然是个割集,最大值就是答案。再把这个点的出边、源到这个点的边插进去即可。所需要的数据结构用可删堆就可以做到。

Farmcraft 首先,因为题目确认了每条边只能走两遍,也就是意味着如果选择了走一个儿子,那么就必须把以这个儿子为根的子树全走完,才能去考虑这个儿子的兄弟。其次,对于两个儿子的先后顺序,一定不会影响到后面的答案,因为总结束时间是不变的。故此,我们分析儿子a在儿子b前的条件:a中的最小完结时间+b走一圈的大小>b中的最小完结时间+a走一圈的大小,于是按照这个排序,自底向上做即可。

Around the world 参考我在之前的文章中所写的那个小技巧,于是这题就可以很愉快的在O(n\times s)的时间复杂度内解决啦!那么问题来了,50pts的subtask有卵用嘛。

发表评论

电子邮件地址不会被公开。 必填项已用*标注