UOJ Logo matthew99的博客

博客

HNOI2019 Tour

2019-04-07 14:48:36 By matthew99

题目链接

HNOI2019 tour的出题人是我。第一天任何一个题都不是我出的,pdf作者写我是一个印刷错误。fish的出题人在这里进行了说明。

(我突然意识到吉司机题面写九条可怜的强大之处了。如果同样的情况发生在他身上,就算pdf出了错一看题面就知道不是他出的)

这个题出了一定的锅,其中我也有一定的责任。我出这个题的时候最开始没有加读入优化,后面加了读入优化意识到标程非常快,于是把$n$开到了5000。我虽然有和命题组的人说我改了数据范围,也发了新的题面,但我并没有强调所以他们可能最后并没有意识到题面的修改(也有可能意识到了但是版本混淆了),所以最后题面还是3000的版本,但是数据却用的是新的。

最后考场上我只好给了3个3000的数据。由于我数据生成器的特殊性,我不太敢保证我能卡掉所有暴力做法或者错误做法(其实我还是比较自信的因为我觉得如果你真有很高端的优化你也差不多会正解了)。

在UOJ上这个题的范围依然是5000,如果你们考场的程序过不去,请把n改成5000。我相信能过3000的程序都能过5000。

下面放简易题解:

30分的DP就是dp[i][j]表示i到j是否存在一条合法的路径,转移就是枚举i的边和j的边。总复杂度是$O(m ^ 2)$。

考虑减少边数。我们把一种标号单独拿出来,只考虑连接同一种标号的两个点的边。 对于一个连通块,如果它是二分图,那么我们仅保留一棵生成树答案也不会变。这是因为我们容易发现这个连通块之内的转移仍然可以实现(只要另一边在两个点内来回走即可)。如果它不是二分图,我们可以加一个自环。

我们考虑连接不同标号的边,只把这些边拿出来我们也可以形成若干个连通块。对于每个连通块, 根据同样的道理我们保留一棵生成树即可(注意这个时候连通块一定都是二分图)。

这样总边数不超过$2n - 2$,用30分DP的思路可以做到$O(n ^ 2)$并且通过本题。

此外,存在一个$O(nm)$的做法能过70分,做法大概就是DP的时候先转移一边再转移另一边。这个做法和正解并没有多大关系而且如果你缩了图之后再用这个做法会比直接dp更慢,所以不再赘述。

吐槽(雾)

"妈妈这个出题人好懒题解写的太简单看不懂怎么办?"

洛谷上有不少其他人写的(很可能更详细好懂的)题解可供参考:

https://www.luogu.org/problemnew/solution/P5292

新年的Dog划分 数据问题

2019-02-17 13:42:53 By matthew99

作为出题人我发现这个题的数据一不小心造弱了,我以为一张任意图加上一条不是二分图的边可以卡掉大部分错误的判二分图算法。结果没想到连最简单的错误算法都卡不掉,现加了若干组200个点200条边的数据。希望大家做题愉快。

HNOI D1T1 hunt

2018-04-15 13:32:46 By matthew99

第一次给HNOI出题(其实也是第一次给NOI赛事出题)。

题目链接

稍微了解一点MIT的人(比如知道Infinite Corridor不是真的无限长)可能看完题就知道出题人是谁了(然而好像因为奇怪的原因不能把学校名写在题目里,不过大家看到“某大学”,而不是“T大”或者“P大”可能也知道是怎么回事了?)。

简易题解:

如果第i个数之前的运算符是and,则这一位设为1,否则为0,得到的二进制数记为$x$。

对每一位分别考虑,对于第i位,如果第j个数是1,那么这一位设为1,否则为0,得到的二进制数记为$b_i$。

以左边为最低位,按前缀归纳容易证明,第i位的结果为1,当且仅当$x < b_i$。

我们将b从大到小排序,结果设为c,那么答案不为零仅当在c的顺序下,r中没有任何0在1的前面。找到r中第一个0的位置,假设是k,那么解x要满足$c_k \le x < c_{k – 1}$,于是答案是$c_{k – 1} – c_k$。

题外话:

当时出题的时候很紧张,是真的紧张,因为觉得实在是太水了。我当时的70分做法是猜结论,大概就是猜到有用的DP状态有$O(nm)$个再bitset。然后觉得这实在好猜了,其实根本不用猜,只要你注意到DP状态可能不满这个事实,然后直接记录有用状态就行了。

我当时很怕结果出来十几个AC,全场70。然后就再也没人找我出题了。

