ICL 2016 (GP of Tatarstan)

Problem A

Upsolved by ultmaster. (-2)

题意：给定三点 $A,B,C$，求一点 $Q$ 使得 $AQB = \alpha_1$, $BQC = \alpha_2$。

题解：搞出四个圆，然后两两配对。注意交点不能和给定点重合，注意圆重合的情况。

Problem B

Upsolved by zerol. (-10)

题意：有一些 $1\times 1, 1\times 2, \dots, 1 \times 9$ 的东西每种都有若干颜色，问有多少种办法拼出 $2 \times n$ 的形状。

题解：由于 $n$ 高达 $10^{18}$，所以快速幂肯定要的。那么就 $O(n^2)$ DP 跑出前若干项（什么？你不会 DP？不可能），然后 BM 线性递推。

zeorl: 为什么没过呢？因为自主研发的线性递推的板子有问题，倒不是正确性，就是会 RE，还不止一处。

Problem C

Solved by ultmaster. 01:34 (+1)

题意：有 $n$ 个东西，每个东西已知一些事件发生，求在此条件下 另一系列事件发生的概率。

题解：条件概率公式。注意权重。

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Solved by ultmaster. 00:42 (+1)

题意：问有多少个有序数列满足 gcd 是 d，lcm 是 m。

题解：m /= d。然后简单容斥一下。

Problem G

Solved by zerol. 00:13 (+)

温暖的签到。

Problem H

Solved by zerol. 01:36 (+2)

题意：给一个字符串，每次操作就是把字符串切成两半，各自翻转之后再接回去，输出若干次操作之后的结果。

题解：如果把字符串看做一个环的话，每次操作就是翻转这个环，然后换一个起点。所以记录一下翻转了奇数还是偶数次，以及第一个字母的位置就好了。

zerol: 数据范围 2E5，很诱人，直接无脑上了个 rope，然后 T 爆。

Problem I

Solved by zerol. 00:49 (+)

题意：四维空间，要求支持插入一个点，删除一个点，询问所有点中里给定点曼哈顿距离最远的点的距离。

题解：二维的话就非常套路，曼哈顿距离转切比雪夫距离，然后由于求的是某一维的 max，所以枚举每一维，测试一下这一维上最小的和最大的即可。四维的话，也能转切比雪夫距离，就是 $\pm x_1 \pm x_2 \pm x_3 \pm x_4$，当然可以省掉一个 $\pm$，因为切比雪夫距离有个绝对值。

Problem J

Solved by zerol. 03:21 (+2)

题意 & 题解：用 set 维护不相交区间，然后乱搞。

zerol: 有一个 for (auto& x: S) ; 的调试语句，以为编译器会优化掉，实则 T 爆。

Problem K

Solved by kblack. 02:06 (+1)

题意：给两个 01 串，问能否把其中一个转化成另一个，操作是翻转一个包含偶数个 1 的子串。

题解：依次把所有的 1 翻转到尽可能往前，只有最后一个 1 没法操作，把这个作为最小表示，记录下翻转过程，构造方法把两个的过程拼一下。

Problem L

Solved by kblack. 02:56 (+3)

题意：有个 $(a, b)$，可以操作成 $(a+1, b+1)$、$(\frac{a}{2},\frac{b}{2})$（要求整除），$(a, b)$ $(b, c)$可以搞成 $(a, c)$，都不是消耗品，让你把 $(a, b)$ 整成 $(c, d)$。

题解：注意到 $b-a$ 除了 2 以外的质因子都去不掉，可以操作的充要条件是 (a == b && c == d) || ((a-b)*(c-d)>0 && (c-d)%(abs(a-b)>>__builtin_ctz(abs(a-b)) == 0)，然后就随便搞一搞，注意造过的缓存一下，防止使用太多操作。

Problem M

Solved by kblack. 00:07 (+)

温暖的签到。