2016.8.18上午纪中初中部NOIP普及组比赛

链接:https://jzoj.net/junior/#contest/home/1336

翻!车!啦!好吧,那是因为大神归来。

进度:

比赛:AC+20+0+0=120

改题:AC+40+0+0=140

一、跳格子

链接:https://jzoj.net/junior/#contest/show/1336/0

这么多水,怎么跳啊?

考试时发大招:DP!!!

状态转移方程不难想,

而是有的人没反过来想

题目简化:

就是到每个格都能向前跳a[i]格,

从1跳到n最少跳的次数。

正解:

我们写转移方程时都总会想到是怎么“来”的,

而总是没有想到怎么“去”的。

因此,按照题意,我们得要这么做:

设f[i]表示到i点时的最少步数。

1:初始化。f[2..n]=maxlongint,f[1]=0;

2:按题意DP。f[i+j]:=min{f[i+j],f[i]+1}(2<=i<=n 1<=j<=a[i])

3:输出f[n]

二、2048

链接:https://jzoj.net/junior/#contest/show/1336/1

题目坑人!那个“输入”和“输出”那里写着“game.in/out’”,

比赛完之后题目上面的红字才出现“2048.in/out”,(比赛时没有)。

我给自己加20分!!!题目坑的不算!

不过嘛……如果AC了,那改成一个较好的版面,用一下random,就可以玩了!(AC有好处!)

题目简化:

2048大家都玩过吧,就是模拟过程

正解:

模拟过程,注意:

2 4

2 2

2—上—>4

4 0

靠那个方向的那一边的优先

还有判断赢输时应该看看还能不能走,而不应只看是否满了

三、游戏

链接:https://jzoj.net/junior/#contest/show/1336/2

考试时暴搜没判断是否相邻的相等。。。

题目简化:

有三种选法:

1 1 1

1 2 0

2 1 0

然后给出这三个的个数,要求最多能选多少次。

正解:

如果都减去一个u盘和一个鼠标

就变成了:

0 0 1

0 1 0

1 0 0

因为相邻的不同,所以

x <= y+z+1

y <= x+z+1

z <= x+y+1

二分ans,然后看看是否合法即可。

四、极其简单的最短路问题

链接:https://jzoj.net/junior/#contest/show/1336/3

坑坑坑!!空间超限是一定的!!!

然而,神们却机智地一维化。。。

题目简化:

就一个最短路径问题!

正解:

正在脑补中,请稍等。。。

大神回来后翻车是正常的,但是有点离谱。。。

题外话:

1、明天是最后一天了,大家好好珍惜吧。

2、现在莫名其妙的错误越来越多,快坚持不了每天AK了。

04-26 20:52