先说一下解题过程：
爆破肯定不行，题目结尾也给出了。那只能考虑别的思路。由题目中的输入输出格式（都是线段）我们可以想到：输入中的线段端点与输出中的线段端点有关系，可以以此为突破口。
我首先假设的是，推论一：output线段起点一定在input线段端点（起点和终点）的九宫格覆盖内（这里的覆盖可以回绕，即跨行，见下图，图中绿色方格能够覆盖所有红色标记的方格）
后来经过验证，发现一个更严格的条件，推论2，除了左下角以外的所有output线段起点，都在input线段起点的九宫格覆盖内。以下对一般情况进行证明（其他边界或者特殊情况类似，不再赘述）：
1. 考虑除了左下角以外的所有output线段起点：
反证法：考虑除了左下角以外的所有output线段起点, 假设存在一个起点不在input线段起点的九宫格覆盖内，那么在input中肯定是下面的情况：
绿色点为output线段起点，由于该图中没有起点，所以图中同一行元素只能是相同的。由于第一列的元素肯定都不是起点，即前面肯定还有相同的点，即下图：
此时黄色点和绿色点，在output中的值一样，所以绿色点肯定不是output中的线段起点，与假设矛盾。
注意：如果没有那么多列，可以进行回绕来得到上图，对于上下边界情况，是残缺的九宫格，但结论是一样的，感兴趣的可以证明一下。
2. 左下角为output起点的情况，看下图：
在上图中我标出了绿色点的九宫格（回环后的），可以看出绿色点并不在某个input起点的覆盖内，但它确实是一个起点（与上图中的黄色字体所在格的output值不同）。
上面的推论一和推论二都是正确的，注意假设二中的左下角在右下角的的回环覆盖内的，所以也是正确的，下面是代码，使用推论二：
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #define PI 3.14159265359 int resset[9001][2], setcnt; // 0 表示1维索引, 1 颜色 int pair[1001][3]; // 0 value, 1 count, 2 accumulated count int w, h, pairs, pixels; int end[1001], numend; // 输入端点的1维索引 int cmp_func(const void *a, const void *b) { int x = *(int *)a, y = *(int *)b; if(x < y) return -1; else if(x == y) return 0; else return 1; } // bi-section search int getValue(int idx) { int start = 0, end = pairs-1; while(start < end) { int mid = (start + end) >> 1; if(pair[mid][2] <= idx) start = mid+1; else end = mid; } return pair[start][0]; } // int getValue(int idx) // { // for(int i = 0; i < pairs; i++) // { // if(idx < pair[i][2]) return pair[i][0]; // } // } int main() { int indeces[9][3] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1 }, {0, 0}, {0, 1}, {1, -1 }, {1, 0}, {1, 1}}; while(1) { scanf("%d", &w); if(0 == w) break; indeces[0][2] = -w-1;indeces[1][2] = -w;indeces[2][2] = -w+1; indeces[3][2] = -1; indeces[4][2] = 0; indeces[5][2] = 1; indeces[6][2] = w-1; indeces[7][2] = w; indeces[8][2] = w+1; memset(pair, 0, sizeof(pair)); memset(end, 0, sizeof(end)); memset(resset, 0, sizeof(resset)); numend = setcnt = pixels = 0; for(int i = 0; ; i++) { scanf("%d%d", &pair[i][0], &pair[i][1]); if(0 == pair[i][0] && 0 == pair[i][1]) { pairs = i; break; } pixels += pair[i][1]; if(0 == i) { end[numend] = 0; pair[i][2] = pair[i][1]; } else { end[numend] = end[numend-1] + pair[i-1][1]; pair[i][2] = pair[i-1][2] + pair[i][1]; } numend++; // if(pair[i][1] > 1) // 最初AC用的推论一 // { // end[numend] = end[numend-1] + pair[i][1] - 1; // numend++; // } } h = pixels / w; // 找出输出图像中所有的可能的端点 for(int i = 0; i < numend; i++) { for(int j = 0; j < 9; j++) { // int r = end[i] / w + indeces[j][0], c = end[i] % w + indeces[j][1]; // if(r < 0 || r >= h || c < 0 || c >= w) continue; // int idx = end[i] + indeces[j][2]; int idx = end[i] + indeces[j][2]; if(idx < 0 || idx >= pixels) continue; resset[setcnt][0] = idx; resset[setcnt++][1] = 0; } } // 左下角 resset[setcnt][0] = (h-1)*w; resset[setcnt++][1] = 0; for(int i = 0; i < setcnt; i++) { int curr = getValue(resset[i][0]), maxdiff = 0; for(int j = 0; j < 9; j++) { int r = resset[i][0] / w + indeces[j][0], c = resset[i][0] % w + indeces[j][1]; if(r < 0 || r >= h || c < 0 || c >= w) continue; int idx = resset[i][0] + indeces[j][2]; // get value at idx int val = getValue(idx); int diff = val - curr; if(diff < 0) diff = -diff; if(diff > maxdiff) maxdiff = diff; } resset[i][1] = maxdiff; } // sort qsort(resset, setcnt, 2 * sizeof(int), cmp_func); resset[setcnt][0] = pixels; // sentinel resset[setcnt][1] = -1; printf("%d ", w); for(int i = 0; i < setcnt; i++) { int start = i; while(resset[start][1] == resset[i+1][1]) i++; printf("%d %d ", resset[start][1], resset[i+1][0] - resset[start][0]); } printf("0 0 "); } printf("0 "); return 0; }