HNOI 2010 解题报告

0. HNOI2010 AC代码包下载地址

注：
戳上面的标题中的'地址' 下载 代码包，
戳下面每一题的文件名 可进入 题目链接。
每一题 对应代码的文件名 我在 每一题题解的标题旁 备注了。
提醒：请不要直接 \(Copy\) 我的代码，代码仅供用于题目理解与对拍。

1. [HNOI2010]弹飞绵羊\(\ \)(Sheep.cpp)

比较简单的一题。解法有\(INF\)种，这里给两种：
( 1 ) \(LCT\)维护链长，对边界外(\(>n\))开一虚点\(S\)，每次查询即为\(x\)到\(S\)的路径长。
( 2 ) 分块，把序列分成\(\sqrt{n}\)块，对于每个点维护跳出所属块需要多少次，修改与查询都是\(O(\sqrt{n})\)的。

2. [HNOI2010]BUS 公交线路\(\ \)(Bus.cpp)

原题中，一辆公交车经过的相邻两个站台间距离不得超过\(P \ km\)
本题关键就在这里，这意味着在任意区间长度为\(P\)的区间中，每个数字至少出现一次。
然后\(DP\)，\(f[i][S]\)表示做到第\(i\)个车站，\([i,i+P-1]\)区间内的车站情况为\(S\)的方案数。
其中\(S\)是记录每一个车站是否被选择了(\(1\)表示已选择，\(0\)表示未选择)。
每次强制\(S\)中\(1\)的个数为\(K\)，转移时强制移动\(S\)中的第一辆车(保证第一个位置为\(1\))。
显然每次转移都是一模一样的，用矩阵快速幂优化一下就可以跑过\(n\leq 10^9\)的数据点。

3. [HNOI2010]CHORUS 合唱队\(\ \)(Chorus.cpp)

水题，放在普及组第\(3\)题还差不多。
\(f[l][r][0/1]\)表示放置完\([l,r]\)的人，本次放的是\(0/1\)(左端/右端)的方案数。
转移就是一般的区间\(DP\)的转移，自己手玩一下即可，也非常简单。

4. [HNOI2010]CITY 城市建设\(\ \)(City.cpp)

难度比较大......
做法是分治，
对于一段修改序列，修改操作涉及的边我们没法处理，递归解决。
考虑当前所有 不涉及修改的边 ，其实每次我们可以直接排除一些边对后面的影响：

( 1 ) \(Contraction\):
把修改边的权值设为\(-INF\)，跑一遍\(Kruskal\)，
此时出现在最小生成树中的非 \(-INF\)边在后面必须要选。称其为必选边。
( 2 ) \(Reduction\):
把修改边的权值设为\(INF\)，跑一遍\(Kruskal\)，
此时出现在最小生成树中的非\(INF\)边在后面一定不会选。称其为无用边。

那么二分处理修改序列。
在二分的每一层，排除此时的必选边与无用边，然后得到一个新的边集，递归处理。
边界条件是只剩下一个修改，这时修改对应边的权值，然后跑\(Kruskal\)即可得到答案。
每一次删边都大幅度的减小了图的规模，复杂度暂时不会证，就\(O(AC)\)吧。

5. [HNOI2010]MATRIX 矩阵\(\ \) (Matrix.cpp)

个人认为是HNOI2010中出的最棒的一题。
显然确定了矩阵的第一行第一列这个矩阵就可以确定下来了。
直接暴搜这个可以\(0ms\)跑过一个点(~~虽然直接全局暴搜也可以\(24ms\)跑过这个点~~)。
下面看正解，我们先构造一个不管值域范围的和合法的矩阵：
\[c[i][j] = sum[i][j]-c[i-1][j-1]-c[i][j-1]-c[i-1][j]\]
特别的，第一行第一列的\(c = 0\)。假设\(mp[i][j]\)表示最终确定的矩阵。
那么显然有：
\(mp[i][j] = mp[0][0]*f(i+j+1)+mp[0][j]*f(i)+mp[i][0]*f(j)+c[i][j]\)
其中\(f(x) = (x\%2==1) ? (-1) : (1)\)
所以枚举第一行的情况，利用上面的关系是检查第一列是否有解即可。
具体的检验法就是把\(mp[i][j]=\)\(0\)或\(p-1\)带入上面的式子中，解出\(mp[0][j]\)。
得到的两个值即为此时的限制\(Dn_{now}\)与\(Up_{now}\)，
然后\(Dn = max(Dn,Dn_{now})\ ;\ Up = min(Up,Up_{now}) ;\)，判一下空集即可。

6. [HNOI2010]PLANAR\(\ \)(Planar.cpp)

改善心情的一道题 ( ~~HNOI2010题目难度两极分化真的很严重啊~~)。
首先平面图定理：\(边数 \leq 点数*3+6\)，把边数降到\(O(n)\)级。
显然直接把给你的哈密顿路径拉成一个环。
那么除了环上的边，剩下的边只有可能在环的里面或者环的外面。
网上一堆人嚷嚷 \(2-SAT\) 其实完全没必要。
判一下线交，类似关押罪犯那题一样做一遍补集并查集即可。

7. [HNOI2010]STONE 取石头游戏\(\ \)(Stone.cpp)

