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。。 ゆっくり読んでください ...

ZOJ 2112. Dynamic Rankings

Brief description:

给定一个长度为 N 的已知序列 A[i] (1≤i≤N),要求动态维护 M 次以下操作:
1、Q a b k 查询 A[a], A[a+1], A[a+2], …, A[b] (1≤a≤b≤N) 中,第 k 小的数。(Start From 1 ...
2、C x y 修改 A[x] 的值为 y。
( .. N ≤ 50, 000 .. M ≤ 10, 000 .. 保证 A[i] 在任何中间时刻的绝对值都不超过 10^9 ..)

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

SRM 546

Brief description:

Problem 250. KleofasTail
给定下面的变幻规则 。。。

x->2x | x 是任意数
x->2x+1 | x 是偶数

问从 x 开始变幻,落在区间 [l, r] 之间的数字的个数。

Problem 500. FavouriteDigits
求满足数位中有 c1 个 d1, c2 个 d2 的大于等于 n 的最小数。

Problem 1000. FleaCircus
设 P 是一个置换,现在给定 P^4 。。。
计数:所有可能满足的 P。

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

Codeforces Round #124

Brief description:

Problem A. Lexicographically Maximum Subsequence
给定一个字符串,求重新排列这个字符串之后所能得到的字典序最大的串。(略。

Problem B. Infinite Maze
给定一个可平铺的迷宫,问出发点所在的区域是否是封闭的。(记录四维状态 BFS() 即可。。。卡步数 TLE 了两次。。

Problem C. Paint Tree
给定一颗树,和平面内一组点集,问是否存在一个对应关系使得,生成的平面图不产生交叉。

Problem D. The Next Good String
。Good String 定义为,不存在长度大于等于 d 的回文子串。给定一个字符串,求该子串的下一个 Good String 。

Problem E. Opening Portals
给定一个 n 个结点,m 条边无向带权图,选中其中 k 个结点作为传送门,
当一个传送门被点亮后,可以在其他已被点亮的传送门之间做无损传送。
问从 1 号结点出发,点亮所有传送门的最少代价。
( .. 1 ≤ k ≤ n ≤ 10^5, m ≤ 10^5 .. .)
ゆっくり読んでください ...

TCO 2012 Marathon Round 3

。。。经过 2周 的 Coding 。。。R3 昨天落幕。。
。。由于我最后一个版本的算法(。。贪心 后接 搜索。。。
。表现非常不佳。。。

于是最后退回到了倒数第二个版本。。。
(主函数二分套二分。。。
(框架是 构造 接 随机抛点。。 接 构造 再接构造。。。
(后面两个构造是在已得到的结果上进行调整优化。。。
(前面第一个构造是主函数。。。但是因为测试中部分数据得不到良好效果。。因此又接了一个 6s 的随机过程。。。。

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