当时就不停的想HNOI有什么水题,是不是比我这个更水来安慰自己。

后面想想给大家送送分也好,至少这个题不是原题或者错题,能让自己成为大众喜闻乐见的出题人也不错。

结果分数分布大家都懂的。我至今不知道拿50分的是怎么回事($n$只开了$500$?拿50分的人能不能在下面评论区说一下怎么拿的)。于是我的顾虑成了多余的。

不过这也不错,一来我的题终于不是HNOI最水的题了,二来我的题很可能送人进队(比如你A了或者高分暴力),不太可能送人退役(最多就是你30分暴力分挂成10分或者0分)。Still,如果有人因为我的题暴力写错退役我只能抱歉了,对不起我给了30分暴力分

至于重测,那是因为我在Windows下造的数据,然后由于跨操作系统,换行符出了点问题-.-

考场上被各种倒推做法虐了。

其实倒推本质就是动态维护字典序。我很高兴大家因为我的题发明了一种新的排序算法。我可以把这个题改成每次模一个不同的数,然而似乎还是有基于倒推的奇技淫巧可以做。我也可以出成二进制高精度什么的,但是感觉它们还是可以过,也就是说在不懂正解只会倒推的(也就是大多数)人眼里,我把这个题目弄得更毒瘤而不是更神了。

说起来$O(\frac{nmq}{w})$可能是能过的(UOJ上能过TAT),解决方法大概是把$q$弄大,比如$10,000$。但是读入就很tricky了,可以压字符读入但是这样也很毒瘤。

所以大概这个题也只能放了吧,虽然不得不说我不是很喜欢这种倒推的做法,太直接了,个人感觉和标算没法比。但是也没办法,就像一个优美的题,结论就是输出a+b,也会有不明真相的群众写出一种和按位模拟加法等价的做法,你还没什么办法卡。

快乐游戏鸡LCT做法

2017-01-26 19:40:17 By matthew99

首先你得看了题和题解至少算法二之前的部分。

题解地址:http://vfleaking.blog.uoj.ac/blog/2292

我们把每个询问转化为总和减去大于等于最大权值的部分的后缀和。

接着我们按w从大到小加入点,考虑维护每个点的子树中的最小深度

这个怎么维护呢,考虑一个点肯定是更新它到根的路径,所以我们用类似LCT的access的方法更新,我们可以保证随时每个链的最小深度都相同,如果当前的链的最小深度小于用来更新的值就直接退出,否则的话我们就更新,最后再把这些更新了的链连起来。

复杂度显然是$O((n + m)\log{n})$的,用类似证明LCT复杂度的方法证明即可。

答案也很好算,记录一个后缀和即可,你会发现更新的时候也很好打标记,询问也很好处理。

怎样,是不是只要有模板就好写又好调?而且时间效率还不错呢。

代码:http://uoj.ac/submission/123579

UOJ Easy Round #7 题解

2016-10-15 20:15:21 By matthew99

短路

By matthew99

算法一

直接暴力 dfs,复杂度指数级,期望得分 10 分。

算法二

用最短路算法,复杂度 $O(n ^ 2 \log n)$,根据实现情况可以获得 10 至 30 分。

算法三

猜想只能往右或者往下走,然后做一个 $O(n ^ 2)$ 的 DP,可以获得 30 分。正确性证明参见算法五。

算法四

在算法三的基础上进行对称性优化或者使用滚动数组,可以获得 50 分。

算法五

我们考虑假设我们要从左上角走到从外到内第 $i$ 层任意一个中继器上,那么我们最少需要多少代价呢?显然我们一共最少走 $2i - 2$ 步走到 $(i, i)$ 上。其中,第 $1$ 层到第 $i - 1$ 层每层都必须经过至少一个中继器,除了这 $i - 1$ 步,还要再走恰好 $i - 1$ 步。

我们发现剩下来的 $i - 1$ 步至少要走的是 $1$ 到 $i - 1$ 层的前缀最小值之和,为什么呢?考虑一条走到第 $x$ 层某个给定位置且只到过前 $x$ 层的最短路径,那么该路径的最后一步要么是从第 $x - 1$ 层走下来,要么是在第 $x$ 层又逗留了一次。如果是后者,我们总是可以把这最后一步挪到前面去走,相当于对于某个 $k$ 在第 $k$ 层先走了这一步,然后把这一步之后的路径平移一下而不影响平移的这段路径的总时间,这样代价变化就是第 $x$ 层的 $a$ 与第 $k$ 层的 $a$ 的差值。这样我们就推出,如果第 $x$ 层的 $a$ 不是前缀最小值,那么肯定不是最短路径。因此,最短路径肯定不会在不是前缀最小值的层停留超过 $1$ 次,于是这条最短路就是把所有的前缀最小值所在的层的最左上角的点用 L 型的曲线连起来的路径。

