UOJ Logo vfleaking的博客

博客

共找到 19 篇包含 “UOJ Round” 标签的博客:

UOJ Round #15 题解

2016-08-13 22:08:14 By vfleaking

奥林匹克五子棋

from qmqmqm

算法一

答案只与最后的棋盘有关。暴力枚举所有的棋盘然后判断是不是符合条件。

最终复杂度是 $O(nm2^{nm})$。可以获得 30 分。

算法二

如果对于一组 $n,m,k$ 如果有解,那么对于 $n,m,k+1$ 也有解。

明显如果 $k=1$,那先手随便下一个子就赢了,所以无解。

当 $\min(n,m)=1$ 时,如果 $k=2$,那么双方只要棋子间隔分布,就是可行解。

最终复杂度是 $O(nm)$。可以获得 15 分。

算法三

当 $\min(n,m) \lt k$ 时,斜线方向是明显永远符合条件的。所以我们采取像黑白染色那样,这样在横竖方向上最长连续段都是 $1$,明显是符合条件的解。

最终复杂度是 $O(nm)$。可以获得 15 分。

算法四

当 $n,m \geq 2$ 时,可以证明如果 $k=2$ 是无解的。

具体来说考虑 $(1,1),(1,2),(2,2)$ 三个点,由抽屉原理得其中必定有两个点同色,那么他们就成了一个长为 $2$ 的同色连续段。

所以我们来考虑 $k=3$ 的情况。

可以想到,$k=3$ 一定不会在内部有一个 $2 \times 2$ 的同色块,否则这个块的下方三个位置就会形成一个长为 $3$ 的同色连续段。进而一个同色的 L 形也不能存在,因为其上方三个斜向位置都必须和它颜色不同,从而形成一个长为$3$的同色连续段。

这样一来,构造必须是一些 $1 \times 2$ 的条间隔分布。观察发现,这个构造符合题目中的所有条件。再根据上边的结论,$k \gt 3$ 的情况也解决了。

最终复杂度是 $O(nm)$。结合算法二可以获得 100 分。

奥林匹克环城马拉松

from ftiasch,题解 from C_SUNSHINE

算法一

首先我们判断掉无解的情况,即存在一个点度数为奇数,此时方案数为 $0$。

从 $1$ 号点开始搜索欧拉回路,只要记录当前在哪和 $u,v$ 之间还有几条边没有走就好了,状态数是所有 $t_i$ 的积乘以 $n$,每次枚举下一步往哪走,可以从将要走的路上选一条未走过的边来走,并乘以这条路上剩余的边数,这样转移复杂度是 $O(n)$ 的,可以得到 $20$ 分。

算法二

注意到树的每一条边数目都是偶数,且走过去和走回来的次数各占一半,令一个点的度数 $deg_x$ 为走入这个点的次数即这个点相邻边权和除以$2$。

首先先要确定每一条边的方向,这个其实就是在每一组重边中选一半向下,另一半向上,所以是 $\prod \binom{t_i}{t_i/2}$。

那么确定方向之后,欧拉回路如何计数呢?

我们有一个简单粗暴的方法,在每个点上对于每一条入边为它指定一个后继出边,这样边与边之间就连起来了,由于 $deg_x$ 条入边和出边的匹配方案数是 $deg_x!$,于是答案就是 $\prod deg_x!$。

妈呀我怎么过不了样例啊……

可以发现这样确定出来的不是欧拉回路,而是若干个环并在一起。

继续思考,我们可以使用一些类似“骨架”的东西来连接整个欧拉回路。而在连通图中,树是一个不错的选择。

我们令欧拉回路从 $1$ 号点开始走,把最后一次经过除 $1$ 号点以外的点时走的出边拿出来作为特殊边。那么除了 $1$ 号节点以外每个节点有一条出边,并且由于是最后一次,不会出现环。于是这些特殊边构成了一棵以 $1$ 为根的树。

怎么统计这棵树呢?只要从向上走的边上拉一条出来就好了,方案数是 $\prod t_i/2$

