S---【云智计划】---7月11日---模拟测#30 div2【补题】 - 比赛 - 梦熊联盟 (mna.wang)

S---【云智计划】---7月11日---模拟测#30 div1【补题】 - 比赛 - 梦熊联盟 (mna.wang)

预计 \(100+70+0+50+45\)，实际 \(90+50+0+45+25\)。

比赛复盘

A 一眼可做。分析了一下推出了一个三维偏序的形式（实际上是二维偏序，赛时降智了）。感觉不会写。此时注意到值域很小，可以直接枚举 \(4\) 个数用桶统计。这样统计答案和一道 CF div.3 E 有些相似。最后挂的 \(10\) 分是这个枚举的值域范围小了。

B 一开始感觉不难，以为又是简单场。但是样例解释的这个 \(96\times 8754321\) 是怎么来的一直想不清楚（其实很简单，这个例子是将 \(1 \sim 9\) 从高位往低位从大往小依次填的）。先跳了。

C。我能感受到这是我不擅长的题（实际上确实，这是唯一一道没得分的题）。先跳了。

D。又是 \(k \le 5\)！又是分类讨论！有了上次的经验，这种题做起来只是复杂但实际一点不难。先写这道！

因为我的想法和正解 完 全 不 同，所以记录一下：

朴素的想法肯定是尽量往角上填，但良心出题人在样例 1 就告诉我们这样是错误的。

我始终不敢猜太大胆的结论，实际上这题有一个很强的性质是最大的矩形一定放到角上。没猜出来，但是猜+证出了一个极其简单的性质：四条边上都有矩形。

于是分类讨论一下是怎么靠到四条边上的就行。

\(k = 1\) 显然不说了，\(k = 2\) 一定将这两个矩形靠到了两个对角上。左上-右下和右上-左下的情况是完全对称的，算一种即可。

\(k = 3\) 有两种情况：一种是一个放角上，另两个放另两条边上；一种是两个放对角，一个任意放。

\(k = 4\) 有三种情况：一种是一个放角上，另两个放另两条边上，另一个任意放；一种是两个放角上，另两个任意放；一种是放四条边上。

复杂度最炸裂的是 \(k = 4\)。写代码之前以为是 \(n^4\) 带一些小常数，写完代码造的极限数据没过，发现常数是好几百。这还玩啥。

加了一些玄学特判，但愿多给点分（实际 \(k = 4\) 一分没给）。

有个 \(k = 5\) 的数据随机，以为长宽期望 \(n/2\)，\(5\) 个很大概率能拼满，所以直接输出了 \(n \times m\)。实际上确实过了一些点，但是出题人意图不是这样。

发现期望得分 \(\in (30,?]\)。写这么长时间才这么点分？感觉不能再多了就把这题放一边了。

赛后发现这题正解是搜索剪枝？！跟分类讨论没啥关系？！

11 点了。

E 是数据结构！很快会了子任务 \(1,3,4\)。但是子任务 \(4\) 并不像是我能写/调出来的样子，果断放弃了这 \(25\) 分。将这题目标定为 \(10+15 = 25\)。很快也写出来了。

此时 B, C 一分没得。显然 C 不可做，先写 B 的部分分。有一半的分是爆搜，还有 \(20\) 分的性质也差不多会，就不管正解了，将 B 的目标从 \(100\) 降到了 \(70\)。最终也写完了。

最后的时间发现 E 的子任务 \(2\) 特别简单！写！最后在提交之前写完了。但是因为神秘错误，最后写的这份代码没有在任何一个子任务执行！E 确实得了 \(25\)。

比赛过程中好的做法和不足

做的比较好的地方：

1. 时间分配没出大问题。

不足：

1. 分析程序效率时经常忽略常数。
2. 猜结论不够大胆。
3. 根据输入判所属子任务经常判错！！！！！！！

试题分析

• T1：数学。
• T2：找规律。
• T3：思维，单调队列。
• T4：搜索剪枝。
• T5：根号数据结构。

补题情况

A. 整数

令 \(x\) 为输入的数将小数点后的末尾 \(0\) 去掉，并将小数点去掉后得到的整数。令：

• \(a_i\)：\(x\) 中质因子 \(2\) 的出现次数；

• \(b_i\)：\(x\) 中质因子 \(5\) 的出现次数；

• \(c_i\)：输入的实数的小数点后的位数；

那么 \(A_i \times A_j\) 的小数点后应该会有 \(c_i + c_j\) 位。但是因为一个 \(2\) 和一个 \(5\) 能凑出一个 \(10\)，可以将末尾 \(0\) 去掉，所以 \(A_i \times A_j\) 合法当且仅当：

• \(i < j\)。

• \(\min(a_i+a_j,b_i+b_j) \ge c_i+c_j\)。

注意到可以将 \(\min\) 拆成两个式子：

• \(a_i+a_j \ge c_i+c_j\)，即 \(a_i - c_i \ge c_j-a_j\)。
• 且 \(b_i+b_j\ge c_i+c_j\)，即 \(b_i-c_i\ge c_j-b_j\)。

这是一个二维偏序的形式。肯定不能用二维偏序做。

注意到值域很小。考虑枚举这四个数，然后查桶即可。

B. 数字

注意到所有数字一定是从大到小，从高位到低位填的。也就是说 \(A,B\) 的第 \(1\) 位一定是所有数字的第 \(1\) 大和第 \(2\) 大，第 \(2\) 位一定是第 \(3\) 大和第 \(4\) 大，以此类推。我们只需要决定是否交换。

令 \(A\) 已经填好的前缀组成的数字是 \(a\)，\(B\) 的是 \(b\)。考虑一个新的数字 \(c\) 放到哪更好：

• 放到 \(A\) 后：乘积为 \((10a+c)b\)；
• 放到 \(B\) 后：乘积为 \((10b+c)a\)；

做差得 \(c(b-a)\)。所以当 \(b > a\) 时放 \(A\) 后；\(b < a\) 时放 \(B\) 后；\(b = a\) 时，哪个数字剩余的位数少就放谁后面。

C. 游戏

很巧妙的题！

显然 Alice 和 Bob 最终选择的数都是一段区间。令 $len = \r

Alice 希望最大化自己得到的数的和。Bob 能得到的数是除 Alice 得到的数外的数，也就是说他希望最小化 Alice 得到的数的和。