某岛

… : "…アッカリ~ン . .. . " .. .
July 11, 2012

CodeChef July Challenge 2012

(进度: 9 / 10

Brief description:

Problem A. Addition chains:
[加法链][大数][构造]
构造 n 的加法链、长度越短得分越高、长度不得超过 500。
(n ≤ 10^100 )

Problem B. My Fair Coins:
[线性递推数列][类斐波那契数列][矩阵乘法]
略)

Problem C. Dynamic GCD:
[轻重边树链剖分][线段树]
给定一颗树,动态维护以下操作:

  • C u v d: 每次一条路径上的数 + d。(d 为正数)
  • F u v: 求一条路径上所有数的 gcd。

Problem D. Chef’s Dream:
略.. O(nlogn) 贪心)

Problem E. Equivalent Suffix Tries:
给定一个串 S、问有多少串的 Suffix Tries 与其同构。

Problem F. Favourite Numbers:
[自动机DP][数位DP]
给定一组病毒串,问 [l, r] 区间内,第 kth 个包含有病毒串的数是多少。

Problem G. The Gray-Similar Code:
[nice][adhoc]
给定一个长度为 n 的序列 {ai},相邻两个数之间的 xor 相差一位。
问数组中是否存在一组 1 ≤ i1 < i2 < i3 < i4 ≤ n, 使得 a_i1 xor a_i2 xor a_i3 xor a_i4 = 0。 Problem H. Little Elephant and Bubble Sort: [概率][树状数组] 一个数组,对于每一位有 pi 的概率为 ai, 1-pi 的概率为 bi。。 问该数组执行冒泡排序的期望交换次数。 Problem I. Restaurant Rating: [动态维护第 k 大数][大根堆 + 小根堆][平衡树 TLE?] 动态维护一个序列,要求支持以下操作: 1 x: 插入一个数 x。 2: 询问第 kth 大的数,k 为 \floor{n/3}。。。 Problem J. Gift Rift: [签到题][鞍点] 略) ...

Analysis:

Addition chains:
有待补完)

Dynamic GCD:
目测不能上动态树(?。。。

。。。那么树链剖分是常规了。。集中分析单链的情况怎么维护。。
分析修改操作。。那么一段数 +d 的话。。。相对之间的差是不变的。。

然后注意 gcd 的性质。。 gcd(a, b) = gcd(a – b, b);
那么一串数的 gcd 可以转换为。。gcd(a, b-a, c-a, d-a … )
参见 GCJ Qualification Round 2010 Problem B. Fair Warning

这样就可以用块状链表来维护。。。对于块状链表的大小。。

这里有两种选择。。一种是对所有链用一个统一的值 (例如 整颗树的 sqrt(n) 。。
另一种是对每条链用不同的值。。(每条链的 sqrt(n)。。。
这里有待分析。。。

但是以上两种方法都 TLE 了。。。
下面退回前面一个步骤。。。
仍然是利用那个兴致。。。注意到一串数的 gcd 可以转换为

gcd(a, b-a, c-b, d-a) 。。。。。
这样再对原数列差分得到数列 b。。。修改操作的话。。至多只会影响到 b 数组的两项。。。

于是成段修改(+d)成段询问的 gcd 。。。就等价于求以下两个子问题的 gcd。。。。。
成段修改 (+d),单点询问。。。
单点修改,成段 gcd。。。。

以上两个问题分别用线段树维护即可。。

Equivalent Suffix Tries:
。。。

Favourite Numbers:
dp[i][u] 表示当前长度为 i,在自动机的 u 位置时有串是存活的。。
因为串都是反着 Input 的,所以状态转移的时候注意向相反方向转移。
数位DP好像也可以但是好像不怎么好写。。)

The Gray-Similar Code:
假设存在一组解,i1, i2, i3, i4。
则设 Ai1 ^ Ai2 = Ai3 ^ Ai4 = mask;
。。若 mask != 0 ,则必存在相邻两项属于 [i1, i2] 和 [i3, i4] 区间,使得它们的 ^ 等于 mask 中的一个二进制位。
(从路径的角度考虑即可。。)
这样整个算法就分成了两个步骤,首先先判断 mask = 0 的情况,这种情况有两类。(4个一样的数,或者2组2个一样的数。)
之后处理 mask != 0 的情况,做差分预处理出一个 int S[64]; 的数组扫描即可。注意使用 unsigned long long;

External link:

http://www.codechef.com/JULY12/