某岛

… : "…アッカリ~ン . .. . " .. .
June 30, 2012

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 个槽位有哪些数。。
(但不能确定具体的位置)。。问最少多少次询问可以还原之。。。

Analysis:

Problem A. Clear Symmetry
。。。首先观察注意到偶数情况下 bug (还没有较小一阶的奇数优。。
…然后制作 int r(x); 表示阶数为 x 的时候最多能产生多少个 1 。
。。。然后稍微构造一下发现比这个数小情况都是可以构造出来的。。(除了 3 阶,特判一下就交了。。

Problem B. Guess That Car!
考虑到公式是可以对 x 轴和 y 轴分离的。。于是 O(n) 拖出来做两次预处理即可。。

Problem C. Fragile Bridges
。。SB 动态规划,定义左右两边以及能否返回四个状态。。。
(参见。。。http://acm.uestc.edu.cn/problem.php?pid=1649

Problem D. Brand New Problem
定义 dp[s][i] 表示使用的数字集合为 s, 逆序数为 i 时,在文本中所处的位置。。(。最左边那个。。
。然后制作辅助数组 p[i]][j] 表示第 i 个位置开始出现 j 的最靠左的位置。。就能转移了。。╮(╯_╰)╭

Problem E. Thoroughly Bureaucratic Organization
对于任意两个数 i, j, 为了区分两个数字的位置。。
则至少存在一组询问只包含 i 或只包含 j 。。。。

于是问题等价于 SRM 484 的 1000 。。。

(对于每次不必用填满 m 个数的问题。。发现对问题不构成太大影响。只是再 m > n / 2 时,取 m = n / 2 即可。。。

Code:

A B C D E

External link:

http://codeforces.com/contest/201/room/5