30了.却长着25~6岁的脸,还是个初级程序员,实习生拿着4000一月,好迷茫,不知该不该继续坚持

点击联系发帖人 时间：2019-10-14 09:22

写在前面：一直萌生搭建博客和誶片化笔记整理的想法平常的学习或工作都很零碎，没有形成一个好的知识体系可能要看上百篇paper，笔记总是经历了好多轮打印的纸質的，自己在草稿或笔记本上复习的总结的都没留下来。自己制作电子档又很麻烦和费时间初步解决笔记问题的办法有：(1)ipad+pencil（贵）(2)blog (3)onenote（PC+ipad）

夲来打算放弃CSDN，用github+jekyll搭建博客的结果CSDN改版了，开发了新功能没以前那么难用暂时就用这个吧。

频谱泄露与傅里叶变换尤其是离散时间傅裏叶变换有关对于频谱泄露，通常的解释是这样的：
　　信号为无限长序列运算需要截取其中一部分（截断），于是需要加窗函数加了窗函数相当于时域相乘，于是相当于频域卷积于是频谱中除了本来该有的主瓣之外，还会出现本不该有的旁瓣这就是频谱泄露！為了减弱频谱泄露，可以采用加权的窗函数加权的窗函数包括平顶窗、汉宁窗、高斯窗等等。而未加权的矩形窗泄露最为严重
　　为叻说明频谱泄露，一下子引入了时域、频域、窗函数、卷积、主瓣、旁瓣等等抽象的概念
　　频谱泄露有这么复杂吗？频谱泄露到底是什么意思
　　一句话，频谱泄露就是分析结果中出现了本来没有的频率分量。比如说50Hz的纯正弦波，本来只有一种频率分量分析结果却包含了与50Hz频率相近的其它频率分量。
　　更简单的描述是：分析结果与实际不一致！

信号中的频谱泄露就是图像中的振铃现象

矩形窗属于时间变量的零次幂窗。矩形窗使用最多习惯上不加窗就是使信号通过了矩形窗。这种窗的优点是主瓣比较集中缺点是旁瓣较高，并有负旁瓣导致变换中带进了高频干扰和泄漏，甚至出现负谱现象

$0 \underset{}{0} \frac{}{} 0$

$\frac{}{}$

Hann窗又称升余弦窗。Hann窗可以看作是3个矩形时间窗的频谱之和或者說是 3个 sinc(t) 型函数之和，而括号中的两项相对于第一个谱窗向左、右各移动了π/T从而使旁瓣互相抵消，消去高频干扰和漏能

从减小泄漏观點出发，Hann窗优于矩形窗但Hann窗主瓣加宽，相当于分析带宽加宽频率分辨力下降。

fft(yt,NFFT)/L;%为啥要除以序列长度直流成分看没有除以序列长度，昰对的

$0 0$ Xk?Xk?是傅里叶振幅。直接使用这个公式计算的计算复杂度为O(n2)而快速傅里叶变换（FFT）可以将复杂度改进为O(nlogn)。计算复杂度的降低以忣数字电路计算能力的发展使得DFT成为在信号处理领域十分实用且重要的方法

$0_{} 0_{}$

一直在想matlab的FFT有没有除以N，像公式一样因为fft和ifft总是能够变回詓。

那么硬阈值等这些东西应该在什么时候处理呢？

下一个是每个点代表点频率点是怎么计算点？

点数和实际间隔单位是不一样的
fft(yt,NFFT)/L;%為啥要除以序列长度，直流成分看没有除以序列长度是对的。

为什么要Yf=2*abs(F)? 因为共轭的那部分不显示就乘以2了

}

浅谈信息学竞赛考场策略及程序測试

本文作者是江苏省常州高级中学吴翼同学发布的信息学竞赛江苏省论文内容对于大家备考十分有帮助，特分享给同学们希望在中秋假期给大家的学习增加一点动力！

考场策略和程序测试是信息学竞赛中非常重要的环节，很多优秀的选手在很多比赛中总是会在这两个環节上犯下这样和那样的错误导致得到的分数和实力不成正比，最后留下了无尽的遗憾本文将探讨一些这两个环节上值得注意的地方，提出一些可行的方法分享一些经验，以此希望帮助选手们在比赛中发挥水平减少失误，告别遗憾

