作者costbook (CB)
看板C_and_CPP
標題Re: ACM 10789 ... 又是一個Wrong Answer
時間Mon Jul 3 20:00:01 2006
嗯...雖然解出來了，不過有個時間最佳化的問題，
這是一小段code
//如果字元出現次數為質數，則印出該字元
for(int i=48;i<ASCII_PRINTABLE_MAX;i++){
if(ascii[i]>1 && isPrime(ascii[i])){
prime=true;
putchar(i);
}
本來把"字元出現次數"歸零的工作
，是放在下面，不過我想在這邊順便
歸零，於在這邊是加入這段
mascii[i]=0;
，然後把下面綠色的拿掉。結果我自己試
ok，送出去又不行了...看起來從if後面把ascii[*]
歸零都可以啊
}
//若沒有出現次數為質數的字元，印出empty
if(!prime)
cout<<"empty";
putchar('\n');
prime=false;
//字元出現次數歸零
for(int i=48;i<ASCII_PRINTABLE_MAX;i++)
ascii[i]=0;
}
完整+色彩標示的code
http://costbook.googlepages.com/10789-3_cpp.html
※ 引述《ledia (contemplation)》之銘言：
: ※ 引述《costbook (CB)》之銘言：
: : char ascii[ASCII_PRINTABLE_MAX];
: 如果出現次數大於 128, 甚至 256
: 用一個 char/unsigned char 就計不下了
: 所以你 2001 剛好是對的真的運氣很好
: 我用 1999 測, 你的程式就錯啦 :p
: 我以前也死在這種小地方過 Orz
: 重點就是多測點測資, 看看有沒有異常囉
--
年度6大搞笑發言
同學A：機械式鍵盤耶，好爛喔... │同學D：這是個4對16的多工器
同學B：腳踏車也有碟煞喔，騙誰...│同學E：我要寫遊戲外掛
同學C：iPod的音質很好 │同學F：C++除了class，根本就和C一樣
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.139.153.131
1F：→ costbook:1ACM online judge的系統真的怪怪的... 07/03 20:13
2F：→ costbook:我把這三行宣告的順序換了一下 07/03 20:13
3F：→ costbook: int count=0; 07/03 20:13
4F：→ costbook: bool prime=false; 07/03 20:13
5F：→ costbook: char in; 07/03 20:13
6F：→ costbook:就出現runtime error，換回來又好了... 07/03 20:13
7F：→ costbook:不過歸零的問題還是搞不懂 07/03 20:27
8F：推 ledia:如果我沒算錯的話, 你新的 code, ascii 只有 126 格 07/03 21:01
9F：→ ledia:但是 ASCII_PRINTABLE_MAX 是 127 07/03 21:01
10F：→ ledia:因此你歸零會歸到 ascii[126] 這是會出問題的 07/03 21:02
11F：→ ledia:run-time error 或 wrong answer 可能因此而來 07/03 21:02
12F：→ ledia:對了, 寫到第 ascii[126] 時, 就是寫到之前的 stack var 07/03 21:03
13F：→ ledia:也就是 in, prime 那些變數 07/03 21:03
14F：→ ledia:這次我只用看的, 沒測過, 有沒有別的問題我就不知道了 07/03 21:04
15F：推 costbook:對耶...謝啦 (不過只快了0.001秒...) 07/03 21:07
16F：推 ledia:這個加不了多快的... 07/03 21:16
17F：→ ledia:要加快的話, 我建議把 prime 先算好存在 table 裡... 07/03 21:16
18F：→ ledia:最一開始一次算出來, 以後怎麼查都是一次 table-lookuup 07/03 21:17
19F：→ ledia:isPrime 才應該是瓶頸處 07/03 21:18
20F：→ ledia:然後, 分三段 for 可能可以減少一點時間.. 也可能減不了 07/03 21:19
21F：→ ledia:不過至少少 process 一些不可能出現的字元 07/03 21:19
22F：→ ledia:歸零也不需要每個都歸, ascii[i]>0 和 isPrime 拆開 07/03 21:20
23F：→ ledia:ascii[i] > 0 時才需要歸零 07/03 21:21
24F：→ ledia:想到的大概就這些.. 再麻煩一點的.. 就懶得想了 XD 07/03 21:21
25F：推 costbook:好方法，來試試看 07/03 21:27
26F：推 costbook:結果：時間一樣，記憶體用量變大.可能試測資太小， 07/03 21:45
27F：→ costbook:所以看不出效果....算了，去研究下一題了 07/03 21:46
↑我自己發文的...我幹嘛用推文回啊
※ 編輯: costbook 來自: 220.139.153.131 (07/03 21:48)
28F：推 drkkimo:= =...||| 07/03 21:49
29F：→ drkkimo:解說完整喔~ 收錄精華裡給其他人(新手)參考 07/03 21:49
30F：推 cplusplus:用篩法 大概0.008 參考一下吧 07/03 22:36
31F：推 drkkimo:嗯 不過篩法花空間~ 07/03 23:14
32F：推 cplusplus:這一題空間很小啦 而且現在排名排時間 時間比較寶貴XD 07/03 23:51
這個...我寫出來的篩法....好像不太對，
雖然拿了accpeted...
//利用篩法清除非質數
inline void sievePrime(int *ptr){
for(int i=2;i<2001;i++){
if(i*i>=2001/2)
break;
for(int j=48;j<ASCII_PRINTABLE_MAX;j++){
if(ptr[j]==1)
ptr[j]=0;
else if(ptr[j]==2);
else if(ptr[j]>i && ptr[j]%i==0)
ptr[j]=0;
}
}
}
※ 編輯: costbook 來自: 220.139.153.35 (07/04 15:42)