UOJ Logo AntiLeaf的博客

博客

弱菜AntiLeaf的提答练习计划

2017-07-12 06:30:03 By AntiLeaf

还有几天就是NOI了,还有5个晚上可以在学校做题,这5个晚上我决定好好练习一下平常没怎么注意过的提答题,为NOI做准备。

计划每天晚上做一道题(为什么昨天没有呢?因为太颓了),为了防止自己偷懒,每做完一道题我会在这里发(我拿到的分的)伪题解。

同时为了防止偷懒,提前列好计划:

(后两道题还要感谢 @bzoj 的提醒)

(7.17和7.18的话……留出来敲板子和复习好了……)


7.12 UOJ#208 UOIP十合一

我的最后提交

我还是Naive……测试点6想到了答案就是$n$个点的有标号DAG个数,然而并没有记住$O(n^2)$的递推式怎么玩……不过要我手推$O(n^3)$的递推式的话还是不难的……

感觉新发一篇博客可能有点占UOJ博客的版面,那我还是都写在这里好了……

(感觉贴代码有点占地方,毕竟这里还要写好几天……所以就不贴代码了)

测试点1

一眼看去感觉像是出点编号$\le$入点编号,判了一发发现的确是对的,去掉自环就好了……

测试点2

观察一波之后感觉比较有规律,写个程序判一下发现每个弱连通块都正好有5个点10条边,那么对每个连通块分别暴力就行了。

测试点3

不难发现每个点恰有一条出边,那么找出所有的环之后对每个连通块减去选环的方案数再乘起来就行了……

测试点4

这个……因为一眼看着感觉没什么规律,就没往分层图上想……

我还是Naive了啊……第二次被分层图坑了……(上一次是UOJ#259 子集计数问题

测试点5

一眼看上去也没啥规律,不过反正我在做测试点2的时候写了一个Tarjan,直接搬过来判一下发现每个SCC的边数都很少,那么对每个SCC暴力之后乘起来,最后乘上不属于SCC内部的边的贡献就行了。

测试点6

一眼看过去发现是一个$n=100$的完全图,但是一开始NC了,没发现答案就是$n$个点的有标号DAG个数……不过瞎xx暴力了前几项之后发现一个熟悉的数字:543……这个数好像在我写DAG计数的时候见过,那看来答案就是$n$个点的有标号DAG个数了。

然而我是在最后才想起来答案就是这个的,并没有时间再写$O(n^3)$的DP了……有点可惜。

(设$f_{i,j}$表示$i$个点且有$j$个点入度为0的DAG个数,转移的时候瞎xx搞一搞就能搞出$O(n)$的转移了)

测试点7~10

……后4个测试点以我现在的能力是做不出来的……(我没写过测试点7这种类型的子集DP……)

所以……略吧(逃

总结

其实前6个测试点对我来说都是很可做的范围的……然而最后只拿到了40分,看来自己提答经验还是不够,并且做的实在太慢了。

没关系,今晚上还有UOJ#215 【UNR #1】果冻运输,再接再厉……

ps:一会儿还要去UNR……


7.13 UOJ#215 【UNR #1】果冻运输

我的最后提交

这题……有毒……

真的没啥可写的……我的分都是纯手玩……

玩了两个小时只玩出了40分……主要是因为没有直接看一遍所有数据,早知道都这么小我就去写暴搜了啊QAQ……

ps:这种考察选手玩游戏能力的题真的好吗QAQ……


7.14 UOJ#109 【APIO2013】TASKSAUTHOR

我的最后提交

因为某些事情耽误了一点时间,做题的时候心也不静,然后就33分滚粗了QAQ……

子任务1

想卡Floyd很简单嘛……造一个$101$个点没有边的图就行了,至于询问随便打一个即可。

子任务2

要让Bellman-Ford达到$(n-1)m$的上界很简单,反着造(正着造会因为循环顺序的原因一遍更新完)一个边权为$1$的链,其余边边权设成一个很大的数就行了。

为了不让Floyd TLE,最多只能有$100$个点……算了算发现边数需要$10^3$多一点,手动枚举一波边数就行了。

子任务3

……正常情况下子任务1的输出应该正好有$105$个整数,所以直接把子任务1的答案粘过来即可……

子任务5

……我还是Naive

直接把子任务2粘过来了,结果只有4分……后来才想起来因为前面是Dijkstra所以点数可以大一些……QAQ

子任务7

显然后面的问题必须恰好$71$个点和$1500$条边才能满分,随机了几个图发现暴搜都会TLE,随便交一个就好了……

(这个点是真·送分点)

总结

听说这个提答很简单啊……然而分还是这么低,不知道是因为心不静还是能力不够。

还有两道提答,再接再厉。

评论

matthew99
如果UOJ十合一的#9和#10把你卡住了建议跳过,NOI考不到那么难。
bzoj
我感觉#190和#135比第一题更适合noi难度
WrongAnswer
OI考纯手玩不就成偏题了吗……可见 UOJ#215 【UNR #1】果冻运输 并不是手玩题……而是一道搜索题。

发表评论

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