HNOI2011-2012

HNOI2011

Day1

数字游戏

分段计算矩阵快速幂。

勾股定理

通过互质勾股数对构图求独立集个数。后面一问显然是NP的,但是题目有特殊性质,可以断边求树形DP解决。

互质则m、n奇偶不同。

赛车游戏

对上坡进行化简可以发现bs那一段费用是不可避免的,所以可以直接减去,剩下的av就与平路相差无几。
对下坡可以发现如果速度小于Vi不划算,所以令它达到Vmax=-bs/a,其余与平路一致。
那么经过拉格朗日成熟或求导或者贪心可知速度越平均越好,所以问题转化为了一个往阶梯倒水的问题,可用贪心扫描解决。

括号修复

利用Splay维护最大最小前缀后缀和。对于标记的顺序问题,需要简单讨论一下。

Day2

任务调度

暴力枚举第三类任务的类型,然后运用爬山法随机交换两个任务顺序更新答案。

Xor路径

高斯消元解方程。对于这种环形期望的方法就是高斯消元,还可以应用到求电阻电流那一块去。见[CTSC2012 电阻网络]

数矩形

按照长度与中点双关键字排序,按次处理取最值即可。用叉积计算矩形面积避免精度误差。

卡农 组合类DP

这题很神,角度比较巧妙。题目大意是从由1到N构成的集合的非空子集中,选取M个子集,且使得每个数出现的次数均为偶数的方案数。题目的一个隐蔽的性质是前i-1个集合确立了,第i个集合就确立了。

这里可以运用费马小定理来避免求逆元。

HNOI2012

Day1

双十字

Sol. 维护三个树状数组。考察基本数学变形能力,考场上要敢打开,敢合拢,找到题目需要维护的信息才是解决这类题目的关键。

与非

神题属性。需要一定的离散数学功底可得知NAND运算可以组合出任意我们常见的按位运算。同时发现如果将N个K位2进制数放在N行,如果有两列的数完全相同,那么无论你怎样囡,最后结果中这两列的数字一定是相同的。推广到多个数也是显然成立的,所以剩下的工作就是常规的数位DP了。

排队

转换思路很重要,如果想到是先放男生后放女生最后老师的话会相当麻烦与难以讨论,而先放男生紧接着放老师则就是很简单的排列组合了。分两个老师间是否隔有男生来讨论即可。最后对式子进行划归可以只用高乘单与高加解决。

矿场搭建

这题考试时没想出来,理解题意有些不到位。真正理解这道题需要对tarjan求割点有一定深入的认识。在tarjan出的DFS树中,得到的割点如果呈祖先与后裔的关系,那么祖先被割掉后所需要的块需要救援出口就没有意义。所以先删去所有割点,然后对于每一个连通块判断与它相连的割点数目,如果小于2答案加一。注意特判图无割点的情况,这样的答案是C(n,2)。

Day2

三角形覆盖问题

对于的处理手法见【CQOI2005】三角形。
由于本题的特殊性质,交点只在整点出现,也就是关键点只是整数点,而题目中最大高度为。我们可以一格一格地进行暴力处理。用一个链表维护当前区间(区间一旦包含,被包含的区间就永远不会贡献答案,所以删去),统计当前被覆盖单位区间即可。

射箭

一种不知道叫什么的判断半平面交是否为空的方法。
第一点可以想到二分最多能射进的靶子数,然后由抛物线过原点且开口向下可得,对于每一条竖线段,我们可以列出 对式子变形可得到 ,这是半平面交的经典问题,但是题目中的靶子数量太多,用朴素的算法很容易超时,而我们只需要判断交集是否非空即可。于是我们只维护当前交集最高点,若最高点在新半平面内则跳过,否则新的最高点一定是在代表这条半平面的直线上,依次枚举交点取最大值。问题解决。

永无乡

[启发式合并] 每次将rank小的Splay合并进rank大的里去,每次合并和rank较小者规模扩大了至少一倍,所以至多扩大logn次,这样就能在O(nlogn)的时间内求解了。
[划分树+并查集] DFS序中连续的一段就是原图的一个连通块,利用划分树求其中第K小的元素。注意这里并查集的巧用,详见vfk博客。

集合选数

这个详见Matrix67的博客吧,将矩阵旋转一下比较好初始化,比较简单的一个状压DP。