Page 1 of 3123

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 问题。

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

SRM 547

Brief description:

Problem 250. Pillars
。。要在两面墙之间架一个梯子,两面墙高度皆为整数,均匀选自 [1, A] 和 [1, B] 之间。
。中间距离为 w,问梯子期望的长度。
(。。1 ≤ A, B ≤ 100, 000 。。。)

Problem 500. RectangularSum
给定一个逐行逐列依次填 {0, 1, 2, 3, 4, ... nm-1} 的 n × m 矩阵。。
。。。问所有和等于 S 的子矩阵中,面积最小的是多少。
(。。1 ≤ n, m ≤ 100, 000 。。。1 ≤ S ≤ 100, 000, 000, 000。。。)

Problem 1000. MaximalTriangle
问正 n 边形的三角剖分中,有多少种剖分是可以产生一个面积最大的大三角形的。
(。。3 ≤ n ≤ 444 。。。)
ゆっくり読んでください ...

Codeforces Round #125

Brief description:

Problem A. About Bacteria
... 培养皿中的 x 只细菌下一秒会繁衍出 kx+b 只细菌。。(。。。
问如果初始培养皿中有 t 只细菌,至少多少秒才可以繁衍出不少于 z 只细菌。
。。。z 为初始为一只细菌时,繁衍 n 秒的细菌总数。。。(。。。
(略,算术题。。不要把 z 真给算出来即可。。

Problem B. Jumping on Walls
一个忍者在一个坑里, 左右各有一面墙,墙上有一些障碍,初始在最下角。
每秒钟可以上下移动一格,或者跳到对面墙的恰好 +k 位置。。
。。问最终能出跳出这个坑。。
(略, Hash Dp 或者 BFS() 都行。。。。

Problem C. Delivering Carcinogen
给定一颗行星坐标 (xp, yp),轨道半径 R,围绕恒心运转的线速度 vp,
以及一个飞船坐标 (x, y),飞船速度 v。。问到达 p 星球的最少时间。。
。。飞船运行过程中距恒星的距离不得低于 r。。(r ≤ R) ...

Problem D. Cube Snake
给定一个 n 阶立方体,要求构造满足下列性质的路径:
对任意的 k < n, 存在至少 2 个 k 阶子立方体, 满足其中的数字取自一段连续区间。 Problem E. Gripping Story 空间中有一堆吸盘。 。。每个吸盘用 (xi, yi, mi, pi, ri) 表示。。。 。。自身坐标,重量。。。能抓起来的最大物品的重量,以及作用范围。。。。 。。现给定飞船初始坐标。。(x0, y0)。。初始吸盘(p0, r0)... 问最多可以收集多少个吸盘。。。 (。。一旦得到一个吸盘以后以后就可以无限更换使用。。 (。。。注意注意飞船本身不动不动不动!。。并且吸盘吸到飞船里才能使用。。。OOrz。。 ゆっくり読んでください ...

Page 1 of 3123