Muriya Tensei

有笨蛋又错过了

才看到题，第一反应是想到一个简单的思路 基础思路是通过哈希把三个值编码到三个不同的维度，那么每次询问相当于同时校验三个值 但是存在一个可能的问题就是因为不知道值域，因此无法确定出无冲突的哈希，那么可以先通过询问确定值域 如先询问两次a+b+c（由题意三者均非负） 那么单独的a+b+c必然不会超过这个范围 接下来，把之前得到的a+b+c较大者+1作为进制p（当然取更大的素数p 或者直接取位数h 进制取 10^h也是一样的道理） 再次询问 a+b*p+c*p^2 三次（如果前两次不同的话甚至询问两次就够了） 再根据p解码出abc后，取重复出现的即可 --- 去看了眼原题，果然是ICPC啊（） 题目限定了系数只能取 [0, 10] 那就肯定没法编码到三维了，那还是线代吧 应该是只要满足任选三个向量均线性无关即可 这样任意三个都能解出一组解，并且错误的解的组数小于正确的组数

好久没来看看（所以第一题怎么构造，我第一反应就是 a_i = 1 << (2 * i)）

我超，知乎还真有这个问题的解，甚至两问都提到了，撞得彻底（没事，就当给正确答案站台了）

看似如此，但并没有这么简单 （比如这两问，其实就是有区别的，只考虑一个方面显然并不全面）

小羊遇到了一场试炼，与他一同参与的还有n个人。 试炼的内容如下： 1. 所有人（未被淘汰的人）站成一排，并从1开始按顺序编号 2. 随机等概率挑选一个编号为奇数的人淘汰 3. 所有人保持相对顺序不变，重复1,2直至只剩一人，这一人胜出 Q1：那么小羊站在几号位置，胜出的概率最大呢 如果试炼的内容改为： 1. 所有人（未被淘汰的人）站成一排，并从1开始按顺序编号 2. 随机等概率挑选一个编号为奇数的人淘汰，并给其余未被淘汰的人积1分 3. 所有人保持相对顺序不变，重复1,2直至只剩一人，一轮比赛完成，记录每个人的得分 4. 重复试炼m场（m足够大），积分高的人获胜 Q2：那么小羊站在几号位置，胜出的概率最大呢 例子： 如果共3人，编号后如下 1,2,3 进行一轮淘汰后（假设淘汰了1）变为 2,3 保持顺序不变重新编号 1,2 再进行第二轮淘汰（淘汰了1） 2 只剩一人，第一场试炼结束，此时最后剩下的是（初始的）3号选手，留至最后并积了两分

题目：https://sstm.moe/topic/323849-奇怪的算法挑战【第③期】池塘的鸭子/?do=findComment&comment=16223775 答案1：https://sstm.moe/topic/323849-奇怪的算法挑战【第③期】池塘的鸭子/?do=findComment&comment=16227568 答案2：https://sstm.moe/topic/323849-奇怪的算法挑战【第③期】池塘的鸭子/?do=findComment&comment=16235039

惊了，李永乐老师居然讲过这个题了。应该是10/18在ACM群里看到了转发的NGA帖子提到这个（4只鸭子的）题。然后简单延拓一下得到这个问题

坏了，原来李永乐老师讲过这个题了 这个题当初我也证明了好久。 我采用的个办法是，对于每个鸭子的分布可以看其关于圆心对称（或者说是旋转180°）的位置 那么本身n只鸭子就有了2n组点。简单分析一下就能知道，只有相邻的n组点可以被同一个半圆（180°）包括，而这组点的选取方法共有2n种。 概率就是 2n/2^n 即n/2^(n-1) 因此不光是半圆（180°）的情况，也可以这样映射（只是非整数的情况不确定对不对，感觉应该也是对的）就可以得到 n/m^(n-1) 这个式子

仔细看了下你的表达式。试图想出你是怎么化简的（无果）。但是结果吧，令n=n-1就对了好像（偏移了一个） 想了想这个假设。原题设是一个环的话，展成线应该会偏小吧，概率上会差多少呢（难道是(n+1)/2n）大胆猜测小心求证（

好久没来水贴了，最近看到了一个有意思的题目，甚至难倒了好几个大佬，来分享一下 （根本就不是算法题嘛，简单的概率题） 有一圆形池塘，在池塘中被遗留了n只小鸭子，小鸭子们等概率均匀分布在池塘中。 那么请问这n只鸭子们全部位于同一个半圆的概率是多少呢？ tip: 不妨想一想两只鸭子的情况 easy: n=2 mid: n=3, n=4 hard: n∈N+ ex: 除了半圆，即1/2圆的情况外，有没有办法考虑1/m圆的情况呢（m为正整数） ex2: 有没有办法考虑1/m圆的情况呢（m为大于一的正实数）（m可能会∈(1,2)）

