Mr.K 018

好，第0期发了！ https://sstm.moe/topic/252752-每-日-算-法-挑-战-【第0期，有红包】/ 今天这个问题是个图形学的问题，我一个小时之内想出来的（ 有一说一 我觉得应该有现成算法，但我没有查2333

好的！经过一个晚上的商讨，我们的每日算法挑战要和大家见面了！ 如标题所示本期是第0期，就是每日算法挑战的公测。下面放上简介！ 1 这是什么？ 每日算法挑战本质上不就是拿来热版的花招么 每日算法挑战，顾名思义，就是每天会po一道算法相关的题目，来让大家讨论讨论，做一做。当然了，这个每日算法挑战并不是什么ACM之类的算法题，各位就算交了代码也没有用。因此，大家只要说说算法和思路，最多给出伪代码就可以了。伪代码写得也可以随便一点，但是太过耍赖的“伪代码”也是不行的哦！比如这样的伪代码: 输入本题的所有数据； 解题； 输出结果 这样的伪代码说的就太模糊了，有点耍赖。我们约定除了众所周知的少数算法（如排序）之外，伪代码也要由常数时间内就能做完的动作（或自己定义的过程调用）组成。同样地，对于自定义数据结构也尽可能写的清楚一点为好。 如果觉得伪代码要求太复杂了，其实也不用非得写伪代码，只要能说明白算法的大致实现过程也可以。写得详细的可以拿到和伪代码一样的奖励哦！ 2 有奖励吗！ 有啊，当然有了！我们欢迎所有形式的讨论，尤其会对这样的贴子发放奖励： 首先给出了正确答案（或者相对本题可以接受的答案）的，可以拿到最多的奖励！ 虽然不是首先给出答案，但是有一些新内容的（比如新方法啊，复杂度等等的讨论啊，算法思路的说明啊，以及正确性证明等等）； 参与讨论，有一些新颖的见解或者指出了其他人答案的bug的。 顺带一提，三种奖励可以叠加！ 今天作为公测，我先放出来一道我随便杜撰的题吧! 第0期 我的世界 K想要在MC里搭一个雕塑。他手头有一个STL文件，里面保存了这个雕塑的样子。 题目中为了简化，认为STL文件由若干三角面组成，每个三角面由九个实数组成，前三个、第4-6个和第7-9个实数分别定义了三角面的三个顶点。可以认为每个STL文件中的各个三角面能围成一个封闭的几何体。 我们规定，对于每个MC中的方块区域，只要三角面穿过了这个区域，就要在那里搭上方块，并且这个雕塑是实心的，即几何体的内部也要填上方块。 K在搭建雕塑之前，首先要知道他要准备多少个方块，来计划挖矿（指给苦力ABCDE等人安排挖矿任务）。现在他想问问你，修雕塑要多少方块呢？ 输入 第一行是一个整数n，表示这个STL文件中的三角面个数。 接下来有n行，每行有9个实数，分别表示三角面中的三个顶点，顺序是X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3。 输出 输出一行，其中有一个整数，表示雕塑需要多少方块。 嗯……这个题是我杜撰的，因此没有预设的正确答案，大家可以畅所欲言。

@萨卡 诶，你也是萨卡

emmm说起来有点不好意思，这两天现实中比较肝，那个坑好几天没怎么动了

好的，我看看今天下午弄一下

@萨卡 萨卡中之人K桑可能性微存？

关于这个问题，我有很明确的答复：这个活动是面向所有人的，以算法交流为主，重点在于如何解决问题，而不是编制没有bug的程序，所以我希望合格的标准能尽可能放开一些。 只不过伪代码肯定不能瞎写对不对（ 关于您提出的这一条规则，实际上是在数据定义方面做的一点注解。实际上可能不会明确地写给大家看。这条规则实际上是说，遇到数据定义中有歧义的地方，按照C语言中struct的处理方法处理。大家读代码的时候如果能看懂是怎么回事或者有注明，就用不上这条规则了。

确实，汇编是真的可怕

