Description

平平帶著韻韻來到了游樂園，看到了n輛漂亮的遙控車，每輛車上都有一個唯一的名字name[i]。韻韻早就迫不及待地想玩名字是s的遙控車?？墒琼嶍嵁吘惯€小，她想象的名字可能是一輛車名字的前綴（也就是說能確定一個i，使s是name[i]的前綴），這時她就能玩第i輛車；或者是一個無中生有的名字，即s不是任何一輛車名字的前綴，這時候她什么也不能玩。
你需要完成下面的任務：
1.韻韻想了m個她想要的名字，請告訴她能玩多少次。
2.由于管理員粗心的操作，導致每輛車的擺放位置都可能出現微小的差錯，原來第i輛車現在的位置可能是i-1、i、i+1中的任意一個（第1輛車的位置不可能是0，第n輛車的位置不可能是n+1）。請你計算出共有多少種可能的排列。
注：數據保證當s是name[i]的前綴時，i是唯一確定的。一輛車可以玩多次。

Input

第一行是2個正整數n、m。
接下來n行，每行1個字符串name[i]，表示第i輛車的名字。
接下來m行，每行1個字符串s，表示韻韻想要的名字。

Output

第一行輸出韻韻能玩的次數。
第二行輸出共有多少種可能的排列。

Sample Input

4 4

Abcd

DeF

AAa

aBccc

Ab

AA

AbC

aBcc

Sample Output

3

5

Hint

對于題目涉及到的字符串嚴格區分大小寫，且長度小于255。
對于20％的數據 n≤10,m≤10；
對于40％的數據 n≤1000，m≤1000；
對于100％的數據 n≤10000，m≤10000。

題解

抱著第一題不會太難的心態看，然后就懵了 囧

第一問：

查找，判斷+統計。普通的暴枚會TLE，用一個神奇的優化方法把字符串轉成類似前綴和的東西比較，速度驟然上升

第二問：

先是一本正經列了一個2維dp如下

f[i][j]=f[i?1][j]+f[i?2][j?1]
表示前i輛車有j輛和右邊交換位置，因為和右邊換等同于和左邊換所以不作考慮
然后你就會發現j是個醬油
設f[i]表示前i輛車的總方案數，則
f[i]=f[i?1]+f[i?2]
這是什么？？？！！！！
斐波那契數列
由于數據大，要打高精度
嘗試過矩陣乘法，然后要打高精加和高精乘，于是我可恥地放棄了

代碼/pas:

typenum=recordv:array[1..3000]of longint;len:Longint;end;
varn,m,i,j,ans:Longint;st:array[0..10000,0..300]of real;l:array[0..10000]of longint;a:array[0..10000]of real;u,v,w:num;s:string;
function add(x,y:num):num;
vari,t:longint;
beginfillchar(add,sizeof(add),0);add.len:=y.len;if x.len>y.len then add.len:=x.len;t:=0;for i:=1 to add.len dobeginadd.v[i]:=(x.v[i]+y.v[i]+t)mod 10;t:=(x.v[i]+y.v[i]+t)div 10;end;if t<>0 thenbegininc(add.len);add.v[add.len]:=t;end;
end;
beginreadln(n,m);for i:=1 to n dobeginreadln(s);for j:=1 to length(s) dost[i,j]:=st[i,j-1]*1.9+ord(s[j]);end;for i:=1 to m dobeginreadln(s);l[i]:=length(s);for j:=1 to length(s) doa[i]:=a[i]*1.9+ord(s[j]);end;for i:=1 to n dofor j:=1 to m doif st[i,l[j]]=a[j] theninc(ans);writeln(ans);u.len:=1;u.v[1]:=1;v.len:=1;v.v[1]:=1;for i:=2 to n dobeginw:=add(u,v);u:=v;v:=w;end;for i:=w.len downto 1 do write(w.v[i]);writeln;
end.

轉載于:https://www.cnblogs.com/olahiuj/p/5781268.html

總結

以上是生活随笔為你收集整理的遥控车_vijos1458_纪中1724_水的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。