测试数据和完整解题报告在此下载： DropBox | Skydrive

正文：

10月28日_G122_cnPhil_的解题报告

先看哈：

选手列表

编号 姓名 总分

02.mt 02.mt 400.00

standard standard 400.00

–测试器上一角，Orz mt大牛。

简单题目

Easy

时间限制：1s

空间限制：128M

【题目背景】

经典题目自有经典算法。

 

【题目描述】

给你一个N*M（N,M<=1000）的01矩形，求一个面积最大的不包含数字1的矩形。

 

【输入数据】

第一行两个数N，M。

接下来N行，每行M个数为0或1。

 

【输出数据】

一个数ans表示最大空矩形的面积。

Sample

Easy.in

2 4

1 0 0 0

0 1 1 0

 

Easy.out

3

Solve:

这道题，我是用类动规方法做的。对于一个点，记录其竖直向上、水平向左两条最大可以达到多长，再根据这个点左边、上面的点的值求出以这个点为右下角的矩形最大能达到多少。mlj的方法：枚举每列，求出每两个1或边界之间的最大可取矩形。（预处理时标记每点最左最右双向可取长度）

SB题

SB

时间限制：1s

空间限制：128M

【题目背景】

题如其名啦……

【题目描述】

给你一棵N（N<=10000）个节点的树，求每个点到其他点的最大距离。

【输入数据】

第一行一个数N。

接下来若干行每行两个数k，t描述一条点k到点t的边（输入数据保证无重复边）。

【输出数据】

N行每行一个数表示每个点到其他点的最大距离。

Sample

SB.in

5

1 2

1 3

1 4

4 5

SB.out

2

3

3

2

3

Solve:

这道题，有个两遍深搜的方法：首先对于每个点，先构造树结构（任选一点作为根），回溯时求出它到底层的最长路和次长路，然后再对于每个点i，枚举这个点到根的每个点j，若这一段ij不在j的最长路上，那么用ij长+j的最长路更新i点值，若这一段ij在j的最长路上，那么用ij长+j的次长路更新i点值。另外还有一个树形动规的方法，貌似很难实现：从底层到根，一层一层来，对于一条边u,v，求出去除其后，以u为根，最长的一条 路径（有边就是路，不管是子是父）就等于u连出的边的目标点的最长路径值，然后对v为根也做一遍。最后，加一个废点指向根，求出经过根的最长路径。这个方法被指有误！不知道是我听错了还是怎么地。哪位大牛能给我讲讲这个树形动规的方法？

判断

Compare

时间限制：1s

空间限制：128M

【题目背景】

这不是道水题！这真的不是道水题！这绝对不是道水题！！！

【题目描述】

给你一个n(n<=1000)个点m(m<=n*（n-1）/2)条边的图和k(k<=100)个程序对这个图做从点1到点n的最短路后得到的的结果，写一个compare判断谁的输出最优。

【输入数据】

第一行三个数n，m，k。

接下来m行，每行三个数a，b，data表示点a到点b有一条长度为data的无向边（任意两点间最多只有一条边）。

接下来k行，每行为一个程序得到的路径方案(保证路径方案的长度不超过2000)。

【输出数据】

如果所有输出均不合法，输出’Wrong‘，否则输出一个保留4位小数的实数，表示k个人得出结果中最小的一条合法路径长度。

Sample

Compare.in

3 3 4

1 2 5.2000

2 3 3.5000

3 2 6.0000

1 2 3 2 3 2 3 2 3 2 3 2 3

1 2 2 3 3 3

1 3

1 3 2 3

Compare.out

8.7000

Solve:

我觉得这道题目内容和上一道题的标题很配。

最优序列

Best

时间限制：1s

空间限制：128M

【题目背景】

背景的意义就是没人看得懂……

题目的意义就是没人做得出……

【题目描述】

给出一个长度为n(n<=1000) 的正整数序列，求一个子序列，使得原序列中任意长度为m 的子串中被选出的元素不超过k(k<=m<=10) 个，并且选出的元素之和最大。

【输入数据】

第一行三个数n,m,k 。

第二行n 个数，表示各元素数值大小。

【输出数据】

一个数，表示最大元素和。

Sample:

Best.in

10 4 2

7 3 4 8 2 6 5 7 4 8

Best.out

36

Solve:

与其说是动规，还不如说是搜索。以一个二进制串表示状态情况，然后考虑第i个取不取时，若第i-m个状态值为0，那么这个i状态值一定为0，否则枚举0,1。冷吧！