我有个临时的想法，还不太成熟。 首先我们不希望参加者提交代码，只需要伪代码即可。这个是大的方面。 考虑到伪代码和文字描述的模糊性，有必要提出几点这里使用的伪代码/文字描述规范，不满足规范的视为思路说明，而非伪代码。我目前想到了如下几点： 文字描述必须包含输入、处理和输出过程，不能假定数据在开始时就已经输入完毕，存储在内存中； 算法的每一步，要么是常数时间内可以完成的动作，要么是众所周知的方法（如排序、最短路等），要么是调用在同一段伪代码中定义的其他方法。循环和方法定义的执行体不视为一步，而是当作多步处理，但其中的每一步仍需满足本条的规范。 要对使用的数据结构有明确的定义。数据结构中要引用其他数据结构的，可以使用指针（如Node* next = nullptr），若做了相应说明，也可以使用引用（如Node next = Null）。但是若没有做说明，则默认内层数据结构是外层数据结构的一个字段，访存时可直接通过外层数据结构的地址和偏移量来访问内层数据结构的成员。默认整数是32位的，实数是64位的，指针是32位的，除特殊说明外字符是单字节的ASCII字符。 尽量少bug。我们不是OJ，不要求伪代码完全正确，但也不是对正确性毫无要求。我们能发现或者被其他人指出来有明显/严重的bug的算法，会酌情扣除少量奖励。奖励发放后被指出错误的，不会追回奖励。 奖励方面，我自己拿不出太多节操，同时我想这个虽然有比赛的成分，但是主要目的还是激发活跃性。因此奖励可能不会太多，就是意思意思。所以可不可以这样： 首先给出可接受答案的，受上赏； 并非首先给出可接受答案，但是给出了新的内容，如算法细节、另一种方法（这个应该不太常见）、更详细的说明、证明等等，受中赏； 参与讨论，给出了有价值的想法以及提出解答中的bug的，受下赏。 非规范的伪代码（即“思路说明”）按详细程度酌情给奖励，最高可以给到相当于一段伪代码的奖励。同时考虑若干加分项： 对算法及其思路进行了较详细解释说明的，如动态规划问题解释清楚动归的目标和状态转移函数； 计算了算法的时空复杂度的。整数和实数的四则运算可以认为能在常数时间内完成，高精度数除外； 对于一些特殊算法（如贪心和剪枝等），证明了正确性的。 @ZERC @inuisanaa @随性而为 @NianRuoshui @魍魉QAQ @提辖 讨论一下，六位的看法是？

其实也没打算是编程，只是算法

要不然让参与者给伪代码？ 给出算法的伪代码表示总比编出能跑的程序简单点

采用参与者提交程序代码的方法的话也不是不行，这种方案就是我初始化一个虚拟机来跑提交的代码，然后构造出一些数据来测的样子。 虚拟机我有，要写一个东西来自动化输入输出并且测量程序用时，而且我也没想好怎么测内存使用 老实说我不喜欢这个方案因为这样有点本末倒置（大家又不是人均ACM，其实我也不打ACM的），大家负担也重咱们负担也重。我要是看到一个让我编程的挑战肯定直接跑路，不会像数学挑战那样坐下来做题的，因为编程时间挺不可控的

说正经的 题目有了，形式呢？ 总不能我把底下所有人写的程序一个一个跑一遍我们学校OJ吧，何况有的题早就关了，就剩下题面

好的，我数了数光前些年校赛和新生赛题目就有三四十道，每天一道就是一个月，一个月的时间三次元板块复兴有望啊（

我刚刚搞到了我们学校以前的校赛和新生赛题目 网址是我们学校的moodle平台，所以就不贴了 我或许能找到校友（不是

SSTM virtual judge 我看行

对呀，所以说上课学会了py的语法距离真正的会py我觉得有点距离

py：都 给 👴 爬

这个确实 一般大学C语言是必修，py是选修而且教的非常浅，光会py本身没有用过库那不就是不会py么（ 计算机或软件相关的系除外，这种人主流不太奇怪的语言上手都比较快

啊 不会是要论坛搭OJ或者自己运行程序吧？ 而且要测的话，很多时候拿得到题拿不到数据，除非我们把代码拷出来送到相应OJ平台去测——但那样的话答题人就不能先把程序跑通了再提交么 所以我觉得具体的细节还得考虑一下

