XVIII Open Cup named after E.V. Pankratiev. Grand Prix of SPb

Problem A

Solved by Xiejiadong. 2:40 (+2)

题意：用 $0/1$ 串 $c_0c_1c_2\cdots c_n$ 表示复数 $a$ ，其中复数 $a=\sum_{k=1}^n c_k\cdot (1-i)^k$ 。

题解：直接暴力转换是算不出来的，因为最多有 $500000$ 位，可以发现 $(1-i)$ 间隔 $4$ 乘四倍，高精度都没法做。

如果没有进位，直接相加即可，考虑进位的情况，即其中一位是 $2$ 的时候怎么用别的表示，可以发现，第 $i$ 位是 $2$ 的话，等价于第 $i+2$ 和 $i+3$ 位是 $1$ 。

按照这个法则进位即可。

不过有一个情况，就是按照这样的法则进位 $111+111$ 的时候，会发现，进位会发生死循环，其实 $111+111=100$ ，需要特判。

Problem B

Solved by Xiejiadong. 1:06 (+)

题意：给定一个十进制数，要求将他的二进制位任意重组，不能有前导 $0$ ，求能组成多少个完全平方数。

题解：数的范围是 $10^{18}$ ，则完全平方数的底数最多是 $10^9$ ，暴力预处理，将所有完全平方数按照二进制下 $1$ 的个数和 $0$ 的个数分类记录。

打出表，直接根据表得解。

Problem C

Solved by Xiejiadong. 0:29 (+)

题意：有 $n$ 个鸡和鸡蛋，要求鸡蛋能够装鸡必须满足鸡蛋的大小 $\ge$ 鸡，求一对一映射的方案。

题解：$n\le 12$ 直接暴力全排列会 TLE ，加了优化也不行，最坏的情况就是会跑慢。

考虑用状态压缩 dp 处理即可。

Problem D

Unsolved.

Problem E

Upsolved by Kilo_5723.

题意：给定 $\frac{a}{b}(1 \le a < b \le 10^9)$ 精确到第 $18$ 位小数的结果，求任一对可能的 $a,b$。

题解：设结果为 $x$，则 $x-5 \cdot 10^{-19} \le \frac{a}{b} < x+5 \cdot 10^{-19}$。先特判左边等于的情况，约分判断分母大小是否 $\le 10^9$。如果不可行，将左右都化为分数形式，问题转换为求解 $p,q$，使得 $\frac{p1}{q1} < \frac{p}{q} < \frac{p2}{q2}$，用类欧几里得算法求解。

Problem F

Unsolved.

Problem G

Solved by Kilo_5723. 0:42 (+1)

题意：给定一个地下坑道的剖面图，问在给定规则下，是否能找出一个空位不可能被水浸湿。

题解：暴力逐行判断即可。

Problem H

Unsolved.

Problem I

Solved by Kilo_5723. 2:38 (+3)

题意：平面上有 $n \le 500$ 个互不共线，起点相同的向量，每次可以询问两个向量的叉积是否 $>0$，要在 $20000$ 次询问内判断这 $n$ 个向量是否属于一个经过原点的半平面，并将其排序。

题解：考虑快速排序，每次取出一个向量，将所有在其左侧，右侧的向量分别排序后合并。注意特判 $n=1$ 的情况。

Problem J

Solved by Weaver_zhu. 2:06 (+2)

题意：给两个数列{a}，{b}，枚举$a_i+b_j$组成一个新的$n^2$个数的数列，输出新的数列中间$n$个数。

题解：二分出新的数列第一个数和最后一个数，枚举$a_i$二分找出$b_j$算上中间的数，然后根据个数计算第一个数和最后一个数的个数。

Problem K

Unsolved. (-9)

Problem L

Solved by Kilo_5723. 0:13 (+)

题意：给出 $n$ 个数，问有多少种将其划分到两个集合中的方式，使得两个集合内的异或和相等。

题解：显然，如果 $n$ 个数的异或和为 $0$，任意的划分都满足要求。如果不为 $0$，则不存在这种划分。