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.