something
Update 8.30
突然发现好久没写博客了……
主要是因为暑假期间基本上都是学长讲课或者是出去学习
一些性质就不用自己总结了
学到的算法也没有深入研究过,如果有缘能继续学习这些算法的话会连暑假做的题一起发出来
(好像也没人看我博客这样子
这篇就是用来记录点基础的东西给自己看
Cdq
排序很重要 少不了
核心不是找三维偏序关系 而是用左边的更新右边的
二维平面上的可以拆分成几个方向
边双联通分量
重边的情况可以把Tarjan函数中的fa换成边的编号
但要注意两点 初始化head和cnt为-1 以及递归到下一层的时候要用i^1
边双缩点之后是一棵树
两个边双联通分量只有一座桥
点双联通分量
某个点是割点当且仅当它在多个点双里面
反过来也成立 某个点在多个点双里面则一定是割点
两个点双只有一个割点
由于一个点有可能在多个点双里面 所以点双入栈要用边
Update 9.30
【CQOI2013】新数独
1.必须要完全确定初始化没有错误
2.用三目运算符的时候一定要用括号括起来
3.搜索里面如果出现了超乎常理的现象,可以看是不是C++的问题,不是的话看看是不是该用局部变量的用了全局,看不出来的话能改的改一改
4.找到规律之后最好用差不多10组数据确认一下,沉下心来用笔指着仔细看是不是符合规律
5.0和-1不一样,所以为了避免粗心错误尽量用==符号
6.调试的时候可以加条件设断点,这样就不用重新开始了
【ARC102】C
1.跑两列的杨辉三角时要开的数组是$C_n^3$
2.如果题目实在想不出来,一团乱麻的时候可以先想办法让自己平静下来,然后从头开始想,可以用笔把思路记录下来
【COGS1148】新汉诺塔
1.尽量想想有没有特殊情况
2.仔细检查数据是不是和标准输出一样,小数据的话可以逐行认真看,大数据可以写程序对比
【JSOI2010】部落划分
1.合并问题往并查集和最小生成树上面想是没坏处的
【SDOI2016】齿轮
1.写bool类型的dfs的时候要想想每次搜索对结果的影响到底是【为0或1 直接return】还是【算进总和 最后判断】
2.没说自己连通的无向图就是不连通(当然如果题目有特殊条件能判断出来就不算
【POI2013】Tales of seafaring
1.遇到特殊情况下的询问,比如“自己和自己”时“自己独占一个连通图”,仔细分析一下所有情况
2.如果一个点需要取好几种情况下的路(比如边权为1时的最短路),或许可以尝试一下Bfs
【CodeVS2495】水叮当的舞步
1.注意把握时间,不要一条道走到黑,比较长的算法最好经过严格证明再开始写
2.搜索题先想一遍每种搜索方法,想不出来可以勇敢尝试一下A*
3.开了映射数组之后好好检查是不是每个地方都对应的使用了映射数组
4.用邻接表读图的时候注意分清你要用的是边还是点
5.多重循环看看里面的会不会反过来影响外面的
6.多组数据的话注意及时清零,然后不要随便return 0
【Poj1184】聪明的打字员
1.对于一个整数 每一整数位上的操作其实可以用加减法来实现
2.搜索前一定先仔细想想怎么搜最好,可不可以这么搜
【AHOI2012】铁盘整理
1.估价函数能剪多一点就剪多一点(即使只有一层),但要在正确的前提下,不要嫌麻烦
2.估价函数的复杂度要尽可能的小
3.要注意题目用不用离散化,不能看见样例是顺序就想当然,仔细看题
【JSOI2008】最小生成树计数
这个是单独针对这种题会出现一些错误:
1.做最小生成树时,判断$num==n-1$要放在循环内部的最后而不是开头(因为你有可能要打标记
2.搜索与并查集相结合的时候,要考虑是不是要开数组储存这一层的$f[i]$
3.$for$循环中$break$的时候会不会提前跳出,需要好好想一下
4.多次在之前的基础上进行并查集运算,如果你的$f[i]$每次都初始化了,那就得从头到现在的合并过程再模拟一遍
【BJWC2010】次小生成树
1.在记录最大值与次大值的时候,注意是否需要保证最大值与次大值不同