UOJ Logo vfleaking的博客

博客

UOJ系统更新啦

2021-04-02 03:55:03 By vfleaking

趁着大家睡觉更新一波UOJ

UOJ终于支持 C++ 14、C++ 17、C++ 20 了。。。按照之前大家在 UOJ 用户群的投票,选择把之前所有语言为 C++ 的记录更名为 C++ 03。

第一个 C++ 20 的提交记录!https://uoj.ac/submission/466125

操作系统升级到了 Ubuntu 20.04,编译器升级到了 g++ 10.2.0。

测评机变成了一台双核的测评机,目前只开了一个核,之后会把另一个核也开起来的。希望以后测评能更稳定一点吧。。。

新版编译器编译出来的 C++ 程序好像内存会大一些,跑 A+B 好像也不能稳定地做到 0ms。。。不明觉厉

非传统题的测评程序需要重新编译,除了509和569之外都搞好了,这两个就先隐藏了 QwQ4月2日下午六点更新:修好了)

如果最近发现了 UOJ 的啥 BUG,不要犹豫!赶紧告诉我哦……

(啊困困,感觉上面都是在随机码字。。)

4月4日更新:现在测评是双核的啦!为了测评稳定性我现在关掉了超线程。

4月8日更新:原来的老测评机现在永久地关闭了。一路走好 QwQ

UOJ开始记录测评历史

2021-02-19 19:41:16 By vfleaking

14年,vfk 在写 UOJ 的时候

  • 大家还在争论 C++ 和 Pascal 孰优孰劣;g++ 最新版还是 4.8;C++ 11 还没有什么人写;
  • 大家在为 NOI Linux 换成 Ubuntu 12.04 的内核而欢呼雀跃;Ubuntu 14.04 LTS 还是非常新潮的操作系统;
  • Chrome 还没有满地跑;IE 还没有退出历史舞台;
  • Bootstrap 4 还没有出;HTML 5 和 CSS 3 还有很多浏览器不支持;
  • 王宏老师在 WC 上关于IOI近年的非传统题演讲还言犹在耳;OI 界掀起了一波出非传统题的风潮;提交答案题我记得还只有 Contest Hunter 一家能测……

vfk 当时以为,我们 OIer 只要固定一组系统配置,那么对大家的程序就都是公平的。。并且 vfk 当时不知为何还产生了 “计算机的世界过去迭代了这么多轮了,所以未来变化不大了” 的错觉。。所以当时就固定下来了在当时看来还很新潮但现在看来已经有点老旧的配置。。。

所以怎么办呢?vfk 最近决定升级一下操作系统、编译器版本等等。。并支持下大家心心念念的 C++ 14、C++ 17、C++ 20。。。

捂脸熊

但是这样的话以前的测评记录结果可能重测后就会变化了。为了即将到来的升级,vfk 先码了一个支持记录测评历史的功能,这样以前的历史可以被保留下来(吼吼,所以以后有人瞎 hack 的话,也容易回滚历史了!)

例子: UOJ 的第一个测评记录 https://uoj.ac/submission/1 现在存了上一次测评的结果(这时候有人就要问了,诶,为什么这个记录上一次的测评时间不是 14 年哇?这是因为 vfk 老是为了调 bug 而偷偷重测这个记录 233333)

升级不知道什么时候能搞好,有进展我就在这里吼一嗓子 QAQ

一嗓子: https://vfleaking.blog.uoj.ac/blog/6666

UOJ NOI Round #4 排行榜

2020-08-13 18:10:25 By vfleaking

下面宣布 UOJ NOI Round #4 总排行榜!(自动鼓掌,瓜几瓜几瓜几瓜几……

因为参赛人数比预期多,所以金银铜牌数量都进行了扩充。

祝取得高分的选手在 NOI 中继续保持高水平!

没参加笔试还拿到牌牌的选手在 NOI 中一定要记得参加笔试哦(大雾)