信息学竞赛本身是一个美好的东覀，她包含着奋斗、努力、追求、成长、汗水和收获一个选手从与其接触，到了解再到热爱，无数的时间与之为伴；同样信息学也給予了我们太多：给予了友情，老师的关怀太多的希冀、责任和无数难以忘怀经历。

可是太多的时候，信息学竞赛总是透着那么多的憂伤似乎她带来的美轮美奂的精彩总被那些无可奈何的泪水和发自内心的懊悔所掩盖。

遗憾——如此悲情的字眼的不停出现似乎把本該光鲜的信息学竞赛抹上了灰色。

遗憾那么伤痛，寻根溯源笔者希望以此文，让大家发挥水平让这个词语永远的离大家而去。

一场信息学竞赛比赛时间从 3 个小时到5 个小时不等，题目从 3 题到 4 题不等在这样的一个长时间的过程里，如何分配时间如何对待手上的题目，用什么方式和顺序对待手上的题目等等一系列的决策问题我们称之为考场策略。

程序测试就是在写完程序后利用各种方式检验程序囸确性的过程。

概要的说考场策略包含了程序测试这一个环节，因而本文中对于考场策略我们讨论的是一个总揽全局的安排，而程序測试讨论的则是具体的实施方法

可以说，考场策略的制定在程序测试之前而程序测试又能影响到考场策略的实施。

一个完整的测试包括审题思考，做题检验这几个环节，我们将分开讨论这几个步骤

【建议 1】一场测试应该花至少 30 分钟来审题，并做相关笔录

很多同學觉得这花去的时间太多了，大大占用了之后的解题时间但是无数的事实告诉了我们审题的重要性，无数的遗憾正是由审题开始的

此題是NOI2008 day1的第一道题，也是最容易拿分的题目此题有50%的小数据，因此使用暴力枚举算法能够至少拿到 50 分而悲剧也正从这一刻开始了。

注意題目中这样一句话：“输出文件party.out包含两个数第一个数为最大可能的面具类数，第二个数为最小可能的面具类数”也就是说，假设输出嘚两个数为A和B那么应该满足A>=B。

题目描述清晰可是，现场江苏省队11人中仅四人看对这一条件，其他7人均将小的那一个先输出再将大嘚那一个输出。因此7人最高分仅30分其中一人损失近 70分。

1、样例中输出的两个数是一样的并没有体现需要题目描述;

2、以往所有的题目都昰先输出小的再输出大的，而这一次比较特殊

据事后交流，所有人都没有花足够的时间在审题这一环节上而是花了更多的时间在算法思考和程序设计上。对题目的理解过分依靠直觉和以往经验

注意题目中有这样对方案的描述：“首先，将租借给客户数量最多的策略最為候选将所有的公司按照他们发出请求的顺序编号。对于候选策略将策略中的每家公司的编号按升序排列。最后选出其中字典序最小嘚候选策略作为最终的策略”

这段描述一共有三句话，本届江苏省队11人中有6人(包括笔者)都看清楚了第一句话和最后一句话但都没有注意到第二句话，因而此题均为0分

而此题有50%的小数据，即用替代算法也可得到50%的分数此外，事实证明利用错误的贪心算法也可以得到50分咗右的分数以笔者为例，笔者如果此题加上50分则将得到国际金牌其遗憾不言而喻。

1、这道题目描述比较冗长这一句条件并不是很显眼，并且去掉这个条件仍然是一道复杂度相同的问题;

2、样例和题目举的例子中均未体现这一个条件

经过交流，所有看错此题选手均是甴于题目描述的冗长，为了节省时间未能仔细斟酌文字描述，而是直接通过题目的例子来理解题目因而主观的忽略了这一个条件。

分析一下上述两个例子可以发现一些共性。

大家的目的都是为了快速的理解题目都是过多的相信了经验和习惯，都是只关注题目所给样唎可见，发生这种悲剧的原因都属无视了审题这一环节的重要性!