话说每年省选都一定会有一道毒瘤题。这题我感觉考场想出来的概率为\(\% eps\)......
题目的意思是：给两个栈和一些双端队列，问先后手最优方案下的取值。
先看栈，栈的取值其实是固定了的。
对于栈\([a_e a_{e-1} ....a_2 a_1>\)，如果有\(a_e > a_{e-1}\)，
那么当前的先手(当前取的人)去取\(a_{e-1}\)肯定是不优的，因为对手立刻可以取掉\(a_{e}\)。
我们把这种情况放到最后，按照奇偶顺序去取。
然后是双端队列，双端队列的处理则比较巧妙：
对于双端队列\(<a_1 a_2....a_{e-1}a_e>\)，如果存在\(a_{i-1} < a_i > a_{i+1}\)这样的上凸关系，
那么此时的先手与后手的收益差其实是确定了的，
所以我们把收益替换为：\(a_{new} = a_{i-1} + a_{i+1} - a_i\)。
由于这样合并后，先后手收益关系并没有变，
所以这样不断变化，序列每个元素其实就变为了先后手收益差。
注意理解这里：这里的先后手收益差中的先手是指第一个取这个元素所代表的石子堆集合的人。
然后把元素从大到小排序，依次取，得到最终两者的数量差，解方程即可的到两人的最终石子数。

8. [HNOI2010]FSK 物品调度\(\ \)(Fsk.cpp)

此题又是强行二合一(另外一道~~蛇皮题~~是[SDOI2010]粟粟的书架)。
先解决比较简单的一问吧。假设我们已经得到了\(pos_i\)数组，那么最少步数是多少？
这一问还是比较容易的。先把循环节都跑出来，把长度为1的丢掉,
设循环节的长度为\(L\) , 那么就两种情况：

( 1 )循环节中有 \(0\)(空位),
那么直接循环\(L-1\)次把循环节上的每一个点归位即可，一共操作\(L-1\)次。
.
( 2 )循环节中无 \(0\)(空位),
那么先把\(0\)拉进循环节，再循环\(L-1\)次，然后把\(0\)踢出去，一共操作\(L+1\)次。

然后就是\(pos_i\)数组的求解。我们要给每一个点分配一个位置，
看一下公式：\(pos_i=(c_i+d*x_i+y_i)\ mod\ n\)
如果\(y_i\)固定，那么\(pos_i\)的取值会构成一个环。
所以我们从小到达枚举\(y_i\)，检查\(y_i\)对应的环中是否还有\(pos\)可以取。
如果没有可取的，\(y_i++\), 到下一个环中继续找，直到找到了一个合法的取值为止。
显然这个东西直接用并查集或者链表维护就行了。

9. HNOI2010 考察知识点汇总

( 1 )弹飞绵羊(Sheep)： \(LCT\) 、分块
( 2 )公交线路(Bus)：状压\(DP\)、矩阵优化
( 3 )合唱队(Chorus)：区间\(DP\)
( 4 )城市建设(City)：二分、最小生成树
( 5 )矩阵(Matrix)：搜索与剪枝、数学推导
( 6 )平面图(Planar)：平面图定理、并查集
( 7 )取石子游戏(Stone)：逻辑推导，贪心
( 8 )物品调度(Fsk)：并查集、置换群

随机推荐

poj1006生理周期（中国剩余定理）
/* 中国剩余定理可以描述为: 若某数x分别被d1..….dn除得的余数为r1.r2.….rn,则可表示为下式: x=R1r1+R2r2+…+Rnrn+RD 其中R1是d2.d3.….dn的公倍数,而 ...
八卦一下黄晓明和Angelababy的电话号码
最新一期20150605的<奔跑吧兄弟>真是太搞笑了,邓超被大家整的... 但这一期有个细节引起了我的注意,就是Angelababy在现场打电话给黄晓明,而拨键声音十分清晰.一些拥有“绝对 ...
【腾讯Bugly干货分享】手游热更新方案xLua开源：Unity3D下Lua编程解决方案
本文来自于腾讯Bugly公众号(weixinBugly),未经作者同意,请勿转载,原文地址:http://mp.weixin.qq.com/s/2bY7A6ihK9IMcA0bOFyB-Q 导语 xL ...
SQL 常用语法一
整理笔记,并将常用的SQL语法记录下来. 这些方法有 CASE WHEN, IFNULL,GROUP BY,LIMIT,SUBSTR 1,字段转换 CASE WHEN 意义: If(a==b) a=c ...
ToB蓝海的台阶-PaaS,SaaS技术详解
前言随着大量SaaS公司进入市场,我们看到颠覆性的软件服务以各种方式进入企业流程-从营销工具到支付系统.随着SaaS帮助优化业务流程,实现更流畅和自动化的运营,风险投资公司首先潜入池中寻找最优秀和最 ...
js 发送短信倒计时、秒杀倒计时实现代码
<!doctype html> <html> <head> <meta charset="utf-8"> <meta name ...
2014年蓝桥杯省赛A组c++第1题(暴力求解)
/* 小明带两个妹妹参加元宵灯会.别人问她们多大了,她们调皮地说:“我们俩的年龄之积是年龄之和的6倍”. 小明又补充说:“她们可不是双胞胎,年龄差肯定也不超过8岁啊.” 请你写出:小明的较小的妹妹的年 ...
MySQL锁机制&amp&semi;&amp&semi;PHP锁机制,应用在哪些场景中呢？
正文内容模拟准备--如何模拟高并发访问一个脚本:apache安装文件的bin/ab.exe可以模拟并发量 -c 模拟多少并发量 -n 一共请求多少次 http://请求的脚本 C:\phpStudy ...
解压版中文乱码问题MYSQL中文乱码
安装的是解压版的MYSQL,具体配置参考:https://jingyan.baidu.com/article/9c69d48f85032f13c9024e15.html . 1:解压之后copy 一个 ...
机器学习--&gt&semi;期望风险、经验风险与结构风险之间的关系
https://blog.csdn.net/liyajuan521/article/details/44565269 在机器学习中,通常会遇到期望风险.经验风险和结构风险这三个概念,一直不知道这三个概 ...

秒客网

$HNOI\ 2010$ 解题报告