历年NOIP第三题简略题解

前言

老师要求写的…我就只写第三题了。

NOIP 2011 – Mayan游戏

一个棋盘5×7, 10种颜色方块会掉落的三消游戏。方块只能左右拖动, 给定搜索深度, 问消完所有方块的最小字典序解。

解题报告

按照字典序大搜素, 加上可行性剪枝暴力模拟, 就可以通过了。

NOIP 2011 – 观光公交

有一条 又长又直 的公路, 沿路有N个站点, 有M个乘客。
第i个乘客个会在Ti时刻到达站点Ai, 等车前往Bi, 保证[latex]B_i \ge A_i[/latex]。
一辆公交车从0时刻在1站点出发一次经过站点2, 3, 4, …最后前往N站点, 从第i-1站点前往i站点需要消耗时间Di。
所有乘客都必须被运送到目的地, 并且公交车可以在任何一个站点等待乘客。
乘客i的等待时间为 到达目的地时间-乘客来到车站时间 , 现在公交司机有K个氮气加速器, 能让某一个非零Di缩小1, 现在他想让所有乘客等待时间之和最小, 问最小等待时间之和。
[latex]N,M \le 1e3, K\le1e5[/latex]

解题报告

正解是贪心, 复杂度 O(N×M) , 算算发现1个亿是可以过滴!
设 lst[i] 表示第i个站点到达最晚的乘客, 那么公交车到达第i个站点的时间可以递推出来:
$$ time[i] = max\{ time[i-1], lst[i-1] \}+D[i] $$
考虑贪心K次, 每次重新处理处time数组, 定义nxt[i]的意义为如果你让Di减一, 那么time[i], time[i+1], …, time[nxt[i]]都会减一, 而time[nxt[i]+1]会保持不动(在第i站到太早要等人)。
这意味着在使用氮气加速器之前的time[nxt[i]]等于lst[nxt[i]], 并且对于任意整数j属于[i, nxt[i]), 都有time[j]&rt;lst[j], 这个是可以线性处理的。
接下来考虑让Di减去一给答案带来的负贡献。
形式化地, 答案可以如下表达:
$$ ans = \sum_{j=1}^{M} (time_{B_j} – T_j) $$
考虑到time[i], time[i+1], …, time[nxt[i]]都会减一, 我们统计能让B[j]落在区间[i, nxt[i]]内的j的数量, 这就是对答案的负贡献了, 这个是可以利用前缀和线性处理的。
由于需要最小化答案, 很明显的贪心策略就是每次找到最大贡献的D[i], 然后减一重新贪心, 贪心K次, 具体大力实现就可以了。

NOIP 2012 – 开车旅行

题目大意懒癌发作不写了…

解题报告

这就是个代码题…正解应该是类似倍增的乱搞吧…
如果我们预处理从每个城市小A和小B会开车到达的节点(复杂度是NlogN级别的), 那么这些东西形成了类似一颗树的结构(虽然每个节点都有两条出边, 但是对于每个确定的询问就只有一条出边)。
然后就可以开始处理st表了, 接下来就直接在st表上进行询问即可。
处理真的恶心…贴一下预处理代码, nxt1和nxt2代表分别由B和A来开车会从i开到哪个城市:

	for(int i = 1; i<=N; i++) {
		nxt[i][0][0] = nxt1[i]; // B
		len[i][0][0] = abs(H[nxt1[i]]-H[i]);
		lenB[i][0][0] = len[i][0][0];
		nxt[i][1][0] = nxt2[i]; // A
		len[i][1][0] = abs(H[nxt2[i]]-H[i]);
	}
	for(int lvl = 1; lvl<20; lvl++) {
		for(int i = 1; i<=N; i++) {
			nxt[i][0][lvl] = nxt[nxt[i][0][lvl-1]][lvl==1][lvl-1];
			len[i][0][lvl] = len[i][0][lvl-1]+len[nxt[i][0][lvl-1]][lvl==1][lvl-1];
			lenB[i][0][lvl] = lenB[i][0][lvl-1]+lenB[nxt[i][0][lvl-1]][lvl==1][lvl-1];
			nxt[i][1][lvl] = nxt[nxt[i][1][lvl-1]][lvl!=1][lvl-1];
			len[i][1][lvl] = len[i][1][lvl-1]+len[nxt[i][1][lvl-1]][lvl!=1][lvl-1];
			lenB[i][1][lvl] = lenB[i][1][lvl-1]+lenB[nxt[i][1][lvl-1]][lvl!=1][lvl-1];
		}
	}

NOIP 2012 – 疫情控制

题目大意不写了…

解题报告

这题还是比较好的, 探究一些性质:
1.答案有单调性。
2.任何一个位于非根节点的军队只可能向父亲移动, 向儿子移动一定是不优的。
3.军队行为分为两种:守住阵地(根节点深度为0, 军队移动到深度为1的节点就停止移动), 重新部署(一路移动到根节点, 然后移动到根节点的一个儿子节点再保持不动)。
发现N只有50000, 容忍Nlog平方N的算法, 考虑二分答案。
检查的话就按照以下方法贪心:
1.能够移动到根节点的军队全部移动到根节点。
2.不能移动到根节点的军队尽量向上移动, 这个用树链剖分或st表都可以。
3.用bfs搞出根节点的子树中没有被控制的。
4.把能够跑到根节点的军队贪心地进行重新部署, 具体贪心操作就是按照行动能力把能够到达根节点的军队重新排序, 按照行动能力从小到大枚举, 如果这支军队原先所在的子树没有被控制就把军队放在原先的子树, 否然随便选一个军队能够到达的。
然后就搞定了。

NOIP 2013 – 货车运输

给你一个无向图, 边带权, M个询问, 每次询问两个点u和v之间边权最小值最大的路径。

解题报告

最大生成树+LCA裸题, 注意处理不连通情况即可。
吐槽:这题暴力爬树也能过…

NOIP 2013 – 华容道

给你一个N×M的棋盘, 棋盘有一些固定的格子, 其他都是可以移动的棋子或者空格子, 一共只有一个空格子和一个特殊格子, 每次可以选择一个和空格子四联通的格子移动到空格子。
给出棋盘, 有Q个询问, 每次给出空格子, 特殊格子和目标位置的坐标, 问最少进行多少次操作能够让特殊格子移动到目标位置。
[latex]N, M \le 30, Q \le 900 [/latex]

解题报告

由于状态数很小, 暴力搜可以拿60分。
考虑到白色格子只可能从某处移动到特殊格子四周, 预处理当特殊格子在任意位置时, 白色格子从特殊格子四周出移动到每个位置的最小步数, 这个是4×N^4的。
然后利用预处理的信息暴力回答询问即可, bfs大力跑得飞快, 我用dijkstra一样的写法只能卡时间线过…

后面的还没写, OJ又挂了