Mr.K 018

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

这个题可以证明是个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-完全问题，大家可以说说为什么？（不要求严谨的证明，思路也可；证明无奖励）

编程题……同盟没有OJ啊……

不清楚，不了解，没兴趣.jpg

有一说一 不怕别人嫌我进度慢 我数学还没复习到级数呢 所以一概作不会处理

……emmm算了 告辞（

第三题……无穷级数求和不会，告辞 这个题不用级数的话，没准能泰勒公式展右边，去凑左边？

我当初做的那道跟网上找来的条件不同，当时大家做出来的解确实不一样 这件事就启发我，可以适当修改条件来求所有可能解，或者对条件进行编码作为程序输入，求一段能给出所有可能解的程序 我觉得这个要是做成程序的话，数据量应该不会超过10^5

好，我好了，用不到拉格朗日乘数法 32(A+B)-(A^2-2AB-B^2)=64+256实际上是 32(A+B)-(A-B)^2=64+256 设A+B=C, A-B=D，则最小化目标即C，同时上式变为 32C-D^2=64+256。显然令C取最小需要D=0，即A=B。此时，C=2+8=10，原式=1 取到最小值时，由C=10, D=0得A=B=5，a和b的正负号可任意选取。

第二题找到个线索：求原式的最小值，实际上是求a^2+b^2的最小值，并且原式成立需要a^2+b^2≥8 这个可能有用，先放在这里 更新：对约束进行整理，得 32(A+B)-(A^2-2AB-B^2)=64+256 其中A,B分别是a,b的平方，于是可以用拉格朗日乘数法解本题。 我算一下

这类题我以前见过，记得解决方法。 顺带一提，推荐一个爱因斯坦的五色房子问题。这个是原文： 这个题我最开始做的时候好像条件和原题不一样，所以有多解。因此可以考虑修改若干条件，求所有可能符合条件的解，或者干脆求合法解的数目

先做第一个吧。思想就是7个数要尽可能平均，否则就是从尽可能平均的状态中把较小的数匀一些给了较大的，就违背题意了。 考虑最平均的状态。由于要求数字不相同，设最小的那个数为n，有n+(n+1)+...+(n+6)=159, i.e. 7n+21=159，解得n约为19.7。换言之n=19时和小于159，n=20时和大于159.于是取n=20,逐个从n开始-1，直到七个数和为159为止。 n=20时，n+(n+1)+...+(n+6)=161.只需使原本为n和n+1的两个数各自减去1即凑出159. 最终解得七个数分别为19 20 22 23 24 25 26

正要考研，觉得自己有点凉……

你好，我只是知道ACM，并不打ACM

我是计科的，数学题想不出来 但是感觉可以从ACM里找点算法题当压轴题，或者给出一些能AC的算法求证正确性啥的？（啥也不懂，随口一说

来吧，尽管来 反正我来一道空一道就完事了

有一说一 勉强看懂了 光是这个凑微分我就想不到，幂级数展开就更别提了 还需修炼啊

我天 这凑微分 这泰勒公式等一下，这是怎么展的？我怎么没看懂 秀的我头皮发麻 大家都是带学生怎么差距就这么大呢

It's OK. Those regulations are not meant to be an obstacle for non-Chinese native speakers. If I have to say, although users of this site are mostly Chinese speakers, it is not Chinese-only. So feel free to communicate in Chinese or English. BTW Google does a bad job translating between English and Chinese. It's called "Joke maker" among some of us, so perhaps you may consider Youdao or Baidu instead of Google. Their websites are written in Chinese, but should be able to use in the same way as Google.

恭喜毕业！ Kris，永远的神（确实是这样

emmm这个地址是没问题的，但有的电脑立hosts文件不止一个（分散在不同的位置里），其中只有一个起作用。想知道自己文件改没改对，可以打开cmd或者PowerShell，输入 nslookup sstm.moe 然后看输出的地址里有没有205.185.127.78，如果没有的话说明你文件可能改错了，建议搜出C盘里所有叫hosts的文件，都加上那行（ 如果输出地址里有的话，那可能就的确是没法直连论坛，就只能用梯子了

毫无疑问教室上课。 教室上课＞直播网课，因为更有学习氛围，不容易开小差，还能实时地与老师交流。 直播网课＞课程录像，因为看录像学习时间和学习时长都没有保证，也不知道哪里会是重点。 遗憾的是，我们大学都是课程录像的……

而且你可能发现了，用户组的转换也是人工的……