Tag: 算法笔记

【算法笔记】单纯形

Qizy Leave a comment

这个算法，时间复杂度是玄学，可以被卡到指数级别。
所以感觉不太可能会是std（校内互测除外QAQ）
所以，就弃坑了！ 不学啦！（╯－＿－）╯╧╧
连去清华的学长hht都说不用学，那就放心地腾出时间学有用的东西吧！
hht_simplex

不过，还是给一份资料吧：http://pan.baidu.com/s/1o783G2e
另外《算法导论》上也有讲，有远大志向的同学可以去看看哦！

【算法笔记】再看网络流

Qizy Leave a comment

最近几天，重新来看网络流的相关题目，发现之前看的基本上都忘了 QAQ
看了一个上午，有以下收获
1.最大流的正确性依赖于每一条s-t流对应了一种实际方案
2.网络流也可以作为二分的可行解判定方式
3.网络流只能在0/1之中做选择，对于1/2、2/3之类的，可以考虑降到0/1之后算贡献
4.对于割边，可以在残余网络中DFS搞一搞，一端可到源点，一端可到汇点即为割边

另外，提供一点网络流24题的相关资源：
1.完整题解：http://www.snowyjone.me/2015/07/lp-and-flow-a/
2.精选题解：https://blog.sengxian.com/solutions/networkflow-24-all
3.大神题解：https://www.byvoid.com/blog/lpf24-solution
4.OJ传送门：http://cojs.tk/cogs/page/page.php?aid=3

【算法笔记】非递归DFS

Qizy Leave a comment

众所周知，DFS可能会爆系统栈。
当然手写栈可以解决这个问题，但是我不会QAQ
但昨天%原教的代码，发现DFS，可以用一个“BFS + while() + 当前弧” 给优雅地替换掉
例如：

void DFS(int w, int f){
	l[w] = ++tot; dep[w] = dep[f]+1;
	for (int i=head[w];i;i=nxt[i])
		if (to[i] != f) DFS(to[i], w);
	r[w] = tot; fa[w][0] = f;
}

就可以用一下代码给完美替代：

inline void BFS(){
	BUF[1] = 1; dep[1] = 1;
	for (int fro=1,bak=1;bak<=fro;bak++){
		int w = BUF[bak];
		for (int i=head[w];i;i=nxt[i]){
			if (!dep[to[i]]) dep[to[i]] = dep[w]+1,
			fa[to[i]][0] = w, BUF[++fro] = to[i];
		}
	}
}

inline void DFS(){
	for (int i=1;i<=n;i++) now[i] = head[i];
	int w = 1; tot = 1;
	while (w) {
		if (!now[w]) {
			r[w] = tot;
			w = fa[w][0];
		} else {
			if (!l[w]) l[w] = ++tot;
			int tmp = to[now[w]]; now[w] = nxt[now[w]];
			if (dep[tmp] != dep[w]+1) continue;
			else w = tmp;
		}
	}
}

代码虽然长一点，但是可以接受，链剖也是可以搞的
至于空间代价，这个只是多了一个当前弧的数组
至于时间代价，有图有真相：non_recursionrecursion

 

【算法笔记】凸包上选点问题

Qizy 28 Comments

问题一：在凸包上，选三个点使围成的面积最大
结论：一直不停的转一转，O(n)可过
证明：YYY的不严密的反证法

问题二：在凸包上，选四个点使围成的面积最大
结论：最优解一定是由两组对踵点对构成，于是旋转卡壳卡一卡也是O（n）的
证明：可以一步步证到，一般的点，一定不是最优解，进而证到，最优解一定是由两对对踵点对构成

哎，今晚好想睡觉，先简单写写，过几天再来填坑QAQ

【算法笔记】字符串阶段性总结

Qizy 6 Comments

Ⅰ. KMP：https://drive.google.com/open?id=0ByB-BvDiMuh9SmFKTlZ1RDQ3SUU
Ⅱ. AC Automaton：https://drive.google.com/open?id=0ByB-BvDiMuh9LV9nTVJheHdwSlU
Ⅲ. Manacher：https://drive.google.com/open?id=0ByB-BvDiMuh9Z2w0N29GclhrX0E
Ⅳ. Palindromic Tree：https://1drv.ms/w/s!AuAAi_9x9e9Gzl4ufwII3sPWi-dQ
Ⅴ. 最小表示法：https://drive.google.com/open?id=0ByB-BvDiMuh9cWotUzJfUE5Hcjg
Ⅵ. Suffix Array：https://1drv.ms/b/s!AuAAi_9x9e9GhntDrSBj8_-W-cuL
Ⅶ. Suffix Automaton：https://1drv.ms/w/s!AuAAi_9x9e9G0SJxlKAQoRMnv0X1

马上要NOI 6连测，时间比较紧，写得特别水QAQ，等过了这段时间，再静下心来重写一次吧

优秀博客备份：
lazycal.logdown.com/posts/195299-suffix-automaton-summary
abcdxyzk.github.io/blog/2014/04/09/alg-suffix/