國(guó)家集訓(xùn)隊(duì)作業(yè)anti-arithmetic permutations解題報(bào)告

1、反等差數(shù)列解題江蘇省常州高級(jí)中學(xué)問題描述用 1 到 n 這 n 個(gè)整數(shù)排成一個(gè)數(shù)列ai，使得數(shù)列中不含等差數(shù)列。ai中含等差數(shù)列就是指存在 3 個(gè)下標(biāo) I,j,k(ijk)使得 aj-ai=ak-aj。數(shù)據(jù)限制：3=n=1000000。題目來源POI1996 Stage3 Problem 4算法分析如果 ai,aj,ak(ijk)等差數(shù)列，由奇偶性不難得出這三個(gè)數(shù)的奇偶情況只可能有 4種：都是奇數(shù)，都是偶數(shù)，奇偶奇或者偶奇偶。這意味著什么呢？如果把 1 到 n 當(dāng)中的奇數(shù)排面，偶數(shù)排在后面，顯然就避免了后兩種情況的發(fā)生。即使有等差數(shù)列出現(xiàn)，也只能出現(xiàn)在排面的奇數(shù)序列和排在后面的偶數(shù)序列當(dāng)中。那

2、么如何處理奇數(shù)序列呢？很簡(jiǎn)單。把每個(gè)數(shù)加 1 再除以 2，原來 1,3,5,就相應(yīng)地變成了 1,2,3,。對(duì)偶數(shù)序列也可以進(jìn)行類似的處理。1 到 n 的整數(shù)中偶數(shù)的個(gè)數(shù)是n/2，奇數(shù)的個(gè)數(shù)是 n-n/2，這樣一來，就把規(guī)模為 n 的問題拆分成了兩個(gè)規(guī)模分別為n/2和 n-n/2的子問題。程序的實(shí)現(xiàn)可以用化搜索。開一個(gè) 1.n 的數(shù)組 b，bi是一個(gè)長(zhǎng)度為 i 的鏈，表示用1 到 i 的整數(shù)排成的一個(gè)滿足條件的序列。注意，并不是所有的 bi都需要計(jì)算的，只需要計(jì)算有用的。比如 n=9 時(shí)，要知道 b9就必須知道 b4和 b5，要知道 b4就必須知道 b2，要知道 b5就必須知道 b2和 b3，要

3、知道 b2就必須知道 b1，要知道 b3就必須知道 b2和 b1，所以當(dāng) n=9 時(shí)，只要計(jì)算 b1,b2,b3,b4,b5,b9就可以了。下面估算一下這個(gè)算法的時(shí)空復(fù)雜度。先來看空間復(fù)雜度。因?yàn)樵谡麄€(gè)過程中只是在添加結(jié)點(diǎn)，所以只要考慮最后的空間就可以了。為了敘述方便，把一條鏈中每一個(gè)結(jié)點(diǎn)的空間大小都看作一個(gè)。因?yàn)?bi是一條長(zhǎng)度為 i 的鏈，所以占用的總空間就是所有需要計(jì)算的 i 的和。比如 n=9 時(shí)，占用的總空間就是 1+2+3+4+5+9=24 個(gè)。考慮一個(gè)很大的 n，要計(jì)算 bn最多只要知道 bm和bm+1就可以了（m=n/2）。把 bn叫做第一層，bm和 bm+1叫做第二層，要知道

4、第二層需要知道的鏈叫做第三層，。不難用數(shù)學(xué)歸納法證明：每一層最多只有兩條鏈，而且它們的下標(biāo)是相鄰的整數(shù)。因?yàn)榈?i 層的鏈長(zhǎng)度約為 n/2i-1 個(gè)(n+n/2+n/4+)*2=2n，空間復(fù)雜度為O(n)。，所以總的空間約等于再來看時(shí)間復(fù)雜度。由于使用了化搜索，程序沒有任何的重復(fù)計(jì)算，而且計(jì)算一條鏈只需要把兩條鏈的內(nèi)容掃描一遍就可以了，所以時(shí)間復(fù)雜度就等于空間復(fù)雜度，也是 O(n)的。因此這個(gè)算法的效率是相當(dāng)高的。源程序Program Sequence;ConstInputFile=seq.in; OutputFile=seq.out;Maxn=1000000;TypeLink=Node;No

5、de=Record data:Long; next:Link;End;Vara:Array 1.Maxn of Link;n:Long;Procedure Read_Data; BeginAssign(Input,InputFile); Reset(Input);Read(n); Close(Input);End;Procedure Work(n:Long Vard,p:Link; BeginIf an=Nil ThenBegin);Work(n div 2); Work(n-(n p:=an div 2;While pNil DoBegindiv 2);New(d); d.data:=p.d

6、ata*2; d.next:=an; an:=d; p:=p.next;End;p:=an-(n div 2); While pNil Do BeginNew(d); d.data:=p.data*2-1; d.next:=an; an:=d; p:=p.next;End;End;End;Procedure Solve; BeginFillchar(a,Sizeof(a),0);New(a1); a1.data:=1; a1.next:=Nil; Work(n);End;Procedure Answer;Varp:Link; BeginAssign(Output,OutputFile); Rewrite(Output);p:=an;While p