电路手动分析

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将于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 抱枕一个！

赴京赶考

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。

什么！怎么切过去全是中文？

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

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

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

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 抱枕一个！

手机的生产

from wangyisong1996

大家好我是wys，我第一次出UER的题感觉很excited

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

阅读更多……

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

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

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

最后 CTSC 滚粗，OI 再见。

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 抱枕一个！

欢迎加入带花树神教！

为了方便后人：

窝的代码！ http://uoj.ac/submission/16359

匹配教程大一统： http://www.csie.ntnu.edu.tw/~u91029/Matching.html http://web.ntnu.edu.tw/~algo/Matching.html （UPD：2020年10月5日）

某 python 代码：http://jorisvr.nl/maximummatching.html

唔……提前预告一下……Delayyy的集训队论文是匹配……内置了关于匹配的算法的详细（雾）介绍，包括一般图最大权匹配。

带花树真是个优美的算法啊～！ T^T……

链接: http://pan.baidu.com/s/1jG5UjKa 密码: 7egs

UPD：百度云说我文件名涉及了不良内容然后封了？？？我稍微改了一点，重发下：

链接: https://pan.baidu.com/s/1XPtdgFPsIIb4mPoUdV7USg 密码: ykjh