CodeChef December Challenge 2012

。水题略。。)

Sereja and Data Structures

Brief description:

。。给定长度为 n 的数列 {an}。。记 s(l, r) 为 [l, r] 区间里最大数与最小数的差。。。
。。。询问所有 s(l, r) 的的积。。(。。数据保证是随机生成的。。。

Analysis:

。。分治。。每次找到当前区间的最大值记作 m(。。或最小值。。可以比较哪一个更接近中点。。
。则按从小到大的顺序插入其他数字。。(。这一步暴力排序。。
。。。。左右各维护当前最远的可用距离。。。复杂度 O(nlog^2n)
。(Remark:和 N 年前我出的一个题 一样。。依赖于数据的随机性。。不过这个题的 Killer 似乎很好构造?。。给个递增的数列就行了。。

Arigeom Beats

Brief description:

。给定 n 个正整数 {An},将这些数分解成一个 AP(算数序列) 和一个 GP (几何数列)。。。
允许一个数同时出现在 AP 和 GP 中。。。 p 可以是有理数。。(记 d 为 该 AP 的公差。。p 为该 GP 数列的公比。。下同。。
(。。{An} 递增给出且互不相同。。。。n <= 1e4, Ai <= 1e5 ... 。。)

Analysis:

(。。。做法类似 CF 这题。。
。。

由于每项至少存在在 AP 和 GP 中的一个。。。
。。考察前 3 个数。。必然有 2 个会落在 AP 或者 GP 中。。且是该数列中最小的两项(外层共需枚举 6 种情况。。
。。。。。那么 Sub Task 是验证是否存在一个 AP (或者 GP 数列)。。使得。。某些数字必须出现。。某些数字可以出现。。

  • 对于 AP。。。
  • 。。如果存在,则对所有必须出现的数字排序。。d 一定是所有相邻数字的差的 gcd 。。。

  • 对于 GP。。。
  • 。。如果存在,则对所有必须出现的数字排序。。则 最小数 和 最大数 必然可以是 GP 数列的第一项和最后一项。。
    设最大数 / 最小数的最简分数为 A / B 。。GP 数列有 m+1 项。。那么 a 和 b 的 m 次方根都必须是有理数。。。
    。。即合法的 m 为 。。。 A 和 B 的所有质因子的幂的 gcd 的约数。。。。

Different Trips

Brief description:

。。给定一颗有根树。。问所有根到叶子结点所构成的字符串集合。有多少不同的子串。。。
。结点所表示字符等于这个结点的度数。。

Analysis:

。。开始一直从动态添加字符的角度考察这个问题。。(。。呵呵呵。。
。后来在著名图论巅峰人物 Daizhenyang 的注视下终于认识到了我的弱菜本质。。。

。其实把根到每个结点的路径。。组织成一颗静态的后缀数组就行了。。。
。。要对倍增算法进行少量的 Modification。。。(。。使用倍增祖先。。其他全部类比原算法即可。艹?。。这似乎是个经典的题啊?

。。按照叶子到根结点的顺序计算 height 数组的。。以保证线性复杂度。。
1. 遇到已经计算过的。。则直接 break 掉;
2. 若某时刻 u, v 相同。。则直接 height += dep[u]; break 掉。。

(Remark: http://www.lydsy.com/JudgeOnline/problem.php?id=1921

Quasi-Polynomial Sum:

.. 这个题需要用到。二项式定理 (Binomial theorem)。。霍纳规则(Horner’s method)。扩展欧几里德算法(Extended Euclid’s algorithm)。。数论变换(Number-theoretic transform)。。快速傅里叶变换(Fast Fourier transform)。和中国剩余定理(Chinese remainder theorem)
。。。这个题超出了本菜的能力范围。。。(呵呵呵呵。。。
。。。(题解 看都看不懂我会乱说?。。 。。

WordNinjas:

。。。考虑到最后附加题本菜的算法非常弱智。。就不和大家分享了。!!。。
由于我没能把拟多项式和给撸出来。。最终还是傻逼的滚出了第一版主要还是自己弱也没什么好难过的。
。。(。。啥时候我才能像戴牛那样虐爆全世界呢?。。。 )。。。

External link:

http://www.codechef.com/DEC12