• 周日. 11 月 10th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

NOI挑战赛#2 (vp) 记录

admin

11 月 28, 2021

NOI挑战赛#2 (vp) 记录

赛场:69+0+10

赛后:69+0+100

题解

T3

题意:给定 (S,C),求有多少个 (sin[1,S],cin[1,C]),使得:存在若干个整数边长的矩形,它们周长的和为 (c),面积的和为 (s)

(S,Cle 10^6)。几档小部分分是100,2000,6000,30000,100000,400000。

(只会这一个题)

对于一个 ((c,s)) 如果它满足条件,给 (c) 加上 (2),给 (s) 加上 (1),同样满足

(即,加上一个 (1 imes 1) 的矩阵)

因此,对于 ((c_0+2k,s_0+k)) 这样的,如果 ((c_0,s_0)) 满足,就全都满足了

注意到所有这样的点构成一条直线,直线的本质区别在于截距 (2s-c)

那我们枚举这个截距 (i),找到最小的 (s_0) 使得 ((2s_0-i,s_0)) 可行,那对于 (s>s_0,c=2s-i)((c,s)) 一定也是可以的

(f(i)) 表示最小的 (s_0) 使得 ((2s_0-i,s_0)) 行,那问题就是求 (f(i))

暴力的枚举一对 ((c,s))(O(nlog n)) 的。再去枚举 (i) 更新 (f),就是 (O(n^2log n))

(g(i)) 表示最小的 (s_0) 使得 ((2s_0-i,s_0)) 可以由 一个 矩形搞出来。先预处理出 (g),再用 (g) 更新 (f)

更新 (g)(sxrightarrow[cmin]{} g(2s-c)),这个 (O(nlog n))

更新 (f)(g(i-j)+f(j)xrightarrow[cmin] f(i)),这个 (O(n^2))

注意到我们去掉了一个 (log) ,相当于是预处理掉了。这样据说就能拿不少分了,实现的好甚至可以拿到80多

那怎么拿100呢?观察第二个转移,暴力输出每个最优的 (j),发现它都在200以内,(O(200n)) 直接水过

小 技 巧:对于一个限制不多,输入很少,题面很短(讲人话:比较数学)的题目,如果用(复杂度不对的)dp做,通常转移会比较有规律,可以打表观察

赛场记录

我他妈人傻了啊我艹,这啥题啊

泡一杯咖啡,稍微迟了点,8:15开的场,定时闹钟5h

看第一题 -> 有了思路 (去上了个撤硕)->发现思路假了

撤硕是一个充满魔法的地方,我每次去撤硕里都思维特别活跃,发现做法假了或者想出新做法

继续想,⑧会,看T2

看完T2,我脑子一转,这咋做啊,完全没有头绪(题解也完全没懂)

准备打一个 (O(2^n)) 的暴力,(nle 15)。然后仔细一看发现这个数量其实是 (2n),所以复杂度会到 (2^{30}),然后就傻了

去看了T3,仔细一想发现不会正解,退而求其次次次次次次,发现我只会 (n^5),而最小的 (n) 有 100 那么大

此时时间过去了2h,我却已经获得了0分的高分。

但是我的低配大脑长期这样运转,不太能吃的消。再加上今早起的早,没睡够,就睡着了

睡了5min多,脑子里想起来我还在比赛,啪的一下就起来了,跟他妈诈尸一样

我的T2基本上就放弃了(事实证明这个决策是对的),我去主攻T1T3

我发现我的T1问题在于只比较一个串,如果同时比较一堆串接起来其实就对了。然后我就暴力的实现了这个比较。期望得分18。由于数据比较水,最终我的暴力比较跑的飞快(因为我有很多break,且串的LCP非常短),只有最后一个subtaskT掉了,喜提69的高分

我还去想了T3,把那个 (O(n^5)) 的超高速dp,优化到了 (O(n^4))

然后我又想,对于一个面积,周长的方案数是面积的因数个数,因数个数加起来,其实是个调和

然后这个dp就优化到了 (O(n^3log n)),终于有分了,获得了10分的超高分!!!

后来,比赛还有30min结束的时候,我注意到,对于一个 (s),满足条件的 (c) 大致在一个区间里,而只有小部分空缺

我就打表,存每个 (s)(l,r),还有空缺。理论需要跑5~6min,实际跑了20min,因为跑第一遍RE了,我改了几下,再调了一会,重新跑的

事实证明这个空缺是真的少,存储空缺的表用了35K,但是存l,r的表用了他妈48K,而noi.ac这个垃圾网站只允许交50KB的代码(NOI赛场是100KB),我只好压缩一下这个表,就在打好的表上做修改,取个差分,二进制+char的压缩,等等。但是压缩那个表的程序由于太长了,本地渣机编译失败了,时间也不太够了,一阵手忙脚乱还是没搞出来,痛失10分!!!(表打出来就有20了)太可惜了!!!

至此,比赛结束。我打了 18+0+10=28分,获得了69+0+10=79分,挂了-51分。

耗耗反思

  • 当发现比赛题目全他妈不会的时候,冷静下来,从最naive的部分分开始想,心态千万不要乱。如果困可以睡,也不要怕睡觉多浪费时间,如果脑子困,这是唯一方法
  • 去上个撤硕冷静一下
  • 脑子里完全没想法的时候,如果不想傻愣着,可以试试去打表 (别比赛快结束了打表程序没跑完)

发表回复