2019 多校(MUTC) Diary Round 5

大家好，我是（并不擅长写blog的）syr

这是一场两人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
观察到一次函数可合并的性质，我们令A = -Σ1<=j<=i aj + Σi