JSOI2014解题报告

JSOI2014 拼图

首先考虑暴力做法,就是枚举(low)和(upp)然后贪心的选.

这个时候考虑优化暴力显然不是很可行,考虑根号做法.

如果(n leq sqrt{100000}),那么这个时候这样子的暴力复杂度就对是吧.

如果(m le sqrt{100000}),考虑枚举每一个白点,找到离他最近的黑色点,把这段距离当成一个(low,upp)即可.

JSOI2014 宅男计划

宅的天数和送餐次数应该是相关的(肯定).

然后直接退火就行了.

JSOI2014 骑士游戏

考虑令(dp_i)表示砍(i)号怪物所需要的最小魔耗,发现这是一个没有负权边的图,直接(dijkstra)转移(dp)即可.

JSOI2014 支线剧情

不难注意到这可以转换成一个上下界费用流,每条边([1,Inf)),直接跑即可.

JSOI2014 保龄球

比较神奇的(dp),个人认为是(JSOI2014)中最难的一题.

首先考虑怎么样最优,肯定是一个全中后面跟补中,补中后面再放全中.

如果当前是全中:

后面要放失误那么肯定是放最大的.
后面要放补中肯定是放第一个比较小的.

如果当前是补中:

后面要放失误肯定是放第一轮最大得分的.
放补中就放最大的.

注意到补中一定是按照第一个排序后放区间的,失误排个序取两次的最大值,然后就可以(dp)了.

但是注意到有可能有附加局,所以你放的失误可能有特例不满足上述要求,考虑枚举即可.

设(f_{i,l,r,j,k,o})表示放了(i)轮全中,补中还剩下((l,r])中的可以用,失误放了前(k)个,有没有放特殊局,上一次是全中/补中/失误.

随便转移即可.

JSOI2014 奇怪的计算器

一个比较常见的套路,考虑把所有的询问放在一起,这个答案序列肯定是根据初始值的大小单调的.

直接拿线段树维护即可.(也可以用吉利线段树)

JSOI2014 支线剧情2

如果没有存档/读档直接对于每一个节点算儿子中的叶节点个数然后(dp).

有了读档枚举哪一个儿子读档进行最优解即可.

*JSOI2014 病毒分类

没写.考虑将前后缀搞出来就是一个最小割跑出答案.

至于输出方案可以考虑判断那些边边权为(0).

JSOI2014 强连通图

第一问很明显就是最大的强连通分量的大小.

第二问就是要求缩点后入度为(0)和出度为(0)的点中取(max),因为你可以将这两个连起来然后让图联通.

JSOI2014 歌剧表演

考虑一次表演之后会把一些几何分成可以被划分和不能被划分两种.

然后用(set)暴力维护即可.

JSOI2014 士兵部署

无脑题,每次加一个点,求动态凸包面积.

直接二分就行了.

JSOI2014 回文串

考虑先用(manacher)求出最长回文半径,然后对于每一个([l,r])区间询问会对其造成限制,分成([l,mid])和((mid,r])分开处理即可.

JSOI2014 电信网络

模板题,直接连边跑最大权闭合子图即可.

JSOI2014 打兔子

考虑每相邻的坑不会打,然后顺序(dp).

问题在于(1)打了会对(n)有影响,直接钦定(1)开枪和(n)开枪即可.

JSOI2014 序列维护

模板线段树2,甚至只要改输入格式.

JSOI2014 学生选课

很明显可以二分,二分之后发现每一个学生只能选两门课目,跑个( ext{2-SAT})就行了.

JSOI2014 矩形并

首先考虑贡献是一个矩形,可以对于每一个矩形打上(1)标记,然后查其他的矩形,可以用二位树状数组维护.

但是这样子会(MLE),考虑第一维变成扫描线即可.