/*
演算法:
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
/*
演算法:
1.先輸入第一列字串,並儲存於一個linklist中
2.邊輸入第二列數字,並比較與第一列的linklist是否有相同的地方
怎麼改進TLE呢?Orz
*/
# include
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()
短暫測試了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)...........
這題用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)
又如何實作呢?
如果可以的話,麻煩再指教一些,謝謝!
謝謝你的回答!
不過請問可以指教的詳細一點嗎?因為我還是個學生,懂的不是很全方面,
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 了....
謝謝你的回答!
不過請問可以指教的詳細一點嗎?因為我還是個學生,懂的不是很全方面,
Space trade-off 是指linked list吧?
那所謂的O(1)和O(N)的差別是什麼??(我是連O(1)都搞不清楚是什麼的人...Orz)
又如何實作呢?
如果可以的話,麻煩再指教一些,謝謝!
所謂 O(1)就是程式的運算時間固定,跟題目的輸入無關。
例如:1+2+3+.....+99+100
如果用迴圈跑就會是 O(n) , n=100
如果用大家耳熟能詳的高斯公式解 (1+100)*100/2 (理論上)運算時間跟n無關 也就是 O(1)
他既然跟你講是遞增(非嚴格??)
你就先輸入一列
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
謝謝回答!有些眉目了!感激!
加強到什麼境界了
都沒辦法AC =口=...
原先1分的程式碼 重傳也是0分
謝謝回答!有些眉目了!感激!
加強到什麼境界了
都沒辦法AC =口=...
原先1分的程式碼 重傳也是0分
可是這題給看了也很難知道錯哪裡或是速度阿
又因為測資組數不多,一定有人會直接送出答案。
謝謝回答!有些眉目了!感激!
加強到什麼境界了
都沒辦法AC =口=...
原先1分的程式碼 重傳也是0分
可是這題給看了也很難知道錯哪裡或是速度阿
又因為測資組數不多,一定有人會直接送出答案。
這邊的系統好像又沒處理好換行問題了
就是題目兼測試資料編輯那裡
已重測 變成 NA score:1
就是題目兼測試資料編輯那裡
已重測 變成 NA score:1
所以現在是系統的問題囉? ...吃了一堆NA
= ="
就是題目兼測試資料編輯那裡
已重測 變成 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。。。死活想不通。。。求解。。。
谢谢回答!有些眉目了!感激!
风险值
甲,乙:数组[0 .. 1000000]的四字;
M,N和我,J型,K答:Longint型;
开始
readln(氮,男);
对k:= 1到n做
开始
答:= 0;
对于i:= 1米做
阅读(一[一]);
对于i:= 1米做
阅读(二[一]);
我:= 1;
记者:= 1;
而(我“0)和(j> 0)做
开始
而(一[一]0)和(j> 0)做
如果当时我=米
我:= 0
其他
公司(一);
如果(a [一] = B的研究[J])和(我“0)和(j> 0),则
开始
公司(答);
如果当时我=米
我:= 0
其他
公司(一);
如果j =米则
记者:= 0
其他
公司(十);
结束;
而(一[一]“乙研究[J])和(我”0)和(j> 0)做
如果j =米则
记者:= 0
其他
公司(十);
如果(a [一] = B的研究[J])和(我“0)和(j> 0),则
开始
公司(答);
如果当时我=米
我:= 0
其他
公司(一);
如果j =米则
记者:= 0
其他
公司(十);
结束;
结束;
writeln(答);
结束;
结束。
d478用这个交流了,放到这里就一个再生一个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;
}