那么假设我们走到的最深的一层是第 $x$ 层,首先第 $x$ 层不是前缀最小值的话那么一定不是最短的。如果是前缀最小值,那么最短路径就是先走到第 $x$ 层左上角,再绕一圈绕到第 $x$ 层右下角,再走出去(代价和走过来是一样的)。

这样,我们暴力枚举 $x$,走到第 $x$ 层的代价可以在线计算,然后每次更新答案即可。

时间复杂度 $O(n)$,期望得分 100 分。

同样的我们也证明了算法三的正确性。

怎样,是不是一个超级送分大水题呢?

天路

By zhj, vfleaking,题解 By vfleaking

什么鬼?

嘿嘿嘿……vfk 又来出题玩玩了。事情是这样的,我和 zhj 发现了一个好玩的 idea,然而我并不知道怎么套个优雅的模型。这时 zhj 拯救了世界,于是就出出来了。

哎说实在的过去的一年给 CCF 出题有点心累,在自家 UOJ 上出题各方面还是爽多了2333……

依稀记得 NOI2016 讲题时我兀自地讲讲讲,台下纠结分数线的梦想们并没有多少热情听。后来当我看到分数线公布以及签约的现场有点百感交集,感觉给 CCF 出一次题的事情多,责任也好重……在 UOJ 上自己随便出出出题至少不会直接影响选手痛失金牌。

但愿我出的萌萌哒题目们都能让大家有所启发吧。

谜之声:怎么近似算法都出到 OI 里啊?这真 NOIP 难度?

咳咳客官别急,往下看。敢承诺这个近似算法非常 NOIP 向,并不是那种数学大不等式乱搞证 bound 型。

算法一

对于 1 号测试点,$n \le 100, a_i \le 100$。

大暴力!

你会使用 for 循环吗?

时间复杂度 $O(nV^2)$,可以获得 10 分。(其中 $V$ 为权值范围)

算法二

对于 1,2,3 号测试点,$n \le 100$。

权值范围好大啊……

不要慌,你可以先枚举 $k$,然后枚举 Nokia1050 是在哪一段时间连续拦截了 $k$ 次攻击嘛……该区间中高度的最小值和最大值作为高度区间。

你会使用 for 循环吗?

时间复杂度 $O(n^3)$,可以获得 30 分。

算法三

对于 4,5 号测试点,$n \le 1000$。

在算法二基础上,把每次扫一遍求最小值最大值改为 for 的时候乱维护维护就行了……

(而且 $O(n^3)$ 常数好就过了呢)

(感觉在 CCF 系列比赛这样送分会被选手喷的……hhh)

时间复杂度 $O(n^2)$,可以获得 50 分。

算法四

对于 6,7 号测试点,$n \le 10^5$。

诶数据随机?

同学们你想到了什么!随机数据的前缀最小值只会变化 $O(\log n)$ 次对吧!

所以当我们固定左端点移动右端点时,区间内最大值与最小值至多只会变化 $O(\log n)$ 次。

拿个单调栈维护一下……每次给对应的长度区间更新答案。

脑抽选手可以使用线段树,但其实由于答案单调,所以可以变成给一个长度的后缀更新更新,于是就能 $O(n \log n)$ 的复杂度了。

可以获得 70 分。

算法五

还是数据随机的情况,观察数据我们注意到如果区间长度够长,那么答案就非常接近$10 ^ 6$。

所以我们设一个几百左右的值 $l$,然后处理小于 $l$ 时的答案,剩下来的输出 $10 ^ 6$ 即可。

同样可以获得 70 分。

算法六

好了好了所以之前的部分分跟近似算法都没什么关系……

这题应该怎么近似呢?你想,要是直接把权值除以一个大常数,做完之后再乘回来,看上去好像很近似!但是冷静冷静就会发现这样做出来是个绝对误差的,如果碰到 \begin{equation} 233333 - 233332 = 1 \end{equation} 这种就 GG 了。

所以……相对误差,看上去很没头绪。

来来来先把近似算法扔进垃圾桶,来想想如果要你求出准确解,你可以怎么做。

