Difference between revisions of "ICL 2016 (GP of Tatarstan)"

From EOJ Wiki
Jump to navigation Jump to search
 
(One intermediate revision by one other user not shown)
Line 9: Line 9:
 
== Problem B ==
 
== Problem B ==
  
Unsolved. (-10)
+
Upsolved by zerol. (-10)
  
 
题意:有一些 $1\times 1, 1\times 2, \dots, 1 \times 9$ 的东西每种都有若干颜色,问有多少种办法拼出 $2 \times n$ 的形状。
 
题意:有一些 $1\times 1, 1\times 2, \dots, 1 \times 9$ 的东西每种都有若干颜色,问有多少种办法拼出 $2 \times n$ 的形状。
  
题解:由于 $n$ 高达 $10^{18}$,所以快速幂肯定要的。那么就 $O(n^2)$ DP 跑出前若干项,然后 BM 线性递推。
+
题解:由于 $n$ 高达 $10^{18}$,所以快速幂肯定要的。那么就 $O(n^2)$ DP 跑出前若干项(什么?你不会 DP?不可能),然后 BM 线性递推。
  
 
zeorl: 为什么没过呢?因为自主研发的线性递推的板子有问题,倒不是正确性,就是会 RE,还不止一处。
 
zeorl: 为什么没过呢?因为自主研发的线性递推的板子有问题,倒不是正确性,就是会 RE,还不止一处。

Latest revision as of 02:05, 11 March 2019

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 (+)

温暖的签到。