.棋盘上的士兵_solution.pdfVIP

Soldier的解题报告 中山纪念中学高二(19)班 陈启峰 January 25, 2007 题目 在一个 N 行 M 列的棋盘上，摆放着 K 个士兵，一个士兵占据一个 格子(可能有多个士兵占据同一个格子)。 第 i 个士兵控制棋盘上所有与它相距不超过 Ri 的格子。 两个格子(X1,Y1)、(X2,Y2)间的距离定义为|X1-X2|+|Y1-Y2|。 现在给出 K 个士兵的坐标，请你写一个程序返回被控制的格子的 总数。 输入格式 第 1 行： 三个正整数 N、M 和 K。 第 2 ~ K+1 行： 每行三个自然数 X 、Y 和 R 。 X 表示士兵所在的行的编号； Y 表示士兵所在的列的编号； R 表示士兵的控制范围。 输出格式 第 1 行： 被控制的格子的总数。 数据范围 在 15%的数据中，1≤N,M ≤1000，1≤K≤100 在 25% 的数据中，1≤N,M ≤5000，1≤K≤100 在 35% 的数据中，1≤N,M ≤10000，1≤K≤100 在 50%的数据中，1≤N,M ≤100000，1≤K≤100 在 65%的数据中，1≤N,M ≤100000000，1≤K≤100 在 80%的数据中，1≤N,M ≤100000000，1≤K≤1000 在 100%的数据中，1≤N,M ≤100000000，1≤K≤100000 样例输入 4 4 3 1 1 1 3 1 1 3 3 1 样例输出 10 初步分析： 看完这一个题之后，可能很多读者都对此题没有思路。所以我们 首先得分析一下一个棋盘上的士兵控制的区域到底是什么样子的。 1、画一个中等大小的棋盘： 图１: 一个 10 ×10 的棋盘 2、放一些士兵在棋盘中，画出它控制的所有格子。 图 2 : 黑点表示士兵，红点和黑点是被控制的方地 当棋盘上只放一个士兵的时候，被控制的区域就像一个偏斜 45 度的正方形。我们可以把这些区域看成一个偏斜 45 度的完美正方形 吗？再看看下图： 图 3 ：黑点表示士兵，红点和黑点是被控制的方地 这样看来就没有什么规律了。比如最右边的士兵控制的区域有一 半被棋盘切去了。再说，除去这棋盘的限制地把一块区域都看成一个 正方形，我们又该怎么样转化，又该如何等价起来呢？我估计这问题 不易被解决。 深入分析： 我们尝试将棋盘奇偶染色。这样图２被转达化为下图 图 5 : 黑点表示士兵，红、绿和黑点是被控制的地方 这样来看，该图中的红点和绿点所组成的点集可以分别被转化一 个正方形： (1)绿色： 将每一个绿点绕其左下点逆时针转 45 度。 图 6 : 绿点是被控制的地方 看到了吗？只要把每个方形放大就是一个大的正方形了。为了计 算处理，我们同建立起直角坐标系： 图 7 : 转化后的一个大正方形 我们设正方形的左下角的坐标(x,y)表示一个正方形。这样原来的 x y +y x − (x,y)就变成了( , ) 。 2 2 (2)红色： 情况与绿色的相似。 在这样分析之后，我们的思路就开始清淅了。 算法分析： 正当前途一片光明时，N×M 的棋盘这一限制破坏这优美的性质 呢。怎么样办呢？很多做这题的人都卡在了这一个问题上。其实我们 可以先不考虑棋盘地区性计算士兵的控制面积，然后再算棋盘之外的 控制面积。 这样，算法的总体框架就出来： 子算法 1——忽略棋盘后