2018-11-1 NOIP 模拟赛解题报告

T1 Domino 多米诺骨牌

题目大意

给你N个骨牌,上下各有一个数,要使上面一排的和为偶数,同时下面一排的和也为偶数,最多要翻转多少次?如果无法达成那么输出-1。

解法

水题秒切

根据数的奇偶性质,无论如何,我们最多只需要翻转一个骨牌即可达成目的。所以只有三种可能:翻转一次达成目的,无法达成目的,不用翻转就达成目的。

骨牌有以下几种情况:

1上下两排和一奇一偶

1.我们如果翻转一个上下奇偶性不同的骨牌,上下两排奇偶性分别翻转,还是一奇一偶,无法达成

2.我们如果翻转一个上下奇偶性相同的骨牌,那么上下两排奇偶性根本没变过,无法达成

所以这种情况直接输-1

2上下两排和都是偶数

这种情况默认就达成条件,不用翻转,输出0

3上下两排和都是奇数

1.我们如果翻转一个上下奇偶性不同的骨牌,上下两排奇偶性分别翻转,就变成两偶了,符合条件

2.我们如果翻转一个上下奇偶性相同的骨牌,上下两排奇偶性不翻转,还是两奇,无法达成

所以对于这种情况,我们只需要枚举其中一个骨牌是否上下奇偶性相反就行了。

T2 lift 电梯问题

题面

某大厦共有 N 层,现在知道共有 K 个请求要上下电梯;下面告诉你每个请求乘电梯的出发层次和结束层次。请你求出整个电梯的运行过程。

假设电梯一开始停在第一层,运行 K 个请求最后回到第一层。 例如有个 9 个层次的电梯,共接收到 5 个请求。

那么电梯的运行路线为:1-2-5-6-8-9-5-4-2-1

解法

也是水题qwq.

因为这么多请求都是同时发生的,所以电梯肯定是从1层到请求中的最顶层,然后再下来。

因为电梯为了时间最优,肯定不会跑回头路,比如有一组数据是这样的:  1,4;3,2;2,1  。运行路径肯定不是1-2-1-3-4-2-1,而是1-4-3-2-1。

所以我们可以根据乘客上下分成两组,分别桶排,然后上行的从小到大输出,下行的从大到小输出。

注意:

如果有一个乘客从某一层到顶层,另一个乘客从顶层到某一层,注意判重。

T3 月亮之眼

题目链接

用SPFA进行差分,关于SPFA,虽然“死了”但是做差分应该不会卡你…

从第a个珍珠到第b珍珠有一条单向边c,就建一条从a到b的正权边c,再建一条反过来的负权边-c。

(如果自上而下有一条边,那么从上到下的距离就是c,从下到上的距离就是-c,这样如果有矛盾的情况,就是负环了,同时这种方法也可以求最短路。)

取结果数组中距离最大的结点,就是最顶端的结点,设其长度为$maxx$,则每条边长度是$dist[i]-maxx$。

关于判断负环:如果一个结点进队N次以上,那么直接输-1并退出。

T4 口袋的天空

题目链接

也是比较水的一道题。

因为题面中给你边,还让你选择边,那和最小生成树最接近了。

Prim 算法是基于点的操作,所以暂时不考虑。

只剩下 Kruskal 了,还是基于边的操作,那应该就是了。

N个结点,N-1条边,那肯定是一棵树,也就是一个联通块。

那我们需要很多联通块,所以肯定要少连几条边,少连的这几条边肯定要越大越好。

我们如果连n-1条边,就有0个结点被孤立,总共1个联通块。

我们如果连n-2条边,就有1个结点被孤立,总共2个联通块。

……

我们如果连n-i条边,就有i-1个结点被孤立,总共i个联通块。

所以Kruskal连最短的n-k条边就可以了。

暂无评论

发送评论


				
上一篇
下一篇