2019 多校(MUTC) Diary Round 5

大家好,我是(并不擅长写blog的)syr
from MUTC Dairy 4
这是一场两人round。MK同学因为要上数学课而不能参加Round 5 & 6的大部分。因此比赛就由我和XGN来完成了!

Look Down through 1001 ~ 1004

1001: 好短啊,看起来挺可做的,不会。
1002: 看起来和JSOI R1D1T1好像啊,肯定要搞个trie吧,不会。
1003: 计算几何,不会。
MK把1003给在他旁边的ryz看了,ryz说是计算几何和三分。

XGN对MK: 快把你电脑给ryz!
ryz:我不帮你们,除非你们打不过lxr
XGN:lxr? 当然打不过

1004: 看了一眼没啥印象,跳了
这时候有人过了1006

Problem 1006's first look

这不是个Z的裸题吗?
和XGN交换想法之后,确定了做法。因为我有Z的板子,所以就交给我做了。
12: 28: 41 Problem 1006 Passed

Problem 1005's first solution

此时MK和XGN开始讨论1005

Problem 1005's solution #1
dp(i, S)表示当前最后一个数放的是i,还有S集合内的没放的方法数,先算dp,之后进行递归找字典序第k大的

XGN开始迅速coding,然而发现并不好写

XGN: i am very confused at the details in 1005

正在看1007的syr此时提出可以替代XGN来写,于是达成一致之后syr和XGN互换了题目。

Problem 1007

在之前的思考中syr提出了一些(毫无营养与毫无依据的)observation,它们对解题毫无帮助。
于是XGN不得不从头想起。
13: 28

XGN: i think i 找到规律了

Problem 1007's sol
step1: 打表
step2: 找规律
step3: 特殊值OEIS
step4: AC
Narayana's cows sequence

13: 42: 58 Problem 1007 Passed

Problem 1005's second solution

写着写着syr同样get very confused at some details in 1005,因为
1. 并不能根据字典序来确定每个序列的第一个数
2. 所谓的状压dp根本不用算,因为它等于__builtin_popcount(msk)!
这就产生了

Problem 1005's solution #2'
枚举第一个数,找到每个数的前k个permutation,放一块儿排序
复杂度: O(k * n * n * logn(k * n * n)) ≈ 2e7log

于是就愉快地TLE了。
这时候发现这道题的做法越来越暴力了,我就往暴力的方面多想了想。

Problem 1005's solution #2
对于n <= 8的情况, 由于n! <= 40320,可以处理所有permutation然后排序
对于n > 8的情况, 由于前两个数可以确定之后也能保证剩下来的数的排列个数超过k,那么就将前两个数确定为n和1,这样保证了结果序列字典序最小,再在剩下的里面选第k大的。

15: 09: 29 Problem 1005 Passed
但是后来我发现这个做法其实是假的。为什么呢?因为上述做法中n>8的情况“剩下来的书排列个数超过k”是显然错误的 (7! < 10000)。hack数据也很简单:

1
9 10000

dreamoon的数据好水

正确的做法是对于n>=10的情况用上述做法中的n>8的情况做,而对于n=9的情况我们可以用一个priority_queue维护排列,一开始插入每个数开头的最小的,然后弹出k个最小的,每弹出一个就把它的next_permutation插入。当然这是后话了。

Problem 1004

当我正在code 1005的时候,XGN指出1004是“零点分段法”。
我:“零点分段法是什么神奇的算法???为什么我从来没听说过???XGN是怎么会的???”
没有多想,我接着写1005。1005 AC之后,XGN那时也没什么想法了。我想,我也帮不了他吧。
于是我就开始颓了去上了个厕所。路上我猛然想到,"零点分段法"不是一种算法,而就是东方上课讲过的一种做数学题的方法。。。鬼知道我一开始在瞎想些什么。。。
然后就醍醐灌顶了,于是我给XGN口胡了一个做法:

Problem 1004's solution
考虑将零点排序,得到x1, x2, ..., xn。对于一个区间[xi, xi + 1), 若有一个解x'在此区间中,那么带入原方程得Σj |aj*x'+bj| = C => Σ1<=j<=i -(aj*x+bj) + Σi<j<=n (aj*x'+bj) = C
观察到一次函数可合并的性质,我们令A = -Σ1<=j<=i aj + Σi<j<=n aj, B = -Σ1<=j<=i bj + Σi<j<=n bj,原方程化为Ax+B = C,就可以愉快地解辣

XGN code完wa了一次,经过一番细致的检查发现是分数类写得不对,即分子分母同为负时没有消负号。
改完就PE了又改完又CE了然后又PE了然后就
16: 17: 20 Problem 1004 Passed

总结

这次很遗憾,没有达成题数单调递增的目标(1002对于我们来说并不是完全不可做)。但是在两个人的情况下也达到了大众题数,挺好的了。
MK回来之后祝贺了我们,还连着道歉。在连着上数学课的情况下,他还抽出时间来帮我们看比赛,其实能做到这样,缺席一两次又有什么关系呢?
下次加油吧!