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。

ゆっくり読んでください ...

SRM 548

Brief description:

Problem 250. KingdomAndTrees
给定一个数列,要求修复成递增序列。。(所有项都是正数。。。
。定义修复代价为变动最大的数字改变了多少。。求最小修复代价。。。

Problem 450. KingdomAndDice
给定两块骰子。。数字选自 {1, x} 。。
其中一块骰子上的数字已经全部确定。。另一块骰子部分确定。。
。。先要求确定剩下的数字。。使得该游戏尽可能公平。

Problem 1000. KingdomAndCities
计数:求 n 个顶点、m 条边、其中前 k 个顶点恰好连 2 条边时形成连通图的方案数。
( n, m < = 50, k <= 2 .. . ゆっくり読んでください ...

SRM 484

Brief description:

Problem 250. RabbitNumber (兔子数 ...
问 [l, r] 区间内 "兔子数" 的数字有多少。
兔子数为满足 S(x^2) = S(x)^2 的数字, 这里 S(x) 为 x 的数位和。
( .. . 1 < = l, r <= 10^9 .. ) Problem 550. PuyoPuyo 一个堆栈, 可以往里面放 4 种颜色的球,当栈顶连续 L 个球颜色相同时,消去这 L 个球。 问往里面放 n 个球的话有多少种放法使得栈空。 ( . ..n <= 1000, L <=10 .. .) Problem 950. NumberMagic (猜数游戏。。 Taro 在心中想了一个 1~n 之间的数字 x,Hanako 每次可以询问一个 m 大小的集合。 Taro 返回 x 在 / 不在 其中。。。问至少多少次询问一定可以猜出这个数。 ゆっくり読んでください ...

ZeroJudge b179. 空罐 Cans

Brief description:

... 给定一个初始基因,基因每轮每次会在后面添加 {a, b, c ,d} 中的一个字符形成 4 个新基因。旧基因在分裂过后会损失第一个字符。。。。
有 n 组有害基因,如果出现了有害基因作为子串则丢入医院。。
如果一个基因长度变为 0 则被丢入回收场。。
问最后分别有多少基因丢入医院多少基因丢入回收场。。。
( .. p < = 100, n <= 100, Σ = {a,b,c,d} .. ) ゆっくり読んでください ...

Codeforces Round #127

Brief description:

Problem A. Clear Symmetry
。。一个 01 矩阵被称之为:
Clear: 如果没有 1 相邻。
Symmetrical: 如果在 旋转90度 的作用下不变。
要求在满足上述性质的情况下,构造一个阶数最少的有 x 个 1 的 01 矩阵,求这个阶数。

Problem B. Guess That Car!
给定一个 N×M 的格点,每个点有一个全值 Aij,当人站在某个交点位置时将对每个格点产生一个代价。
定义为 Aij 乘以距离的平方。问站在哪个位置时,所有格子产生的代价最少。

Problem C. Fragile Bridges
给定一排要石,要石与要石之间有一座桥,每个桥有一个耐久度 Ai,当往到达 Ai 次的时候,
桥会坍塌,问能移动的最长步数。(可从任意位置开始。。

Problem D. Brand New Problem
给定 n 和一个长度为 l 的数组,构造一个大小为 n 的子序列,使得其构成 1, n 的一个重排,且逆序数尽可能小。
( n ≤ 15, l ≤ 500000 .. .)

Problem E. Thoroughly Bureaucratic Organization
已知有一个长度为 n 排列,但不知道每个位置分别是多少,每次询问可以确定其中至多 m 个槽位有哪些数。。
(但不能确定具体的位置)。。问最少多少次询问可以还原之。。。

ゆっくり読んでください ...

【套题】GSS 系列

Brief description:

序列 a 的 l, r 之间的最大子段和 (Maximum subsequence sum) 定义为:
Query(l, r) = Max {a[i]+a[i+1]+...+a[j] ; l ≤ i ≤ j ≤ r}.

GSS 系列是 SPOj 上的一组数据结构习题,一共 6 题,大部分是和最大字段和有关。

GSS1: 只有询问。GSS3:单点修改。
GSS5: 询问时,限定区间两端点 i, j 的取值范围。
GSS2、GSS4:相对的独立问题。。
GSS6: 加入插入和删除操作。
GSS7: 树上 GSS 问题。

ゆっくり読んでください ...