2012年8月18日星期六

排列(《算法竞赛入门经典》习题2-10)

本题(算法竞赛入门经典 第二章习题2-10)极水,我还写个解题报告,足以证明我有多弱菜了。

本题有多种做法,效率不一。下面介绍三种我使用的方法。
1、受本章开始的7744问题的启发,依次枚举abc,def,ghi,编写一个check()函数,用以判断这三个数是否把1~9的9个数字每个用了一遍,若是,则符合要求,输出。不幸的是,因为这样做不好判重(实际上也没有判重),用了5s左右才计算出所有四个解。舍弃之。
2、在网上搜索本题,发现真是有人把题目的最后一句(“提示:不必太动脑筋。”)理解得非常透彻,利用九重循环abcdefghi分别1~9,层层判重,最后一层判断是否合题目要求,是则输出。经我自己重新编写测试,出解大约需要0.85s。仔细阅读原程序后,发现有两个很好的优化:
(1)d可以直接从2a开始循环,g可以直接从3a开始循环,原因显而易见(a:b:c=1:2:3)。
(2)不必计算x=100a+10b+c,y=...,z=...然后判断xyz关系,直接用abcdefghi判断即可,这样可以节省大量时间。输出时用printf("%d%d%d,%d%d%d,%d%d%d\n",a,b,c,d,e,f,g,h,i);即可。
优化后,约0.15s出四解。

2012年8月1日星期三

高三前夕的随想

明天八月一日,又是一年开学时。这次,我们是要进入传说中最变态的一年——高三了。

    还有个位数的小时就要结束的这个暑假,也许会是高中毕业以前我所经历的最有意义而又最轻松的一个假期。

    说有意义,是因为我总算没有虚度这个20天的暑假。前几天,彻彻底底的放松,顺便重温一下已经放下一两个月的OI。然后就到了潍坊市的昌邑市(好别扭的说法),开始7天的信息学夏令营生活。在那里,我不仅系统地学习了信息学竞赛的知识,也丰富了人生经历,得到了很多生活经验、哲学思考和生活启示。Now I can't resist remembering it.(一个暑假没动英语!Now  I miss English so much that I can't help using it!!)(为了保持结构紧凑,有兴趣的reader请到这里阅读camp summary)23号下午从潍坊回到济南,我直接就跟闻达玩去了,让他请客吃饭看电影(嘿嘿),然后一直玩到24号下午,和赵志宇一起回了家。(我又想起了赵志宇用我的手机给我爸妈说不要来接了,做他家的车回去,@#……&**&~~……%¥#@)这回可真是满足了我看电影的欲望,先是看了《四大名捕》(from which I learned the idea that true love requires no deeds aiming to get it),然后看了《画皮II 3D》,这个是全当做看特效了,没啥感觉。(突然发现这么长时间没写英语,语法、词组什么的都忘干净了。)回到家,几天时间本来是打算认真练习学过的东西,但是,结果你懂的……只是练习了高精度和排序而已。。现在我做梦都梦见自己在打#include<iostream>。总是一不小心就到了NOIP吧乱转,然后又一次被打击:不用STL就别选C++。可是我现在仍然对STL一窍不通。我的C++程序几乎就等于.C把后缀名改成.CPP的东西。不管怎么说,如果说那几天夏令营让我掌握了必要的知识,那么这几天乱七八糟的练习就让我对OI实战熟悉了不少。