怎样提高智商

from vfleaking

算法一

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

算法二

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

阅读更多……

UOJ Round #5将于1月17日星期六晚上19：00举行！比赛将进行3个小时，共三道题。

这是UOJ第五场UOJ Round。UOJ Round 还是一如既往的省选难度～！欢迎大家来玩～！

1929年1月17日，美国漫画家艾尔济·席格创作的漫画人物大力水手第一次在漫画《顶针戏园》中登场。大力水手漫画一问世即大受欢迎，甚至在当地出现食用菠菜的热潮。

T^T……说起来还是满满的童年回忆呢……虽然情节都忘光了。为了纪念大力水手，此次比赛将以大力水手为主题。

出题人：vfleaking, jiry_2, taorunz

这场成绩将计入rating。

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

UPD：比赛已经结束，恭喜获得前 5 名的选手！

1. matthew99
2. orz_VFleaKing
3. SanSiroWaltz
4. saffah
5. ppfdd

元旦三侠的游戏

from keavil

算法一

对于第一个测试点，我们有 $ n = 2 $ 。那么必定有 $ a = 2 $， $ b = 1 $。

显然，无论我们增加 $ a $ 或者是 $ b $，都会违背 $ a^b \leq n $ 的要求。那么这种情况必定是先手必败的。因此直接输出No就能获得$10$分。

算法二

这是一个博弈问题。我们考虑用 $ f_{a,b} $来表示当前的游戏状态。$ f_{a,b} $为 $ 1 $ 表示当前的 $ (a,b) $ 是先手必胜状态，否则表示当前的 $ (a,b) $ 为先手必败状态。

然后我们就可以用记忆化搜索来转移了。注意到 $ a $ 显然不能超过 $ n $，而 $ b $ 不能超过 $ \log n $ 。那么就可以在 $O(n \log n)$ 的时间内处理出全部的状态了。

阅读更多……

UOJ Round #4将于元旦假期期间的1月2日星期五晚上19：00举行！比赛将进行3个小时，共三道题。

这是UOJ第四场UOJ Round。当然！UOJ Round难度定位一直都是省选难度～！欢迎大家来玩～！

圣诞期间，著名的大坏蛋圣诞老人开始横行，地球表面的人类基本被清洗。

于是元旦期间，主张正义、维护世界和平的元旦三侠：生蛋侠、圆蛋侠、零蛋侠开始积极行动，联合起来消灭圣诞老人。但是生蛋侠每天忙着生蛋，圆蛋侠圆滚滚走起路来根本停不下来，零蛋侠每天沉浸在题海战争里却还是考试领零蛋。这种战斗力怎么能战胜圣诞老人？请用你的智慧帮一帮他们吧！

出题人：keavil, vfleaking, wangyisong1996

这场成绩将计入rating。

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

UPD：比赛已经结束，恭喜获得前 5 名的选手！

1. alpq654321
2. jiangshibiao
3. saffah
4. liuzurang
5. wwt16

附漫画说明圣诞老人为什么是坏蛋：

阅读更多……

核聚变反应强度

算法一

对于 $n=1$ 的数据，就是求一个数次大的约数。

众所周知一个数$x$的约数是成对出现的（$d$、$\frac{x}{d}$），其中总有一个不超过$\sqrt{x}$。所以从$1$到$\sqrt{a_1}$地枚举$d$就能找出所有$a_1$的约数了。排序输出次大的即可。

复杂度：$O(\sqrt{a})$

算法二

先找出$a_1$的所有约数，然后枚举$i$，$\text{sgcd}(a_1,a_i)$显然也是$a_1$的约数，所以枚举$a_1$的所有约数，找到是$a_i$约数的次大的即可。

复杂度：$O(n\sqrt{a})$

阅读更多……

UOJ Round #3将于12月20日星期六晚上19：00举行！比赛将进行3个小时，共三道题。

这是UOJ第三场UOJ Round。UOJ Round难度定位一如既往地大概还是省选难度～欢迎大家来玩～！

63年前也就是1951年12月20日，美国爱达荷州阿科市，EBR-1 首次由核能产生电能，点亮了四盏灯。于是 EBR-1 成为了世界上第一个核电站。几十年过去了，核电作为相当安全、环保、经济的能源正在逐步的代替其它的各种能源。

