Mr.K 018

应 @摸鱼奇才咖啡喵 的邀请，我回来接着班门弄斧辣！ 什么叫每期算法挑战呢？就是说，算法挑战每更一期，算法挑战就更一期 第一期，先来一个简单题吧。 #1 题目来自哥们的×家凤1800 描述 MrK 019是一名大一新生。这一天他随机翻开刚买的×家凤1800，映入眼帘的就是这道题： 019心说这还不简单，直接暴力枚举出了结果2/3。但万万没想到，此时018从旁边走过，大笔一挥把题干中的3改成了500…… 输入 第一行一个整数m（1≤m≤1000），表示样例个数； 接下来m行，每一行都是对应样例中书的数量n（1≤n≤500）。 输出 输出m行，每行一个小数，表示对应样例所求概率，保留8位有效数字。 样例输入 2 3 4 样例输出 0.66666667 0.62500000 样例输出的解释： 2个样例，对于样例1，三本书可能的排法有6种，其中合题意的排法有123、132、213、321四种，因此概率为2/3； 对于样例2，四本书可能的排法有24种，其中合题意的有1234、1243、1324、1342、1423、1432、2134、2314、2431、3124、3214、3241、4132、4213、4231共15种，因此概率为15/24，即5/8。

公网IP！ 能请教一下怎么要来公网IP么（（（

对矩阵的可能形状做了一些观察，又参考了yhz的回复，以下是目前为止观察得出的结果。如果一个仅由0和1为元素的n阶方阵合题意，那么它必须： 1）是沿副对角线对称的，前面不少人都发现了； 2）左上三角形要么只有一个连通分量，要么只有两个连通分量。若有两个： 2.1）这两个连通分量必须各自占据一些处在边线（左或上）和反对角线上的元素，否则整个矩阵就会出现多于2个的连通分量。进而得知， 2.2）右上方元素和左下方元素分属不同的连通分量； 2.3）参考yhz的回复，边线上0和1只能翻转一次； 2.4）反对角线上0和1也只能翻转一次。如果翻转了多于1次（例如3次。参考2.2，不可能翻转偶数次），就会破坏原有两个连通分量的连通性，形如 0 1 1 1 1 1 0 1 1 0 1 0 1 1 0 0 1 1 0 0 0 上述几个要求只是必要条件，并非充分条件，例如，将上例（4，3）处的1换为0可以使得矩阵满足上述五个条件，但仍不合题意。 从另一种角度考虑，合题意的矩阵，一定存在某种分割线分割开其左上三角，一段位于反对角线、另一端位于上或左边线，且其一侧均为0，另一侧均为1。 但诡谲的是，这个分割线如果从对角线出发的话，是可以向下甚至向右行进的

反正作者的目的就是“啊总之这个人死了”，死因是什么不重要，那泥头车安排上就行了！而且泥头车确实可以拿来杀人，没毛病 除了泥头车之外，比较随机的死法应该也是有的吧，比如办公室里猝死啥的？但是感觉还是泥头车经典啊

如楼上所言，网上确实有好多教程，pygame也有官网，里面应该也有一些参考资料。 如果你不愿意慢慢读教程里的代码的话，你也可以 help(pygame.image) help(pygame.Surface) help(pygame.font)

……所以说大佬是谁，视频关键词是什么

这个没有仔细了解过，貌似有些小说是作者值班的时候写出来的，所以如果值班的时候来的病人多，那一章内容就少

确实有，也不一定非要不得志……（指国内） 当然，这种情况下人家大多是写着玩，半途鸽了的比比皆是x

喝咖啡，我习惯用那种袋装的咖啡粉（就是提前磨好的咖啡豆）。不用磨豆，袋子架在杯子上以后浇开水即可。看咖啡足够浓了之后扔掉袋，加点糖就行。适合冬天喝。夏天的话还是去咖啡店弄点冰咖啡更好一点…… 好多人（包括我）其实并不追求咖啡的味道。香当然更好，但是在我眼中咖啡的本质是一种介乎饮料喝药品之间的东西，跟红牛差不多（

？！！！我直到看到成品图都以为用的枣子是红枣，还寻思怎么给红枣剥皮呢……

这么说，windows的符号链接时不能连接到目录上吗？

其实之所以我当初设定阻力和速度成正比好像是因为原版ksp里阻力是跟速度成正比的……

我这里对“突然都贴右行驶”进行以下解释：某时刻所有的车都急刹车，并按其原本前进方向的反方向以原速率行驶，仅与地球相互作用，作用时间可以忽略不计。 南北方向不变，因为任取一条街道，两个方向上车流密度的期望相同，而在南北两个方向上变向产生的角动量刚好抵消，没有影响。 在东西方向上不同。由于街道有宽度，地球是个球体，因此街道靠南一侧的车的角动量的大小，比质量、速度均相同但沿街北侧行驶的车略大。当突然改变行驶方向时，角动量的变化量也比沿街北侧行驶的车大。南侧车原本向西行驶，现在向东行驶，角动量变化量沿地轴指向北极，因此总的角动量变化量沿地轴指向北极。 根据角动量守恒，地球的角动量变化量沿地轴指向南极，即获得了自东向西的角速度，自转略减慢。 一本正经的胡说八道

