UOJ Logo ydc的博客

博客

#4 NOI2014 消除游戏题解

2019-05-11 17:32:02 By ydc

求问uoj有哪些表情能用啊?有没有一个表情包的list呢?

虽然知道版刷uoj是不现实的(何况对于一个只能业余时间来陶冶情操的人),但还是看到#4空着有点不爽,毕竟这里是个打游戏总想着集全成就的强迫症患者。

这是我当年进队的那场NOI,考完后很快就把几道传统题做了,但这题一直没做。其实搞OI时,我从来就没管过提答题,觉得费时费力(事实上做这道应该不算太难的提答题就花了我好多时间orz)。

也是退役了之后心态变得不那么功利了,单纯为觉得好玩而刷。(划掉)

网上翻了一圈也没翻到较详细的题解(更别说代码),就来写个题解造福一波。(还会放代码)

解锁成就:AC提答题!

测试点一

观察发现,正好有一个超长回文数和一个超大质数构成,手玩!

测试点十

找规律了好久,感觉并不擅长提答。从输入可以猜出想让你回文串干掉所有数。发现第一行是回文,但二三行并不是。发现每9列会进行一次循环。

所以其实做法就是,如果我能把每个$3 \times 9$给干掉,由于循环节的特性,所以就能一次性干完了。

然后试图干掉前9列的27个数。分成9个$3 \times 3$的块,块与块构成回文。

最关键的是,从左上角(1,1)出发,按照RDLDRRUUR这个策略,会让每个块构成一个回文。

所以事实上……你不断重复这个策略。。。就做完了!

测试点二

随机,每次随机一个质数或回文串,多次得分取最高。

一个优化是串的开头,本来是随的,效果不好,改成了第一个非-1元。可能是这样更容易消完吧。

测试点三,测试点四

这两个点就是要你搜质数。

我们发现事实上测试点二还能更进一步,质数的密度是很高的$1/\ln n$。我们即使强行要求每个数必须是长为18,从一个点出发,上下左右4个方向走,将会有几乎$4^18$个数字串可以选,而这当中几乎肯定有质数。

所以你写个DFS,很快能搜完一个“由500个18位质数”组成的解。

测试点五

数据范围不大,暴力搜!

搜的结果发现并没有找到既是质数又回文的8位串。

由于数据范围实在不大,所以我每次搜数字串的流程如下:每次枚举串长(从8到2),找到长度等于该串长的分值最高串(程序同时考虑了质数与回文的情况,尽管好像回文没有用)。这个枚举是真纯暴力,就是起点是枚举的,然后枚举$4^8$种情况。最后在所有情况中取max。

交了一发这个点9分,但是我已经纯暴力了。想了想发现,我现在是“若目前最优值小于当前答案,更新解,否则不更新”。我改为“否则,若相等则以0.5的概率更新解”,然后外面套了10次迭代,于是10分了。

测试点六

接下来就是搜回文串了。

这个点很水,直接搜。

测试点七

我用6的程序怎么搜都搜不出来,绝望了一阵。

睡了一觉之后做了点小改动。

随机起点变为将起点设为中心,700+变900+。

然后让两端分别按逆序枚举(比如一个往左另一个就先试着往右)

结果秒出。。。卧槽

测试点八

关键在于方向的搜索顺序!

奇技淫巧:奇数轮顺着搜,偶数轮逆着搜。

然后我本来是,随机一个中心点,以他为中心搜若干条回文串。这个“若干”本来定的较大。

经实践发现,定很大和定个10000,结果差不多。而将这个“若干”改为10000后,枚举一个中心点的时间就很低了——低到可以爆枚所有中心点。

实践又发现,枚举前10行作为中心点后,程序已经能跑出很优的解了。

测试点九

虽然$K=5$,但只要和之前一样,找一个超长回文串就很优了。

观察发现,他“几乎”是对称的。打印一下发现100000个数里仅仅36个不对称的数。

我们将不对称的数置为0,将问题转化为,从左侧某个点出发,找一条全不为0的以第64列为终点的尽可能长的路径,然后翻倍——如果能经过所有点那就太好了。

于是试图去弄一个加了剪枝的求哈密顿路径的算法,没啥进展。

最后我启发式的想出这么一个策略:

从(1,1)出发,右,下,左,下,右,下,左,下……直到最后一行,右,右,现在到了(n,3)。然后右,上,左,上,右,上,左,上……直到第一行,然后右,右,如此循环。“尽可能”地按这个策略。

什么叫“尽可能”的呢?就是DFS时,搜索的最优先顺序是这样的即可。接下来“不能这么做的”,就会自动被回溯过程中弄掉。

于是我将DFS的规则定义如下:假设列%2=0,除了在顶端底端外不能往右;假设列%2=1,他就不允许往左。

        int tmp[6],cand=0;
        if(y%2==0)
        {
            if(x==n&&y%4==2)
                tmp[++cand]=DIR_R;
            if(x==1&&y%4==0)
                tmp[++cand]=DIR_R;
            tmp[++cand]=DIR_L;
            tmp[++cand]=DIR_D;
            tmp[++cand]=DIR_U;
        }
        else
        {
            tmp[++cand]=DIR_R;
            tmp[++cand]=DIR_D;
            tmp[++cand]=DIR_U;
        }
      for(int i=1;i<=cand;++i)
        {
            int px=x+movex[tmp[i]],py=y+movey[tmp[i]];
            if(check(px,py))
                DFS(px,py,lcor,rcor);
        }

大家可以根据上述代码理解一下~然后发现很快就出了个非常优的解(不确定有没有经过所有非对称数,反正能拿10分就对了!)

代码可以参见这里

评论

ydc
看了一下发现我购票教的是vfk的代码,自己的代码居然只有97分,哭了
matthew99
非常不错的题解,欢迎来切两道近年HNOI的题目(出题人都是我我会乱说?)

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。