【游记】FJOI2020 自闭记

Day -1

颓废

Day 0

颓废

试机的时候知道 FJOI 竟然不用 FrC 提交了,改成用一个垃圾网页提交。

问了问技术人员,评测像是有开栈的样子。

Day 1

A:
给定一个 (n imes m) 的网格图,有 (s) 个关键点,你需要以每个关键点为起点,分别画一条到边界上的点的路径,使得所有路径两两没有公共点。求路径长度之和的最小值。(n,m leq 2000)(n imes m leq 2 imes 10^4)

B:
给定一张 (n) 个点 (m) 条边的无向图,每个点有一个颜色 (c_i)。对于每个点,你需要求出删除和这个点相连的边后,有多少个颜色相同且不连通的点对。(n,m leq 500005)

C:
有四个栈按顺序从左到右排成一行,第一个栈从栈底到栈顶依次为 (1sim n),其余三个为空。每次你可以将任意一个非空栈的栈顶弹出,并将其放到右边的下一个栈,无法操作时结束。你需要时刻保证第三个栈从栈顶到栈底是递减的。对 (M) 取模,(M) 范围神秘。

求全部做完后,第四个栈可能有多少种形态。(n) 大概是 (10^6)(忘了)?

开场看完题,发现这个题面连空间限制、模数范围、多测数组组数都不给,问技术人员,竟然说「经过讨论,我们决定不放空间限制,你们需要自己考虑」。但是想到我在考 FJOI,那就不管了。

发现 T1 是个费用流,但是好像只能稳过 70pts,就先不管了。

看完 T2,发现是建完圆方树,就只要求跨过每个点的同色点对数即可,随便整个树上启发式合并就做完了。于是很快就写完并拍上了。

绕回来搞 T1,认真分析了一下,流量 (mathcal O(n+m)),点数和边数都是 (mathcal O(nm)),那 EK 费用流不是直接爆炸,想不到什么靠谱的做法了。回忆起 Johnson 算法,复杂度感觉也不是特别稳,而且我 T3 还一分没有,那就写个 EK 先不管了。

后面都在做 T3,一直没啥思路,最后 30min 的时候打表得出一个性质,但是来不及做了,考试结束的时候感觉已经快算出 (mathcal O(n^2)) 的递推式了,就非常自闭(这个题怎么 p 点暴力分都不给)。

成绩出来以后发现,T3 大家都没什么分,T2 人均 AC,T1 人均 70/100。很毒瘤的一点就是 T1 把 EK 改成 Dinic 多路增广就过了(它们理论复杂度是一样的,但是这题的表现多路增广更好)。
哎,出个费用流都要卡算法,这个 FJOI 真没意思。

Day1 考完是 rk5,不会要 B 队队长了吧。

Day 2

A:

数轴上有 (n) 个点,点 (i) 的坐标为 (x_i)。你需要在这些点中,选取至少一个、至多 (p) 个作为仓库。在点 (i) 建仓库的费用为 (c_i),每个点有一个权值 (a_i)。你需要最小化建仓库的费用 与 (sum_{i=1}^n a_id_i) 的和,其中 (d_i) 表示 (i) 与离它最近的仓库的距离。(n leq 10^6)(p leq 5 imes 10^5)(大概)

B:

求将凸 (n(k-2)+2) 边形划分成 (n) 个凸 (k) 边形的方案数,对 (10^9+7) 取模(划分所用到的 (k-1) 条边的端点都需要是原多边形的顶点)。(n leq 555555)(k leq 200)(大概)。

C:

给定一个长度为 (n) 的非负整数序列 (a_1sim a_n),有 (q) 次询问,每次给定 (l,r,k),求有多少数对 (x,y) 满足 (l leq x leq y leq rland f(x,y)=k),其中 (f(x,y)) 表示 (operatorname{mex}{a_x,a_{x+1},cdots,a_y})(n,q leq 2.3 imes 10^5)

听说是 CF1148H 弱化版。

开场看完题,发现这个题面还是连空间限制、多测数组组数都不给,今天就懒得问技术人员了。
不过题目里面的数据范围,划分成凸 (k) 边形中的 (k) 竟然 (geq 2),我就很纳闷线段怎么划分,问技术人员——「(k=2) 其实是没有问题的,我为了让你们在你们的角度上方便理解,就改成 (geq 3) 吧」

发现 T3 比较熟悉,想了想大概口胡了做法,但是似乎非常码,就先不管了。

干 T2 干了半天干不出什么东西来,T1 也不怎么会,只能回来写写 T3。

写完 T3 还有 1h 多,剩下两题都没有暴力分,感觉 T2 有点方向就一直在搞 T2,搞半天搞不出来。

搞 T2 之后心态崩了搞了搞 T1,惊奇地搞出一个凸优化+斜率优化 DP 的做法,但是只有 30min 了……心态爆炸,写完了代码然后来不及调了。

估计 100 的期望得分就直接飞了,成绩出来之后是 110。发现一堆人写挂了,最高分是 xyz32768 140(恭喜 xyz32768 喜提队长)。

统计了一下我还是 rk5,喜提 B 队队长(QwQ),心态爆炸。


简单评价一下,论思维难度,今年的 FJOI 确实比往年进步不少,而且原题也少了,并且比联考也难不少,今年 FJOI 这么难我确实是没有想到的,而且代码难度两天都很大。

不过相比去年,区分度还是很明显的,选拔结果也比较科学,省队选手和本省 CSP 前列的选手有很大的重合。

但是作为一场选拔赛,部分分出得这么少、题目描述和数据范围不完整规范、样例太弱、空间限制不给,其质量是不合格的,基本上一道题不是 0 分就是 100 分,不过两天只要做出一道题多一点就能进省队了。


那么 NOI2020 加油吧。

原文地址:https://www.cnblogs.com/cyx0406/p/13195565.html