确定了最后一条出边之后找欧拉回路的过程其实也不难,对于一个点 $x(x>1)$,前 $deg_x-1$ 次可以非特殊出边中任意挑选,最后一次只能走特殊出边,方案数是 $(deg_x-1)!$。对于 $1$ 号点来说没有特殊边的限制方案数仍然是 $deg_1!$。

于是方案数变成了 $deg_1!\prod_{x>2} (deg_x-1)!$,再乘上其他系数……妈呀我怎么还是过不了样例啊。

注意题目要求循环同构算同一种方案,但是你强制起点是 $1$,而 $1$ 在欧拉序列中可能出现了多次,于是你就统计了多次。

解决办法也很简单,$1$ 在欧拉序列中出现的次数恰好是 $deg_1$,除掉即可,这样最后一部分方案数变成了 $\prod (deg_x-1)!$。

时间复杂度 $O(n)$,期望得分 $20$ 分,结合算法一可获得 $40$ 分。

算法三

观察树上的结论,我们会发现有向图的欧拉回路计数问题是有一个通用公式的:

$$T \cdot \prod (deg_x-1)!$$

其中 $T$ 是以某个节点为根的树形图数目。

于是问题就变成了给图定向。

考虑一个环的情况,由于 $t_i \leq 10^4$,我们可以直接枚举在环上转了几圈,那么每条边往两个方向走的次数都能计算出来。

接下来就是求环的树形图数目了。

对于 $n=m=3$ 的情况显然可以手算,其余的情况,注意到树只比环少一条边,那么枚举那条边断开就好了。

时间复杂度 $O(t_in)$,期望得分 $30$,结合算法一二可获得 $70$ 分。

算法四

环的问题解决之后,环套树问题就变得十分容易了。事实上,枚举任意一条环边正着走了多少次,根据有向图欧拉序列条件式 $indegree_x=outdegree_x$,就可以直接给无向边定向,定向的方案数直接用组合数计算就好了,例如 $t_i$ 条无向边有一侧是 $s_i$ 条,方案数就是 $\prod \binom{s_i}{t_i}$。

第二步就是树形图计数,这一步只要把环上的树形图计数和每个点的外向树树形图计数直接乘起来即可。

最后乘以 $\prod (deg_x-1)!$ 即可。

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

奥林匹克数据结构

from ppfdd,题解 from matthew99

算法一

直接按照题意模拟,时间复杂度$O(n\sum{{m_i} ^ 2})$,加上一些小优化很容易做到$O(n\sum{m_i})$。

算法二

考虑KMP的过程,我们同样考虑对b串建出KMP中的fail数组。那么我们发现,只需要将KMP中判断两个数相等的操作改成判断只要最后一个数字在整个序列中的名次相同即可。

用主席树实现可能会有常数问题。我们发现,我们只需要用树状数组预处理出b串中每个位置在它前面的所有数中的名次。然后再用树状数组维护当前的border,由于在KMP中border是单调的,所以每次border变化的时候暴力修改即可。

时间复杂度$O((n + \sum{m_i})\log{n} + \sum{m_i\log{m_i}})$。

算法三

考虑多串匹配,显然就是将KMP改成AC自动机,转移就是考虑下一个数在当前点到根的路径上的所有数中的名次,现在由于没有类似KMP的border的单调性,我们必须用主席树维护了。注意实现的时候,每次失配时一定要顺着fail链走上去而不是直接将转移置为fail节点的对应转移,否则会由于字符集太大无法保证复杂度(注意如果是一棵普通的trie而且字符集很小,一定要将转移置为fail节点的对应转移,因为普通trie的叶子节点深度之和可能很大)。

接着将原串在AC自动机上走一遍,最后更新子树和。注意如果暴力更新子树和会由于复杂度不对而超时。

注意要用平衡树或者hash存储转移。

时间复杂度$O(n(\log{n} + \log{q}) + \sum{m_i\log{m_i}})$。($q$是因为AC自动机上每个点度数最多是$q$)

