UOJ Logo vfleaking的博客

博客

UOJ Round #9 题解

2015-08-09 22:14:23 By vfleaking

电路手动分析

from Picks,题目是 vfleaking 造的。

算法一

首先这个问题转换为,选一个子图使得补成团的边数不超过 $r$。那么设点数为 $n_v$ 边数为 $n_e$ 那么就是要使得 $n_v(n_v - 1) / 2 - n_e \leq r$。

对于 $n, m \leq 4$ 的情况,我们枚举每一个导出子图就行了。

可以获得 30 分。

算法二

有 20 分的数据满足 $n = 1$。

显然我们应该选连续的一段,于是二分答案就可以了。

可以获得 20 分。

阅读更多……

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的英文版

2015-06-07 23:56:24 By vfleaking

大家应该注意到了!可以切换到英文版的UOJ。

什么!怎么切过去全是中文?炸弹熊

因为我只翻译了一部分! = =……

翻译工程貌似很庞大的样子……偶慢慢来吧……反正现在用户没有歪果仁啦。

诚招有兴趣翻译的英语高手。鼓掌熊

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 Easy Round #2 题解

2015-05-17 17:47:23 By vfleaking

手机的生产

from wangyisong1996

大家好我是wys,我第一次出UER的题感觉很excited 捂脸熊

这题的idea是这样来的: 有一天wys在写OJ(雾),发现一个需要fork()的程序输出了很多奇怪的东西, 然而wys并不懂fork(),于是wys去学(wan)习(shua)了一下fork(), 然后发现fork() && fork() || fork()会把一个程序复制5份 捂脸熊,非常有趣, 所以就有了这道题。

阅读更多……

我的第二轮集训队作业

2015-05-14 11:36:54 By vfleaking

接上回:http://vfleaking.blog.uoj.ac/blog/64 结果木有退役。

第二轮集训队作业有三部分,一部分是自选题写题解(我貌似活生生搞成了自出题写题解),另一部分是论文,当然还有喜闻乐见的互测。

http://pan.baidu.com/s/1pJJsIvD (互测大家已经玩过了,就不含互测了 = =……)

最后 CTSC 滚粗,OI 再见。

UOJ Easy Round #2

2015-05-13 22:58:09 By vfleaking

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

这是UOJ第二场UOJ Easy Round。咦为啥在这个节骨眼上搞 Easy Round 呢?大家一定被之前的集训队互测玩坏了,不要慌!UOJ Easy Round 来了!妥妥的 NOIP 或 NOI 难度改善 UOJ 比赛的画风。

Q:到底是 NOI 还是 NOIP 难度能靠谱点吗?

A:然而我做了去年的 NOI 已经分不清楚这俩玩意儿了。具体来说,A题是一道难度低于 UR A 的题,B题和C题都是 UR B 的难度或更低。

每年的5月17日是世界电信日。1865年5月17日,20多个国家在法国巴黎签署《国际电报公约》,并宣布国际电报联盟成立。后来由于无线电及电话等技术的迅猛发展,国际电报联盟在1932年改名为国际电信联盟。1968年国际电信联盟第23届行政理事会上决定,为纪念国际电信联盟建立,强调电信在国民经济发展和大众生活中的作用,特将该组织成立日5月17日定为世界电信日。

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

出题人:wangyisong1996, jiry_2, Glaceon08

这场成绩将计入rating。

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

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

UPD:比赛已经结束!

echo -n 本次比赛的第二名将获得UOJ抱枕一个 | md5sum
0ab58b67706648a636226fb122838aa7

恭喜获得前 5 名的选手!

  1. sevenkplus
  2. matthew99
  3. ppfdd
  4. SanSiroWaltz
  5. wangck1998

恭喜 matthew99 获得 UOJ 抱枕一个!

妈妈我终于会一般图最大权匹配了!

2015-04-26 15:25:26 By vfleaking

集训队互测 2015 Round #3 题解

2015-04-13 22:37:55 By vfleaking
共 59 篇博客