原来Windows也有符号链接啊！我以前一直以为符号链接是Linux特有的东西来着。 好像比Linux的符号链接功能还强大一点，我记得Linux的符号链接只能链接目录来的 好像是Windows 10新增的特性？这么看来Linux是越走越远了啊（悲）

按摩啊。 一直想去来着，连地方都查了查，但总是因为时间问题+怂没能成行……

输入数据只包含一行，这是因为多行可以轻易地当成一行处理。 这个实际上是对应OPT调度算法。操作系统里之所以用LRU之类的算法是因为难以确定之后使用“方块”（可以理解为cache行，内存页甚至磁盘块啥的都行）的情况，只能用既往的情况去推将来。但本题里用方块的情况是完整地告诉程序的，这个规模的输入数据全存下来也不会MLE，所以用OPT即可。 姑且做得仿真一点，我们认为搭方块还是要按顺序的，因为实际操作中不按顺序搭方块真的会增大记忆开销的（因为会涉及到寻址的问题），而且允许不按顺序搭方块的话这题不就退化成数输入中有多少个不同的数了吗kora

没人来看啊……感觉这个题应该没那么难了吧？

其实原则上不是，这里是为了出题做的简化 而且实际上不按顺序搭会带来其他问题……我这个K后来觉得还是一个个搭好一点

我在想，修改题目中的条件，改成不必只有最后才能回家，而是随时可以回家放东西，出来后身上的重量值回到1，这个题是变得简单了还是更复杂了

附加题是我真的想在生活中这么优化一下，所以并没有考虑复杂度（ 那这么看，恐怕只能分支限界一下

第24期终于来了…… 快到期末了，下一期啥时候能出还是个未知数…… 嘛，好歹这一期出来了不是么？ 今天这道题其实是个操作系统题，题本身不太难。 第24期 我的世界2 K上一次在MC里搭了个奇观（雕塑）之后，这次又想再搭一个奇观。这次他要搭一个像素画。他这个人其实没什么美术细胞，所以搭像素画的方式跟别人不太一样：首先写了个程序，用一些（可以再水出一期算法挑战的）技术手段导出了一张表格，告诉他每一格该搭什么方块。之后，把要搭的图像输入进去，拿到表格，对着表格搭像素画。 K按照表格搭像素画的时候，发现他的快捷栏不够大，只能容纳9个方块，因此下一个要搭的方块常常没有出现在快捷栏里面。这时只能去方块表里找，找到对应的方块之后再放在快捷栏里的某个位置（那个位置里如果原先有方块，就被换掉了）。众所周知从方块表里找一个特定方块是非常麻烦的，因此K打算尽可能减少从方块表里找方块的数量。 现在告诉你像素画某一行的各个方块分别是什么，快捷栏初始时是空的。试问K最少需要从方块表里找多少次方块？ 输入 第一行两个整数m n，m表示有多少种方块，n表示要处理的方块数量，即像素画这一行的长度。满足0<m<1000, 0<n<100 000。 （不要问为什么要摆那么多方块，问就是盖奇观） 接下来n行，每行一个整数a_n，表示这个位置的方块种类，满足0<=a_n<m。 输出 一个整数，表示找方块的最少次数。 以上。另外还有一道附加题，和上次一样，不保证存在多项式时间的解这个题根本就是不存在了吧（。 要从家里出去去若干个地方买东西。不妨认为家在(0,0)处，其余的商店都在平面上的某个位置。由于街巷和建筑物的限制，在两个点之间移动只能横平竖直地移动。出发时携带了质量为1单位的物品，每个商店都有一个质量值，表示到那个商店后身上另外携带的质量。从家里出发，要访问所有的商店后再回家。定义每段路的体力花费为路程和携带质量的乘积。 试求一个访问商店的序列，按这个顺序访问商店，总的体力花费最小。 --------------1705更新-------------- 经 @yhz012 的提醒，基本确定这个附加题是个NP完全问题

是的 空气阻力的话这次先这样吧2333

大家好我不是ZERC，但是我看最近每日挑战系列大家好像都没怎么更（对说的就是你，K018），所以我来越俎代庖，发一份数学挑战。（不，不是因为懒得动脑子） 众所周知我不是搞数学的，所以我是出不来那么难的题目的。本题的难度大概在真正的每日数学挑战的题目1和题目2之间。下面是题目： 有一门大炮，可以将炮弹以大小恒定的初速度v发射出去，v与地面的夹角θ可以调节。炮弹质量为m，受阻力与速度成正比，比值为k。本题中的地面是水平面，没有起伏。不妨认为大炮位于坐标原点，指向第一象限开炮，并令y轴正方向为上方。 1）炮弹的运动轨迹是什么？ 2）炮弹落点（轨迹与x轴交点）的横坐标？ 3）求一角度θ∈(0,π/2)，使得落点距离大炮的距离最远。

只能说…… 这个“凭什么”用的就很好，猜猜看这次疫情过后这个卡卡是会赖自己不争气还是会赖别人鼓捣出疫情来把他家毁掉？ 正常人都会选择后者吧，我看这位就算他们家是正常经营不善倒掉的，估计也赖不到自己头上 没有人是阿Q，又或者人人都是阿Q

的确，因为这个限制并不是我加的，而是客观要求，今天这个附加话题是某个更大话题的一部分