ICL 2016

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Solved by Kilo_5723. 01:54 (+)

题意：从上到下有 $n$ 个骰子摞起来，每个骰子每一面上的字母都是已知的。现在 $n$ 个骰子从上往下每个骰子显示出的字母形成了一个字符串，问水平旋转这些骰子后能显示出目标的字符串的几率是多少。

题解：分别根据每一位显示出的当前字母计算出能显示出目标字母的几率，累乘即可。

Problem D

Unsolved.

Problem E

Solved by Kilo_5723. 04:24 (+2)

题意：有一个圆以及圆外两个点，问最短需要画多长的线，使得点到点以及点到圆相互连通。

题解：猜测最优解一定是 Y 字型的，下面一支连接圆，上面两支连接两个点。那么三分下面一支线段与坐标轴成的角度，再三分三支交点距离圆的位置即可。

Problem F

Solved by Weaver_zhu. 01:28 (+3)

题意：求有多少长度为$n$的数列使得$gcd=a$，$lcm=b$。

题解：每个素数分开考虑，然后容斥。指数有个范围$1-k$，问题转化为值域情况下$gcd=1,lcm=n$。发现可以容斥，且只和范围的长度有关。总的大小是$k^n$，减$\sum dp[x],x < n$就行了。以后做这种题可千万别忘记检查傻逼计数会不会记重复了。

Problem G

Solved by Xiejiadong. 00:11 (+)

温暖的签到。

判断同类型盘子的最大数量即可。

Problem H

Solved by Xiejiadong. 01:45 (+1)

题意：每次选择一个位置 $x$ ，翻转子串 $s[1\cdots x]$ 和子串 $s[(x+1)\cdots |s|]$ ，求进行 $n$ 次操作以后的状态。

题解：可以用 spaly 瞎搞搞。

如果把字符串看作一个环的话，每次操作其实就是环的翻转以及起点的变化。

环的翻转只需要根据总操作次数的奇偶性判断即可，起点的变化，每次暴力处理即可。

Problem I

Solved by Xiejiadong. 03:14 (+)

题意：支持加点、删点、和询问和一个点的曼哈顿距离最远的距离。

题解：四维的曼哈顿距离可以用类似二维的方式进行切比雪夫转换。

也就是转换成 $ max\{|(x_1\pm x_2\pm x_3\pm x_4)+(y_1\pm y_2\pm y_3\pm y_4)|,|(x_1\pm x_2\pm x_3\pm x_4)-(y_1\pm y_2\pm y_3\pm y_4)|\}$ 。

用八棵线段树分别维护 $\pm$ 的八种情况即可。

Problem J

Solved by Kilo_5723. 03:41 (+1)

题意：有两种操作：

第一种操作可以给定起点和长度，从这个起点开始往后找第一个没有被染色的点，从这个点开始给之后长度至多为给定长度的没有被染上颜色的部分部分染上颜色。

第二种操作可以擦去一个点上的颜色。

问每次进行第一个操作，有多少个新点被染上了颜色。

题解：维护当前每一段连续的染色段，根据题意进行操作进行合并，拆分，添加和删除即可。

Problem K

Solved by Xiejiadong. 04:07 (+)

题意：每次可以选择一个包含偶数个 $1$ 的 $0/1$ 串反转，要求构造一个方案变成目标串。

题解：对于每一个位置都是暴力的向后选取一个包含偶数个 $1$ 且满足最后一位是当前位置的子串，翻转即可。

这样做的话，显然所有的位置都是可以得到可行解。

问题主要就是最后一个 $1$ 怎么处理。显然如果前面处理完以后，最后一个 $1$ 不在它该在的位置上，这是一个不合法态。

证明这个问题的话，可以考虑一共有两个 $1$ 的字符串，且第一个位置都是 $1$ ，后面两个位置不匹配的情况。

由于翻转的时候，两个 $1$ 的相对位置不会发生变化，所以这样的状态是不可行的，上面最后一个 $1$ 的状态可以归结到这里。

Problem L

Solved by Kilo_5723. 01:22 (+1)

题意：一开始有一个二元组 $(a,b)$，每次可以通过任意一个已有的二元组 $(a,b)$ 新增一个二元组 $(a+1,b+1)$，可以通过一个已有的 $a,b \mod 2 = 0$ 的二元组 $(a,b)$ 新增一个二元组 $(a/2,b/2)$，可以通过两个已有的二元组 $(a,b),(b,c)$ 新增一个二元组 $(a,c)$。求一个方案，使得能得到目标二元组 $(c,d)$。

题解：特判 $a=b$ 的情况。考虑 $a<b$ 的情况（$a>b$ 则翻转）。

假设 $b-a=x$，那么令 $x$ 除去所有 $2$ 的因子后变成 $x'$，当且仅当 $c<d$ 且 $gcd(d-c,x')=x'$ 的时候才能达到 $c,d$。

通过 $(a,b)(->(a+1,b+1))->(\lfloor \frac{a+1}{2} \rfloor,\lfloor \frac{b+1}{2} \rfloor)$ 得到 $(k,k+x)$，再通过 $(k,k+x)+(k+x,k+2x)->(k,k+2x)(->(k+1,k+2x+1))->(\lfloor \frac{k+1}{2} \rfloor,\lfloor \frac{k+2x+1}{2} \rfloor)$ 得到 $(1,1+x)$，最后通过 $(1,1+x)$ 得到 $(c,d)$即可。

Problem M

Solved by Kilo_5723. 00:37 (+)

题意：求 $n$ 个分数的最小公倍数。

题解：通分求 lcm 再化简。Python 真好用。