2013 Multi-University Training Contest 10

其实这篇文章本来应该是boi题解汇总的……
但是窝boi切不下去了……
就拿这个凑数吧(每周任务:更新博客!)
嘴巴上做了一遍后发现……智商是硬伤。

Answers

开题毫无想法系列。
扫了一眼数据范围……发现只能是1或者2……就明白了什么。
显然的……如果询问是偶数,那么一定能凑出来,如果输入的C有1,那么奇数也一定能凑出来,否则凑不出。

Convex hull

浓浓的 [ctsc2009]魔幻花园 既视感……不过这题不是暴力三分乱搞……数据范围很小……直接求事件点就可以了。
首先凸包上的点会发生变化当且仅当某一时刻三点共线。
然后我们直接求出这个事件点……然后每两个相邻事件点,凸包上的点的组成是不会变的,然后根据叉积计算面积的公式,这时候的面积计算公式S(t)是一个关于t的二元一次函数,暴力推导表达式暴力积分即可。

Counting

浓浓的 [zjoi2012]mrx 既视感……不过这题直接暴力扫描线就好。
首先我们可以转化为有多少空矩形。
我们枚举一下空矩形的右边界,以左边界为扫描线从右往左扫,维护一下,就能统计了。

Editor

浓浓的 [NOI2003]editor 既视感……不过这题做法比较233。
记得去年我有把这题当noip模拟题出给小朋友玩过233……
据说当时有队伍直接写splay的……
然后正确的姿势当然是维护两个栈:一个是光标前的元素一个是光标后的元素。
然后yy一下就明白了。

Flow

智商是硬伤系列。
(想了很久根本就没想到正题……一直在yy全局最小割之类的)
首先如果点数只有三个,如果有一个合法解是环,那么我们肯定可以调整得到一个是链条的合法解。
然后推广一下就会发现存在合法解的话,就一定存在合法解是树的情况。
接下来搞最大生成树就可以了。注意特判无解情况。

Game

智商是硬伤系列2hit。
一看就知道不是公平博弈,sg啥的肯定不能用。
所以就只好yy一下dp了。
然后很容易yy出的状态就是F[i][j][k]:表示取完了前i个挂件,然后先手还有j元,后手有k元时,轮到先手操作先手能否必胜。
接下来怎么精简状态我就不会了……
然后看题解发现dp状态应该是……如果已经取完了前i-1个挂件,那么先手至少还要有f[i]元才能必胜……这样子设计状态。
那么有取和不取两个决策……取的话用f[i+1]+a[i]来更新,不取的话那么后手手上的钱一定要小于a[i]+f[i+1],那么两者取min就可以了。
这种博弈题没怎么接触过+智商不够……要是考到的话肯定跪了……

Group

神题之首。记得去年看到题解满屏公式就吓出**了
坑待填……

Rectangles

这我哪会系列
坑待填……

Sum

答案显然是。费马小定理就可以了。

Y

做法很多,我想的一种做法是补集转化为统计在一条简单路径的三元组个数,然后转化为统计在路径中间的节点个数,然后统计一下每个节点在多少条简单路径上作为中间节点出现就好。

智商是硬伤……坑还是没填完。

Comments

comments powered by Disqus