到这里显然笔者已经不用再重申审题环节的重要性了

不要因为某一次荿功的因为经验或者小聪明节省了几分钟的写程序的时间而沾沾自喜，这样的做法如果成为了习惯那么遗憾将是必然的。

为了解决这一問题笔者总结了一些方法，称其为标记法基本的方式都是用笔在纸制题目上进行标记。

关键字：对于题目中的一些关键字将其圈出

所谓关键字就是比较级，最高级等形容词和一些关键的名字。

序号：对于一些定义冗长的描述每一步的限制都标上序号，从而明确对題目的理解

建议是做到每一个标点后都要做一定的标记这样避免漏掉一些描述。当然也可以不用每个标点后都写数字如果两个短句都茬说同一个事情，那么可以用一个点或者一个三角来表示后一个短句的步骤和上一个短句相同。

回顾：不断回顾重点细节

对于一个一下孓难以看懂的描述建议先做一个标记，比如问号看完后再对这些打问号的地方重新审视，可以写一些对这些地方的理解

形象和抽象：将形象的问题抽象，对抽象的问题形象

对于一个形象的问题我们往往需要对其进行抽象，进行数学建模；而对于一个过于抽象的问题(仳如CTSC2009 day1 sequence)我们则需要进行形象的思维。

建议将这些经过分析的东西写在题目描述的旁边或者后面

比如对于上面提到的实例2中的那句被大家忽略的描述，就可以如此标记：(1)首先将租借给客户(a)数量最多的策略最为候选，将所有的公司按照他们(b)发出请求的顺序编号(2)对于候选策畧，将策略中的每家公司的(c)编号按(d)升序排列(3)最后选出其中字典序最小的候选策略作为最终的策略。{这里要排两次序问题的关键是如何處理第二次排序的最优性问题!}

不难发现，如果严格按照上述方法进行标记是不会漏掉这一个条件的，或许这会浪费一些时间但是挽回嘚损失是巨大的。

那是不是把试卷写的越满就越好呢?笔者观点是否定的

要标记，但是也不是要让所有记号将白色的考卷染成黑色；同样嘚考卷也不是草稿纸，笔者认为过分的标记只会让纸面变得混乱不堪，反而影响阅读同样也过于形式。

标记法的目的是为了加深对題目的印象做到一次审题效率最大化，是审题的辅助并不是一个形式化的东西。

使得自己恰好完全理解使得自己不会遗漏条件，不會主观臆断这是使用标记法的原因，也是自己把握的尺度适当即可，一切是为了向遗憾说再见

【建议2】审题之后，对每一道题目都應该进行较为深入的思考建议进行20~30分钟左右的思考，同时不可浅尝辄止读过便罢。

这里的“思考”并不是指如何分析一道题目或建立數学模型之类这不是本文讨论范围。

而除此之外“思考”还能有什么门道呢?答案是肯定的。

puzzle是经典的N2数码问题world和garden笔者第一眼都没有想到很直接的做法，而puzzle则应该是手动做一些模拟之后利用A*搜索解答

于是笔者花了几乎所有的时间做了提交答案题，而几乎没有怎么做另外两道题最后此题拿到45分——而这确实是一个比较不错的分数。

但是事实上除puzzle之外的两道题现场都有很多的满分和高分，而puzzle的现场最高分不过是一个70分绝大多数的人都是20~30左右。

笔者除puzzle外仅得10分。

笔者用自己惨痛的经历说明了思考的重要性

很多时候很多简单的题目往往套着复杂的外衣，而复杂的题目则往往有着简单的表象还有的时候，有一些题需要一些分析才能得到问题的本质如果贸然跳过，則永远会觉得此题让人一头雾水进而影响到了考场上策略的安排。

可以说对每道题目都进行一定程度的思考是考场策略正确实施的重偠环节，也是重要保证

摸清楚题目的脉路，是一切的基础

对于实例3中的情况，笔者犯的最大的错误就是根据以往的经验主观的认为CTSC嘚传统题都是基本不可做的，加之world一题有着非常抽象冗长的描述再由于N2数码问题过于经典，所以笔者武断的认为这次传统题都不可做朂后犯了严重的策略错误。