好难啊，不会 能想到的思路1是二分答案+dfs的check，但是好像答案因为有差值1的约束，并不具有单调性 思路2是试图转化为二分图，想不懂，大概是只能处理min(c,n)== 2的情况 最后就是枚举size+dfs回溯了。总感觉问题是npc的，但又不会证明或者规约 （我说实话，就算数据量很小，指数级dfs回溯都不一定会写，好讨厌带约束的最值 这题我如果遇到，我就直接模拟退火了，生死由命成败在天

（看了看，BFS裸题吗） 那么就根据题意输入建立邻接表，广搜就可以啦 再优化点可以把反向邻接表建出来，跑双端BFS。 不过麻烦但是并不困难的内容就是根据最短距离来写出路径了（visit哈希表标记下路径转移即可） （虽然说是树的问题，事实上一个人的UID会在多个地方出现吧，并不能简单由下至上推出来，还是变成了有向有环图）

所有数x 求 (x|1)的异或和，剩下的就是单身狗啦（

可以说是相当完善了，用信息熵可以确认m≥⌈log(t/c+1) n⌉，并且用进制表示的方法很简单的也能描述出m=⌈log(t/c+1) n⌉的实现方法

有东西的.jpg，那么可以不盲猜来提供一下具体方法或者思路吗

我本来想说根本没在怕的来着，结果想到这只是外围（摔

现在明白为什么数地块和数岛都是12了（左右黑色连通是与上下白色连通是互斥的） 所以对于任何x层浮岛，每层x+1座的情况下，黑白两种情况是等价等概率的

是这个意思没有错 就是理解成一个限时任务就行，只能在规定时间内完成

算法的话，就是并查集了，把所有岛看做点，桥看做边，遍历所有的桥在并查集中合并其两侧的点，用并查集检查两端的节点是否属于同一个集合就行了

题目：https://sstm.moe/topic/295448-奇怪的算法挑战【第②期？】寻找宝物/ 正确答案：https://sstm.moe/topic/295448-奇怪的算法挑战【第②期？】寻找宝物/?do=findComment&comment=15269425

一座奇怪的地牢中有一件宝物，宝物存在于宝箱之中，而在这个地牢中有着无数外观相同的宝箱，你的手中却只有一把一次性的钥匙可以打开其中一个宝箱。并且一旦进入地牢，就会触发机关，如果宝物没有被拿到，那么地牢将在一定时间后重置，可能没有充足的时间来尝试检查宝箱。 万幸的是，你的巫师朋友告诉你，他能为你制作一种卷轴若干，卷轴可以花费一些时间，来探测宝物，一个卷轴可以同时探测许多的宝箱，并不会耗费更多的时间，当探测到有宝物存在时，卷轴就会碎裂，也许你就能知道宝物所在的位置了。（ps：如果没检测到的话，卷轴还能继续使用，但是每张卷轴每次检测都需要花费一定的时间） 你思维十分敏锐，选择用哪些卷轴来探测哪些宝箱并不会花费时间，并且发现宝箱之后可以瞬间将其打开拿到宝物，这样。朋友为你准备了充足的卷轴，但是告诉你，在一个地牢使用过的卷轴就没办法在其他地方使用了，因此只要你每动用了一个卷轴就给他一颗魔晶石。 已知：地牢经过 t 时间就会重置，而你的卷轴检测需要花费 c 的时间，在你进入地牢之后发现，其中有 n 个宝箱。 那么你最少需要多少魔晶石才能找到宝物呢？ 例如：2个宝箱，1分钟后地牢重置，卷轴检测花费1分钟。 你需要 1 颗魔晶石即可。 解释：你只需要用一个卷轴就能够发现一个宝箱中是否有宝物，那么你瞬间就能知道宝物的位置并拿到，因此你只需要1颗魔晶石。 又如：4个宝箱，10分钟后地牢重置，卷轴检测花费7分钟。 你需要 2 颗魔晶石。

此内容有访问限制，请到内容页面查看。

****** 补一发（被打死

******* 吗 夜应该明朗还是柔和(搞不清呢 夜是紧张的不也是很(我来表演一个东方永夜抄 ———— 有个傻子没打答案