凉心模拟Day1题解

道歉

由于T2出题人@fengsongquan 不知道他提供题目有原题。
@fengsongquan 道歉原帖

抱歉,第二题题是我看一本数学书(《趣味学数学》(图灵出版社))的时候想到的,没想到POJ已经有原题了,我出这题之前根本就没看到过这个原题,也没有仔细查有没有重题,于是就这样了,我向大家再次道歉,不要再怼了QwQ

且由于我们验题组没有在poj上做过这题,导致我们并没有发现这道题是原题。给洛谷管理员和广大OIER造成了不好的体验与影响。

在这里向全体OIER们和洛谷管理道歉!!!

希望各位OIER能够原谅我们,以后我们一定会改进,争取能做的更好。

在这里再次向各位道歉!

前言

本来早就准备好了题解,但由于比赛出了锅,我们斟酌再三,还是把题解放了上来。

本场模拟赛为本团队原创(T2不是)的题目,难度NOIP提高组,三道题都有验题人验过题了,题目应该不会有太大问题。
本题解按分数档给出题解。

第一档

第一题做法很多,因为数据纯随机,所以可以直接暴搜记忆化,或者一些奇怪的贪心都能过。但是注意记忆化的话内存不能开一亿个int,可以用内存更小的类型来代替。拿不到100分也有70分。
第二题没什么想法的话直接特判掉1,2两个点,20分还是稳的。写个40分也可以。
第三题看不懂题意可以直接弃疗….
70+20=90,这个基本分还是要有的。

第二档

第一题100分。
第二题直接暴搜记下所有可能的状态,可以拿到40分。
第三题个人认为拿24分的唯一难点就是看懂题意(Gold_7在花了20分钟后认为题面描述没有问题),直接按照题目描述模拟即可(虽然有点麻烦)。
100+40+24=164,这个应该大多数OIer都能拿到。

第三档

第一题AC。
第二题40分,第三档出题人没有给出合理的解决方案,或许能拿到60分。
第三题可以加个前缀和优化能拿到第二个点,48分到手,第三个点可以暴力第一个操作之后使用线段树维护,可以再拿24分。
那么可以有100+40+72=212分,这个应该算一个比较高的分数了。

第四档

接下来关键是要二三两题中挑一道拿到更高分数,对于一般提高组水平的选手可能只能花较多时间在其中一道上。可以看出相对来说第二题更考察思维能力,第三题更考察代码能力。这里推荐A掉第二题。
第二题可以看出是一道结论题。Retcarizy第一眼看到这道题就感觉是与某种东西的奇偶性有关。我们考虑如何使得空格移动之后奇偶性不变。一种方法是将图中格子按蛇形的方式展开,就像这样:


我们去掉空格后得到了一个这样的序列:
14,2,6,7,3,13,1,5,4,11,12,15,9,10,8。
可以发现,无论怎么移动格子,该序列的逆序对个数的奇偶性不会变。并且该序列的逆序对个数不为0或1时可以通过操作使得逆序对个数减少2。所以对于初始状态和最终状态逆序对个数奇偶性不同时一定不可行,而且都是偶数的情况下由于逆序对个数为0的排列是唯一的,所以一定可行。但是对于都是奇数的情况下乍看难以得到一个可行的证明方案。这个问题可以先猜个结论,具体的证明已经有数学家给出了,但是证明过程有点长,这里就不提供了。
所以我们就求个逆序对个数判下奇偶性相不相同就可以了。其中第7个点是暴力求逆序对(虽然觉得这档部分分没什么用)。
100+100+72=272分,已经是一个很高的分数了。

第五档

最后一档当然就是AK了。
大佬在A掉前两题之后可以开始搞第三题了。第三题是我花了很长时间出出来的水题….其实思维难度并不高,个人认为学过线段树和矩阵乘法的都能想到正解(只不过代码细节有点多而且难调)读懂题目之后可以大概总结为以下几个:
区间第i项做某种操作i次,
区间做某项操作,
询问区间和。
这样我们可以想到矩阵。通过矩阵方面的理论我们可以这样描述:
设一次傻逼风暴的转移矩阵为A,事件1相当于对一段区间分别加上$A^1,A^2,A^3,A^4……$
事件2和事件3都相当于对一段区间乘上一个矩阵。
事件4和事件5都可以通过对一段区间的矩阵求和来实现。
我们知道矩阵符合分配率,矩阵乘法符合结合律(学过矩阵乘法的人往这个方向想一下也不是很难,其实特别好证),所以可以直接扔到线段树上来维护,标记和维护的键值都是用矩阵来描述的。
由于常数比较大,所以把时间限制开到了10s(实测O(松)还是只能拿48分)(标程在常数极其不优秀的情况下极限数据跑了7s)。还有一点要注意,本人在题面中均使用集合的方式来描述区间,所以可以l>r,为了保证写出正解的人能拿到高分所以我放在了第一个点(对暴力来说并没有什么关系)。

标程

T1 天下第一(peerless)

(法一) 记忆化搜索

这应该是本题的正解

  • c++版本

  • pascal 版本

(法二) 玄学猜想

  • pascal

T2 玩游戏(game)

T3 傻逼症(sbvirus)

Tagged with:

5 thoughts on “凉心模拟Day1题解”

发表评论