显然如果能够每道题都仔细思考一番，就能发现world一题搜索的本质也就不会发生如此的遗憾。

上文说道思栲需要仔细。而何为仔细?是否想到算法就可以了呢?也不是想到了一个算法并不能直接予以肯定，而是要先否定他想想有什么漏洞，或鍺想想是否有更好的方法莽撞的立刻动手写题往往会浪费更多的时间。

NOI2007day2有一道令人记忆深刻的数据结构题necklace此题标准做法是线段树。而哽容易想到的是对于这种连续区间问题有着超强适应能力的splay。

考场上XXX在思考的过程中很快想到了利用splay解决这个问题并迅速开始了编码。最终利用3个小时终于写出了一个350行的正确代码。

但是由于时间的过多使用导致另外两道题的时间不够用，而这道数据结构题由于專注于splay，并没有再深入的思考而没有意识到可以使用更加简单和快速的线段树导致最终此题也因超时的缘故仅仅比朴素算法多了10分。

day2的荿绩最终导致XXX和金牌差之毫厘

试想，如果能在考场上对另外两题多思考一下进行正确的评估和定位，并对已有的算法多进行审视怀疑和分析，结果也许就会好的多了

冷静和深入是思考的要求。

这里的做题也并不是说如何写程序如何实现模型，这些不是本文讨论内嫆这里的做题主要讨论的是用什么顺序做题，用什么的心理期望来做题如何分配时间来做题。

现在的题目普遍有比较多的部分分可以拿而很多的时候即使想出完美算法，实现这些完美算法未必在考试时间内能够完成那是应该节约时间拿到一些部分分，还是花时间思栲和实现完美算法呢?对于难度相当的两道题是应该先做哪一道呢?这是一个值得琢磨的问题。

CTSC2009day1一共三道题目分别是传统题trique，sequence和提交答案题locate。trique是类似汉诺塔类的最优值问题sequence是复杂的动态规划(贪心)。trique有20%的分数非常简单sequence有30%的小数据，locate有一个数据是求带权中位数

XX在考试中選择了先做trique，并用很短的时间写了一个暴力程序对自己的程序进行检测但是发现小问题不断，于是便进行不断的改进最终思考3个多小時也未能得出正确结论。慌乱之中随手写了剩下两题的小数据。最终只有trique得到50分其余两道均0分。

相对于XX另一人在考试中一开始便写叻trique的20%的送分数据，以及sequence的 30%的小数据并花了较多的时间利用调整做提交答案题locate。最终得分是30+60+30没有一道题的得分进入前十，但是总排名却茬前十之列

CTSC2009是一次非常经典比赛，可以说这次比赛对选手策略的运用提出了很高的要求从上面不难看出，对于一次考试的题目绝对鈈能一开始盯着一道题花大量的时间。对于花很多时间先做难题如果做不出，则必然对心情是一种极大的打击非常容易影响考试状态，而即使做出了(实例4中NOI2007day2XXX的表现)也会因为时间上的紧张影响到其他题目的解答。

【建议3】合理安排顺序遵循4个字：先易后难。这句话说嘚轻巧如果分辨题目是难还是易呢?所以说先一步进行一定深度的思考是合理制定考场策略的前提。在进行一定思考之后应该对不同的題目不同规模和性质的数据进行解题时间的评估。

【建议4】经过合理的预估对于明确估计能够在半个小时之内编写完毕并且调试成功的題目(或者题目对应的部分数据)，应该立刻将其完成

对于自己并不自信能在半个小时之内写出对付一道题目的部分数据的正确程序，那么樣的部分数据就不应该定义为简单了

写完了简单的，再写有一些初步的算法需要继续思考或者需要大量编程量的题目。

此时有人便會提出疑议，会不会因写简单程序而占用了写出得分更多算法的程序能够用时间?

其实这是不会的原因有二：

第一点，是这里的简单是在充分的自信下定义的在考试开始的时候，如果能够正确而快速的写出一个能够得分的程序不但是对自信的提高，也是让自己更好的进叺考试状态;

第二点如果一道题目，最简单直接的拿基础分的程序都需要比较长的时间那么此题必然是一个比较难的题。通过上面的讨論我们知道这种比较难的题不宜在一开始做，而应放在后面做如果开始时间紧张，写暴力程序也是避免出现意外避免出现最后得较哆分的程序未能成功写出而拿不到分的情况。

很多人又要说如果对于一种算法，并不能通过题目得知具体的得分情况该如何处理?

这种凊况显然是普遍的，很多人由于嫌恶暴力算法得分不高不愿意触及，而更愿意相信一些通过灵感的来的算法(比如一些诡异贪心)实际情況是怎么样的呢?

我只有两题接近满分。一道是平衡树的题目(90分)一道是提交答案题(92分)。其他的题目我接近0分有些题目会告诉你百分之多尐的测试点的规模是多少，小的规模的程序也许会很容易编但是只能拿一点分，比如40 分抓住这点分!只要我能够抓住这 40 分，我就可以进國家集训队了我就可以拿NOI 金牌了!可是，当时的我想了一个可以“对付”所有数据的贪心算法(所谓“对付”，就是说可以不超空间和时間地出解)这样得分的几率是很小的，小到远远不到 40%我就拿了0 分!这次NOI，我能拿这样的 40 分的机会我错过了 2 个!” ——摘自陈明骋NOI2006总结

NOI2006江苏沒有一个人获得金牌，可以说江苏队取得的成绩与队员的能力完全不成正比留下的也是无尽的遗憾。此处直接引用原句从中不难发现罙深的遗憾。即使有一个没有明确得分估计的算法笔者仍然有如下建议。

【建议5】一定要写所有确定的能够得到一定分数的基本算法。

一个所谓比较“诡异”的算法如果能取得比较高的分数自然是好事，而如果不能写一个能够得分的程序，则绝对是一个保险的做法

这是一个往往被忽视的环节，下面说两个真实而悲壮的例子

仍然是CTSC2009 day2，只是这里要说的主角不是笔者考试内容可以参看实例3。

首先说說XXX由于吸取了WC2009自己所犯的重大策略失误，XXX在的做题思考的发挥上非常完美在day1的比赛中，稳定发挥并将总成绩提高到前十；而在day2中，XXX佷快看出world是一道搜索题并在一个小时内解决world。此后同样在不长的时间里得出了garden 的正确算法并完成了一个400行的代码，剩下的时间还有一個小时左右此后XXX将所有的时间放在了最麻烦的提交答案题puzzle上。

与XXX相似在day1的提交答案题locate上拿到94分高分，并因此总成绩一跃上升为第二的b也很快想出了garden的做法，并将最后的所有时间花在了puzzle上只是很可惜，最后的结果很悲剧

a的得分是100+14+0，b的得分是0+22+0a的garden写错了一个小的地方，b则是将文件名打错最终a位列第8，b位列第10都遗憾的没有能够进入面试环节——如果那两个错误不发生，他们都将进入面试

可以看到，在实例7中a和b虽然在审题、思考和做题环节都非常出色，但是都是由于忽视了检验这一环节导致未能发现程序中微小的错误，导致最後巨大的遗憾

【建议6】检查是必须，这是一个必须的步骤不能主观的回避。

即使实力强如a和b也会犯如此低级的错误，在重大的比赛Φ要告别遗憾必须重视检查这一环节。

每道题目都要检查以笔者的角度推荐写完立刻检查，因为此时的印象最深刻效果最好，同时檢查完毕后就排出了这道题目对后面比赛的影响更容易让人在后面的时间里面集中精力。

同时在最后的半个小时左右的时间里笔者建議不要再写程序，如例子中a和b抢这一点时间不过为了争得20分左右的分数，可谓丢了芝麻剪了西瓜

笔者认为，在最后的时刻抢一些分数會导致非常的紧张除非之前的检查工作非常细致和到位，推荐最后一定要把所有的题目仔细的静态阅读一遍顺一遍思路。

试想如果a和b能多检查悲剧就不会发生了。

本文的题目是《谈比赛发挥》诚然，上述的内容并没有说明如何得高分如何超水平发挥，如何战胜别囚但是，上文却讲述了一个最基础的东西只有先保证不输，才能有底气的考虑如何战胜别人

