UOJ Logo saffah的博客

博客

NOI2020美食家,神奇做法 revisited

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

NOI2020美食家,神奇做法

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²$。

https://loj.ac/submission/911370

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

#98

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

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

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

R.I.P.

集训队互测 2015 Round #5 题解

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

集训队互测 2015 Round #5

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 名的选手!

  1. nooon
  2. Rating_Jia_Jia
  3. SkyDec
  4. wwx
  5. charlie01
saffah Avatar