算法四

注意到如果$\max{m_i} \le 25$,我们可以对于长度小于$\max{m_i}$的串全部预处理一遍hash值并存下来,具体来说可以存在一个数组里面然后排序,然后询问的时候直接二分查询个数即可。

用树状数组加上异或哈希实现常数较小,可以通过四个$\max{m_i} \le 25$的点。

时间复杂度$O(n\max{m_i}\log{n} + q\log(n \max{m_i}))$。

算法五

我们考虑在线怎么做。对于普通的字符串,这个问题显然是用后缀三兄弟或后缀平衡树解决。那么在这个问题上是不是也可以如此呢?

后缀数组!

慢着……这玩意儿。。。后缀数组要求把后缀进行排序,很好,两个名次数组怎么比较顺序?

后缀自动机!

慢着……这玩意儿。。。一个结点能识别的子串的长度都不固定,怎么玩?

后缀平衡树!

慢着……这玩意儿。。。还是不知怎么比较两个名次数组的顺序啊。

后缀树!

慢着……这玩意儿。。。诶不慢,好像可以。

考虑用Ukkonen算法构造后缀树的过程,显然每一步也很容易用主席树推广到这题上。

然而直接用 Ukkonen 算法会被卡复杂度。我们把孩子数不等于 $1$ 的非根节点称为特殊节点,原因是在普通串上,一个特殊节点的后缀链接显然会指向一个特殊节点,因为特殊节点已经有两个不同的字母作为转移,那么它的后缀链接肯定也有这两种字母,而在本题中不然,由于后缀链接指向了一个更浅的点,因此两种转移可能会合并为一个。

解决方法很简单,在找后缀链接的时候,如果它的父亲不是特殊节点,那就找它父亲的父亲,直到找到一个特殊节点,再从那个特殊节点开始求出当前点的后缀链接,可以证明这样的复杂度是正确的。

构造完后缀树之后求一遍子树和,每次在后缀树上跑一边查询即可。

时间复杂度 $O(n \log n + \sum{m_i(\log{m_i} + \log{n})})$。

有人说,有后缀数组和后缀自动机了,还要后缀树干嘛?从这题可以看出,每个数据结构都有自己的特性。后缀树在这题上能够成功的原因,也许是因为他其实是某种后缀 Trie 的 AC 自动机吧。而 AC 自动机能够解决离线问题的原因,也许是因为他其实是推广后的 KMP 吧。这一切,也许正是奥林匹克数据结构的魅力所在。

UOJ Easy Round #3

2015-08-19 14:12:09 By vfleaking

UOJ Easy Round #3将于8月23日星期日晚上19:00举行!比赛将进行3个小时,共三道题。

这是UOJ第三场UOJ Easy Round。注意了!这次是妥妥的 NOIP 难度!货真价实,童叟无妻!(咦?)

每年9月1日时全国各地都有秘密人员秘密聚集在秘密场所。没错,那就是开学!

距离开学还有一周多一点,准备好了吗?你作业做完了吗?

本次比赛将以开学为主题。

出题人:Starzxy, loriex, jiry_2

这场成绩将计入rating。

参加本次比赛将有机会获得 UOJ 抱枕!15d16fe70b8479bb53d45018bf1647e0 是获奖条件的 md5 码。比赛结束后将公布条件。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

UPD:比赛已经结束!

echo -n 本次比赛得分超过200的选手中得分最低的人。如果没有这样的人那么取比赛的第一名。 | md5sum
15d16fe70b8479bb53d45018bf1647e0

恭喜获得前 5 名的选手!

  1. matthew99
  2. alpq654321
  3. r_64
  4. NanoApe
  5. wangyurzee7

恭喜 alpq654321r_64 获得 UOJ 抱枕一个!

UOJ Round #9

2015-08-04 23:21:07 By vfleaking

UOJ Round #9将于8月9日星期日晚上19:00举行!比赛将进行3个小时,共三道题。

