Posted on 2010-06-15 10:27
Onway 阅读(190)
评论(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秒。“提倡和谐，拒绝暴力”。