Mr.K 018

可以啊，模拟了栈的算法直观一点，好想。 而且时空复杂度都是一样的

原题：https://sstm.moe/topic/253265-每-日-算-法-挑-战-【第5期】/ 已经到第二天了，还没看到第5期有任何正确答案。其实各位已经很接近正确答案了，但是都不约而同地忽略了这句话： 当然对任何输入序列都能用两个栈实现排序，相应算法楼里已经有人给出过了。实际上不考虑时间复杂度的话，可以构造出不止一个的用两个栈排序的算法，这里不再赘述。 但是，有没有只需1个栈呢？0个呢？这是本题的另一个考点。 对于0个栈的情况，很简单，当且仅当输入序列已经有序的时候，就不需要栈，输入一个输出一个就行。 对于1个栈的情况，这时需要模拟一下栈的操作了。目标很简单：第k次输出，要输出k。 假设我们刚刚输出完k-1，下一个轮到k了。由于我们不能访问栈中除栈顶元素以外的其他元素，所以k要么出现在以后的输入序列里。那么我们分下面几种情况讨论： 1）k在栈顶。直接弹出k输出即可，皆大欢喜； 2）k在输入序列的某处。我们可以把k之前的元素逐一压入栈中，然后输出这个k。 3）输入序列读完了，也没有发现k。这意味着k既不在栈顶，也不在输入序列里，只能在栈的内部。我们只有一个栈，实际上是访问不到k的。出现这种情况就意味着这个输入序列不能用一个栈排序。 不难发现，用一个栈排序出了上述方法外，别无他法。那么，我们可以在O(n)的时间内解决本题： 1. 遍历输入序列，若发现有序则输出0，结束； 2.进行上述模拟。若从1到n都成功“输出”，则输出1，结束；若出现情况3)，则输出2，结束。 ------ 所以说，这个题是不是比各位想象的简单呢？

陷阱受害者+1 有一说一 我特意提了一句不同输入序列结果会不同的来着 想想看，什么情况下一个栈就行呢？这才是本题的第二个关键

没错，就是这个意思。 但是，判断是否能只用一个栈的算法？ 我现在不知道为啥评不了分，记一下这里有个50+的糖

你会发现这个题其实不关心排序算法的复杂度，只要能让栈的数量少一点，O(n!)都是无所谓的，因为反正也不是真的排序嘛（

抱歉写错了，数据应该是4 5 1 3 2，马上改

各位注意这句话：

“最少需要多少个栈” 你已经接近正确答案了

小声说 传送门那个题不用管了，那个是我记错了，本来想出成单向的，可是出题的时候脑抽觉得单双向一样 今天这个题不是难题哦

第5期来啦！ 这道题看上去没什么头绪，但其实没有那么难哦！ 前排召唤阵： @yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui 第5期 简单的排序题 Mr.K 018: 现在有一列数，从1到n，是乱序排列的，要对它排序。 Mr.K 019: 听上去不复杂啊，然后呢？ Mr.K 018: 你能使用的数据结构只有栈。队列啊，数组啊，堆啊什么的都不许用，只有栈。 Mr.K 019: 你等一下，栈是个啥？ 插入科普：栈是个啥？ 摘自百度百科：栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。就是说，一个栈是*后进先出(Last In First Out, LIFO)*的。 可以把栈想象成一个装鞋盒的筒子。这个筒子很细，鞋盒只能放一排，因此每次只能取走最顶上的鞋盒，也只能把新的鞋盒放在最顶上。不过，倒是可以认为这个筒子很长，可以装很多很多鞋盒。 图5-1 堆栈及其操作示意 好的，我们继续。 Mr.K 018: 除此之外，我希望你用尽可能少的栈就完成这个任务。能用一个就不用两个。 Mr.K 019: 可是我根本不需要用栈啊，直接一口气把1到n输出不就完了么？ Mr.K 018: 呃不是的，这里其实是把一个其他什么数据元素表示成数字了。本来那个东西没准是份名单啊什么的，数字其实就是个id。不过那不重要。 Mr.K 018: 简单说，直接输出是不行的，必须排好序之后输出本来的那个东西才行。不过，输出了之后，那个数就可以不管了。 Mr.K 019: 啊，这……那我不会（直球 Mr.K 018: 我早就知道你不会，那降低一点要求吧。我给你这一列的数，你告诉我最少用几个栈就行，剩下的事情我来办。 Mr.K 019: 啊，这…… 就算018已经降低了要求，019好像也还是不太会。现在他把这个问题抛给了各位，相信同盟的各位肯定能解决这个问题。 需要说明的是，不同的输入序列需要用到的最小栈数可能是不同的，请对每个输入序列分别计算。 输入 有多组测试用例，请读取到文件尾。 每组测试用例由两行组成。第一行是一个正整数n，满足1<=n<=10^5；第二行是一个1到n的排列，保证1到n的每个数都刚好出现一次。 输出 每个测试用例输出一行一个整数，表示对这n个数进行排序最少需要多少个栈。 样例输入 5 4 5 1 3 2 样例输出 2 输出解释 可以先把前三个数压入栈1，随后弹出栈1顶端的1.之后把3和2压入栈1后，依次弹出栈1顶端的2和3输出。此时，栈1中有4 5，栈2为空。将栈1顶端的5弹出并压入栈2，就可以弹出栈1顶端的4输出。再弹出栈2顶端的5输出，结束。

