Login with GitHub. Nope?
修正 C++ 的程式碼在使用一定量動態記憶體後會產生 RF 的問題 @ 2019/12/6 4:45pm NeoHOJ 強勢復活中 (Open beta)
Submit  Ranklist

Problem : 309 - Algorithm Speedup

Problem Statistics

Solved Member: 2  Submission: 15  User Tried: 3

Statement:

請你計算F(x,y)的值,其中x,y皆是一個數列,x=(x1,x2...xn),y=(y1,y2...ym)。

Boolean F(x,y)
{
  if W(x) ≠ W(y)
    return 0
  else if |W(x)| = |W(y)| = 1
    return 1
  else
    return F(p(x),p(y)) ^ F(s(x),s(y))
}

其中:

•W(x)為數列x的數字集合 (每種數字的個數與順序不重要)
•p(x)為數列x的最長前綴,並滿足W(x) ≠ W(p(x))
•s(x)為數列x的最長後綴,並滿足W(x) ≠ W(s(x))
• ^ 為Boolean運算,A ^ B = 1 唯若且若 A,B 皆為 True
•|W(x)|為數列x的數字種類

例如,若x=(2,3,7,2,7,4,7,2,4),則W(x)={2,3,4,7},p(x)=(2,3,7,2,7),s(x)=(7,2,7,4,7,2,4),|W(x)|=4。

由於遞迴計算F(x,y)太慢了,請你想辦法使他計算更快,每筆測試資料會給定x,y數列,請你輸出F(x,y)。

Input:Output:

第一行為k (1 ≤ k ≤ 13),表示共有 k 筆測試資料。

每筆測試資料佔三行,第一行為n,m (1 ≤ n,m ≤ 100000),分別表示x數列與y數列的長度,第二行有n個數字表示x數列,第三行有m個數字表示y數列,數列的值皆不大於100。
對於一筆測試資料輸出一行0或1。

Sample Input:Sample Output:

2
4 5
3 1 2 1
1 3 1 2 1
7 7
1 1 2 1 2 1 3
1 1 2 1 3 1 3
0
1

Source:

POI 16 Stage 1

Problem Setter

Testdata:

TestTimeMemoryScore
01000ms65536kb
1-11000ms65536kb10
1-21000ms65536kb
2-11000ms65536kb10
2-21000ms65536kb
3-11000ms65536kb10
3-21000ms65536kb
4-11000ms65536kb10
4-21000ms65536kb
512000ms65536kb10
612000ms65536kb10
712000ms65536kb10
812000ms65536kb10
912000ms65536kb10
1012000ms65536kb10