NOIP 2014

题目链接:https://vijos.org/p/category/2014

D1T1 生活大爆炸版 石头剪刀布

没想到noip还会出纯模拟

D1T2 联合权值 

dfs一下就统计出来了

D1T3  飞扬的小鸟

这个dp有、东西,日常不会dp

 

D2T1 无线网络发射器选址  

记前缀和,然后枚举

D2T2 寻找道路

先在反图上从终点bfs,求出哪些点能到终点,然后从起点正着按题意bfs就好了

D2T3 解方程

直接解肯定没办法,只能枚举答案,然后随机素数取模验证。

 

 

NOIP 2013

最近突然想回顾一下历年noip题目,就开个新坑吧,题解就从略了

题目链接 https://vijos.org/p/category/2013

D1T1 转圈游戏

公式就\((x+m10^k)\%n\),现在一眼的事情当时想了很久orz

D1T2 火柴排队

首先肯定是小对小,大对大,才能使那个式子最小,这一点可以交换一下然后做差说明。并且题目保证了高度互不相同,也就是给了两个排列,问最少交换相邻元素多少次,才能使两个排列一样,再转化一步,假设第一个排列就是1,2,3,…n,问第二个排列最少交换相邻元素几次才能变成1,2,3,…n,这就是逆序对的定义了。

不知道如果不保证高度互不相同该怎么做orz

当时这个题爆零了,一点也不会QAQ

 

D1T3 货车运输

这个不难看出是最大生成树上倍增求路径边权最小值。要注意的是可能是一个森林,当时蠢的用tarjan判连通性了,强行增加码量。还好在赛前刚给别人讲过倍增,这题满分了。

D2T1 积木大赛

可能太简单,这题没什么印象了

D2T2  花匠

当时从最长上升子序列的思路出发,然后推了推,写了个单调队列,具体怎么写的忘了,不过也是AC。实际上最简单的做法只需要扫一遍,求出拐点的个数,加2就是答案了。

D2T3 华容道

这题xjb搜,就得了5分…

正确做法是bfs预处理,拆点,建图跑最短路。

具体来说:可以观察到只有空白块位于指定块的四方向上,指定块才可以移动。本质上还有另外一种移动方式,就是指定块不动,空白块从它的上/下左/右中的一个移动到另一个。那么这样就可以bfs预处理了,状态也有了,(x,y,k)表示指定块在(x,y),空白块在相邻的k方向上。spfa求最短路即可。