为了纪念世界上第一个核电站的诞生以及物理学家利用核裂变发电的脑洞，此次比赛将以核电站为主题。

出题人：delayyy, vfleaking

这场成绩将计入rating。

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

点击此处直达报名

UPD：很抱歉地通知您，此次比赛将推迟一天。之前由于清华集训导致出题人完全没有时间造题，屋漏偏逢连夜雨，昨天恰好赶上我因为北京的神奇病毒发烧打了一天吊针，今天振作起来赶着造第三题的数据及标程。

考虑到比赛质量为第一位，我很怕这么仓促的准备会影响比赛的题目质量，出一些sb错误，所以比赛将延期一天。

一直以来UOJ都和BestCoder撞了，实在对不起，今天想打BestCoder的同学去打吧 T^T……

真心表示万分抱歉……

时间推迟到12月21日星期日晚上19：00。

UPD：比赛已经结束，恭喜获得前 5 名的选手！

1. saffah
2. TakanashiRikka
3. fotile96
4. laekov
5. Starzxy

猪猪侠再战括号序列

算法一

有一个超良心测试点满足 $n \leq 4$。注意到 $8$ 个元素的排列最多 $8!$ 个，所以直接使用 bfs 或者 dfs 搜索，每次对于一个序列枚举所有可能的翻转区间然后搜下去就好了。可以获得 10 分。

算法二

算法一显然太无脑了。考虑翻转操作其实用起来非常不爽，因为牵连的元素个数太多。如果题目允许你每次交换序列中的两个元素的位置，那么其实要好办很多。

于是我们重新设定目标，把目标序列变为一个显然是合法的括号序列，类似这样 “(((())))”。

我们从左往右依次处理原序列的前 $n$ 个括号，如果发现有一个右括号，我们就在右边随便找个左括号。由于左括号和右括号都是 $n$ 个，所以我们总能找到。然后我们把当前位置到那个左括号之间的序列翻转过来，这样当前位置就很开心的成了左括号。翻转过来之后当然中间的括号一团糟啦！不过我们是从左往右考虑，所以我们只用保证当前位置以左是与目标一致的。至于右边嘛，这是以后的事情了。

暴力在右边找左括号，然后再暴力翻转序列就能做到 $O(n^2)$ 了。可以获得 50 分。

阅读更多……

UOJ Round #2将于12月6日星期六晚上19：00举行！比赛将进行3个小时，共三道题。

这是UOJ第二场UOJ Round。UOJ Round难度定位大概是省选难度～欢迎大家来玩～！

这次我们荣幸地请到了百度贴吧上的 _叫我猪猪侠 来出题！他带来了一道很符合猪猪侠风格的题！敬请期待猪猪侠带来的狂欢题！

出题人：_叫我猪猪侠, vfleaking, jcvb

唔……这次题目难度目测比上次要简单些。上次那么多人看题跑是什么情况……= =……这次坐等神犇AK。

这场成绩将计入rating。

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

UPD：比赛已经结束，恭喜获得前 5 名的选手！

1. fotile96
2. C_SUNSHINE
3. thomount
4. latrommI
5. saffah

缩进优化

算法一

方便起见用 $/$ 表示整除，$X$ 表示最大的 $a_i$。

要最小化的就是 $\sum_{i=1}^{n} a_i / x + a_i \bmod x$。

枚举 $x$ 再暴力计算上式并更新答案，由于 $x$ 不超过 $X$，所以复杂度是 $O(nX)$。可以获得20分。

算法二

$a_i$ 相同的可以合并在一起，然后就得到了 $O(n + X^2)$ 的算法，结合算法一可以获得40分。

阅读更多……

UOJ Round #1将于11月22日星期六晚上19：00举行！比赛将进行3个小时，共三道题。

这是UOJ第一场UOJ Round。UOJ Round难度定位大概是省选难度～欢迎大家来玩～！

唔……其实UOJ Easy Round只会在每年的noip季节出现，省选难度才是主旋律的。

出题人：delayyy, Picks, vfleaking

这场成绩将计入rating。

这次改了下排名系统。如果你某题得零分是不计罚时的（之前好像坑了不少小朋友）。

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

UPD：比赛已经结束，恭喜排名前5的选手！

1. fotile96
2. SanSiroWaltz
3. PoPoQQQ
4. matthew99
5. thomount

题解在这里