第四題:(magic)
方案一:
暴力,四重循環,枚舉每一個數字的在每個位置出現的個數,然後再加起來即可
理想分數:35~45分
方案二:
我們可以用一個數軸來表示出四個數的位置:
A B C D
__|____|_________|___|____
2i 6i+k i
從題意中我們可以得出xB~xA=2(xC~xD)
(xC~xB)÷3>xB~xA 那麼 xC~xB>3(xB~xA) 然後xC~xB=3(xB~xA)+k{k為任意值} 最後 xC~xB=6(xC~xD)+k
設xC~xD=i 那麼 xA~xB=2i,xB~xC=6i+k;
那麼就需要枚舉i 和 xC的位置和xB 的位置,因為k是拿不準的。
加答案時就隻用乘另外3個數在輸入時出現的個數。
Inc(a[j,1],w[i1]*w[k]*w[l]);
這樣就可以很快的算出所有方案的個數。
理想分數:80~85分
方案三:
那麼我們隻能想想100分方法了。
根據上面的方法,我們可以想到一個絕妙的n方的方法。
首先枚舉i,這個免不了,然後算出字首和和字尾和。
還是剛剛那個圖:
A B C D
__|____|_________|___|____
2i 6i+k i
我們算出字尾和就是到達C最小的取值範圍8i+1.
Sj 表示到j這個位置最多有多少個C和D可以存放的位置。
S[j]=S[j+1]+w[j]*w[k];
J是枚舉C的位置的,k是由C算出的D的位置,w[i]就是表示i這個數在輸入時出現的次數。
這樣就可以有效的枚舉出C和D在後面出現的個數。
在枚舉A的位置,算出B的位置,再像上次一樣加答案:
Inc(a[j,1],S[k+6i+1]*w[k]);
K就是由j算出來的B的位置,k+6i+1就是目前C最小的位置,再乘一個B的個數。這樣就相當于85分方法的三個數相乘。
算字首和同理,用來算C和D的方案數。
代碼:
var
a:array[1..15000,1..4]of longint;
b,w:array[0..40000]of longint;
n,m,i,j,k,l,i1:longint;
s,s1:array[0..15001]of longint;
bz:boolean;
begin
assign(input,'magic.in');reset(input);
assign(output,'magic.out');rewrite(output);
readln(n,m);
for i:=1 to m do
begin
readln(b[i]);
inc(w[b[i]]);
end;
for i:=1 to n div 9 do
begin
fillchar(s,sizeof(s),0);
fillchar(s1,sizeof(s1),0);
for j:=n-i downto 8*i+1 do
s[j]:=s[j+1]+w[j]*w[j+i];
for j:=1 to n-8*i do
begin
i1:=j+i*2;
if (w[i1]>0)and(w[j]>0) then
begin
inc(a[j,1],s[j+8*i+1]*w[i1]);
inc(a[i1,2],s[j+8*i+1]*w[j]);
end;
end;
for j:=2*i to n-7*i-1 do
s1[j]:=s1[j-1]+w[j]*w[j-2*i];
for j:=8*i+1 to n-i do
begin
i1:=j+i;
if (w[i1]>0)and(w[j]>0) then
begin
inc(a[i1,4],s1[j-6*i-1]*w[j]);
inc(a[j,3],s1[j-6*i-1]*w[i1]);
end;
end;
end;
for i:=1 to m do
writeln(a[b[i],1],' ',a[b[i],2],' ',a[b[i],3],' ',a[b[i],4]);
close(input);
close(output);
end.