要不然找找各个大学计院的算法新生赛？那些题一般都不难

别吧，那阁下说的是哪个迪杰斯特拉…… 我还以为是最短路那个迪杰斯特拉

这个题可以证明是个NP完全，所以Dijkstra这种多项式时间的算法肯定是不行的。 证明的大概思路：这个问题可以规约到若干种不同的NP完全问题。例如，当船的出港时间为0，也没有货物要起吊（就是说只需要入港即可）的情况下，这个问题就退化成多机调度问题。众所周知，多机调度问题是个NP完全问题，因此本题也是一个NP完全问题。假设能找到本题的多项式时间算法，相当于证明了P=NP

缓冲区是无限大的，送到那里去就好

@ZERC大佬弄了个每日数学挑战， @Xchara大佬也做了个逻辑分析https://sstm.moe/topic/252606-数学做累了？那就来试试这个简单的逻辑分析题吧/ 诶，莫非我也能用这种方式水节操？ 我也来蹭蹭热度！ 这道题是从一个老旧PPT上扒来的问题，名字叫“港口调度问题”（名字估计也是瞎起的，反正我百度这个名字百度不出啥来）。这道题题目如下： 港口调度问题 已知若干货轮(C1~Cn)要在港口停泊卸货。港口具有： 2个相同的泊位M1、M2 2个相同的起吊设备T1、T2 2辆相同的运输车V1、V2 3个仓库S1~S3 起吊设备不与泊位绑定。起吊设备在一个泊位起吊完成后，移动到另一泊位（若需要）的时间忽略不计。运输车空闲时停留在港口缓冲区等待被吊车运送至此的货物。运送到目的仓库后，运输车立刻返回缓冲区等待下次运输。 船上的货物首先要随船入港，之后被起吊设备运送到港口缓冲区，随后被运输车运送到指定仓库。每个货物起吊时间不一定相同，货轮出入泊位时间也不一定相同。4艘货轮均在0时刻抵达，现要规划入泊、吊送货物方案，通过设置合理的轮船出入泊位、吊车吊运货物和运输车运输顺序，使总的调度用时尽可能短。 “总的调度用时”的定义：从0时刻各货轮抵达起至最后一个货物进入仓库、货船全部离港且运输车全部返回缓冲区为止所花费的时间。 作为数据，货轮、货物和仓库的相关信息列如下。 表1：货轮信息表 货轮序号 入港用时 离港用时 C1 26 20 C2 15 10 C3 30 24 C4 40 26 C5 50 25 表2：货物信息表 编号 所属货轮 目的仓库 起吊用时 P11 C1 S1 15 P12 C1 S1 26 P13 C1 S2 37 P14 C1 S3 9 P15 C1 S2 32 P21 C2 S3 8 P22 C2 S2 9 P23 C2 S3 27 P24 C2 S1 11 P25 C2 S2 4 P26 C2 S3 5 P31 C3 S3 8 P32 C3 S1 51 P33 C3 S2 27 P34 C3 S1 13 P35 C3 S3 29 P41 C4 S1 10 P42 C4 S2 22 P43 C4 S1 25 P51 C5 S1 17 P52 C5 S3 26 P53 C5 S3 7 P54 C5 S2 30 P55 C5 S2 43 表3 仓库信息表 编号 往返时间 C1 16 C2 20 C3 24 构造出各位认为总用时足够短的调度方案，说明轮船、货物起吊、运输车的调度顺序并推算出方案的调度时间，相应定义见题干。 由于数据是我瞎编的，我也不知道准确的最短用时是多少（被打死）。因此，从现在到明天（即4月7日）21点为止为有效时间，将会选出得出调度时间最短的解的作者，给予我自掏腰包的100节操奖励！（多人给出的解均为最优的，奖励只颁给第一个给出已知最优解的作者；同一个人的多个解以最优的为准；奖励颁发之后给出的解很遗憾是无效的） p.s. 这道题是个NP-完全问题，大家可以说说为什么？（不要求严谨的证明，思路也可；证明无奖励）