BZOJ 2007: [Noi2010]海拔

同1001一样,对偶图最小割转最短路

又被卡spfa= =

话说为什么总是有些人总喜欢卡spfa,又好写一般情况又快,为何老是要逼人写迪杰斯特拉= =

要就题目直接说会卡spfa嘛

好吧其实是前几天考试被spfa卡掉一半点发牢骚的= =不要介意= =

话说最近真的有些背,各种卡时卡空间(差2MB就过了的惨痛经历啊QAQ)

好吧不说那么多了= =
CODE:

 

BZOJ 1835: [ZJOI2010]base 基站选址(DP,线段树)

可以很容易的写出dp方程:

F[i][j]=min(F[l][j-1]+w[l][i])+c[i] (w[i][j]从l+1到i-1这些点p里,所有满足d[p]+s[p]<d[i] && d[p]-s[p]>d[l]的点的w[p]之和)

考虑i+1,会对方程造成什么变化

w[l][i]会变得跟大了(满足d[p]+s[p]<d[i]的点更多了

可以发现增长的是一个区间,求和也是一个区间

线段树解决

CODE:

BZOJ 1797: [Ahoi2009]Mincut 最小割

割一个很好用的结论:

对残余网络的S与T分别作bfs,得出每个点是否和S/T在同一连通块中

一条x到y的单向边

满足1:当x,y不同时属于S/T连通块且该边满流

满足2:当x,y分别属于S与T连通块且该边满流

CODE:

 

 

对信息学竞赛中调试方法的建议

信息学之于其他竞赛学科的不同,就在于需要通过写程序来表达自己的思维和想法。如何尽可能又快又好地调试程序,成了我们必须要思考的问题。相信很多同学都有过这样的经历:思考一个算法只花了半个小时,但是把这个算法写对却花了一天。。思考与实现的时间往往不成正比。

下面是我结合自己的经验给出的一些小建议,仅供大家参考,如果有不太好的地方,也欢迎指正~

关于调试有一个大前提,就是思考的方向一定得严谨正确,因为思考决定实现,如果思考的时候有漏洞,那么实现的程序肯定也不强健。在想出算法之后不要急着实现,一定要认真反复地论证:我的算法每一步的定义是否严谨,是不是哪里还有漏洞,我的算法所得到的东西是否就是题目需要求解的。确认了自己的想法后再开始实现。

假设我们现在写完了一个程序:

第一步:静态查错(俗称裸眼观察^_^),即不测试数据,而是通过反复地看代码来检查。静态查错首先要检查是否有变量名打错,语法是否正确,你打的代码和你的想法是否相符。然后要分析代码的逻辑性是否严谨正确,是否能在所有情况下都能正确运行。最后还要验证是否在所有边界情况都能得到正确的解,包括数组是否开够,会不会有n=0的情况等等。静态查错是最有效的查错方法,为什么有的大牛能够一遍写对很复杂的代码,因为他们静态查错的能力非常之强,并且在敲程序的过程中就已经在静态查错了。在实践中,我建议大家尽量让自己的程序模块化(即一个函数做一件事情),然后检查的时候边看边打上注释,这样能让自己更清醒地判断,也方便以后能轻松阅读自己的程序。

第二步:动态查错,用数据来验证代码的正确性。人眼往往不可靠,我们需要用更安全的数据来判定。一般而言在普通的OI竞赛中,时间是比较充裕的,我们有时间来对拍。对拍需要三个程序,一个是你需要提交的标准程序(std),一个是能够通过部分数据的暴力程序(plain),一个是用来生成数据的程序(mk_data)。

关于plain程序,一般会比较好写,所以一定要认真检查,不要写错!

关于mk_data,一般需要得到一个随机的整数,c++语言写法如下:

<

p style=”background-color: #ffffff; font-family: tahoma,helvetica,arial; color: #454545;”>我们可以运行一次mk_data,得到一组数据,然后分别用std和plain跑一遍,看结果是否一样。当然这样手动是比较麻烦的,我们可以用脚本来自动对拍,下面是windows下用bat脚本对拍的普通写法:

(约定plain的输出文件是1.out,std的输出文件是2.out)

将这一段话写在一个文本文件中,将其重命名为ck.bat,然后和上述三个程序放在同一文件夹下,双击ck.bat,就能够实现对拍了。对拍的优势在于能够近似模拟出出题人的数据来检验你的程序,一般在考场上通过了对拍的程序很难写挂。当然有的时候随机数据不一定能够满足我们的需求,这时候需要我们从出题人的角度出发,去构造一些最坏情况下的数据,来检验我们程序的强健性。

第三步:提交之前,检查文件名,再次编译程序,运行一遍样例,以防手抽。

静态差错大大降低了程序出错的概率,减少了动态调试的时间,动态查错给程序上了双保险,最后的检查防止了意外情况的出现。这样的程序的正确性能够大大提高。

在调试中,最关键的一点,是站在逻辑的高度去思考程序,而不是从某个数据的角度去查看变量,这样才能避免陷于调试的泥潭不能自拔。

BZOJ 2324: [ZJOI2011]营救皮卡丘(带上下限的最小费用最大流)

这道题么= =还是有些恶心的,第一次写带上下界的网络流,整个人都萌萌哒~~~

首先先预处理得最短路后

直接用费用流做就行了。

第一次写,还是挺好写的= =

CODE:

 

BZOJ 1198: [HNOI2006]军机调度(搜索)

直接暴搜就行了= =

CODE:

 

BZOJ 1103: [POI2007]大都市meg(dfs序,树状数组)

本来还想链剖的,结果才发现能直接树状数组的= =

记录遍历到达点与退出点的时间,然后一开始每个到达时间+1,退出时间-1,置为公路就-1,+1,询问直接点1到该点到达时间求和就行了- –

 

BZOJ 1228: [SDOI2009]E&D(SG定理)

这道嘛,很容易就看出是个nim和,然后问题就是怎么算子问题的sg函数了

先暴力个表看下规律,很容易就找出来了~~~(百度空间又渣了,图贴不出来= =)

32

0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 4 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 5

1 1 2 2 1 1 3 3 1 1 2 2 1 1 4 4 1 1 2 2 1 1 3 3 1 1 2 2 1 1 5 5

0 2 0 2 0 3 0 3 0 2 0 2 0 4 0 4 0 2 0 2 0 3 0 3 0 2 0 2 0 5 0 5

2 2 2 2 3 3 3 3 2 2 2 2 4 4 4 4 2 2 2 2 3 3 3 3 2 2 2 2 5 5 5 5

0 1 0 3 0 1 0 3 0 1 0 4 0 1 0 4 0 1 0 3 0 1 0 3 0 1 0 5 0 1 0 5

1 1 3 3 1 1 3 3 1 1 4 4 1 1 4 4 1 1 3 3 1 1 3 3 1 1 5 5 1 1 5 5

0 3 0 3 0 3 0 3 0 4 0 4 0 4 0 4 0 3 0 3 0 3 0 3 0 5 0 5 0 5 0 5

3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 5 5 5 5 5 5 5 5

0 1 0 2 0 1 0 4 0 1 0 2 0 1 0 4 0 1 0 2 0 1 0 5 0 1 0 2 0 1 0 5

1 1 2 2 1 1 4 4 1 1 2 2 1 1 4 4 1 1 2 2 1 1 5 5 1 1 2 2 1 1 5 5

0 2 0 2 0 4 0 4 0 2 0 2 0 4 0 4 0 2 0 2 0 5 0 5 0 2 0 2 0 5 0 5

2 2 2 2 4 4 4 4 2 2 2 2 4 4 4 4 2 2 2 2 5 5 5 5 2 2 2 2 5 5 5 5

0 1 0 4 0 1 0 4 0 1 0 4 0 1 0 4 0 1 0 5 0 1 0 5 0 1 0 5 0 1 0 5

1 1 4 4 1 1 4 4 1 1 4 4 1 1 4 4 1 1 5 5 1 1 5 5 1 1 5 5 1 1 5 5

0 4 0 4 0 4 0 4 0 4 0 4 0 4 0 4 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5

4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 5 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 5

1 1 2 2 1 1 3 3 1 1 2 2 1 1 5 5 1 1 2 2 1 1 3 3 1 1 2 2 1 1 5 5

0 2 0 2 0 3 0 3 0 2 0 2 0 5 0 5 0 2 0 2 0 3 0 3 0 2 0 2 0 5 0 5

2 2 2 2 3 3 3 3 2 2 2 2 5 5 5 5 2 2 2 2 3 3 3 3 2 2 2 2 5 5 5 5

0 1 0 3 0 1 0 3 0 1 0 5 0 1 0 5 0 1 0 3 0 1 0 3 0 1 0 5 0 1 0 5

1 1 3 3 1 1 3 3 1 1 5 5 1 1 5 5 1 1 3 3 1 1 3 3 1 1 5 5 1 1 5 5

0 3 0 3 0 3 0 3 0 5 0 5 0 5 0 5 0 3 0 3 0 3 0 3 0 5 0 5 0 5 0 5

3 3 3 3 3 3 3 3 5 5 5 5 5 5 5 5 3 3 3 3 3 3 3 3 5 5 5 5 5 5 5 5

0 1 0 2 0 1 0 5 0 1 0 2 0 1 0 5 0 1 0 2 0 1 0 5 0 1 0 2 0 1 0 5

1 1 2 2 1 1 5 5 1 1 2 2 1 1 5 5 1 1 2 2 1 1 5 5 1 1 2 2 1 1 5 5

0 2 0 2 0 5 0 5 0 2 0 2 0 5 0 5 0 2 0 2 0 5 0 5 0 2 0 2 0 5 0 5

2 2 2 2 5 5 5 5 2 2 2 2 5 5 5 5 2 2 2 2 5 5 5 5 2 2 2 2 5 5 5 5

0 1 0 5 0 1 0 5 0 1 0 5 0 1 0 5 0 1 0 5 0 1 0 5 0 1 0 5 0 1 0 5

1 1 5 5 1 1 5 5 1 1 5 5 1 1 5 5 1 1 5 5 1 1 5 5 1 1 5 5 1 1 5 5

0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5

5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

只能这样了= =

很容易就能写出来了= =

CODE:

 

Noip 2014酱油记+简要题解

好吧,day2T1把d默认为1也是醉了,现在只能期待数据弱然后怒卡一等线吧QAQ

Day0 第一次下午出发啊真是不错,才2小时左右就到了233,在车上把sao和fate补掉就到了= = 然后到宾馆之后,没wifi的生活就是惨啊QAQ 把空境补完就睡了= =

Day1 时隔一年,终于又回到了六中,不过题目真是越来越简单了QAQ,day1 3道水题直接水过了,然后就开始对拍了,不过我对拍+出数据的正确方法还没掌握,必须给力一点啊QAQ 回到宾馆之后,去找偏远小渔村补番队的蹭了下wifi 下了魔法少女伊利亚 ,不得不说伊利亚真是太萌了,结果看到12点把第一季看完了,真是不好啊

Day2 题目还是依旧水,不过t1居然被样例误导了默认d为1了!!!!对拍时数据也都是d为1的特殊情况,结果就gg了QAQ,t2水过之后直接看T3,貌似想到了正解(不过和别人的不一样,但应该能过吧)就水了70分,结果就只能470分滚粗可能是我最后一届的noip了QAQ,现在只能期待奇迹了QAQ

这次暴露出了很多问题啊,尤其是day2,一开始轻视了,以为前两题是很容易的就有点轻视了,不能这样子啊QAQ

不过既然已经考完了,就不要理了,这100分放在省选也就5分的差距而已,加油!在省选上拿回这5分!!

我的oi之路永不停息!

附:noip简要题解:

day1 :

T1:直接暴力枚举就行了,主要表不要打错就行了

T2:树形DP,记点i的儿子之和以及最大,就能转移了,可能爆栈,建议用队列实现

T3:dp,很容易推出O(nm^2)的做法,然后就可以发现,对于向上飞的情况可以用一个桶来存,就把时间降到o(nm)了

day2:

T1:直接暴力枚举每个点然后计算就行了QAQ(别跟我再提这道题了QAQ)

T2:变成反向边两次bfs搞定

T3:首先如果直接暴力枚举+高精度乘法可以拿50分

用秦九韶算法就能将计算转成高精度除单精度+高精度减法就能70分了

观察70分算法,发现算法瓶颈在于需要对很多不可能的解进行试除

可以发现x必须是a0的约数,而a0的约数在1~m的范围内大概只有10000个左右,又转成70分算法了

线性筛出m范围内的素数,然后对a0进行m以内的分解质因数后枚举a0的约数后进行计算,复杂度o(n位数a0的位数)就能100分了

ps:以上的正解纯属瞎扯= =(自己打后还是不能过= =)

正解应该是:可以发现,如果在mod m条件下f(x)=0,那么x以及x的倍数就可能为f(x)=0 的一个解,那么先用一个小素数(10000左右)筛下,然后用一个大素数(2*10^9左右)来判断就可以啦~~~

[Noi2014]魔法森林( 动态mst lct)

以前一直觉得lct特别难写,自从学了丽洁姐的lct之后,觉得lct居然能这么短,这个主程序能40行左右解决~~~~

这道嘛~~虽说能用spfa解决,但还是写下lct吧

把边按a值排序后一条一条插入并维护bmx值就行了= =

不过还是得膜拜云神在考场上a了这道题,我花了好久,自己还是太弱

NOIP就要来了,在这里祝自己RP++吧

毕竟升高二后,每天几乎都是怀着梦想睡觉的

希望这一年能不辜负我的愿望吧

向着最高点,冲吧!!!

CODE: