| Profil de WXYZWXYZ的异人馆PhotosBlogListes |  Outils  Aide |
|
30 novembre 线段树初级心得 一次做题，最重要的并不在于你做出了多少题，而在于你在这次比赛中有进步。因此我对上星期的POJ月赛非常满意。
这次月赛我只做出一题：E题。我一看，马上知道是线段树。可惜我虽然在很久以前就是好好学学线段树的想法，但久久没有实现。遇到这样一题，只好傻在那里。然后翻翻其它题，觉得除了B题还能想想外，其它暂时还差点。然后在攻B题两个小时后，还是以失败告终。这时我非常失望，竟然连一题也做不出来？然后下个决心，马上做E题，马上学线段树。
当即从网上找来一个线段树的论文+PPT，大概看了下，就开始写代码了。第一次写，卡了不久，终于写好了，提交下，超时。然后找出超时原因，修改提交，一个Wrong Answer。第一次写啊，这样的结果并不出乎我意料。然后就自己开始找数据检验代码了。不久找到一组，修改后，再次提交，还是Wrong Answer。改吧改吧，能完成就是很好的了。修改提交，终于Accepted了。当时无比兴奋啊，走遍各个知道我有做题的宿舍，逐个欢呼。我终于写出了第一个线段树了。
1、线段树之所以快，在于预处理，然后可以二分快速得出答案，对于多次区间操作的题特别适合。
2、由于线段树的特性，要使之快，必须在查询或修改某个区间并且此区间的首尾与线段树某段的首尾完全重合时，就必须终于再向深处递归（最多还可以再深一层），就必须在此区间上完成操作并且return，也正因为有这个才能保证线段树的log(n)时间。
3、构造线段树时，还须想清楚，在修改区间时，是否逐步修改，还是采用在统计时逐步统计。
4、在进行递归时，要想清楚这层递归与上下两层递之间的关系，怎样传递参数等。最好先考虑最底层，然后再逐步向上思考。
此为线段树初级心得，可以说是线段树最基本的东西吧。对于区间的插入与删除等，我还是不会，可能后来会有个中级或高级心得了。 27 novembre 我烦，我矛盾，我不管了 就那计算机组成原理实验吧，因为周末没有时间，就于上周四花了一下午研究好并且做好了。当然，我可能算是做得最早的人了，我也非常好心地把一个我参考的网址发到我们班的群上，当时下午四点几吧，没人回答，不过算了，下午是没什么人上Q的。
但并非每个人都像我这样，早早去筹划实验的，周末做的吧，还算可以了，大部分在昨天才开始到处找。只记得我发个网址，却又没有记下网址，然后好几个人向我要。据这情况，我也在概猜测到今天上完英语回来到中午去上实验课之间的时间会怎样了，上英语课时我还考虑着要不要不回宿舍，避开大家。
最终我还是选择回宿舍，因为我想coding，不出十分钟，过来n人，要我的实验报告。我能怎样做呢？虽然我已猜到这结果，但这一幕仍然使我措手不及。出于同学的面子，好像我应该给；但对于实际情况以及我自己的意愿，我不想给。好大的矛盾，好烦！
最后不管了，扔给一同学，想怎样就怎样，不管了。 20 novembre 瓢虫的精华 我变瓢虫了，因此QQ头像也顺理成章地变成一个瓢虫，而QQ签名也顺理成章的变成瓢虫的精华。以后有机会变个毛虫吧。
渐渐觉得自己与大家思想脱节了，不像大家一样情绪多变，游走于各地，关注周围事物，并对此发出某种发自内心的感慨，而我并没有进入这种状态，只有在偶尔上上spaces才能稍微找回这种感觉。脱节归脱节，但这只能大概说明思想走不同路线吧，大概就是我异故我在。每天大部分时间都在想程序，总有想不完的程序，几乎任何想法都只与程序有关。
看看大家，可能除了枫刚转专业忙了点外，大家有时间都走上来发发日志留留言，我有时间都去写段代码。大家对这对那发出感慨，我只能发出一句：“我不同啊。” 9 novembre 编程小事记 这几天来这些小事发生了不少，慢慢说吧。
首先是我刚刚来开始使用STL。先接触到当然是vector，其实还是有原因的，我近期遇到好些要用heap的题，但每题都自己写太麻烦了，于是想写个模版，为了简单，就想到了STL。不过刚好不容易啊，上网查，翻书查，折磨了好几天，才终于写出了个STL实现的堆模版。我还是整个贴出来吧。
/**************************************
使用STL实现的堆（默认为最大堆） 头文件需包含vector,algorithm
主要函数：
建立堆Heap() 堆中插入元素push(_type) 弹出堆顶元素pop() 判断空堆empty() 求堆元素个数size() 置空堆clear() 若要改变堆排序方式，则可重载小于号(<)实现
**************************************/ template <class _type>
class Heap { private: vector <_type>data; public: Heap() { make_heap(data.begin(),data.end()); } void push(_type entry) { data.push_back(entry); push_heap(data.begin(),data.end()); } _type pop() { _type temp; temp=*(data.begin()); pop_heap(data.begin(),data.end()); data.pop_back(); return temp; } bool empty() { return data.size()==0; } int size() { return data.size(); } void clear() { data.clear(); make_heap(data.begin(),data.end()); } }; 有STL代码倒不长。写好了当然要验证正确性和时效性了，一时翻不到好题，就只好将就着用排序题来试了。昨天一试，10^6的数据量，0.3s，当然比快排的0.11s要差多了，但是也不清楚具体与自己写的堆差多少。那么今天终于有时间，自己写了个堆，用同样的题试，0.17s，看来用STL的确是慢啊，用代码长度的简单换来的更长的运行时间，是否值得，就要看题目要求时限紧不紧了，不紧绝对可用STL，反正写了，我就两个模版都保存了。看来收集模版真的好爽。然后今天又用一题试了试STL的map，收取不错的效果。C++有STL就是好。开始感叹以前有STL不会用，全部代码自己一手一脚敲键盘出来。如今终于开始告别刀耕火种的时代，来进行工业革命了，只要转型转得好，生产效率可望大大提高。
然后就是PKU是刷到600题了，再来十几题就到前100了。
还有就是又一个月的周赛结束了，第5至8场总绩我还是排行第一，但是很大程度上是因为有人有次没参赛。不过更可喜的是，算是在我的带动下，我班越来越多人来参加，这次进前15的除了我还有两个我班的。不过我们级本来有些特招生都没怎么来出人头地，问问师兄，听说这届特招的特别水，这样也算是给我上位的一个机会吧。
继续努力！！我还是有很大发展空间的！ 4 novembre km算法 很久之前说好要把二分图最佳权匹配的算好写好贴上来，可惜由于能力的缺乏，只写出O(n^4)的，令我好不满意，我就叫师兄发个O(n^3)的来参考参考。结合网上的一些文章，大概就一知半解吧，让我复述我就写不出来了，只好把其它人的贴上来。下面几段来自wc的小屋。
然后就是KM的时间界。这里略去KM的步骤不谈。众所周知，KM弄不好就会写出O(n^4)的算法，而实际上是存在O(n^3)的实现的。那么O(n^4)究竟是慢在什么地方呢？这个就需要搞清楚O(n^4)的4究竟是怎么来的。
每个点都需要作一次增广，所以有一个n的循环。每个循环内部，每次可能无法得到一条增广路，需要新加入一个y顶点，然后重新寻找增广路。一次最少加进1个点，所以最多加入n次。每次重新找一遍增广路n^2，更新距离标号需要扫描每一条边n^2，所以迭加起来O(n)*O(n)*O(n^2)，结果自然就是O(n^4)。 第一层和第二层循环似乎没有很好的方法可以把它搞掉，所以我们只能从第三层，也就是每次的O(n^2)入手。这一层包括两个部分，一个是增广路的n^2，一个是更新标号的n^2，需要将二者同时搞掉才能降低总共的复杂度。注意更新标号之后有一个最重要的性质，那就是 原来存在的合法边仍然合法，更新只是将不合法的边变得合法。所以当我们找到一次交错树，没有增广路之后，下次再寻找的时候完全没有必要重新开始，因为原先有的边更新之后还有，所以完全可以接着上一次得到的交错树继续寻找。那么应该从什么地方继续号、开始搜索呢？很明显是那些新加进的点，也就是新进入的那些y点。这样虽然不知道每次更新标号会又扫描多少次，但是每条边最多也就被扫描一次，然后被添加进交错树一次。所以这一块，n层循环总的复杂度是O(n^2)。按照这样描述的话，用dfs似乎没有可以接着上一次找的方法，所以只能用bfs来写增广路的搜索了。 然后就是重标号。这一段实际上是由重新扫了一次边，然后对x在树中而y不在的边进行侦测，然后重新标号。想把这个搞掉似乎是有些困难，但是我们先做的是增广路搜索然后才是标号，增广路搜索的时候不也是要扫边么？要是能在bfs的时候记录一下什么信息，到时候直接取用不就好了？所以，做法就是在bfs的时候，对于每个扫到的这种边，更新一下对应的y顶点的标号，这个标号的意义就是y点连接的所有这种边当中可松弛的最小值，定义为slack[y]。然后每次更新的时候扫一下所有的y，对于所有没在交错树中的y，找到最小slack[y]，然后更新就可以了。注意由于我们要接着上一次进行bfs，所以上一次算出来的标号也要留下来。别忘了重标号之后每个y点的slack[y]也要同样更新，这样每次寻找标号并更新的复杂度就是O(n)了，n层重标号最多也就是O(n^2)，然后bfs的O(n^2)，增广的O(n)，所以对于每个点，想对匹配进行增广，复杂度就是O(n^2)，n个点每个点来一次自然就是O(n^3)了。 然后再配合下面的程序吧，防止突发事件资源流失，贴上来好了，以备不时之需。
/*二分图最佳权匹配O(n^3)算法*/
const int max=1000; const int inf=10000; //设定上限 int a[max][max]; //图 int x[max],y[max]; //分别保存x与y的连结信息 int lx[max],ly[max]; //保存x与y的界值 void km(int n) { int i,j,k,p,q,temp; int b[max]; //bfs表 int link[max]; //保存本轮是否搜过并记录结点 memset(lx,0,sizeof(lx)); memset(ly,0,sizeof(ly)); for (i=0;i<n;i++) for (j=0;j<n;j++) if (a[i][j]>lx[i]) lx[i]=a[i][j]; //初始化界值 memset(x,-1,sizeof(x)); memset(y,-1,sizeof(y)); for (i=0;i<n;) //n次迭代 { memset(link,-1,sizeof(link)); p=0; q=1; b[0]=i; while (p<q&&x[i]<0) { k=b[p]; for (j=0;j<n&&x[i]<0;j++) if (lx[k]+ly[j]<=a[k][j]&&link[j]<0) { b[q]=y[j]; q++; link[j]=k; if (y[j]<0) { while (j>=0) { k=link[j]; y[j]=k; temp=x[k]; x[k]=j; j=temp; } } } p++; } //寻找增广路 if (x[i]>=0) i++; else { //修改界值 temp=inf; for (p=0;p<q;p++) { k=b[p]; for (j=0;j<n;j++) if (link[j]==-1&&temp>lx[k]+ly[j]-a[k][j]) temp=lx[k]+ly[j]-a[k][j]; } for (p=0;p<q;p++) lx[b[p]]-=temp; for (j=0;j<n;j++) if (link[j]>=0) ly[j]+=temp; } } return; } 修改界值部分好难明…… 3 novembre Another Week 不经不觉又一周，觉得都好像上来只是写周记了，甚至连周记都空缺。
人在大二，身不由己，特别像我们这样学计算机的，课最多，因此我也了解到很久以前fish那句签名：sophomore, really suffer more.不像晓江他们那样，在他们学院，就要学会闲。
一星期下来考两样试，我也没有办法，考的计算机组成原理好难，考的物理就得反省以前积分没学好，虽然全班每个人都是这样的了，我相对来说还可以，但还是感到一些压迫感。除了考试，这周五天早上都有第一节课，睡不够。还有就是那个计算机组成原理实验的老师，每次都不给好脸色我们看，每次总有无名火，班里的交流对他意见不心，就不敢正面提了。同时，我也觉得他并没有尽到作为一个老师的责任。“师者，所以传道授业解惑也。”就依这句话为标准吧，他完全没有给我们解过任何惑，每次都是布置题目出来，然后我们回去做一周，第二周让他检查，如果实验结果有误，他马上调头走人，就算问他是什么原因，他也不会回答，只能同学们之间交流了。虽然说这样能增强我们独自思考的能力与合作能力，但毕竟我们是学生啊，有些事还是得问老师才能解决，所以我们都对他非常不满意。
然后就是中大派队参加ACM赛亚洲赛区，南京赛区三队都不错，更好的是首尔赛区，派出的一队以亚军出线final，wish他们在final中取得好成绩，wish剩下在亚洲其它赛区的比赛中大继续取得好成绩争取另外的出线final名额，同时也wish自己下年能参加。然后贴一贴学校队的队名。
ZSU_Dubhe ZSU_Merak ZSU_Phecda ZSU_Megrez ZSU_Alioth ZSU_Mizar ZSU_Alkaid
Dubhe(天枢), Merak(天璇), Phecda(天玑), Megrez(天权), Alioth(玉衡), Mizar(开阳), Alkaid(摇光)乃天上之北斗七星，在茫茫夜空带来光明，指引方向。七星联手，所向披靡。愿中大的队伍在今年的比赛中不畏强手，再创佳绩！ 天气在这周也突然转冷起来，据以前所学知识，判断是冷锋过境，冷，雨，风。这场景，令我想起初中某天，突然转冷，大风大雨，三个偶佬还穿着短袖校服，在中午放学时分，在良友一人一雪糕，站在路边，边看下雨边吃雪糕。像这样的事，什么时候才能再试一次呢。
Week by week，看来短时间内都无法改变现状了。 |
|
|
