NOIP2012提高组题解

作者: shad0w_walker(admin) 分类: 算法 发布时间: 2017-08-04 17:27 ė 6 没有评论

花了一个星期的时间陆陆续续把这场补完了,算是多年郁结,自招、高考、ACM拿银、拿金的时候都会想起这场。补完之后回头想想似乎稍微轻松了一点,毕竟人生菜这种东西啊被强加在人身上是不能拒绝的,遗憾这种东西啊一不小心就造成了是不可避免的,梦想这种东西啊轻易就会被现实击碎是很难圆满的。算是给自己找个借口交代吧。

 

Day1T1 vigenere密码

有一个字符串加密(+x mod 26),给出密文和密钥,输出明文。

模拟,大水题。

点击此处展开代码

 

 

Day1T2 国王游戏

国王和大臣们每人双手各有一个数字,排成一列,国王在队首,每个大臣获得的奖赏是他前面的人左手上的数乘积除以他右手上的数向下取整,求队伍怎么安排能让获得奖赏最多的大臣获得的尽量少。

贪心,这道题算我做过的题中数一数二的好题(因为太菜了,想了好多年才想明白)。假设在最优序列中,某一位置p前面所有人左手的数乘积为M,p位置开始是i大臣和j大臣,j大臣的奖赏是M*ai/bj,交换邻项ij,i大臣的奖赏是M*aj/bi,,要使M*ai/bj<M*aj/bi,就是ai*bi<aj*bj。所以按照左右手数的乘积从小到大排序就是最优序列了。注意乘积要用高精度,好久不写高精度有点罩不住了。

点击此处展开代码

 

 

Day1T3 开车旅行

从左往右有n个城市,每两个城市间交通的代价是它们的海拔差,现在ab两人从左往右旅行,从某一点开始ab轮流开车,a每次选择次近城市,b每次选择最近城市,旅行总代价超过x或者无目标还城市就结束旅行。问1,给定一个代价上限x0,问从哪个城市出发ab各自代价比值最小,问2,若干问,给定代价上线x和出发城市s,求ab各自的代价。

这道题首先要处理出每个城市的最近和次近城市,我的做法是从后往前考虑,每次查与当前城市差最小和次小的两个位置,随便用一个数据结构维护一下就行,貌似高中生都喜欢用平衡树,我只用了个set,似乎NOIP是能用stl的。接着用倍增的思想,处理出从i城市开始通过倍增到达哪个城市g[i][j]以及ab各自的代价va,vb。

对于第一问,暴力枚举每个起点倍增统计ab的代价即可,第二问对于每个查询倍增统计一下。

点击此处展开代码

 

 

Day2T1 同余方程

ax ≡ 1 (mod b)的最小正整数解

水题

点击此处展开代码

 

 

Day2T2 借教室

n天每天有一定的空教室,m个订单,按顺序在[s,t]时间区间内申请d间空教室,问能否满足这些需求,不能则输出无法满足的订单序号。

乍一看发现是线段树裸题,申请教室就是区间减值,判断能否满足就是区间求最小值,然后我的做法也是用线段树做的。

据说现场线段树过不了??更加优秀的做法是二分答案,因为第mid个订单无法满足那之后的订单都不能满足,然后将线段树用前缀的思想表示,对于一个区间[s,t]加x也就是给前缀a[s]+=x,a[t+1]-=x,然后在整个线段上从左往右扫一遍就行。

丑陋的线段树代码,用fread似乎可以加快

点击此处展开代码

 

 

Day2T3 疫情控制

给定一棵有边权的树,树的一些节点上有军队,一个军队可以把为根子树上的叶节点控制,现在要移动军队,使得所有的叶节点都被控制,移动一个军队的代价是经过边的权值和,军队不能在根节点上,使边权最大值最小,输出最小代价。

这个显然要二分答案,然后将所有的军队尽量往根节点移动,这里尼玛又要用到倍增了啊,这场比赛这么喜欢倍增吗?将一些军队移动到根节点后还有剩余移动的能力,检查一下还有哪些根节点的子节点需要有军队,然后对每个节点,贪心地安排一个尽量小的剩余移动能力比它边权大的军队。

这里会出现一个问题,一个军队并不用移动到根节点,但移动到根节点之后没法再回去了,解决方法是记录每个军队是从哪个根节点的子节点上去的,如果回不来了,并且这个子节点需要他,就直接给他安排在这个点上。原因是这样的,这个军队A假如移动到根节点,那他这个子树会被另一个其他子树中的军队B控制,而它肯定控制了另一个需要代价比当前代价大的子树,因为如果不比它大,那军队B可以直接去控制,正因为比当前需要代价大,所以如果回不来,那也不可能经过根去另一个子树,直接呆在原地即可。

点击此处展开代码

 

 

本文出自shad0w_walker,转载时请注明出处及相应链接。

本文永久链接: https://www.sdwalker.com/archives/790.html

0

发表评论

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

返回顶部