差额阶段解题报告

1、Problem B Undecodable Codes不可分解的编码解题报告清华大学 毛子青题意描述给定n个01编码串S1,S2,Sn，你的任务是寻找一个编码串T，使得它至少可以被分解为两种不同的Si的排列。例如：给定5个01编码串：S1=0110，S2=00，S3=111，S4=001100，S5=110。那么一个符合要求的编码串T是：001100110，它有以下两种分解方法： 00+110+0110 (S2+S5+S1) 或 001100+110 (S4+S5)而0110110就不符和要求，它只有一种分解方法 0110+110 (S1+S5)。你要寻找长度最短的符合要求的编码串T。若有多个

2、符合要求的最短编码串T，则输出字典顺序最小的。题目规定n不超过20。算法分析算法1、搜索策略在题目给定的规模下，搜索策略是有效的。搜索的关键是要抓住编码串T的性质，也就是至少存在两种不同的分解方法。从搜索分解方法出发，同时搜索两种分解方法，可以大大减少搜索量。还是来看上面的例子：Step1： T=00第一种分解方法：S2 第二种分解方法：空Step2： T=001100第一种分解方法：S2+1100 第二种分解方法：S4Step3： T=001100 第一种分解方法：S2+S5+0第二种分解方法：S4Step4： T=001100110 第一种分解方法：S2+S5+S1 第二种分解方法：S4+

3、S5搜索完成，T=001100110。从上面的例子可以看出，搜索实际上是在两种分解方案的交替延伸中进行的。在搜索过程中，总是存在一种可行的完整的分解方案，而需要枚举延长另一种分解方案，这可能会导致T串的延长(如Step1到Step2)，这样知道两种分解方案都可行且完整，也就找到了一个可行解。从所有可行解中寻找长度最短的就是所求的。算法2、动态规划这道题还可以用动态规划求解。它仍然是采用与搜索策略同样的思路，所不同的是引入了记忆化的方法。仔细分析可以发现，在搜索的过程中，不完整的分解方案所无法匹配的剩余部分，如Step2中的1100和Step3中的0，一定是某个S编码串的后缀。于是，我们只要，将

4、所有的S编码串的后缀定义为状态，在搜索的过程中采用记忆化的方法记录已经计算过的所有状态的最优解，就可以避免重复运算，消除冗余。这正是动态规划的思路。下面阐述具体思路： 显然，初始时S1，S2均为空串。产生解的过程可分为若干步，每步选择一个串插在S1或S2的末尾，那么每个中间状态可以描述成下图所示。BBAA其中A为已匹配的部分，B为未匹配的部分。且B是某个数字串的后缀。这样我们可以定义状态di,j为：当B部分为第i个数字串的后缀wordi,j+1.lengthi时，A部分的最短长度。其中，wordi表示第i个串，lengthi为第I个串的长度。我们发现，其实后面的状态转移与A部分无关，仅与B部分

5、有关。因此，我们可以用动态规划的方法来解决这道题。问题转化为求最短路。初始时，其他如果存在wordk=wordi,1.j 且 ik 其他如果存在wordk=wordi,1.j 且 ik从某个状态di,j出发进行转移，可以分为两种情况：存在某个串wordk是wordi,j+1.length(s)的前缀，则di,j+lengthk = min di,j+lengthk，di,j+lengthk存在某个串wordk，使得wordi,j+1.length(s) 是wordk的前缀，则dk,lengthi-j = min dk,lengthi-j，di,j+lengthi-j最后的解是所有dk,leng

6、thk(k=1.n)中最小的一个。需要特别指出的是上面min函数的定义。因为题目要求找出的串是长度最短且在同长度的串中字典序最小的一个，因此，若长度不等时，可以直接取小的那个；若长度相等，则要追溯前面的状态，取字典序较小的那个。这与一般的动态规划是不太相同的，需要特别注意。虽然本题可以采用经典的求最短路算法来实现，但因为有可能要追溯前面的状态，为了编程方便，可以采用记忆化搜索的方式。另外，由于程序中需要大量用到查找某个字符串是否存在的操作，为了提高程序效率，我们可以用检索树的结构来存储，具体的方法参见数据结构的书中的有关章节。 解题小结 这是一道图论问题，但不经过仔细分析，不太容易看出模型。这

7、就要求我们熟练的掌握各种基本算法，同时对题目进行深入的研究。另外，灵活运用一些高级数据也对提高程序效率有着很大帮助。这是本次总决赛的第二题。它是我们在比赛的最后20分钟内编写完成并正确提交的，对我们最后取得第四名起到了重要作用。当时我们采用的搜索策略，主要是考虑到时间已经不足，而搜索编码的把握性较大，规模也可以承受。实践证明，当时的选择是正确的。程序清单为了测试方便，本程序采用单组数据输入。program match;const maxn=200; maxlen=100; maxs=maxn*maxlen+1; reslen=10000;type Tword=array1.maxlen of

8、char; Tresult=array1.reslen of char;var d:array1.maxn of Tword; len:array1.maxn of longint; tree:array1.maxs,1.2 of longint; data:array1.maxs of char; finish:array1.maxs of boolean; pass:array1.maxn,1.maxlen of longint; v:array1.maxn,0.maxlen of longint; prefix:array1.maxn,1.maxn of boolean; start,n

9、,i,j,k,s:longint; rlen:longint; result,now:Tresult;procedure insert(id:longint);var i,j,k:longint;begin j:=1; for i:=1 to lenid do begin if treej,1=0 then begin inc(s); datas:=did,i; treej,1:=s; j:=s; end else begin j:=treej,1; k:=0; while treej,20 do begin if dataj=did,i then begin k:=j; break; end

10、; j:=treej,2; end; if k=0 then if dataj=did,i then k:=j else begin inc(s); datas:=did,i; treej,2:=s; k:=s; end; j:=k; end; passid,i:=j; end; finishj:=true;end;function small:boolean;var i:longint;begin for i:=1 to rlen do if nowiresulti then begin small:=false; exit end; small:=false;end;procedure s

11、earch(l,p,last:longint);var i,j,k,a:longint;begin if l=p then begin if (lrlen then exit; j:=1; for i:=p+1 to l do begin if treej,1=0 then exit; j:=treej,1; while (j0) and (datajnowi) do j:=treej,2; if j=0 then exit; if finishj then if l=vlast,l-i then begin vlast,l-i:=l; search(l,i,last); end; end;

12、for i:=1 to n do if passi,l-p=j then begin a:=l; for k:=l-p+1 to leni do begin inc(a); nowa:=di,k; end; if alenj then begin prefixi,j:=true; for k:=1 to lenj do if di,kdj,k then begin prefixi,j:=false; break; end; end; rlen:=maxlongint; fillchar(v,sizeof(v),127); for i:=1 to n do for j:=1 to n do if