/*
演算法：
1.先輸入第一列字串，並儲存於一個linklist中
2.邊輸入第二列數字，並比較與第一列的linklist是否有相同的地方
怎麼改進TLE呢？Orz
*/

# include <iostream>

using namespace std ;

struct NumNode {
  long int num ;
  NumNode *next ;
} ;

typedef NumNode *NumPtr ;

void InputASeriesNum( NumPtr & head, int formnum ) {
  if ( formnum == 0 )
    return ;

  head = new NumNode ;
  head->next = NULL ;
  cin >> head ->num ;

  InputASeriesNum( head->next, formnum - 1 ) ;

} // InputASeriesNum()

void PrintAllNum( NumPtr head ) {
  if ( head == NULL )
    return ;
 
  cout << head->num << " " ;
 
  PrintAllNum( head->next ) ;

} // PrintAllNum()

int main() {

  int testnum = 0, formnum = 0 ; // 測資數量、一組的數字數量
  int samenum = 0 ; // 相同的數
  long int nowtest = 0 ; // 正在測試的數
  NumPtr head = NULL, walk = NULL ;

  cin >> testnum >> formnum ;
  for ( int i = testnum ; i > 0 ; i -- ) {
    samenum = 0 ;
    // 現在輸入第一組數字
    InputASeriesNum( head, formnum ) ; 

   
   
    for ( int j = formnum ; j > 0 ; j -- ) {
    // 現在輸入第二組數字並比較和儲存過的第一組是否相同
      cin >> nowtest ;
      for ( walk = head ; walk != NULL ; walk = walk->next ) {
      // 開始比較 
        if ( nowtest == walk->num ) {
          samenum ++ ;
          break ;
        } // if

      } // for // 比較     
      
    } // for 輸入

    cout << samenum << endl ;

  } // for

  return 0 ;

} // main()

這題用linked-List又慢又麻煩~

用Space trade-off 空間換時間

直接開 unsigned int[100001] 來記錄不就解決了

 這題時間複雜度用  linked-List: O(N^2)

                         Array: O(N)

他既然跟你講是遞增(非嚴格??)

你就先輸入一列

1 2 4 6 8 10

假如找 3 5 6 8

你用  binary search 找3(left=0, right =n)

現在你用 b search 繼續找 5 (left <=3的位置, right=n)

再用 b search 找 6 (left <=6的位置, right=n)

我的建議是不要用 cin/cout

改用 scanf/ printf 吧

用習慣就好. 

 這樣可以縮減time

短暫測試了guest所說的用空間換時間....

 結果還是TLE Orz，看來只能回去研究naiee_liao 所說的binary search了！謝謝指教

 (剛剛改過，仍是TLE的程式碼：)

# include <stdio.h>

int main() {

  long int testnum = 0, formnum = 0 ; // 測資數量、一組的數字數量
  long int samenum = 0 ; // 相同的數
  long int nowtest = 0 ; // 正在測試的數
  long int firstseries[100001] ;

  scanf( "%ld%ld",&testnum, &formnum ) ;
  for ( long int i = testnum ; i > 0 ; i -- ) {
    samenum = 0 ;
    // 現在輸入第一組數字
    for ( long int k = 0 ; k < formnum  ; k ++ ) 
      scanf( "%ld", &firstseries[k] ) ;
   
   
    for ( long int j = formnum ; j > 0 ; j -- ) {
    // 現在輸入第二組數字並比較和儲存過的第一組是否相同
      scanf( "%ld", &nowtest ) ;
      for ( int k = 0 ; k < formnum ; k ++ ) {
      // 開始比較 
        if ( nowtest == firstseries[k] ) {
          samenum ++ ;
          break ;
        } // if

      } // for // 比較     
      
    } // for 輸入

    printf( "%ld\n", samenum ) ;

  } // for
  return 0 ;

} // main()

這題用Binary Search 時間要 O(NlogN)而空間也要0(N) , 所以還是用Space trade-off比較好

 會TLE的原因是Space trade-off 不是這樣用的

 用Space trade-off判斷是只需O(1)   你把他寫成判斷要O(N)...........

如果O(1)應該陣列要夠放吧