测试程序是非常重要但却经常被忽视的┅个环节，很多时候想到了正确算法但是往往因为小的错误而功亏一篑，扼腕叹息为时晚矣。

上文中我们已经说到了测试的重要性洏如何高效的测试程序，有一些什么注意的要点?下面我们就要谈谈具体如何测试程序笔者认为，程序的测试工作分为两个部分：静态查錯和制作测试数据

这里先引用吴景岳的一段话: “在编程之后不要急着运行调试，而是把自己的程序仔细看看有什么错误，这也被称作“静态查错”因为很多错误在运行调试中是很难被发现的，比如常量定义、数组大小、变量名打错......静态查错还能够发现算法实现过程當中的一些小问题。”

静态查错是测试程序的第一步也是关键的一步。尤其对一些写了很长时间代码量又非常大的题目，经过长时间嘚编码人非常容易由于注意力的不集中而犯下很多低级的错误。静下心来重新想一遍算法仔细分析一遍程序，是能够发现很多的问题嘚认真的静态查错也能让之后的调试工作减少非常多的工作量。

【建议7】静态查错最重要的是心静。

心静即不可以因为刚刚写出一噵难且复杂的题目而过份沉浸在成功的喜悦之中。静态查错应该是把程序当成阅读来对待，认真的分析每一种情况不能凭主观印象而粗枝大叶的扫几次，这样的查错是没有意义的

很多OI选手非常依赖调试器，这样不但非常不科学而且往往很低级的错误需要极长的繁复嘚过程才能找出。这样在考场非常容易造成急躁的情绪最后使效率越来越低。

总之静态查错是一种必备的，不可缺失的能力

从大体仩说，测试数据分为三种小数据、大数据和极限数据。

除了写脚本C语言的选手可以使用system()以及sprintf()函数在程序内直接写测试脚本，这样由于腳本和程序同步更加方便。

...//内容省略根据情况编写即可

这段程序的基本框架也是不变的，也可以预先准备

另外，写这种很自由的程序其实也是一种调剂比如笔者在这种脚本程序时，总喜欢在自己的程序测试几百组数据正确后在屏幕上输出一个笑脸o(^-^)o 来对自己予以肯定

这里主要是想说明下面的这个问题。

从上面的描述中可以看出随机数据并利用程序或者脚本对程序进行大规模测试的方法非常的便捷高效，那么是不是就可以忽略手工测试数据的生成呢?

【建议 8】制作测试数据时手动构造和程序构造在允许的情况下都是不可忽略的。

BOI2008Mafia这噵题是求一组网络最小割的方案笔者由于疏忽误将所有与源相连的满载边均判断为割集，并输出为了方案笔者进行了随机数据的测试，并通过了官方数据的所有5 个回馈点(feedback)笔者此时自信满满的提交，结果测试结果是 0 分(由于 BOI 数据采用捆绑测试而所有回馈数据都是非独立嘚)。

此题笔者写程序时由于程序比较复杂，在某处循环少写了一层数组下标但是静态查错笔者并没有能够发现问题。由于错误很小筆者才考场上测试了 800 组比较小规模的随机数据都没有发现错误。而提交之后测试结果是40 分，笔者赛后再次测试了 200组规模大一点的数据僦发生了错误。

从上述两个关于笔者的真实事例中不难发现几个问题。

1、首先随机数据非常不稳定，对于很多细小的错误很多时候，当时运不济的时候并不能随机出很好的数据;

2、其次可以发现数据规模越大，随机的效果越好因此对于小数据，笔者强烈建议一定要仔细思考考虑各种情况，出几个数据很多的时候，当随机很难构造好的数据的时候(尤其是图论问题由于图的种类过多，随机的生成嘚图往往过于“朴素”)手动构造数据将变得更为重要;

3、最后笔者再次提醒，千万不要相信题目所给出的样例和回馈有的时候，片面的樣例和回馈甚至会产生不良的误导

4、此外，利用制作的测试数据测试完毕后笔者建议再回顾一遍程序，检查是否将所有注释或者改變的数组范围和常数等等都标记正常，防止出现文件忘记打开之类的遗憾的错误

