2019 多校(MUTC) Diary Round 7

大家好，我是(并没有任何前置定语的)syr。因为没有人愿意写blog，所以就我写了。。。
（多图警告）

Problem 1006's First look

在比赛开始之后思维敏捷的MK迅速开始讨论1006但是很快他发现自己并不能理解题意
事实上，不能理解题意的不只我们三个人

然后看到一堆人交这个破题就是没人过，就先扔了。。。

Problem 1001 A + B = C

Hi everyone! Welcome to the Stage 7 of this series of training contests.

为hyh量身定做的题目
1001是全场第一道有人过的题目(orz djq!!)，所以在看到一整场的不可做题之后我们回过头去看1001
观(废)察(话)：x, y, z中的一个由另外两个可以确定
MK：固定C，把A或B变成小数
SYR：A和B里面最长的最多比C少一位吧
MK：然后拿C来减，减完和B对
GWQ：can use java, java has bigint
Problem 1001's solution
固定C，分别对A和B枚举两种可能的长度，不妨设枚举的是A，用C减它得到B*10^y，和B比对，如果可以就可以，不行就不行（这什么废话。。。）
然后用Java写


这样就获得了TLE的好成绩
然后果断改C++，SE了好几(十)发，最终发现了如下的错误：有可能B原先是一个有trailing zeroes的数，比对的时候要考虑把它的trailing zeroes去掉一部分的情况
13：57：43 Problem 1001 Accepted

Problem 1011 Kejin Player

为jt量身定做的题目
MK又一次提出了关键的做法：倍增
Problem 1011's solution
按照(i + (1 << j), -j)的顺序排序，然后计算
dist[i][j] = dist[i][j - 1] + dist[i + 1 << (j - 1)][j - 1]
dist[i][i + 1] = a[i] * (1 - p[i]) / p[i] * dist[x[i]][i]
复杂度: O(n log^2 n)
(两句话题解)
WA了一发因为没开long long，然后
13：55：40 Problem 1011 Accepted

Problem 1006 Final Exam

一开始MK写了一个根号枚举的做法，然后TLE了，我也不知道他怎么写的，没听懂他的做法所以这一段就跳过了反正就是猜想最优解一定是因子，所以就枚举因子，这样的吧
之后syr发现AC submissions全都是15/31/46ms，觉得应该是直接输出答案，所以尝试了cout << n * m + k << endl和cout << k * m + n << endl
能过就见鬼了。。。
Problem 1006's solution
设每门科目复习的时间为(a_i) - 1, 那么当a_i确定之后出题人需要选出n - k + 1个a_i出来:a_p1, ..., a_p(n-k+1)，同时把m搞成一个n - k + 1份的划分: b_1, ..., b_(n-k+1)，使得对于每个i，有a_pi <= b_i
那么显然出题人会选最小的n-k+1个a_i。将a排序，则变成了存在一种方案把m分成b_1, ..., b_(n-k+1)的方法使得b_i >= a_i
最优的分法是b_i = a_i，所以这个条件等价于sigma(a_i) = m
而总的cost就是所有a_i的和。我们希望这个尽量小，而前n - k + 1个a_i的和已经确定了，就是希望后面的a_i尽可能小，而这个序列是排序过的，所以后面的每一个a_i最小就是a_(n - k + 1)了
所以转化为a_(n - k + 1)尽可能小，而它的最小值就是ceil(m / (n - k + 1))
所以直接输出就好辣！
然后syr就写了这个题
15：31：25 Problem 1006 Accepted

Problem 1010 Just Repeat

这个题我们没有过，就不写具体的做法了。这个题也是MK做的，就是贪心地选择出现次数尽可能多的牌。
但是开这个题的时候时间已经比较迟了，MK写了一个sort的，先WA了一会儿，然后T了，没有过
他改了基数排序，然后来不及了，就没有过。。。

总结

这一场海星吧，至少和别的一些队伍比起来是不占下风的。
但是很遗憾的是我们彻底打破了题数单调不降的纪录
除非下一场能做5个或者6个
谢谢MK， 谢谢GWQ！