Posted on 2010-06-15 10:27
Onway 閱讀(229)
評論(0) 編輯 收藏 引用 所屬分類:
傷不起的ACM
今天完成了昨天剩下的一個水題。關于素數判斷的，用C寫三次CE后還是老老實實的用C++,但居然返回一個TLE。后來想想真的應得TLE，只能怪自己。總以為素數判斷用試除法的復雜度是O(N/2)，做了一些優化后4000+MS才過，但發現原來可以O(N^1/2)，改了后馬上回到16MS，也太強大了。
然后再看了一個DP。當時推了一下規律，推不出，覺得非常像數學題，分析過題目發現可以暴力打表，想想反正沒試過自己打表。便讓電腦跑了幾百億步，費時接近五十分鐘才出了結果。
發現程序運行的那段時間，CPU的占用率一直在33%左右，原來三核的CPU只用了一個核心運行，途中想研究一下多線程怎么個寫法，剩兩個核似乎有點浪費，但上網查了一下，太復雜了，就算了。
然后上泳課的路上回想discuss里的人都說是DP，再想便發現了一點規律，回來很快就推出DP方程了。還是用DP踏實一點。
用暴力費時四十多分鐘，用算法0秒。“提倡和諧，拒絕暴力”。