玩家会选择尽可能快地通关。

双向

第4期来啦！ 前排提示：本题涉及一点概率论，不难，也就高中水平 第4期 芜湖，起飞 本期的题目是在飞行棋的棋盘上展开的。棋盘可以想象成一列n个格子，从1到n编号。棋子从第1格开始，每一轮需要掷一枚均匀的6面骰子，取骰子的出目作为前进的格数。当棋子经过第n格（也就是最后一格时），不论是否刚好在这一格停下，就认为是胜利，游戏结束。特别地，棋盘上有若干“飞行通道”，双向连接两个不同编号的格子。若棋子停在了飞行通道的一端，就可以在这一步里直接移动到另一端，也可以选择不移动，直接结束本轮。 已知棋盘的格数n和飞行通道的情况，问从游戏开始到游戏结束，游戏轮数的期望是多少？ 输入 有多组测试用例，请读取到文件尾。 每个用例的第一行是两个数n1≤n≤105和k (1≤k≤103)，分别表示格数和“飞行通道”的数量； 接下来有k行，每行有两个数a­i和bi，分别表示第i个飞行通道两个端点在第几格，满足1≤a­i<b­i≤n. 输出 对每个测试用例，输出一个小数占一行，表示游戏轮数的期望值，精确到小数点后4位。 后排召唤阵： @yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui

其实对于这种算法题来说py跟伪代码没差啦 大二的时候有同学试过，用py代码交题就没有AC的，全是TLE 这不是很正常的事么

那你可以试试Haskell，算个10k阶方阵乘10k维向量能吃掉我9个G内存的奇葩语言

上学期做DIP的时候用过matlab 上手之后感觉用得很舒服，不太反人类

问题在于，肯互动的就那么几位，出难题大家看看就走了，出简单题大家一看被秒杀也走了 感觉吧，算法题目没有数学受众那么广

超 音 速

据说远古版本没有校内跑步的限制，于是有人在高铁上……

我们这里是没有体育课的，不会给你布置体育活动任务。但是有体育课的，就需要用app每周跑步3次，每次2000+，必须在校内跑，校外无效。听说程序改进了，骑车和轮滑都能测出来x

其实昨天的A题门槛就挺低的，其实那个题非常简单，但我发现降低难度的直接结果是题目被秒杀……

与我无关（冷漠 我只是个无情的玩梗机器

嘛，很高兴你们政治见解一样 我觉得还是讨论明天出什么题更有意义一点（笑 要不要来点编译原理？

emmm 我没看懂，但是论坛里讨论zz真的好么……（如果我理解错了那另当别论） 我私底下觉得还是做我们本来想做的比较好

??? 论ZERC不知道我知道sudo需要密码这件事 拜托，apt好歹也是要sudo的好嘛，我还没菜到这种程度的吧233