saffah的博客 - saffah的博客

NOI2020美食家，神奇做法 revisited

2022-07-04 04:05:17 By saffah

NOI2020美食家，神奇做法（ https://saffah.blog.uoj.ac/blog/6401 ）

又能通过所有 hack 数据啦！（ https://uoj.ac/submission/561732 ）

吊打 std 近 40 倍，快来 hack 吧！

（手动捂脸熊）

2020-08-20 12:40:01 By saffah

果然是假了……5n²m+k² 的结论是有问题的，虽然循环节长度是 5n，但是第一个循环之前的长度可能有 25n²，感谢 pink_rabbit 指出。

这样的话最坏情况的复杂度是 25n³m+k²，只是评测数据看上去是随机的没有出现这种情况……果然加强版题目也算 abuse 随机性了（

可以在这里提交加强版题目：https://duck.ac/problem/2003

————————以下原文————————

设 $f(u,v,t)$ 表示 $t$ 天从 $u$ 走到 $v$ 的最大权值（无视美食节），这在 $t$ 足够大时是有循环节的，循环节之间是等差数列，循环节长度不会超过 $5n$。

暴力哈希找到这个循环节，预处理每个 $u$ 出发在循环节之前的部分，即可每次 $O(1)$ 求一个 $f(u,v,t)$。

对于有美食节的情况，可以朴素 $k^2$ 来 DP 是否经过每个地方。总时间是 $5n²m+k²$。

不知道有没有优美的方法能把这个 $k^2$ 也干掉……

2020-08-16 11:48:45 By saffah

2018年1月7日，#98（【集训队互测2015】未来程序·改）的点赞数是-329。

2020年8月16日，点赞数是+111。

R.I.P.

2015-04-20 22:43:21 By saffah

UPD：所有题解已上传

2015-04-14 21:26:22 By saffah

国家集训队互测2015 Round #5（镜像）将于4月20日星期一晚上18：30举行！比赛将进行4个小时，共三道题。

欢迎大家来虐~！

在OI界，有一段无人不知无人不晓的话：“伊甸城运动场上，一大串ydc排起了有点长的队伍来吃一道菜，这道菜里面含有异丁醇，这队伍有多长？要多长有多长！”

此次比赛将以ydc为主题。

本场比赛内置一道非传统题，一道模板题和一道非模板题，适合下至普及组上至CTSC，从Newbie到IGM全年龄段放心食用。

出题人：saffah,ljcc,Tohka

这场比赛计入rating，涨跌幅度为正常比赛的$\frac 14$

题目难度和题目顺序无关

UPD：比赛已经结束，恭喜获得前 5 名的选手！