一个思路是,我们应该是枚举一个 $k$ 然后某种方式维护一下,但这个看上去就很没办法改造为近似算法。

诶,那如果告诉你一个常数 $c$,我们来把答案 $c_k$ 划一划范围好像很兹瓷啊……那 $c_k \ge c$ 可做吗?

……好像是可做的诶,因为最终的答案肯定是单调递增的,所以范围肯定是一段连续的 $k$。我们可以两个指针再开两个栈乱扫扫,左端点往后挪一挪,右端点也往后挪一挪……就能把 $k$ 的范围求出来了。

嗯很好,于是我们就可以每次找找 $c$,划分 $k$ 的范围。当范围足够小的时候,就可以把这一段的 $k$ 都用同一个数近似了。

事实上,你只需要取: \begin{equation} 1.05^0, 1.05^1, 1.05^2, 1.05^3, \dots \end{equation} 就可以啦!每一段里面随便找个数当答案一定不会超过相对误差的容许范围。

现在还差一个想题时的直觉 —— 就是需要划分的段很少……只要注意到其实段数是 $O(\log V)$ 级别的……23333333……别看人家 $1.05$ 小,但人家也是个指数函数。

中间找到 $k$ 的范围只需要 $O(n)$ 时间乱扫,所以总时间复杂度是 $O(n \log V)$。如果把 $5\%$ 当做变量 $\epsilon$,那么时间复杂度就可以写为 \begin{equation} O(n \log_{1+\epsilon} V) = O(n \log V / \log(1 + \epsilon)) = O(\epsilon^{-1} n \log V). \end{equation}

这个算法其实说明,所有 $f(i)$ 随 $i$ 递增且有个算法告诉我 $f(i) \ge k$ 的第一个 $i$ 在哪里的话,都可以套这个近似算法!(然并卵)

噔噔!这题就做完了!相信比赛时很多选手都轻松 AC 啦~

(为什么一道水题的题解我能写这么长)

套路

By matthew99

算法一

枚举区间,再枚举区间内两个数统计这个区间的答案,再求出整个问题的答案。时间复杂度 $O(n ^ 4)$,期望得分 7 分。

算法二

用 $\mathrm{ans}[l, r]$ 表示区间 $[l, r]$ 的答案,很容易发现 $\mathrm{ans}$ 可以由如下递推式算出: \begin{equation} \mathrm{ans}[l, r] = \begin{cases} |a_l - a_{l + 1}| & \qquad r - l = 1, \\ \min\{\lvert a_l - a_r \rvert, \mathrm{ans}[l + 1, r]\,, \mathrm{ans}[l, r - 1]\} & \qquad r - l > 1. \end{cases} \end{equation}

时间复杂度降为$O(n ^ 2)$,期望得分20分。

算法三:

注意到如果 $m \le 1000$,那么根据鸽巢原理,长度超过 $m$ 的区间肯定有两个相同特征值相同的跳蚤,因此答案是 $0$,所以我们处理长度小于 $m$ 的区间即可。

时间复杂度为 $O(nm)$,期望得分 27 分,结合算法二可以获得 40 分。

算法四:

使用任何一种时间复杂度为 $O(n \sqrt{m + n} (\log m + \log n))$ 的算法(请注意大O符号的意思),即可获得至少 $70$ 分。由于这些算法过于复杂且与标算没有太大关系(或者是标算强行多写了一个 $\log$),故不再赘述。

算法五:

我们考虑如果区间长度是 $x$,那么最小差不超过 $\frac{m}{x - 1}$。

设一个常数 $S$。

如果 $x \le S$,则用类似算法三的方法,可以做到 $O(nS)$。

如果 $x > S$,那么最小差不会超过 $\frac{m}{S - 1}$。我们扫描一遍序列,考虑当前位置作为右端点,用 $r_x$ 表示权值为 $x$ 的数最后出现的位置,然后每次新加入一个数 $z$ 之后,对于所有 $\lvert z - y \rvert \le \frac{m}{S - 1}$,利用 $r_y$ 进行计算更新答案,然后 $r_z$ 即可。时间复杂度为 $O(n\frac{m}{S})$。

设 $S = O(\sqrt{m})$,则总时间复杂度为 $O(n\sqrt{m})$,可以获得 100 分。

这是不是 UOJ 历史上最水的C呢,相信大家 AK 得非常的爽,作为出题人之一看到大家 AK 我也感到非常荣幸。

UPD:好像打脸了。

matthew99 Avatar