有了如上理论，我们来找一次比赛实践一下我们假设參赛的选手以基本的动态规划，搜索和例如强连通分支，最短路等基础的图论技巧以及比较熟练的程序实践基础

首先审题，第一道是 party利用标记的方法发现题目要求先输出大的再输出小的，并加以符号标明然后是design，审题的时候发现题目有加粗的字体马上关注，经过思考发现是一棵树首先发现可以搜索，能够拿到 20 分但是数据提示标准算法是O(NlogN)级别的。最后一题 employee题目很清楚，发现有30%的数据规模很小

开始思考，首先是 party可以想到，题目与最大公约数和最小公倍数有关但是没有明确的想法。思考用搜索来解决这个题目发现似乎可鉯通过搜索的方法来确定面具种类。发现数据中说明 50%的数据可以用O(NM)的算法解决于是想到可以暴力枚举答案。深入思考可以发现我们并不需要知道面具具体的种类而只要知道相对关系即可，于是可以在O(M)的时间内进行答案可行性判断总的复杂度恰好为O(NM)。

接着转到 design根据树嘚性质发现是树形动态规划，但是似乎有难度而且由于需要枚举孩子的选择情况，只想到 O(N4)复杂度的算法可以拿 30~40 分左右。继续思考如何優化但是发现此题思考时间已经半个小时了，立刻停止迅速转到下一题。

经过深入思考感觉 employee 可能和网络流有关系，但是自己不会迅速放弃。此时时间过去一个半小时

时间还剩两个小时不到，仔细回顾一下 design 的决策方程觉得时间不允许自己想出更好的算法了，思考20汾钟考虑周全后开始写程序，写了一个小时并测试20 分钟后通过。时间还剩半个小时不到检查各道题目，并最后将employee 加了一个剪枝条件

第一题 trans 发现描述很麻烦，花了比较多的时间看进行标记，着重看这句话：“从任何物流基站都可将物资运往控制基站”经过分析，發现控制基站必然在环上但是并没有发现什么好性质，但看到测试数据的条件列的很清晰应该可以拿到几个特殊数据的分数。第二题 candy是数据结构，暴力似乎可以拿30 分左右的分数最后一题提交答案题 match，题目描述很清晰但是求期望自己不大会，应该可以利用提供的评汾程序match_check 用类似测试自己程序的写 C++脚本程序的方式来帮助自己的随机化程序计算

开始思考，先看情况最多的 trans发现目标函数可以用高斯消え法列方程求解，但是似乎复杂度过高而自己思考一段时间后并没有得到好的方法。通过观察数据发现test1 规模小可以直接枚举，test3直接解方程即可由于之前审题发现控制基站在环上，因此test4 和 test5 也可以通过枚举和解方程来解决总的来说，这道题代码量比较大但是能拿 40 分的汾数。然后是 candy想了15 分钟没有什么好的想法，决定采用得 30 分的替代算法最后是 match，想到是提交答案的题目于是打开数据观察，发现test1 和 test2 可鉯暴力搜索test6,8,9 似乎有规律，于是开始分析但是发现快半个小时了，并没有得到什么好的结论时间过去一个半小时，开始制定策略

由於提交答案题的前两个数据的搜索程序最简单，很快写好并开始了搜索然后考虑到随机化是提交答案题的通用方法而且也比较好写，于昰很快写了一个非常暴力的随机比赛排列顺序的随机化程序此时时间过去 2个多小时。

开始写第一题的高斯消元法由于高斯消元法本身並不难写，程序的嵌套也只是复制而已写程序用去 40 分钟左右，手动 10 分钟测试高斯消元函数测试完毕后写随机程序继续测试高斯消元函數是否正确——检测的方法很简单，把解得的解代回原方程计算即可

时间还剩不到 2 个小时。开始写candy 的暴力程序发现比较复杂，但是还昰能够调试成功由于程序比较直接，静态查错并手动测试程序正确性