(知乎吐槽传送门: https://www.zhihu.com/question/413718499

阅读更多……

深切哀悼逝世同胞

2020-04-04 01:50:05 By vfleaking

2020 年 4 月 4 日,是中华传统节日清明节,也是纪念所有因此次新冠肺炎疫情逝世的同胞的全国哀悼日。

在这个充满哀思的日子里,UOJ 全站切换为了黑白色,以表达深切的哀悼。

我是土生土长的武汉人,UOJ 也是在湖北武汉备案的网站。曾经武汉是那么的热闹,清晨的热干面铺子,总是人挤人。

但不知何时,这场天灾悄悄地来到人世间,突然在我的家乡爆发。我看到了很多身边人受苦受难,看到了现代文明是如此地不堪一击。

愿每一个因疫情离开我们的人都能被人铭记。

愿每一个因疫情陷入窘迫的小人物都能早日走出困境。

愿我们弱小而无知的人类,能从这段历史中不断反思、总结。

愿我们弱小而无知的人类,永远保持谦虚,永远敬畏自然,永远相信科学和理性。

最后,愿我们每一个热爱计算机科学的 OIer,退役之后仍能走在科技的最前沿,成为人类技术进步浪潮中的一朵浪花。

毕竟,能对抗天灾的,不是傲慢,而是科学。

与君共勉。

近期UOJ的一些改动

2020-03-29 17:08:56 By vfleaking

大扎吼,我四渣渣k,贪玩懒J,介四里没有挽过的船新版本。挤需体验三番钟,里造会赶我一样,爱象节款OJ!(大雾)

咳咳,说人话。就是最近觉得 UOJ 实在是太年久失修了!强迫症的我这两周改了一发各种不爽。

当然在强迫症的眼里不爽的地方太多了,与我自身能付出的时间极度不匹配。所以我只能先改一部分了。。。

已经完成的改动

题目中的图片问题

由于有些题目时间比较久了,图挂掉了。这是因为有些图片是放在奇奇怪怪的网站的,然后有些没能经受起大风大浪,就倒闭了。。。

所以我通过各种方式先把挂掉的图找了回来(主要是找出题人要),然后把所有现存的题目中的图片移动到了 UOJ 的图床 img.uoj.ac 下。

这样只要 UOJ 不倒,图片就不会挂啦!

Mathjax 的问题

博客评论里面,如果对一个评论的回复超出了一页,那么翻页的时候 Mathjax 不会被重新加载。去年 9 月 就有良心用户报告过这个问题。这显然是个 bug,现在已经修好辣!

以及 UOJ 使用的 Mathjax 原来是 2.6.0,有点老了。为了紧跟潮流,现在升级到 2.7.7 辣。当然如果 Mathjax 3 更好用的话会考虑再升级一下。

CE 时的错误信息长度

原来 UOJ 存储时为了节省空间,在大家 CE 的时候会把错误信息只截取前 500 个字节保存下来。

但我寻思着你交个代码就几 KB 没了,何必节省这种空间。。毕竟通常来说只截取前 500 个字节会看得人一脸懵逼。

所以现在把长度限制改成 10KB 了,感觉肯定够用了。

Markdown 教程的链接

UOJ 博客编辑器右上方会有个 “这玩意儿怎么用” 的链接,链到 UOJ博客使用教程

里面附了一个完整的 Markdown 教程链接,但是不知什么时候链接挂掉了。去年 8 月就有良心用户报告过这个问题。

现在我已经把该链接从 http://wowubuntu.com/markdown/ 更换为了 https://www.w3cschool.cn/markdownyfsm/

如果你是考古爱好者,可以在这里找到原来的链接的存档。

即将上线

HTTPS

如果你戳戳 https://uoj.ac 就会发现 UOJ 已经可以通过 HTTPS 访问勒。。

当然我还没有设置把 HTTP 强制跳转到 HTTPS,估计在某个夜深人静的晚上我就会设置了。

交互库加密

UOJ 一直以来都是使用输出 token 的策略来防止交互库被 hack 的,但 UOJ 上有些 CTF 选手水平非常高超,一眼就看穿了怎么把 UOJ 的交互库给 hack 掉,程序跑得比谁都快:#277631, #352160

为了防止世界被破坏,我研究了下怎么更好地防御攻击,做了一个小小的带加密的交互库(见 #509 下方的说明,mt19937_64 未来会改为 AES)。

当然肯定不能杜绝交互库被 hack 的行为,因为你的程序和交互库编译在了一起,熟悉存储结构的 CTF 选手可能仍然有很多绕开密码学的攻击方式。例如 #388739 曾经就获得了满分,还有这种直接改交互库的 srand 的 #205655。。我也会再研究下怎么更好地防御这些攻击。。不过我觉得这里的哲学应该是:只要我们让交互库被 hack 的难度和代码量足够大,大到选手觉得 hack 交互库还不如直接写个正解的话,这种行为就自然被杜绝了。即使真的被 hack 了,我们也会移除此类提交,保证他们不在 AC 的排行榜上出现。

当然有同学就会问了:为什么不直接使用标准输入输出进行交互?这里的主要问题其实是效率问题。如果交互量不大(比如 #545),当然可以采取这种方式。但如果交互量大到了 $10^7$,效率其实是非常低的。所以为了支持所有可能的题目,UOJ 未来将把通过函数交互和通过标准输入输出交互两类题目的支持做得更好。

等到我确定 #509 的有效防御方式之后将会把 UOJ 上所有函数交互的题目加上此类防御,欢迎大家最近踊跃尝试一下有哪些 hack 掉 #509 的交互库的方式并及时告诉我。

准备解决的问题

  • 仿照 UOJ 社区版直接通过 UOJ 系统生成时间空间限制以及样例下载链接,避免出题人手打出错
  • 题库搜索
  • 支持 C++ 14、C++ 17
  • 邮箱认证
  • Runtime Error 和使用危险系统调用的时候给予更多的提示信息
  • ……

解决不了的问题

题目中的维基链接

UOJ 上有些题目(#75, #83, #475)上面有指向维基的链接,但由于众所周知的原因,你不用“一些网络技术”,是没法直接访问的。这些题目链接了维基,主要是因为当时传题的时候维基还是个可以正常访问的网站。为了保持历史的原始风貌,就只能让这些不能直接访问的链接留着了(不过之后可能会换上个镜像。。。吧)

2020.6.6 更新

有点鸽,默默地把标题上的“【持续更新】”去掉了

2020.8.19 更新

  • 评论回复上限从140个字节改为500个字节(因为现在这个时代模仿微博没有任何意义。。)
  • 新增博客按最后回复时间排序的功能

2020.8.24 更新

  • 题面和博客中的列表增加两格缩进,被包含于列表、引用、表格等之内的段落取消自动缩进
  • 博客总览页显示评论数和点赞数

2020.8.30 更新

  • 终于加上了题库搜索。。。之前一直没加的原因其实是我想做个比较完整的站内搜索功能,但我也并没有多少开发时间。意识到这一点之后,我今天趁着有空快速写了个简易的题库搜索功能凑合凑合,参考了点 UOJ 社区版的代码 orz

2020.9.14 更新

  • 所有 http 请求强制跳转到 https

2020.9.22 更新

  • Markdown 支持表格、引用用户名

2020.12.29 更新

  • 增加 IOI 赛制的完整支持

2020.12.31 更新

  • 如果 subtask 内分数是 min 的,那么碰到 0 分的就自动跳过后面的(之前是全部测完)

2021.01.07 更新

  • 管理员可以看见测评机记录是由哪个测评机测的
  • 优化了下对测评记录表的数据库查询。。。(也可能会起反作用。。。欢迎报告)
  • 自动禁止比赛期间的 hack(很久很久以前 vfk 以为 uoj 以后会有比赛期间可以互相 hack 的比赛,现在发现并没有。。所以默认关掉 hack 好了)

2021.01.29 更新

  • 突然发现两台测评机上 libc 和 linux 内核版本不一致,于是均升级到了 apt-get 能升级到的最新版本

2021.02.02 更新

  • 增加超管隐藏评论的功能

2021.02.09 更新

  • 比赛迟到10分钟会弹出参赛提醒

2021.02.13 更新

  • 首页显示 6 条公告

2021.02.14 更新

  • 翻页的范围在原本的 $[x - 5, x + 5] \cap [1, n]$ 基础上增加特判。如果 $x \le 5$ 那么范围固定为 $[1, 11] \cap [1, n]$;如果 $x > n - 5$ 那么范围固定为 $[n - 10, n] \cap [1, n]$($x$ 为当前页编号,$n$ 为总页数)。

2021.02.19 更新

2021.03.13 更新

  • 发现有位机智的小同学对着一个测评记录的历史版本hack了一发:https://uoj.ac/hack/10489 。。。哦豁,赶紧修了这个 bug

2021.03.16 夜里更新

  • 以前说好“关于我”页面要给定制功能的,可是一直咕咕着,好难过。经群友提醒突然想起来了这个坑,并想起了本科的种种忙碌。。然而现在vfk依然忙忙,短时间内可能没机会来码这个功能了。所以。。暂时让这个页面显示用户信息页的东西了,不至于让这个坑太突兀。

2021.04.01 夜里更新

2021.04.04

  • ouuan 发现带有某些特殊字符的评论并不能正常发表。查了下发现是因为 MySQL 字符集的问题,现在什么都可以发啦(包括 🤔😜😀😊😃)

UOJ #34 多项式乘法已更换部分测试数据

2020-03-13 16:14:18 By vfleaking

前两天有良心用户 negiizhao 发现:UOJ #34 多项式乘法有 4 个测试点数据范围虽然很大,但带有特殊性质,导致按运行时间排序的排行榜上出现了一批靠特判数据性质排在前面的选手。

根据 negiizhao 在 UOJ 用户群发起的投票,有 40 票赞成更换数据,13 票反对。所以刚刚我替换掉了原来的第 3、4、11、12 号测试点,把原测试点移动到了 extra test。现在这题正在重测。

感觉这个形式很好,欢迎大家通过民主投票的方式表达自己对 UOJ 的建议哦

超人熊

统计下现在有多少UOJ?

2018-05-10 15:18:49 By vfleaking

Hi,大家好,大家还记得我吗?

好像最近大家在 CTSC + APIO,可是我看到了十五人的成绩单的时候却发现只有几个名字我熟悉了。。。然后又后知后觉地发现 PYOJ 早就消失了。。

我可能淡出 OI 太久了吧。。。突然有点伤感

想起我 NOI 那年是 2014 年,竟然已有四年之远了 (那些年的比赛还是不会搞丢选手程序的 [滑稽])

转眼我已经大三了。。我记得我大一的时候努力适应着大学的新生活,大二的时候立志要做点学术,大三上学期焦头烂额地找春季研修。。。渐渐地就忘记管 UOJ 什么事了。。。看到大家仍然还在孜孜不倦地交题感到很感动。

我有点怀念从前啊,所以大概想近期闲的时候稍微填一些坑,但也不知道最后会填多少。。。

以及我想调查下现在有多少人建了自己的 UOJ 诶,可以在评论区留下言吗?

震惊!UOJ 近期出现一些 RE 的原因竟然是这个!

2017-05-01 23:56:24 By vfleaking

测评机没内存了 [捂脸]

并不是 MLE 会爆 RE,而是程序说 “我要内存!” 结果内存表示 “我不够了!” 的时候会 RE。

有两台测评机,其中一台内存不够了,所以才造成了时而 RE 时而不 RE 的问题。

并不知道为啥内存不够了。。。使用 top 命令查看的时候 %MEM 那一栏大家都挺低的,但是就是可用内存很少。尝试重启了下各种程序发现并没有效果于是重启了 = = 大概现在正常了。

其实我五一假期放到 5.5 号所以大概这几天能修修 uoj 补补小 bug,有没有热心用户来吐吐槽呀?

超人熊

关于最近 UOJ 遭受的 DDos 攻击

2017-02-04 15:04:01 By vfleaking

………………我也没辙啊

如果你看到 UOJ 挂了多半就是被攻击了,超过一定流量阿里云会开启黑洞,切断服务器跟外界的连接,然后就没有人可以访问到 UOJ 了。

不知道是谁干的,最近被干了两次,峰值流量 10 GB。

可能想办 UOJ 这种小网站是挺难的吧,要是咱是个大公司就专门搞一大堆专业的 DDos 的防护了。

UPD: 3 次。

UPD: 4 次。(2017年2月8日)

UPD: 5 次。(2017年2月9日)

Goodbye Bingshen 题解

2017-01-26 18:25:44 By vfleaking

新年快乐!大家打得开不开心呀!

“一起AK吧”

长度测量鸡

from nneztlk

算法一

直接枚举刻度, 时间复杂度为 $O\left(\binom{n(n+1)/2-1}{n-1}\right)$. $n=5$ 时这个数是 $\binom{14}{4}=1001$, $n=8$ 时这个数是 $\binom{35}{7}=6724520$. 期望得分 $10\sim20$ 分.

算法二

我们需要题目描述中的 $s_j-s_i\ (0\le i< j\le n)$ 这 $\frac{n(n+1)}{2}$ 个数取到 $1\sim\frac{n(n+1)}{2}$ 的所有整数, 所以每个整数只能取一次, 即每种长度只能被一种方法量出. 特别地, $s_i-s_{i-1} (1\le i\le n)$ 这 $n$ 段长度两两不同, 故只能是 $1,2,\ldots,n$ 的一种排列.

枚举排列, 时间复杂度为 $O(n!)$. $n=8$ 时这个数是 $40320$. 期望得分 $20$ 分.

算法三

事实上, $n=1,2,3$ 时可以直接试出刻度方案, 分别为 $\varnothing,\{1\},\{1,4\}$, 而对所有 $n>3$ 都不存在满足要求的刻度. 证明如下:

记 $M=\frac{n(n+1)}{2}$, 则对 $n>3$, $M\ge10$. 现假设存在满足要求的刻度方案. 由于需要量出 $M-1$ 的长度, 所以 $1$ 或 $M-1$ 处必须有刻度, 由对称性不妨设 $1$ 处有. 要量出 $M-2$ 的长度, $2,M-2,M-1$ 中需要有一处有刻度, 而如果 $2$ 或 $M-1$ 处有刻度, 则可以用两种方法量出长度 $1$, 矛盾! 所以 $M-2$ 处必须有刻度. 此时由 $(M-2)-1=M-3$, $M-3$ 的长度已经可以被量出. 要量出 $M-4$ 的长度, $2,4,M-3,M-4$ 四处必有一处有刻度. 容易发现只有 $4$ 处的刻度不会引起重复.

现在已经知道 $1,4,M-2$ 处都需要有刻度, 而长度 $M-5$ 尚未被量出. 欲量出 $M-5$, 需要 $3,5,M-5,M-4,M-1$ 中的一处有刻度. 然而它们都会导致 $1,2,3$ 中的某个长度能被两种方法量出, 矛盾! 故不存在满足要求的刻度.

所以只需判断 $n$ 是否大于 $3$. 时间复杂度 $O(1)$, 期望得分 $100$ 分.

直径拆除鸡

from szy042

算法一

输出一朵花,就像 $(1, 2), (1, 3), (1, 4), \dots$

讲真这样子对于 $n \le 10$都是对的

然而当 $n = 11$ 时就开始挂啦

期望得分 20

算法二

输出一棵二叉树

(我没什么想说的

期望得分 $10$

结合算法一可以得30分

算法三

枚举树,按照题意模拟

找到一个最大的输出

UOJ的评测机很萌,所以能比算法一多十分~

期望得分:30

结合算法二,可以得40分

算法四 开花的金字塔

思考一下一棵树被删除一条长为x的直径之后的情况,我们发现,剩余的连通块中的直径最长为 $(\lfloor x/2 \rfloor-1) \times 2$。

证明是容易的。考虑这棵树原来的直径 $a$ 和删除之后最长的直径 $b$。我们取 $a,b$ 上最近的两个点 $c,d$,$c,d$ 两点把 $a$ 和 $b$ 分别分成两部分,各选取较长部分,加上 $c,d$ 之间的链,共同组成一条链,链长度的最小值就是 $\lfloor (a+1)/2 \rfloor + \lfloor (b+1)/2 \rfloor +1$,这条链的长度要小于原直径a,所以b不能大于 $(\lfloor a/2 \rfloor -1) \times 2$。

从取整符号可以看出,直径长度是偶数可以让 $b$ 最大,此时 $b=a-2$。

然后考虑一棵树被删除之后的连通块个数,除了最后一次删除,每多一个连通块,每个点被算入代价的次数显然会减少,于是就启发我们构造一个删除过程中不出现新的连通块的图,与上面的删除直径相联系,我们就可以随手构造一个符合条件的图出来。

将节点数分别为 $1,3,5,7,\dots$ 的链的中点相连,这就是一个符合要求的图。什么?你问多出来的那些点怎么办?扔到长度为 $3$ 的链的中点上(前面的字数太多于是后文称之为天上),变成一座开花的金字塔。考虑这些多出来的点对代价的贡献,放到天上的正确性是显然的。

期望得分:50

结合算法一/三可以得到60

算法五

我们发现算法四还需要结合算法一/三才能获得 60 分,因为算法四没有办法通过 $n=9$ 的测试点,于是,我们发现链的条数不是越多越好。因为一方面,链数增多可以让天上的结点的递归层数增加,但另一方面链数增多需要囤积更多的递归层数很浅的结点。所以我们需要枚举链的条数,将多出来的扔到天上,如果结果大于 $m$,输出之。

期望得分 100。

啊严谨证明是:用 $f[n][p]$ 表示有 $n$ 个节点直径长度为 $p$ 的最多删除次数,用前面得到的删除一条直径后的直径长度关于 $p$ 的不等式搞一搞,就能列个递推式。可以用数学归纳法证明 $f[n][p] = kn - b$,其中 $k$ 和 $b$ 是某个关于 $p$ 的常数。观察 DP 的取值,就能反向构造出对应的最优解了,发现恰好就是上面那样是最优的。

快乐游戏鸡

from scPointer

算法一

注意到当当前死亡次数不变的时候,整棵树上可走的点和边也是不变的。 考虑把每个点拆成 $ \max \{w_i\} $个点,然后跑分层图就好了。

或者你可以设一个状态 $f[i][j]$ 表示死亡 $i$ 次,当前在结点 $j$ 的最短时间然后跑dp。

后者的复杂度是 $O(nq\max \{w_i\})$ 的。这样可以通过子任务 $1$ 拿到 $10$ 分。

算法二

你可以发现每次从点 $s$ 出生到撞程序猿死亡跟前几次是怎么死的并没有关系。所以对于每次 “从点 $s$ 出生到撞程序猿死亡” 的过程都可以贪心选最近的点早死早超生。如果暴力BFS贪心的话复杂度是会炸的,离散化权值也不行。

我们换个角度,考虑有多少次从出生到死亡的过程需要一秒,多少次需要两秒等等。

具体来说,考虑记录 $f[i][j]$ 表示 $i$ 的子树中和 $i$ 距离小于等于 $j$ 的点的权值最大值。 这样 $f[i][j]-f[i][j-1]$ 就等于有多少次从出生到死亡需要 $j$ 秒。 那么只要从 $0$ 开始枚举 $j$ 把贡献加起来,直到 $s$ 和 $t$ 联通的时候直接从 $s$ 走到 $t$ 就好了。

复杂度 $O(n^2+nq)$ ,可以通过子任务 $1,2$ 拿到 $20$ 分。

算法三

算法3-1

因为所有 $s=1$ 所以就可以把算法 $2$ 里 $f$ 的第一维删掉辣。然后把 $f$ 搞搞差分前缀和什么的,每次询问二分就好了。复杂度 $O(n+qlogn)$ 。

算法3-2

或者...让我们回到算法二的第一段。如果你只想到贪心没有想到记录 $f$ 数组,那么第三个部分分也是可以拿的。首先对询问的每个终点按照能到达那个终点的死亡次数排序,然后算法二第一段的贪心过程可以用一个堆或者set来做。

如果一个点可以被到达(可以安全通过它的父亲了),就扔进来,如果死亡次数大于等于某个点的权值(可以安全通过它自己了),就扔出去。当前死亡次数达到某个点的死亡次数的时候就处理一下询问就好了。复杂度 $O(q+nlogn)$ 。

这两个算法和场上可能出现的各种我可能没想过的算法可以通过子任务 $3$ ,这样就有 $40$ 分了。

算法四

算法4-1

为了方便叙述,我们把点 $1$ 放在最左边,点 $n$ 放在最右边,拉成一条链。

然后把所有询问按照左端点从右向左排序,处理 $f$ 数组的时候也从右向左处理。然后观察一下每次往左扩展一个点的时候 $f$ 数组有啥变化,然后你机制的发现这个是可以用线段树转移的,询问也可以在线段树上查询。

等一下!每次加一个点的时候好像是区间对一个数取max唉,是不是要强上一波segment tree beats(吉司机线段树)啊。如果是场上真的有选手卡在这里的话,我表示非(xiao)常(chu)遗(sheng)憾。回到算法 $2$ 看一眼 $f$ 的定义你会发现这玩意是单调递增的,所以我们二分出线段树上最后一个小于要更新的那个数的地方,然后区间覆盖就可以了。

稍微剧透一下兹磁区间覆盖和区间求和的线段树就可以最终解决问题。复杂度 $O((n+q)logn)$ 。

算法4-2

首先还是从右往左处理所有东西。注意到当处理到点 $i$ 的时候,如果存在 $i < j < k$ 使得 $w_j \geq w_k$ 那么我们肯定不可能死在 $k$ 点。

如果把所有这样的点删掉,我们就得到了一个单调栈!然后每次往左扩展一个点就维护一下,询问直接二分就好。注意当删掉一些点以后相当于边权可能会 $>1$ ,加减乘除处理一下就好。 稍微剧透一下你可能需要维护后缀和。复杂度 $O(n+qlogn)$ 。

这两个算法可以通过子任务 $4$ ,或者一些大力出奇迹的算法可能也能过,这样就有 $70$ 分了。

算法五

算法5-1

大致和算法4-1差不多,加上树链剖分和启发式合并的话就能直接做了。代码可能会有一点长。

什么你说不会做?如果能写出4-1的代码,你肯定已经知道了如何往一棵线段树上加一个点更新信息。然后树链剖分以后对于每个点,首先把它的重儿子的线段树拉过来更新一下,然后对于它的每个轻儿子的重链(注意不是轻儿子的子树,否则可能复杂度会多一个log有卡常风险)对应的线段树拉过来更新当前点的线段树就好了。推荐按照树剖的DFS序建一棵线段树,然后上面提到的所有操作都可以在这一棵线段树上做。复杂度 $O((n+q)logn)$ 。

再见丙申C题题解

算法5-2

同算法4-2,同样是加上树链剖分和启发式合并搞一搞。复杂度 $O(n+qlogn)$ 。详见xllend3大爷代码

算法5-?

这题还有很多做法,比如你不喜欢用普通线段树换成动态开点的线段树或者可持久化线段树或者treap什么的也是可以的。当然复杂度和常数就要自己保证了。myy似乎提了一个按权值建LCT的做法:http://matthew99.blog.uoj.ac/blog/2296

数据分块鸡

from jiry_2,数据和题解 from cy

子任务一

设 $f[i]$ 表示最后一个分块点是 $i$ 的最小代价,那么我们转移时可以枚举上一个点 $j$,然后令 $f[i] = \min\{f[j] + w(j, i)\}$,其中 $w(l, r)$ 表示与 $[l, r)$ 相交的询问所产生的代价。

时间复杂度:$O(n^2 q)$。

子任务二

我们可以尝试预处理 $w$ 函数的所有取值。

设 $g[l][r] = w(l, r)$,那么对于一个询问 $[L, R)$, 我们可以根据 $[l, r)$ 与 $[L, R)$ 的相交情况大力讨论一发,拆成把若干个 $g$ 数组的子矩形加上某个数,这可以离线前缀和一下。时间复杂度是 $O(q + n^2)$ 的。

预处理完之后 DP 的复杂度就变成 $O(n^2)$ 了,于是总的复杂度是 $O(q + n^2)$。

子任务四

通过数(da)学(dan)证(cai)明(xiang)我们发现,这个 DP 满足决策单调性。

于是我们可以采用对于满足决策单调性的 DP 的通用做法:在 DP 的同时维护一个单调栈,转移的时候在栈上二分一下得到最优决策点。

计算 $w(l, r)$ 可以通过按照 $[L, R)$ 与 $[l, r)$ 的相交情况分类讨论,拆成对若干个子矩形求和,并用可持久化线段树预处理这些前缀和。

时间复杂度:$O(n \log^2 n)$。

子任务三

通过更进一步的分析,我们可以证明分界点只有可能是 $l_i$,$l_i - 1$,$l_i + 1$ 或 $r_i$,$r_i - 1$,$r_i + 1$。因此我们可以只把这些点拿出来 DP。

时间复杂度:$O(q^3)$。

同构判定鸡

from ppfdd,具体想法 from vfleaking,题解也是 vfleaking 写的。

题出得比较仓促,所以测试点只有 $6$ 个……窝先说一下……窝最初的想法是 “哇终于知道怎么出交互式证明的题了!”,然而造题的过程是:

YY 一个图同构算法 → 不会卡 → 再 YY 一个图同构算法 → 还是不会 → 要不咸鱼一下爆搜看看效果如何 → 那不就从构造题变成爆搜题了,不清真 → 继续 YY……

由于我太弱了所以测试点也比较弱,大家玩得开心就好。

卡算法一

算法一:仅检查结点数及边数是否一致。

直接扔个点数边数相同的两个不同构的图就行了,可以获得 $7$ 分。

卡算法二

算法二:首先仅检查结点数及边数,然后结点数很小时使用暴力,否则视为同构。

在卡算法一的基础上造个大一点的图。

卡算法三

算法三:初始每个结点颜色相同,每次对于每个结点结合自身的颜色和周围邻居的颜色编码产生新的颜色,反复迭代直至稳定。将最后每个图所得颜色进行排序,若相同则视为同构。

废话好多!直接扔两个度数相同的图就行了。

卡算法四

算法四:与算法 3 类似,只是用结点间最短距离信息初始化结点颜色。

有两个方法。一个方法是人类智慧构造一下。首先仿照卡算法三的思路,这个图最好是每个结点的距离数组都长得一模一样。那么考虑把大家围成一个圆圈尝试有规律地连边,试了下最后竟然成功了。

A:$6$ 个点,$i$ 与 $(i + 1) \bmod 6$ 连边,$i$ 与 $(i + 3) \bmod 6$ 连边。

B:$6$ 个点,$i$ 与 $(i + 2) \bmod 6$ 连边,$i$ 与 $(i + 3) \bmod 6$ 连边。

这样构造发现恰好是满足的,就可以同时卡掉算法一二三四了。

还有另一个构造,方法是找两个不同构且每个点度数都相同的图,分别新建一个点向所有点连边。这样其实原图中没有边相连的两个点距离就为 $2$,有边即为 $1$。这样的构造也是可以骗过算法四的。

另一个方法:大爆搜所有无向图,搜到 $n = 6$ 就能找到上面的这个构造了……

卡算法五

算法五:枚举一个图中的一个固定的结点与另一个图中哪个结点对应,将他们分别染成特殊的颜色,其它结点颜色照常初始化,再用算法 3 中的迭代。若存在一种对应使得最后所得颜色相同,则视为同构。

只用在卡算法四的基础上往前面插入一个编号为 1 号点向所有其他点连边就行了,这样给这个点特殊染色不会带来任何信息。

另一个方法:大爆搜所有无向图,搜到 $n = 7$ 就能找到上面的这个构造了……

卡算法六

算法六:一种基于邻接矩阵的整数次幂的迹的哈希算法

啊发现哈希好难卡……发现哈希的模数是 int 范围的。考虑用爆搜来构造。

但是要怎么快速生成很多个满足前 5 个算法的图呢?

可以这样想:算法五里引入的这个向所有点连边的点不会带来任何信息,所以多加几个这样的点也肯定满足题目条件。而且进一步考虑在这样的新点之间连边,如果连边方式一致,那么同样也不会给那个 $6$ 点图带来任何信息。

所以我们可以在卡算法四的基础上,给 $A, B$ 加一大堆新点出来,然后随机连边。但是这样大约需要随机 $O(M)$ 次才能随机到相同的哈希值。

这个哈希函数实在是算得太慢了,GG 怎么办呢。如果用生日攻击的话,那么模数是 $M$ 期望 $O(\sqrt{M})$ 个样本就能卡了。

然而我们可以结合卡算法四中的第二个构造。把新点随机成点度数相等的图就好了。由于 $A, B$ 不同构所以我们可以直接随机不用判断是否随机到了同构的图。

当然场上有一位机智 bzoj 给出了一个直接的构造:在这里 太强了……QAQ……

终极武器

好吧虽然不是想鼓励大家这样做,但是可能很有效。上网搜“graph isomorphism counter example”,可以得到一些奥妙重重的卡图同构算法的反例。下载一些下来喂进交互库说不定哪个就成功了。囧rz……以后出题还是要注意注意别出这种能 google 的题。

嗨呀以及感觉这次的题目总体还是偏难,感谢大家参赛啦!

共 61 篇博客