这是UOJ第九场UOJ Round。UOJ Round 还是一如既往的省选难度~!欢迎大家来玩~!

每年NOI,多少悲欢离合。转眼间NOI2015已经过去了半个月,曾经最深刻的记忆或许正在逐渐变得模糊。

说好的AC呢?只剩下翻江倒海的悔恨了吗?

说好的金牌呢?只剩下空荡荡的机房了吗?

本次比赛将以NOI为主题,谨以此比赛献给我们终将逝去的青春。

出题人:Picks, taorunz, SHUXK

这场成绩将计入rating。

参加本次比赛将有机会获得 UOJ 抱枕!770d27522ac8d04d6bb2a4d1a22deea9 是获奖条件的 md5 码。比赛结束后将公布条件。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

UPD:比赛已经结束!

echo -n 排名最高的掉rating的选手 | md5sum
770d27522ac8d04d6bb2a4d1a22deea9

恭喜获得前 5 名的选手!

  1. dwjshift
  2. greatwall1995
  3. nbdhhzh
  4. matthew99
  5. heheda

恭喜年度悲剧人物 r_64 获得 UOJ 抱枕一个!

UOJ Round #8 题解

2015-06-09 22:22:53 By vfleaking

赴京赶考

from Gromah

大家好,我是 Gromah,大家赴京赶考的路上是不是都是骑的果弱马去的呢。。?(雾)

算法零

$n,m \le 100, q \le 10$ 的话,直接给网格中的每一个格点都建一个点,然后该怎么最短路就怎么最短路,该怎么并查集+BFS就怎么并查集+BFS。

复杂度 $O(qnm)$,可以拿下前30分。

算法一

$n\le 10^5, m = 1, q\le 10^5$ 的话,我们可以直接预处理出 $(1,1)-(1,i)$ 的距离以及 $(1,i)-(1,n)$ 的距离,然后就枚举走的方式 $i-j$ 或者 $j-n-1-i$ 就可以啦。

复杂度 $O(n + q)$,结合算法零可以拿下50分。

算法二

$n,m\le 10^5, q\le 10^5$ 的话,我们发现我们可以突破维度的界限,把每一维拆开分别考虑,最后的答案就是每一维的答案的和。

这为啥是对的呢?

对于 $a_i \neq a_{i+1}$,无论 $b_j$ 取啥值,你从 $(i,j)$ 穿越到 $(i+1,j)$ 的时候,都必然会花费等待时间;否则如果 $a_i = a_{i+1}$ 的话,就必然不会花费等待时间。所以一条路线的总等待时间可以拆分成各个维度的等待时间的和。

然后这个问题就变成一维问题啦,直接用算法一的搞法就可以了。

复杂度 $O(n + m + q)$,可以拿下100分。

阅读更多……

UOJ Round #8

2015-06-02 22:48:28 By vfleaking

UOJ Round #8将于6月9日星期二晚上19:00举行!比赛将进行3个小时,共三道题。

这是UOJ第八场UOJ Round。UOJ Round 还是一如既往的省选难度~!欢迎大家来玩~!

高考,是中华人民共和国重要的全国性考试之一,全国各地均于每年的6月7日开考并依各省情况持续2至3天。

本次比赛将以高考为主题。

出题人:Gromah, jiry_2, jcvb

高考

这场成绩将计入rating。

参加本次比赛将有机会获得 UOJ 抱枕!09119692784963a68c86161a5e4f645a 是获奖条件的 md5 码。比赛结束后将公布条件。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

UPD:比赛已经结束!

echo -n 第一个AC了B题的选手(如果没有人AC了B题,那么第一个AC了A题的选手获得抱枕) | md5sum
09119692784963a68c86161a5e4f645a

恭喜获得前 5 名的选手!

  1. matthew99
  2. gonens
  3. wwx
  4. alpq654321
  5. ppfdd

恭喜 gonens 获得 UOJ 抱枕一个!

UOJ Round #7 题解

2015-03-22 14:02:08 By vfleaking

水题生成器

from taorunz

算法一