題目規定的數到2^64-1 

謝謝你的回答！

不過請問可以指教的詳細一點嗎？因為我還是個學生，懂的不是很全方面，

 Space trade-off 是指linked list吧？

 那所謂的O(1)和O(N)的差別是什麼？？(我是連O(1)都搞不清楚是什麼的人...Orz)

 又如何實作呢？

 如果可以的話，麻煩再指教一些，謝謝！

一個比較普通的方法, 就是對每個在第二組數列的數, 都去尋找是否有出現在第一組數列中,

而去尋找是否在第一組數列中要找 N 次, 而第二組數列有 N 個數, (註：題目上是用 M 而不是用 N)

所以總共要找 N*N 次, 也就是時間複雜度為 O(N^2) ....

不過因為這兩個數列都是嚴格遞增, 所以你不用找得這麼辛苦,

你可以用兩個變數 i、j 各代表目前找到第一、二組數列的第幾個,

如果第一組數列的第 i 個數 A[i] 比第二組數列的第 j 個數 B[j] 大,

則把 j 加 1 , 再繼續比下去,

而如果 A[i] < B[j] , 則 i 加 1 ,

最後如果 A[i]==B[j] , 則把記錄共同的數有幾個的變數加 1 ,

再把 i、j 同時加 1 , 直到 i 或 j 有一個已經超出數列的範圍為止,

這樣最多就是找 N*2 次, 也就是時間複雜度為 O(N) ,

用這樣的寫法就不會 TLE 了....

謝謝回答！有些眉目了！感激！

加強到什麼境界了

都沒辦法AC =口=...

原先1分的程式碼 重傳也是0分

可是這題給看了也很難知道錯哪裡或是速度阿

又因為測資組數不多，一定有人會直接送出答案。 

這邊的系統好像又沒處理好換行問題了

就是題目兼測試資料編輯那裡

已重測 變成 NA score:1 

所以現在是系統的問題囉? ...吃了一堆NA

= ="

測資太大，需要加輸入優化...

不過題目測資出成這樣從根本上就不是在考演算法的正確性了。

var
  a,b:array[0..1000000] of qword;
  m,n,i,j,k,ans:longint;
begin
  readln(n,m);
  for k:=1 to n do
    begin
      ans:=0;
      for i:=1 to m do
        read(a[i]);
      for i:=1 to m do
        read(b[i]);
      i:=1;
      j:=1;
      while (i>0) and (j>0) do
        begin
          while (a[i]<b[j]) and (i>0) and (j>0) do
            if i=m then
              i:=0
              else
                inc(i);
          if (a[i]=b[j]) and (i>0) and (j>0) then
            begin
              inc(ans);
              if i=m then
                i:=0
                else
                  inc(i);
              if j=m then
                j:=0
                else
                  inc(j);
            end;
          while (a[i]>b[j]) and (i>0) and (j>0) do
            if j=m then
              j:=0
              else
                inc(j);
          if (a[i]=b[j]) and (i>0) and (j>0) then
            begin
              inc(ans);
              if i=m then
                i:=0
                else
                  inc(i);
              if j=m then
                j:=0
                else
                  inc(j);
            end;
        end;
      writeln(ans);
    end;
end.

d478用这个AC了，放到这里就一个RE一个TLE。。。死活想不通。。。求解。。。

这道题太恶心了，我用scanf("%llu")读超时，用getchar()优化才过

#include <cstdio>

using namespace std;

const int NUM = 1000000;

unsigned long long N[NUM];

int main()

{

int n, m;

scanf("%d%d", &n, &m);

getchar();

while (n--)

{

for (int i = 0; i < m; i++)

{

N[i] = 0;

for (char c; (c = getchar()) && '0' <= c && c <= '9'; N[i] = 10 * N[i] + c - '0');

};

int sum = 0, l = 0;

for (int i = 0; i < m; i++)

{

unsigned long long t = 0;

for (char c; (c = getchar()) && '0' <= c && c <= '9'; t = 10 * t + c - '0');

while (l < NUM && N[l] < t)

l++;

if (l < NUM && N[l] == t)

{

sum++;

l++;

};

};

printf("%d\n", sum);

};

return 0;

}