-
不要把时间和精力浪费在那些恶心的人身上
2010-03-09
那些无聊的人何必要花精力搭理他们呢，做好自己该做的，不去让这些人影响自己的心精才是最好的吧，保持平静，记住对你真正重要的
-
好久好久
2010-03-08
原来很多时候不是坚持或是什么就能有结果的，这一次真的是回头了，我被耗尽多少只有自己清楚，喜欢上了的却注定是个悲剧，我也许真的该死心了，一辈子自己过也挺好，和母亲家人相依为命。这一辈子出生了就没有几年消停生活，树欲静而风不止，也只能逐渐磨练自己，让自己慢慢在漩涡中也能平静着，心里安宁着。
-
比赛 Tips
2009-09-05
涉及精度时时常+0.0005就能过
有的OJ c++编译器中iostream不包含memset
-
HOJ 2833 Watering Hole 解题报告 - [ACM]
2009-08-25
这道题是FF学长改自USACO的一道MST题目，原题说的挺隐晦，但就是没有任何变形的MST，本题说有个jack和John是好朋友，可以给他提供免费管道，当时只能要一根，有p种管（分连接不同pastures），问对于选每一种管，最小费用是多少，这样可以很自然想到次小生成树，在次小生成树种，max数组中存了树中任意两点间路径上最长边长度，O（1）的查询花费，但是本题点多达10000个，开不了邻接矩阵，所以不能用次小生成树，想了一阵，只能尽量优化着暴力了。
优化一：Heap+prim构造最小生成... -
最近点对模板【o（n（logn）】 - [ACM]
2009-08-24
本做法理论复杂度好，但是由于要开一个大数组，第一内存是个问题，第二拖累了时间，实际效果在HOJ的那道题中不如n(logn)^2的，zoj的那道则会MLE，这是我觉得这个程序超时的原因，如果大家能发现是别的原因，请告诉我，十分感谢！
#include<iostream>
#include<cmath>
#define MAX 2100000000
#define N 100005
#define Max (a&g... -
最近点对模板【o（n（logn）^2）】 - [ACM]
2009-08-24
虽然这个看似复杂度高，但是开的数组比较小，用nlogn的做法需要开p[logN][N]这么大的数组，时间代价更高，在HOJ的一道题中，在机房的机器上nlogn的跑了3s，n(logn)^2跑了2.2s。但是这道题是随机数据，如果出比较恶的不知会怎样。
#include<iostream>
#include<cmath>
#define MAX 2100000000
#define N 100005
#defin... -
2—SAT模板
2009-08-21
2—SAT自制模板[HOJ 1917实测：0.05s]：
/*
Algorithm:2-SAT
Tool:Pool,Queue
*/
#include<cstdio>
#include<cstring>
#include<queue>
#define ini(x) memset(x,0,sizeof(x))
#de... -
2-SAT 算法， 及生成树计数 - [ACM]
2009-08-21
2-SAT
2-Sat问题我了解了最简单的以和平委员会为原型的问题，题目意思为每个国家有两个代表，我应从每个国家任意挑选一个代表参加和平委员会，但是各国间可能有某些代表相互有矛盾，此时我就不能选择这样的代表同时参加和平委员会，给出国家个数v，和矛盾关系数m，及m个矛盾关系，求一个可能的方案，第... -
强连通分量——Gabow - [ACM]
2009-08-20
/*
Template: Doubly Connected Components
Algorithm: Gabow + Stack
Tool: Stack + pool
Time: ??
*/
#include<cstdio>
#include<cstring>
#define MAX 0x01010101
#define MIN(x,y) (x<y)?x:y... -
强连通分量——Tarjan+Union-Find Set - [ACM]
2009-08-20
/*
Template:Strong Connected Components
Graph:DAG
Algorithm: Tarjan + Union-Find Set
Time:?? Slower than Stack version of Tarjan
Function:1. Judge if a can reach b 2.Output the number of SCC
*/
#include<cstdio>... -
强连通分量——Tarjan - [ACM]
2009-08-20
/*
Template: Doubly Connected Components
Algorithm: Tarjan + Stack
Tool: Stack + pool
Time: ??
*/
#include<cstdio>
#include<cstring>
#define MAX 0x01010101
#define MIN(x,y) (x<y)?x:y... -
求强连通分量的三种解法和四种实现
2009-08-20
强连通分量的三种算法和四种实现
常见的（我见过的）强连通分量的三种算法有：1. Kosaraju算法（双DFS）2.Tarjan算法 3.Gabow
... -
HOJ 2360 PKU POJ 3177 Redundant Paths - [ACM]
2009-08-19
这道题题意是要保证从任意一点到另一点总有至少两条完全没有重边的路径可走，换句话说即保证图中任意两点间存在环，这时我们可以将已在环中的缩成一点，因为每个环中点对外部点来讲是一连多连的关系，“同进退，共存亡”，这样全图就缩成一棵树了，此时只要我们两两连接叶子，即可，最后所连边数 = （N(叶子) + 1）/2。
实现过程是：我们通过DFS来寻找桥，并在此过程中用low[son]与idx[father]的关系判断是否成环了，成环后用并查集连接两点，此过程... -
Advanced Graph Theory Training Schedule - [ACM]
2009-08-18
1无向图的双连通分量（割点桥）
2有向图的强连通分量
3前K短路（有环无环）
4生成树计数
5.次小生成树
6最小度限制树
7最优比率生成树
8有向图的最小树形图
9一般图匹配带花树算法
10弦图的判定
11顶点的度序列
12无向图的极大团，最大团
13floyd倍增思想
-
网络流总结：
通过这四天的学习，对网络流有了比较深的了解，主要学习了关于两个问题的五种算法：
1. 最大流——增广路BFS
2. 最大流——增广路距离标号法
3. 最小费用流——Bellman-Ford
4. 最小费用流——SPF... -
滚动数组常用于DP之中，在DP过程中，我们在由一个状态转向另一个状态时，很可能之前存储的某些状态信息就已经无用了，例如在01背包问题中，从理解角度讲我们应开DP[i][j]的二维数组，第一维我们存处理到第几个物品，也就是阶段了，第二维存储容量，但是我们获得DP[i],只需使用DP[i - 1]的信息，DP[i - k],k>1都成了无用空间，因此我们可以将数组开成一维就行，迭代更新数组中内容，滚动数组也是这个原理，目的也一样，不过这时候的问题常常是不可能缩成一维的了，比如一个DP[i][j]需...
-
后缀树是一种特殊的字典树，但是从抽象程度，应用面，使用，构造的难度上都比字典树高的多了，它的应用我熟悉的有三种，据说还有更强大的功能：
1.查找一个字符串s是否包含字串t：【字典树同法】 后缀树中包含所有s的后缀，则若t是s的一个子串，则它必是每个后缀分支的前缀，我们按照字典树的查找方式，查是否存在一个后缀包含这个t就可以了。 2.统计s中子串t出现的次数：【找叶子数】 要查找t出现的次数，我们需选择一条前缀是t的... -
树状数组，线段树简介 - [ACM]
2009-08-09
据weisili学长说，线段树是一个非常灵活，变种很多，应用很广的数据结构，实在是很感兴趣，比起DP，数据结构和图论方面的东西对我还是有更大吸引力的。
线 段树实际上是一个特殊的二叉树，它不停的将线段二分，在操作前需按照线段长度先将线段树建好在进行操作，在插入线段时，即覆盖线段上某个子线段，同样递归 操作，修改相应线段/线段组的count值,count代表此段区域被覆盖过的次数，插入的方式可以保证不会在计算覆盖次数时出错，查询某点被覆盖次数 时，按照其所属范围递归...
共1页 1
