vfleaking的博客from wyx528
容易发现，每次可能的操作不会超过 3 种，因此只要在需要决策的时候暴力枚举其中的一种即可，指数级复杂度，可以得到 20 分。
由于要求字典序最小，所以必然要把尽可能小的数提前出栈，更特殊地，一定会把最小的数最先出栈。
当最小的元素出栈时，记栈底元素为 $x$，栈顶元素为 $y$，未进栈的元素中最小值为 $z$，则下一个要出栈的元素必为 $\min\{x,y,z\}$。由于题目保证给定的元素互不相等，所以这一步是没有歧义的，也就是说 $x,y,z$ 中任意两个都不会相等。这样，我们便得到了输出序列的第二个数。
可以发现，只要重复这个贪心过程即可取得最优解。使用朴素算法，选取未进栈元素最小值的时间复杂度为 $O(n)$，因此完成一组数据的时间复杂度为 $O(n^2)$，可以得到 60 分。
使用堆或者平衡树来优化算法二中选取未进栈元素最小值的时间复杂度，使之降为 $O(\log n)$，这样完成一组数据的时间复杂度变为 $O(n \log n)$，可以得到 100 分。（比赛时还真有人这么干……）
再见，乙未！
转眼间，乙未年已经过去。过去的这一年，羊族守护着中华大地。除夕夜，羊族完成了一年的使命。零点钟声敲响，猴族首领接过了羊族首领的生肖旗，开启了新的一年。
猴族的首领名叫猴腮雷，因两腮上各长了一个腮雷而闻名于世。他有一句名言：没有什么是一颗腮雷解决不了的，如果有，那就两颗。
在新的一年里，祝大家一帆风顺万事如意，即使遇到困难也要迎难而上，在最艰难的时候也要坚信 —— 没有什么是猴腮雷解决不了的。
我们将于除夕前一天下午 13:00 到 18:00 举办一场盛大的 Goodbye Yiwei 赛。
即：2月6日下午 13:00 到 18:00。注意此次比赛时间为 5 小时，共 5 道题 ABCDE 来给大家贺岁～
赛制仍然是OI赛制，但是题目难度嘛，水题和省选难度题兼有。欢迎所有人包括萌萌哒NOIP选手来玩！
出题人：wyx528, sevenkplus, Rating_Jia_Su_Qi, saffah, ppfdd
这场成绩将计入rating。
参加本次比赛将有机会获得 UOJ 纪念品！你可以选择 UOJ 抱枕或 UOJ 充电宝！8e2519a93491ea3651f808eb830fe26c 是获奖条件的 md5 码。比赛结束后将公布条件。
再次提醒大家比赛中途只测样例，最后会进行最终测试，把所有提交记录重测。
UPD：比赛已经结束！
echo -n ABCDE都得分的人中成绩顺序对数最多的（顺序对是逆序对的反义词），有多个人取排名最靠前的 | md5sum
8e2519a93491ea3651f808eb830fe26c恭喜获得前 5 名的选手！
恭喜 heheda 获得 UOJ 抱枕一个！
不得不说今天是个伤感的夜晚。我们此时站在这里，连接过去和未来。曾以为我们的计划会成为我们的未来，却不知道大浪拍击沙滩的力量比飓风更有力。
UOJ从哪里来？今晚的UOJ还是一年前发布时的那个UOJ吗？
为什么我们慢慢忘了那最虔诚的最初，渐行渐远……
于是我意识到，我们应该回去，回头看看那最初的原点。
最初我是怀着对OI界题目的不满，最初我和业界毒瘤有很多比较难的脑洞想出给大家玩，最初的最初是那场引发我对OI比赛的思考的NOI2013……
我们想建立的是，一个能自由评测各种类型题目的OJ，一个题题高质量的OJ，一个定期举办高质量的比赛的OJ —— 一个能带给OIer思考与收获的OJ。
那么怎样的题才能被称为好题？我记得那年我造题，一造就是一周。没有别的，就是死磕。磕题面的简洁严谨，磕标程的运行效率，磕数据，写好几个暴力分别卡掉 —— 这一切都源于我对现行OI出题人的不满。出到比赛里的题，平时抛之脑后，考前紧急造题，最后端给选手的是一碗方便面。
一道好题应该被仔细推敲过。好题应该有很强的数据，好题应该又清晰的题面，好题的标程应该优美题解应该详尽。
一道好题不应该是两道题拼在一起，一道好题会有自己的idea —— 而它应该不加过多包装地突出这个idea。
一道好题应该新颖。真正的好题，应该是能让人脑洞出新的好题的好题。
一道好题应该具有它的选拔性质，具有足够的区分度。应该至少4档部分分，让新手可以拿到分，让高手能够展示自己的实力。
不得不说我认为我出过的题中最优美的还是两年前的那个嵌入了函数式线段树的网络流题 a+b problem。
嗯，这一切都是开端。接下来就是 UOJ Test Round #1，UOJ Easy Round #1，UOJ Round #1，UOJ Round #2，UOJ Round #3，这几场我都很满意。
等到UOJ Round #4及之后的时候我发现情况有些不对了，因为没有什么题可出了。 UOJ比赛的频率是两周一次，对于要造题的我来说是相当辛苦的。应该就是从这场比赛开始吧，由于没有好脑洞，我开始使用起自己特有的脑洞能力去改编出题人给我的不那么完美的题，死磕直到令人满意。
往后看去，UOJ Round #5的C题考验了大家对莫比乌斯反演的灵活运用，纯考智商的UOJ Round #6的C题是一个小小的巅峰，各种贪心得到简洁结论又需要用一些技巧优化复杂度的UOJ Round #7也相当有意思。
再往后看去，让人觉得有趣的又有多少呢？
后来UOJ搬运了集训队互测这头怪兽。
后来我CTSC滚粗，退役了。这之后其实我心态完全发生了变化 —— 因为OI已经几乎与我无关。
后来UOJ的比赛完全造好题目的时间离比赛开始的时间越来越近。
后来有出题人给我idea，我没有太多耐心跟他一起脑洞一起改编。
后来我为了“两周一次”这个承诺而造题，而不是为了最初的一场大梦，甚至连两周一次也做不到。
我渐渐意识到，自己都觉得没那么有趣的题目，别人凭什么觉得有趣？远远超过三小时的汗水，才值得几百人为一场比赛花上三小时。
我想起了我最初的一句“宁缺毋滥”，我想起了激励了我很长时间的洛克菲勒与协和医院的故事：我们要以最高标准建一所医院，成为中国医学界的一座标杆 —— 而我们清楚地知道，论题目的数量，世界上千万万OJ不缺我们UOJ一家，我们要做的就是聚集最优秀最热爱信息学的OIer，建立一个题目质量难以企及的OJ。
然而说好的题目质量呢？
今日的UOJ Easy Round #5，被点了好多差评。当然我一开始是吐槽那些“不会做题就直接点差评”党们，或是抱怨做题人不懂出题人的艰辛 —— 然而，做题人和出题人什么时候互相理解过？看到网上对葛军的一些言论，假若那些截图是真的，那么同为出题人我特别能体会到葛军的心情。但是我们能抱怨那些来做题的人吗？
回到最初最初的想法，从服务器到域名，从数据库到网页前端，从一句ptrace到一整个沙箱，从零散的idea到一整场比赛，我做这些到底是为了什么？就是想让大家一起享受算法的乐趣啊……就是想帮助大家实现自己的信息学梦想啊……
所以有什么好抱怨的呢？我想要帮助的人觉得自己在浪费时间，是他们的思想境界问题吗？其实，我自己也没有特别认真对待最近的这些UOJ比赛不是么？
我知道我在吃老本，一点点考验着在座的各位由于过去的比赛而产生的对UOJ的信任。然而这些终将过去，没有多少人还会记得UOJ Test Round #1的文件名排序，UOJ Easy Round #1的有趣的并查集，UOJ Round #1的仙人掌……重要的是当下，重要的是未来UOJ如何发展。
看到比赛前热情洋溢的报名人数，看看最后点赞寥寥差评者众的局面，我想，其实这一切都是因为我变懒了吧。虽说经历了这么多，让我跟最初的那个理想的我相比更加现实了一些，更加能理解作为一个出题人他所面临的窘境，但是当我今天回忆起我们最初究竟是要干什么的时候，我还是清晰地意识到：不能再迷失了，虽然我没时间负责具体的造题，但是，是时候回去了 ——
回到那场大梦，坚持UOJ的精神。
因为不忘初心，方得始终。
众所周知 vfk 一夜间变成了大学生。
然后大学全新的环境我自己都还没把自己玩清楚，忙了一段时间后发现果然 UOJ 就这么坑着了。
其实出发去大学之前还想着可以咬牙硬撑。还记得 UER #3 吗？在大家激战正酣的时候，vfk 正在整理内务、把被子叠成豆腐块。就这样我在军训期间成功办了比赛。
然而，我那次完全没有以前认真，有些题自己并没有仔细检查，慌慌忙忙就出了。
有这样一件事非常激励我：当年洛克菲勒想做慈善，提升中国的医疗卫生水平。他派出的调查团给出了两个方案：
洛克菲勒选择了方案2，他建了一所从硬件设施到专业水平都世界一流的医院，那就是协和医院。据说第一届只招了 7 个学生，最终有 3 个人成功毕业。协和的严谨认真的精神传承至今，成为中国近代医学史上的一座丰碑，被千百万医学后辈仰望。
我在创办 UOJ 之初就想到：论题目数量，天下 OJ 不缺 UOJ 这一个。我跟洛克菲勒的选择一样：我们要的不是数量，而是质量。
也许你有所耳闻，UOJ 的比赛的题目的审核较为严格。当题目不有趣时我会和出题人一起讨论，不断地改进、加强。所以，一场 UOJ 比赛要耗费我大量的时间和精力 —— 这对于我来说有点奢侈。
抱歉我就这样把 UOJ 比赛拖欠了 2 个月。我很感动的是 jiry_2 和 C_SUNSHINE 愿意来帮忙给 UOJ 的比赛找题、审题，嗯，是时候让现役选手出点有趣的题目给大家了。
这周的 UER #4 由 jiry_2，C_SUNSHINE 和我共同负责，欢迎各位！
虽说博客题目是暂别，但是也不是暂别吧，因为 vfk 一直就在这里，UOJ 的团队一直在这里。我们会忙活 UOJ 的事，只是花的时间比以前少多了。
我很喜欢 UOJ，即使从 OI 退役了也如此，高三折腾 UOJ 的日子是最难忘的回忆，愿 UOJ 有更加美好的未来。
by Starzxy
首先，光标移动范围不可能超出 $(1,1)-(n,m)$ 的方格。其次，只有 →，↓ 与 Fn 是有效的按键。（很显然吧……
枚举每一种不同的操作,时间复杂度$O(3^{n+m})$。可以获得10分。
设 $N[x],x\in$｛↓ , →｝表示按下 $x$ 键后光标行位置的变化。
设 $M[x],x\in$｛↓ , →｝表示按下 $x$ 键后光标列位置的变化。
用 $F[n][m][k_1][k_2]$ 表示光标移动到第 $n$ 行第 $m$ 列最后分别按下的 ↓，→ 或未进行按键操作是 $k_1$ 与 $k_2$，则 $F[n][m][k_1][k_2]=min(F[n-N[k_2]][m-M[k_2]][k_x][k_1],F[n-N[k_1]-N[k_2]][m-M[k_1]-M[k_2]][k_1][k_2])+1$，$k_x$ 为任意操作，$\mathrm{DP}$ 可以做到 $O(nm)$ 的复杂度。可以获得50分。
对于只有一行或者一列的情况，多枚举一些就能找到规律。（啊啊啊就在右（下）边我要拼命按右（下）按Fn！
可以获得20分，结合算法二可以获得70分。
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 名的选手！
恭喜 alpq654321 和 r_64 获得 UOJ 抱枕一个！
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 名的选手！
恭喜年度悲剧人物 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。
什么！怎么切过去全是中文？
因为我只翻译了一部分！ = =……
翻译工程貌似很庞大的样子……偶慢慢来吧……反正现在用户没有歪果仁啦。
诚招有兴趣翻译的英语高手。
鄂公网安备 42010202000505 号Server time: 2024-04-25 06:50:54