PTT數位生活區 / C_and_CPP (C/C++)

Re: ACM 10789 ... 又是一個Wrong Answer

看板C_and_CPP (C/C++)作者 (CB)時間18年前 (2006/07/03 19:42), 編輯推噓9(9推 0噓 23→)
留言32則, 4人參與, 最新討論串1/1
嗯...雖然解出來了，不過有個時間最佳化的問題， 這是一小段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
→
07/03 20:13, , 1F
1ACM online judge的系統真的怪怪的...
07/03 20:13, 1F
→
07/03 20:13, , 2F
我把這三行宣告的順序換了一下
07/03 20:13, 2F
→
07/03 20:13, , 3F
int count=0;
07/03 20:13, 3F
→
07/03 20:13, , 4F
bool prime=false;
07/03 20:13, 4F
→
07/03 20:13, , 5F
char in;
07/03 20:13, 5F
→
07/03 20:13, , 6F
就出現runtime error，換回來又好了...
07/03 20:13, 6F
→
07/03 20:27, , 7F
不過歸零的問題還是搞不懂
07/03 20:27, 7F
推
07/03 21:01, , 8F
如果我沒算錯的話, 你新的 code, ascii 只有 126 格
07/03 21:01, 8F
→
07/03 21:01, , 9F
但是 ASCII_PRINTABLE_MAX 是 127
07/03 21:01, 9F
→
07/03 21:02, , 10F
因此你歸零會歸到 ascii[126] 這是會出問題的
07/03 21:02, 10F
→
07/03 21:02, , 11F
run-time error 或 wrong answer 可能因此而來
07/03 21:02, 11F
→
07/03 21:03, , 12F
對了, 寫到第 ascii[126] 時, 就是寫到之前的 stack var
07/03 21:03, 12F
→
07/03 21:03, , 13F
也就是 in, prime 那些變數
07/03 21:03, 13F
→
07/03 21:04, , 14F
這次我只用看的, 沒測過, 有沒有別的問題我就不知道了
07/03 21:04, 14F
推
07/03 21:07, , 15F
對耶...謝啦 (不過只快了0.001秒...)
07/03 21:07, 15F
推
07/03 21:16, , 16F
這個加不了多快的...
07/03 21:16, 16F
→
07/03 21:16, , 17F
要加快的話, 我建議把 prime 先算好存在 table 裡...
07/03 21:16, 17F
→
07/03 21:17, , 18F
最一開始一次算出來, 以後怎麼查都是一次 table-lookuup
07/03 21:17, 18F
→
07/03 21:18, , 19F
isPrime 才應該是瓶頸處
07/03 21:18, 19F
→
07/03 21:19, , 20F
然後, 分三段 for 可能可以減少一點時間.. 也可能減不了
07/03 21:19, 20F
→
07/03 21:19, , 21F
不過至少少 process 一些不可能出現的字元
07/03 21:19, 21F
→
07/03 21:20, , 22F
歸零也不需要每個都歸, ascii[i]>0 和 isPrime 拆開
07/03 21:20, 22F
→
07/03 21:21, , 23F
ascii[i] > 0 時才需要歸零
07/03 21:21, 23F
→
07/03 21:21, , 24F
想到的大概就這些.. 再麻煩一點的.. 就懶得想了 XD
07/03 21:21, 24F
推
07/03 21:27, , 25F
好方法，來試試看
07/03 21:27, 25F
推
07/03 21:45, , 26F
結果：時間一樣，記憶體用量變大.可能試測資太小，
07/03 21:45, 26F
→
07/03 21:46, , 27F
所以看不出效果....算了，去研究下一題了
07/03 21:46, 27F
↑我自己發文的...我幹嘛用推文回啊 ※ 編輯: costbook 來自: 220.139.153.131 (07/03 21:48)
推
07/03 21:49, , 28F
= =...|||
07/03 21:49, 28F
→
07/03 21:49, , 29F
解說完整喔~ 收錄精華裡給其他人(新手)參考
07/03 21:49, 29F
推
07/03 22:36, , 30F
用篩法 大概0.008 參考一下吧
07/03 22:36, 30F
推
07/03 23:14, , 31F
嗯 不過篩法花空間~
07/03 23:14, 31F
推
07/03 23:51, , 32F
這一題空間很小啦 而且現在排名排時間 時間比較寶貴XD
07/03 23:51, 32F
這個...我寫出來的篩法....好像不太對， 雖然拿了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)
‣ 更多 costbook 的文章
文章代碼(AID): #14gGA_37 (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 costbook 的文章
文章代碼(AID): #14gGA_37 (C_and_CPP)