D1T3题解

· · 题解

Day1

T3

:::info[我毫无头绪。]

简单来说，我们可以注意到两件事情：

  1. 如果剩下的候选项的数量小于剩余询问总长，可以直接询问所有候选项，答案为 x 的情况下返回的一定是 x+\sum_{i=1}^{n-1}\gcd\{a_i,a_{i+1}\}(a_1<a_2<\cdots<a_n)

    据此就可以判断答案。

  2. 我们要做的实际上是在前三次询问中将最大可能的候选项个数压缩到最小。

我们先考虑如果限制更宽，比如每次询问 35 个数，该怎么做。绝对不是我把题目看错了
这样至少搜索第一步的过程和长度无关，我们可以用模拟退火或者其他的什么爬山之类的东西搜一下有没有很好的解。
::: :::info[该如何优化？] 最简单的退火方法当然是设每个询问后答案相同的桶里的数的个数的最大值 M=\max c_i 为估价函数，但是这样实测效果并不好，并不能很好反映桶的分布的某种平均性。所以我们考虑增加 \sum c_i^k 作为关键字，并以某种权值和 M 一起计入估价函数。

因此我们可以设计比较规则如下：

(M,\sum c_i^4,\sum c_i^3,\sum c_i^2,|S|)

其中 S 是所有 c_i 构成的集合。

同时我们设能量函数

E(s)=A_0\cdot M+A_4\cdot\sum c_i^4+A_3\cdot\sum c_i^3+A_2\cdot\sum c_i^2

这里给出一组参数

\begin{cases} A_0=10^{10}\\ A_2=1\\ A_3=120\\ A_4=8 \end{cases}

可以跑出如下的例子：

{ 18,19,38,40,231,350,425,510,765,900,990,1155,1200,1440,1560,1575,1750,1785,1836,2040,2142,2205,2310,2464,2520,2600,2769,2840,2841,2871,3248,3314,3423,3478,3498 }

这组数据跑一次之后最多剩下 64 个数，接下来只需要随便询问两次即可。 ::: :::info[该如何转化？] 我们发现限制非常严格，但这也带来了一个好处：

考虑先处理 3 次询问，外层枚举询问长度，对于固定的第一步询问 L_1 个数、第二步询问 L_2 个数，外层进行上述退火搜索第一步方案，内层再套一层退火搜索第一步方案下每个桶的第二步方案。

对于第二次，我们已经知道不能让最劣的剩下的数超过 L=35-L_1-L_2 个，对于超出的部分我们应当给予相当高的惩罚。我们这次比较以

V=\sum\max(0,c_i-L)^2

为第一关键字，设计能量函数也以此为基础：

E(s)=A_v\cdot V+A_0\cdot M+A_4\cdot\sum c_i^4+A_3\cdot\sum c_i^3+A_2\cdot\sum c_i^2

同样给出一组参数

\begin{cases} A_v=8\times 10^{11}\\ A_0=2\times 10^{9}\\ A_2=0\\ A_3=1\\ A_4=10 \end{cases}

那么接下来还有一个问题：退火的过程中如何进行随机变异。我们考虑如下的方案：

  1. 修改 O(1) 个位置；
  2. 扰动范围逐渐减小。

对于不同类型的扰动，以不同概率进行：

  1. 概率局部加减；
  2. 完全随机重置；
  3. 随机选一个目标位置，然后在范围内找约数最多的整数；
  4. 乘除小质数（下取整）。 同时，保证扰动后严格递增，即不出现重复元素。

加上一点小小的实现细节，我们就搜出了方案！

FOUND 8+4+23
first={420,840,1155,1540,1890,2160,2520,3003}
adaptive_branches=37
max_first_bucket=96
max_after_second_bucket=23
max_calls=3
max_total_length=35
second[1213]={518,616,726,2679}
second[1215]={155,585,720,818}
second[1217]={412,581,747,1013}
second[1223]={304,496,836,896}
second[1248]={1220,1330,1452,1494}
second[1249]={360,1355,1413,3016}
second[1250]={1110,1252,1427,1650}
second[1251]={483,1120,1481,1572}
second[1253]={672,1082,1132,1316}
second[1271]={429,655,1420,1452}
second[1273]={2222,2334,2400,2640}
second[1275]={2005,2300,2450,2536}
second[1279]={2016,2163,2233,2288}
second[1281]={956,1664,2095,2240}
second[1295]={525,2132,2214,2265}
second[1363]={1791,1945,2030,2126}
second[1365]={1945,2115,2202,2247}
second[1367]={1952,1969,2030,2132}
second[1528]={899,962,1068,3144}
second[1529]={751,922,1038,1269}
second[1532]={779,919,994,1197}
second[1535]={728,891,940,981}
second[1563]={1472,1662,1725,1800}
second[1565]={1427,1684,1888,2933}
second[1567]={1628,1716,1798,1870}
second[1571]={1493,1576,1723,3500}
second[1612]={2640,2736,2862,3154}
second[1613]={699,2589,2819,2878}
second[1616]={2532,2704,3024,3037}
second[1619]={2466,2582,2658,2759}
second[1631]={1468,2205,2671,2824}
second[1632]={88,198,306,1131}
second[1633]={144,336,870,2034}
second[1634]={1,109,189,405}
second[1635]={1,143,204,429}
second[1637]={203,315,372,2395}
second[1643]={88,276,334,347}

::: :::success[该如何提取？] 都到这一步了代码还写不出来？

直接枚举前两步的所有可能情况随便搞一搞即可。 :::