XIX Open Cup named after E.V. Pankratiev. Grand Prix of SPb, Division 1.

Problem A

Solved by Xiejiadong. 2:48 (+1)

题意：给出了宠物属性的生成方式，选定一个时间，使得获得的宠物属性最强。

题解：宠物的生成方式中有 salt 是未知的。

因为 salt 最多不过超过 $2^{31}$ 。我们可以根据样例暴力的求出这个 salt 。

接下来就是按照每一个时间计算出宠物的属性，求一个最优的了。

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Solved by Xiejiadong. 0:48 (+)

题意：平面内被无数个十字形覆盖，求从一个地方到另一个地方至少要穿过多少十字形的边界。

题解：根据题目给出的十字形中点形式$(2i+j,i-2j)$ 可以得到，对于相邻的十字形，其实他们的中心坐标计算的时候的 $(i,j)$ 哈密顿距离为 $1$ 。

于是对于每一个点求出这个点所在的十字形的重点，解方程解出 $i$ 和 $j$ 计算哈密顿距离即可。

Problem E

Solved by Weaver_zhu. 3:24 (+1)

Problem F

Solved by Kilo_5723. 0:59 (+6)

Problem G

Solved by Xiejiadong. 0:31 (+2)

题意：求一个最小的数使得其数位和为 $n$ ，且不包含数字 $d$ 。

题解：显然这个数不可能包含数字 $0$ 。

首先肯定会考虑使用尽可能少的位数，那么如果能用 $9$ 就尽量用 $9$ ，否则用 $8$ ，最后会余下一个数字，显然这个数字肯定会放在第一位，因为最小。

对于这个数字，如果是数字 $d$ ，考虑用第二位数来中和他，即保证他们的和不变，但让第一个数变大，看是否存在可能使得前两个数都不是 $d$ 。

如果无法达到，那么只能再增加一位，通过三位来取代当前两位的数字和。

需要注意只有一个数字的情况。

Problem H

Unsolved.

Problem I

Solved by Weaver_zhu. 1:40 (+3)

Problem J

Solved by Xiejiadong. 2:09 (+7)

题意：有两个字符串 $s$ 和 $t$ ，均为 $100$ 位，可以询问 $100$ 次，每次会随机选择一个字符串，并随机将其中 $15$ 位取反，求出这两个字符串。

题解：考虑要想办法把每次询问中的字符串 $s$ 和 $t$ 区分开来。

于是考虑对于每一位，假设如果有一位 $$ 和 $t$ 一样的话，那么这个位置的 $0/1$ 分布应该大致是 $15:85$ ，显然多的一个数字就是这个位置上的数字。

那么对于不满足近似这个比例的位置，一定会有两个字符串是不同的，考虑通过这个位置相同的唯一类分成两类，然后其他没有确定下来的位置可以通过以多数为准来确定位置。

Problem K

Solved by Kilo_5723. 4:40 (+4)

Problem L

Unsolved.