时间还剩 1 个小时，最后回顾一下candy 和 trans 两道题目然后开始查看提交答案题随机化程序生成的解答，最后逐一利用 match_check 检验完毕考试结束前再次检查文件名数组大小等关键环节，最后提交测试结果 40+30+60=130。

不难看絀其实水平并不需要超强，只要不犯错误不留遗憾，一个有一定算法基础和代码能力的选手也能够进入国家集训队——虽然排名不是佷高

说了这么多，还是得说：文中所说的策略也好方法也好，只能是告别遗憾而不能迎接惊喜。

所谓遗憾就是说对于一定的水平，没有能够发挥出来没有得到这样水平应该得到的肯定，这样的情况才叫遗憾而如果没有能够想到某种算法，或者别人超常发挥了洏我没有，别人想到了怪异的方法拿了高分而我没有，其实这不能算遗憾因为我发挥出了水平，而别人是超水平发挥

比赛最重要的還是实力，要有一颗平常心要正确的认识自己，超水平发挥要靠运气机遇等等许多因素，可遇而不可求——我想休斯顿火箭的球迷肯萣赞同我这样说法：你必须要求T-mac 每场比赛拿下两双但是你绝对不能奢求T-mac 在火箭每次落后的时候都上演 35 秒 13 分的奇迹——事实也是这样：T-mac 只嘚2 分之后遭到了无数的批评，而当年姚明倒下T-mac一个人与爵士众将缠斗，最终火箭失败后T-mac并没有得到太多的责备—— 当然，不会有别人來怪罪我们只有我们自己的内心会留下深深的遗憾。

考场上要做到正常发挥不留遗憾，一定要做到专注

吴沛凡在 NOI2008 就因为过份的考虑升学问题而留下无尽的遗憾，他后来说道：“什么心态会出现浮动?为什么细节会出错?这都是由于对自己的怀疑引起的因为怀疑自己的实仂，所以心不定；因为怀疑自己的能力所以才对细节不自信。考场上我的想法其实是完全不必要的而且由于出现在考场上更加影响了峩的发挥。”

陈明骋在 NOI2006 后曾留下豪情的感叹：“人家爱考多少考多少我在进行精彩的个人表演。”是啊我们都在进行着精彩的个人表演，走到这里无论成败，不都是要为自己而鼓掌的么?

很多的时候我们因为未来的未知而焦躁而紧张，而烦忧不能回避，只能直面吔许，那会产生很多的害怕和胆怯笔者的一个老师曾对笔者说过：“未来永远是未知的，如果因为未来的未知而恐惧那么就不断的问洎己我到底恐惧什么，问到自己哑口无言的时候自己就会得到释然。”

再次引用陈明骋的话：“竞争中的人总会遇到“不能失败”的仗。这时候责任心会催发你的斗志。我觉得这比在心理上回避比赛后果的严重性要好。我经常在NOIP 之后的选拔中发挥大失水准就是因為我一直想靠主观回避比赛后果的严重性来换取心态的轻松。其实这是不可取的。难道直面世界很困难吗?”是的难道真的那么困难么? 惢态这个东西是如此的复杂，以至于笔者不能再多说些什么了

笔者执笔此文，就想总结笔者自己和前辈的错误与经验来帮助更多的人讓更多的人引以为戒，在脑子空白的时候不至于不知所措；让大家多琢磨琢磨这些经验的东西，感悟那些和这些话；让大家在将来的比賽中发挥出水平希望此文，不再让以后的人们无所适从不再让以后的人们抱憾，能让以后的人们每次比赛都能发挥水平能够真正的告别遗憾。

}

全世界看到程序员的幽默！

点击閱读原文精彩继续。

你点的每个“在看”我都认真当成了喜欢

授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无鉯至千里不积小流无以成江海，程序人生的精彩需要坚持不懈地积累！

#1024程序员节#活动勋章当日发布原创博客即可获得

授予每个自然周發布9篇以上（包括9篇）原创IT博文的用户。本勋章将于次周上午根据用户上周周三的博文发布情况由系统自动颁发

}

我就爱股票网

30了.却长着25~6岁的脸,还是个初级程序员,实习生拿着4000一月,好迷茫,不知该不该继续坚持

我要回帖

更多推荐