再见，甲午！

过去的一年是甲午年（提起甲午总是想到120年前那场惨烈的中日甲午战争），值此新春佳节之际，我们将于大年三十的前一天大年二十九下午 13:00 到 18:00 举办一场盛大的 Goodbye Jiawu 赛。

即：2月17日下午 13:00 到 18:00。注意此次比赛时间为 5 小时，共 5 道题 ABCDE 来给大家贺岁～

不要问我为啥甲午的翻译是 Jiawu！谷歌娘告诉我的！

我们准备了一些有趣的题目，不过题目还没有完全确定，过几天会在这里发布出题人。

至于 UOJ Round #6，由于近日来大家都去期末考试去了（从网站的访问量上可以看得出来）。然后二月初也够呛，接着就是一年一度的 WC 了，也没人会打。所以 UOJ Round #6 将被移到再见甲午赛之后。

赛制仍然是OI赛制，但是题目难度嘛……水题和省选难度题兼有。欢迎所有人包括萌萌哒NOIP选手来玩！

提前祝大家春节快乐！（貌似太早了 = =……）

UPD: 公布出题人：Picks, saffah, vfleaking, wangyisong1996

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

1. fullpower
2. zld3794955
3. yu990601
4. BillXu2000
5. Chenyao

很久以前写的题解。听说有人找不到他们？

动态仙人掌 系列题解之一 —— 动态仙人掌 I

动态仙人掌 系列题解之二 —— 动态仙人掌 II

动态仙人掌 系列题解之三 —— 动态仙人掌 III

动态仙人掌 系列题解之四 —— link-cut cactus

UPD (2020-08-15): 不好意思，其实后来 163 博客倒闭了，转战 csdn 了

动态仙人掌 系列题解之一 —— 动态仙人掌 I

动态仙人掌 系列题解之二 —— 动态仙人掌 II

动态仙人掌 系列题解之三 —— 动态仙人掌 III

动态仙人掌 系列题解之四 —— link-cut cactus

由于 UOJ 什么的七七八八的事情，集训队作业一直缓慢。但是我最终还是做完啦！

第一轮集训队作业试题准备：http://pan.baidu.com/s/1sj6ZhOL

第一轮集训队作业试题泛做：http://pan.baidu.com/s/1kT0zNBx

试题准备就是传说中的每个集训队成员重造 3 道题，试题泛做是传说中的 100 道题题解 = =……都是很久以前的题了，我猜没什么人需要？不过还是挂出来吧。有句古话说得好：彼之砒霜，吾之蜜糖。说不定对你有用？

顺便附第一轮集训队作业内容：http://pan.baidu.com/s/1AlBqu

坐等WC退役。

怎样提高智商

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})$

阅读更多……