迟到的NOIP游记

呃。。。。。。看标题就知道不对劲是吧。。。。。。。

好吧这要到一个月之前。。。。。

双11前(NOIP2017pj)lz说“很简单的,一等不难,只要你把*******(和谐掉)打熟,然后********(其实是忘了也就是有好好认准备的意思)”。。。。。。

然后像我这么辣鸡的楞还不好好努力。、。。。。。。。

(上面怎么每一行都是。。。。。。)

在这之前我们有集训,我也参加了。lz说每天晚上最好都腾一点时间刷题打模板什么的。。。。。。

However

我之前每天作业都写到12点后/喷血.jpg

哎算了好好改过吧(我好弱QAQ)

---------------------------------------------------------------------------------------------------------------------

嗯好的前一天我们就一直在颓废(我没带电脑)(即使借了电脑也最多打出一个归并模板)(本来想把最短路搞熟的)哎。。。。。。

双11的那个早上我们挺早起的。。。。。

(我还信心满满以为自己能靠奇技淫巧拉一点暴力分)

当我到了比赛地点时莫名紧张又莫名膨胀(哇我好敢哦)

记得赛前LZ跟我说:“很简单的,文化课那么好应该没什么问题吧”;

然后我就虚了emmmmmmmmm

---------------------------------------------------------------------------------------

好的T1,,,很水的小学生一年级题。。。。不说。。。。。

-------------------------------------------------------

T2。。。。

给你几个书码,再给你几个查询码,然后问你以这些查询码作为结尾的书码有没有匹配项,若有就输出编号最小的书码,否则输出-1。。。。。。。。

我的写法就是枚举所有编码,然后去取余,如果可以的话就每次min一下。。。。

这样效率mn,反正数据不大(当时有人说有前导0吓死我)

嗯。。。有几个神犇为了给我这种蒟蒻让路不屑的不给啊掉(感人)

-------------------------------------------------------

T3吗。。。。。哎伤心

这题我看了一开始很蒙:什么鬼啊什么暴力都是假的。。。。。。。

ugly宽搜?最短路?图DP?

于是懵逼的我就打了个爆搜。。。。。

没判边界和没记录数据然后就炸掉怎么也调不好(最后打了个假DP却没拿分)orzzx打了DP拿80

后来才知道要弄一种类似记忆化+剪枝的东西(我真的太弱了qwq您们都想得出来)以下深搜思路:

从第一个点开始搜。每次搜上下左右4个点,然后用ans[x][y]记录搜过点的价值,因为每一个点有可能搜多遍,所以如果搜到的ans[x+i][y+j]>=ans[x][y]就不必再搜下去。。。。

反之替换然后进行下一步:{判断是否空,如果是空格就dfs(x+i,y+j,sum+2,1)1表示用过;然后如果是1,就判不能再搜空白;(因为说膜法的颜色可以自选,所以最小的价值肯定是改成同色即0)

如果是有色,就dfs(x+i,y+j,sum+1或sum,0)0表示有色格;然后按要求继续搜下去;}

if(x==a&&y==a)就min一下sum;最终的sum即为答案;

本题个人觉得主要就是解决死循环问题以及用不用膜法。

---------------------------------------------------------------------------------------------

T4跳房子

我看了也是一脸懵逼。。。。(什么鬼一看到DP就想吐血)(而且范围还辣么大)

然后题目我也没怎么看懂。。。。。他们说二分DP队列优化???我没听过这种操作。。。。。。(哎还是太咸了)

找时间去干吧。。。。。(其实T4的暴力好像比较好打)

——————————————————————————————————

莫名有些绝望啊

渐渐,我迷失了;

恍恍,它离去了;

悄悄,我无言了;

想想,力不足了;

NOIP,Nerve On Improving Practice

原文地址:https://www.cnblogs.com/A-nice-orange/p/8007291.html