对于前6个数据$n\le5$,$5!=120$,只有$16$个约数。 我们直接用$16^5$枚举这些子集,找到一个和等于$m$的集合即可。

当然,由于$n$很小,你还可以用分类讨论之类的方法乱搞。

期望得分:30分

算法二

对于前14个数据$n\le9$.

我们可以将本问题看成一个背包问题来解。

时间复杂度是$O(d(n!)*m)$的, 其中$d(x)$表示$x$的约数。

期望得分:70分

阅读更多……

UOJ Round #7

2015-03-18 11:46:51 By vfleaking

UOJ Round #7将于3月22日星期日晚上19:00举行!比赛将进行3个小时,共三道题。

这是UOJ第七场UOJ Round。UOJ Round 还是一如既往的省选难度~!欢迎大家来玩~!

每年的3月22日为“世界水日”,旨在推动对水题资源进行综合性统筹规划和管理,加强水题资源保护,解决日益严峻的缺乏水题的问题,开展广泛的宣传以提高公众对开发和保护水题资源的认识。

本次比赛将以世界水日为主题。

地球

出题人:taorunz, saffah, Picks

这场成绩将计入rating。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

UPD:比赛已经结束,恭喜获得前 5 名的选手!

  1. alpq654321
  2. wwx
  3. kfdong
  4. qmqmqm
  5. mazeyu

UOJ Round #6 题解

2015-03-08 20:45:20 By vfleaking

破解密码

from:Starzxy

这都是vfk出的QAQ你萌别打我

算法一

暴力枚举每一位的字母,判段Hash值是否相等,时间复杂度$O(26^n)$。可以获得20分。

算法二

用高斯消元消元就好啦,时间复杂度$O(n^3)$。可以获得50分。

算法三

对于每一个$a_i$,把它变为$a_{i+1}$就是把$a_i$的首字母移到最后一位,对应的,设$a_i$首字母为$c$,$h_{i+1}=((h_i - 26^{n-1}\mathrm{num}(c))\times 26+\mathrm{num}(c))\bmod p$。对于每一位,我们枚举$c$,因为$p$是大于$26$的质数,且数据保证有解,可以确定每一位有且仅有$1$个小写字母满足。

阅读更多……

UOJ Round #6

2015-03-02 22:21:08 By vfleaking

UOJ Round #6将于3月8日星期日晚上19:00举行!比赛将进行3个小时,共三道题。

这是UOJ第六场UOJ Round。UOJ Round 还是一如既往的省选难度~!欢迎大家来玩~!

公元321年,就在3月8日的前一天,3月7日,罗马帝国皇帝君士坦丁一世正式宣布星期日为罗马的休息日。屈原跳河只换来端午1天,中国成立只换来国庆7天,各个学校的老师还经常剥夺休息日。你看看人家君士坦丁一世,随手一挥送休息日就每周送一个,简直就是业界良心中的战斗机!

所以本次比赛将以星期日为主题。

鼓掌熊

出题人:Starzxy, Picks, jiry_2

这场成绩将计入rating。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

UPD:比赛已经结束,恭喜获得前 5 名的选手!

  1. matthew99
  2. qmqmqm
  3. PoPoQQQ
  4. Dylan_Sun
  5. wyh2000

UOJ Round #5 题解

2015-01-17 22:18:48 By vfleaking
$\newcommand\lcm{\mathbin{\mathrm{lcm}}}$

怎样提高智商

from vfleaking

算法一

有一种算法叫做手算。只要你脑力足够,算出 $n = 2, 3$ 什么的大概没有问题。可以获得 20 分。

算法二

有一种算法叫做爆搜。我们裸暴力搜索 $h_i, a_i, b_i, c_i, d_i$ 再裸暴力求方案数,只要你不是写得太糟糕,考试三个小时跑出 $n = 2, 3, 4$ 还是妥妥的。对于 $n = 5, 6$ 的话留给人类智慧达人、搜索剪枝达人、随机化乱搞达人、模拟退火达人。

阅读更多……