集训队作业fence解题报告

1、Fence 解题建立模型题目中允许每根木条最多削去m 个长度，处理起来甚是不便。先预处理：对每类木条，分别削去 0, 1, 2, , m，得到若干新的木条种类；然后将所有的木条综合，除去重复，得到的木条种类集合记为S。不妨令n = |S|，则问题的模型可以描述为：已知：集合 S，n = |S|。 求：一个正整数 p，使得：1、p 不能由 S 中的数通过加法运算得到。2、对所有的 q p，q 均能由 S 中的数通过加法运算得到。可见模型已与m 无关，其中的n p能不能由S 中的元素组成（“组成”即通过加法运算得到）。然而这样的 q 有无穷多个，不可能逐一判断之，必须合理的对所有自然数进行分类，然

2、后分而治之方是可行之法。设S 中最小的元素是u，则可以按照mod u 的值将所有自然数分成u 类。而且显然，如果t = ku + r（r u）可以由S 中的元素组成，那么任意的t = ku + r（r k）就都可以由S 中的元素组成。如果x 满足：x mod u = r。x 能由S 中的元素组成。x 是满足条件(1)、(2)的最小正整数。则记f(r) = x。显然，凡是不小于f(r)、模u 等于r 的数，都能由S 中的元素组成。接下来考虑如何求f。迭代法用迭代法求f 是十分容易想到的。第一步：赋初值。令所有的f(i) = +。对所有的 xS，如果满足 x f(x mod u)，则更新 f(x

3、mod u) = x。第二步：迭代。任取a, b（a u, b u），使得 f(a) + f(b) f(a + b) mod u)。如果找不到则“迭代”结束，否则更新f(a + b) mod u) = f(a) + f(b)。这样就求出了所有的f。然而迭代法的时间复杂度过高：O(n3)，实际应用中表现也比较差。因此不得不考虑优化算法。类 Dijkstra 算法上述迭代法十分类似最短路的迭代法；而问题模型本身也和最短路问题十分类似，于是我猜测是不是可以将解决最短路问题的高效算法 Dijkstra，通过一定改进，“移植”到本题上来呢？是肯定的。 第一步：赋初值。令所有的f(i) = +。对所有的

4、xS，如果满足 x f(x mod u)，则更新 f(x mod u) = x。同时给每个f(i)一个属性checki :优值。一开始所有的checki false。第二步：更新。，表示当前的f(i)是否能确定为最1、从所有满足 checki = false 的f(i)中选择一个最小值，记为f(p)；如果不存在这样的p，则结束算法。2、checkp true。3、如果q 满足：f(p) + f(q) f(a1) + f(a2) + + f(al)其中(a1 + a2 + + al) mod u = p。显然f(ai) = f(t + ai) mod u)。因此：f(p) f(a1) + f(a

5、2) + + f(al) = f(a1 + a2) mod u) + f(a3) + + f(al)= f(a1 + a2 + a3) mod u) + f(a4) + + f(al)= f(a1 + a2 + + al) mod u) = f(p)即f(p) f(p)，。命题得证。因此，原算法是正确的。完成f 值已然求出，余下的工作就十分简单了。设最后的结果为x；gi = fi / u（x表示取整）；g = maxgi。显然，凡是除以u 商为 g 的数，都能表示；故而x / u = g 1。如果某个p，满足：1、gp = g。2、p 是满足条件 1 的最大值。则x mod u = p。所以，

6、x = (g 1) * u + p。整个算法的时间复杂度是 O(n2)（1=n=3000）。小结此题的关键在于要对自然数按照mod u 的剩余类来划分，将复杂不可解的问题简化。另外对迭代法进行优化时，类比的方法也起到了重要作用。通过此题总结出一些基本经验：1、化难为易、化繁为简。2、大胆合理的联想、类比。程序constfin = fence.in; fout = fence.out; maxn = 3000;procedure pr(x : long); 输出 beginassign(output, fout); rewrite(output);if x = 0 then wrin(-1) e

7、lse wrin(x); close(output);halt;end;varmin :eger;f : array0 . maxn of long;procedure init; 初始化 varcheck : array-maxn . maxn of;i, j, x, n, m :begineger;assign(input, fin); reset(input);readln(n, m);fillchar(check, sizeof(check), false); for i := 1 to n do beginreadln(x);for j := x - m to x do checkj

8、 := true; end;close(input);min := 1; while not checkminnc(min);求 ufor i := 0 to min - 1 do fi := maxlong; for i := 1 to maxn doif checki and (i fi mod min) then fi mod min := i;end;f 数组赋初值procedure main; varcheck : array0 . maxn of;i, j, p :eger;tmp, minv : long; beginfillchar(check, sizeof(check), false); for i := 1 to min do beginminv := maxlong; p := -1;for j := 0 to min - 1f not checkj and (fj minv) then begin minv := fj; p := j;end;选最小的 f(p)if p = -1 then break; checkp := true;标记for j := 0 to min - 1f fj maxlongtmp := minv + fj;then begin更新if tmp ma