DMKaplony's OI Blog

[置顶]3月31了...说好的3,4月份要好好学习知识,现在稍稍总结一下...

时间复杂度

（渐近时间复杂度的严格定义，NP问题，时间复杂度的分析方法，主定理）

这个方面没什么进展。。。



排序算法

（平方排序算法的应用，Shell排序，快速排序，归并排序，时间复杂度下界，三种线性时间排序，外部排序）

排序的话，Shell和归并没怎么看，线性的只写过计数排（写后缀树组时被迫的...），外排也没怎么看。。。


指针

（链表，搜索判重，邻接表，开散列，二叉树的表示，多叉树的表示）

不知道和指针有什么关系。。。Hash倒是用了几次，不过好像我对Hash这个东西有点轻视。。。毕竟不是完美的算法。。。
二叉和多叉用Pointer没什么问题，邻接表也早已经代替了邻接矩阵（尽管这不一定是一个进步...）。


图论

（图论模型的建立，平面图，欧拉公式与五色定理，求强连通分量，求割点和桥，欧拉回路，AOV问题，AOE问题，最小生成树的三种算法，最短路的三种算法，标号法，差分约束系统，验证二分图，Konig定理，匈牙利算法，KM算法，稳定婚姻系统，最大流算法，最小割最大流定理，最小费用最大流算法）

这里东西比较多，
图论模型这个东西不好说。。。
平面图要加强，这个只看过一遍，但是没有用到做题里面。。。
欧拉公式和五色没怎么看，也没怎么用。。。
强联通和割会用了Tarjan，掌握的还算可以，但是真的需要加强。。。
Euler回路好久没有用了，但是还记得算法，写起来可能稍慢一点。。。
AOV和AOE真的真的好久没有涉及。。。
最小生成树只知道2种方法，并且只实现过Prim，这个有点遗憾。。。
最短路的。。。有3种算法么？知道Dijkstra+Heap和SPFA（话说竟然cc那么习惯些Dij+Heap...），都实现过，还有那种标号法，没有实现过，看DP的时候看到过一次。。。
标号法？最短路的么？。。。
差分约束，曾经练了好几n次，后来应该全部掌握了，但是现在忘了点，需要再看一遍。。。
验证二分图。。黑白染色吧？只知道这个。。。
Konig定理，忘了是哪个定理了，说出来可能知道。。。
Hungary算法，好久没写，但是还是应该能写出来的。。。
稳定婚姻，延迟认可（GS）算法，看来几遍感觉不难，但是一直没有实现过。。。
最大流，不会Dinic，只用ISap，然后就这样。。。
费用流，zkw的那个算法真的很好，问题是稍稍变一下我就不会了。。。所以还是被迫的SpfaFlow，不知道是不是cc这个也用Dij+Heap来写。。。
最小流最大割定理，我只知道他们是相等的，其他一概不知。。。


这个还不全，比如还有强联通图定向算法和最小树形图的一大堆东西。。
强联通定向刚才看的，感觉不难，但是还没有去实现。。
我的最小树形图还是用Pascal写的。。感觉比较古老。。




数据结构

（广度优先搜索，验证括号匹配，表达式计算，递归的编译，Hash表，分段Hash，并查集，Tarjan算法，二叉堆，左偏树，斜堆，二项堆，二叉查找树，AVL，Treap，Splay，静态二叉查找树，2-d树，线段树，二维线段树，矩形树，Trie树，块状链表）

这个比较复杂，
Bfs不用说了，验证bracket比配也不说了，表达式计算好久没写了。。
递归的编译是不是字符串处理？
Hash说过了。
分段Hash是字符串的RK么?
并查集感觉还行，但是有时候就是写不对（我只是说比较复杂的题目）。。。
Tarjan，哈哈，只是求LCA时没用过这个。。。
二叉堆。。。写的比较顺手，但是上次那个Dij+Heap还是不知道错在了哪里。。。
左偏树，好久没写了。这个真的需要好好的加强。。。
斜堆，左偏树的自调整模式，会LeftistHeap就行了。。。
二项堆，没写过，痛苦的是连PairingHeap都实现过，竟然没写过二项堆和斐波那契堆。。。
二叉查找树，AVL，Treap，Splay，静态二叉查找树，我只用SBT估计就行，其他的没实现过，但是都明白大概怎么写（最多就是写不出来...）。。。
2-d树不知道具体是那种树。。。
线段树，这个好好加强了一会，现在的感觉是还需要再加强。。。
二维线段树，没实现过，不过感觉写成二叉的那种然后切矩形比较不错。。。
矩形树，不知道是不是我认为的二维线段树的那种写法。。。
Trie树，哈哈，这个写的很顺手。然后还有一堆东西等字符串那里去写。。。
块状链表。。这个真的有必要写么？感觉性价比真的不怎么样。。。


这个也不全。。。
想到了看到过的笛卡尔树和杨氏图表。。。感觉都是很优秀的数据结构。。但是只是看过。。。



按位运算

（and，or，xor，shl，shr，一些应用）


这个没什么好说的，但是自我感觉很差，差的不行了的那种地步。。
想到CrazyProgramming里面绝影说过，至少要做到一眼能把c*18优化成(c<<1)+(c<<4)才行。。。

数论

（整除，集合论，关系，素数，进位制，辗转相除，扩展的辗转相除，同余运算，解线性同余方程，中国剩余定理）

这个方面比较惨，本来数学就差（不像cc那个数学课代表...），
整除，会点儿有限。。。
集合，不知道怎么用，当做不会。。。
素数，这个。怎么用？但是会求了。但是O(n)求筛素数真的不是很熟的说。。。
进位制，这个。。勉强当做不会吧。。。
Gcd还是会的。。。
ExGcd只写对过一次。。。
同余？这个要研究的很深很深的。。。
线性同余方程和中国剩余定理。看过n遍，实现过0遍。。






计算几何

（平面解几及其应用，向量，点积及其应用，叉积及其应用，半平面相交，求点集的凸包，最近点对问题，凸多边形的交，离散化与扫描）

计算几何很难，但是貌似ACM很青睐。。
平面解几和应用，不明白指什么。。。
向量，这个知道。。。
点积和叉积，这个还是会算的，但是应用的话，掌握的不好。。。
半平面交。。。独立想到了好像是O(nlogn)的算法，O(n^2)的不会，
但是现在都忘记了。。。
凸包还是会的。但是真的不喜欢极角排序，还是用x-y排序的那种比较顺手。。。还有，最远点对这个好像找到了O(n)的方法，祝贺自己。。。
最近点对，这个不是分治么？分治我可真的一窍不通。。。
离散化常用，自己写QSort，然后去重。。。
扫描。。。听这个词像是O(n)的算法。。。




组合数学

（排列与组合，鸽笼原理，容斥原理，递推，Fibonacci数列，Catalan数列，Stirling数，差分序列，生成函数，置换，Polya原理）

这个方面ccccc(差差差差差...)。
基本还都不会。。。




概率论

（简单概率，条件概率，Bayes定理，期望值）

同上，
但是总想写高斯消元或者高斯约当消元，一直未果。。。




矩阵

（矩阵的概念和运算，二分求解线性递推方程，多米诺骨牌棋盘覆盖方案数，高斯消元）

这个稍稍好一点，
原因是用矩阵和QPow来加速DP。。。
其他应用一概不会。。。



字符串处理

（KMP，后缀树，有限状态自动机，Huffman编码，简单密码学）

这个应该比较好了。。
KMP首先是会写了，EXKMP也是。
后缀树没写过（也没想写过），后缀数组可以了，但是一直不熟悉。。。
自动机没用过（包括AC的）。。。
但是写过TrieGraph，其实这个就是自动机，但是没用来写过题。。。
Huffman这个东西，好久没碰了。。。
简单密码学。。。我看到了简单。。但是没看见密码。。。


动态规划

（单调队列，凸完全单调性，树型动规，多叉转二叉，状态压缩类动规，四边形不等式）

这个大多都明白，但是很多东西都不是特别熟练，就这样。。。
四边形不等式真的有很大用处么？




博奕论

（Nim取子游戏，博弈树，Shannon开关游戏）

这个最烂，一窍还不通。。。



搜索

（A*，ID，IDA*，随机调整，遗传算法）

啊哈，
这个应该多做做题了。。


微积分初步

（极限思想，导数，积分，定积分，立体解析几何）

啊哈。。立几的不会，其他的比较惨。。。

 

 总体情况就是这样。。。
经过了一个月的努力，已经进步了不少了，
照原计划，4月份把剩下的东西搞定。。。
话说。。。大哥（肖伊康同学...）进了数学的国家队。。。
我不管这些，我只知道为了一个人我要好好的NOI和高考。。。
我只知道：
我和我最后的倔强，握紧双手绝对不放，下一站是不是天堂，就算失望不能绝望，我和我骄傲的倔强，我在风中大声的唱，这一次为自己疯狂，就这一次我和我的倔强。。。

我相信，在晚上摸黑爬起来，打开电脑的时候，这首歌会一直陪着我，我也相信，以后绝对不会睡的太早，不能睡的太早。。。

加油，我的NOI！！！

[置顶]I'm coming...

OI之路继续...准备NOI2010... 有像HQM神牛一样的遭遇，就要有和HQM神牛一样的成绩！

3月31了...说好的3,4月份要好好学习知识,现在稍稍总结一下...

时间复杂度

（渐近时间复杂度的严格定义，NP问题，时间复杂度的分析方法，主定理）

这个方面没什么进展。。。



排序算法

（平方排序算法的应用，Shell排序，快速排序，归并排序，时间复杂度下界，三种线性时间排序，外部排序）

排序的话，Shell和归并没怎么看，线性的只写过计数排（写后缀树组时被迫的...），外排也没怎么看。。。


指针

（链表，搜索判重，邻接表，开散列，二叉树的表示，多叉树的表示）

不知道和指针有什么关系。。。Hash倒是用了几次，不过好像我对Hash这个东西有点轻视。。。毕竟不是完美的算法。。。
二叉和多叉用Pointer没什么问题，邻接表也早已经代替了邻接矩阵（尽管这不一定是一个进步...）。


图论

（图论模型的建立，平面图，欧拉公式与五色定理，求强连通分量，求割点和桥，欧拉回路，AOV问题，AOE问题，最小生成树的三种算法，最短路的三种算法，标号法，差分约束系统，验证二分图，Konig定理，匈牙利算法，KM算法，稳定婚姻系统，最大流算法，最小割最大流定理，最小费用最大流算法）

这里东西比较多，
图论模型这个东西不好说。。。
平面图要加强，这个只看过一遍，但是没有用到做题里面。。。
欧拉公式和五色没怎么看，也没怎么用。。。
强联通和割会用了Tarjan，掌握的还算可以，但是真的需要加强。。。
Euler回路好久没有用了，但是还记得算法，写起来可能稍慢一点。。。
AOV和AOE真的真的好久没有涉及。。。
最小生成树只知道2种方法，并且只实现过Prim，这个有点遗憾。。。
最短路的。。。有3种算法么？知道Dijkstra+Heap和SPFA（话说竟然cc那么习惯些Dij+Heap...），都实现过，还有那种标号法，没有实现过，看DP的时候看到过一次。。。
标号法？最短路的么？。。。
差分约束，曾经练了好几n次，后来应该全部掌握了，但是现在忘了点，需要再看一遍。。。
验证二分图。。黑白染色吧？只知道这个。。。
Konig定理，忘了是哪个定理了，说出来可能知道。。。
Hungary算法，好久没写，但是还是应该能写出来的。。。
稳定婚姻，延迟认可（GS）算法，看来几遍感觉不难，但是一直没有实现过。。。
最大流，不会Dinic，只用ISap，然后就这样。。。
费用流，zkw的那个算法真的很好，问题是稍稍变一下我就不会了。。。所以还是被迫的SpfaFlow，不知道是不是cc这个也用Dij+Heap来写。。。
最小流最大割定理，我只知道他们是相等的，其他一概不知。。。


这个还不全，比如还有强联通图定向算法和最小树形图的一大堆东西。。
强联通定向刚才看的，感觉不难，但是还没有去实现。。
我的最小树形图还是用Pascal写的。。感觉比较古老。。




数据结构

（广度优先搜索，验证括号匹配，表达式计算，递归的编译，Hash表，分段Hash，并查集，Tarjan算法，二叉堆，左偏树，斜堆，二项堆，二叉查找树，AVL，Treap，Splay，静态二叉查找树，2-d树，线段树，二维线段树，矩形树，Trie树，块状链表）

这个比较复杂，
Bfs不用说了，验证bracket比配也不说了，表达式计算好久没写了。。
递归的编译是不是字符串处理？
Hash说过了。
分段Hash是字符串的RK么?
并查集感觉还行，但是有时候就是写不对（我只是说比较复杂的题目）。。。
Tarjan，哈哈，只是求LCA时没用过这个。。。
二叉堆。。。写的比较顺手，但是上次那个Dij+Heap还是不知道错在了哪里。。。
左偏树，好久没写了。这个真的需要好好的加强。。。
斜堆，左偏树的自调整模式，会LeftistHeap就行了。。。
二项堆，没写过，痛苦的是连PairingHeap都实现过，竟然没写过二项堆和斐波那契堆。。。
二叉查找树，AVL，Treap，Splay，静态二叉查找树，我只用SBT估计就行，其他的没实现过，但是都明白大概怎么写（最多就是写不出来...）。。。
2-d树不知道具体是那种树。。。
线段树，这个好好加强了一会，现在的感觉是还需要再加强。。。
二维线段树，没实现过，不过感觉写成二叉的那种然后切矩形比较不错。。。
矩形树，不知道是不是我认为的二维线段树的那种写法。。。
Trie树，哈哈，这个写的很顺手。然后还有一堆东西等字符串那里去写。。。
块状链表。。这个真的有必要写么？感觉性价比真的不怎么样。。。


这个也不全。。。
想到了看到过的笛卡尔树和杨氏图表。。。感觉都是很优秀的数据结构。。但是只是看过。。。



按位运算

（and，or，xor，shl，shr，一些应用）


这个没什么好说的，但是自我感觉很差，差的不行了的那种地步。。
想到CrazyProgramming里面绝影说过，至少要做到一眼能把c*18优化成(c<<1)+(c<<4)才行。。。

数论

（整除，集合论，关系，素数，进位制，辗转相除，扩展的辗转相除，同余运算，解线性同余方程，中国剩余定理）

这个方面比较惨，本来数学就差（不像cc那个数学课代表...），
整除，会点儿有限。。。
集合，不知道怎么用，当做不会。。。
素数，这个。怎么用？但是会求了。但是O(n)求筛素数真的不是很熟的说。。。
进位制，这个。。勉强当做不会吧。。。
Gcd还是会的。。。
ExGcd只写对过一次。。。
同余？这个要研究的很深很深的。。。
线性同余方程和中国剩余定理。看过n遍，实现过0遍。。






计算几何

（平面解几及其应用，向量，点积及其应用，叉积及其应用，半平面相交，求点集的凸包，最近点对问题，凸多边形的交，离散化与扫描）

计算几何很难，但是貌似ACM很青睐。。
平面解几和应用，不明白指什么。。。
向量，这个知道。。。
点积和叉积，这个还是会算的，但是应用的话，掌握的不好。。。
半平面交。。。独立想到了好像是O(nlogn)的算法，O(n^2)的不会，
但是现在都忘记了。。。
凸包还是会的。但是真的不喜欢极角排序，还是用x-y排序的那种比较顺手。。。还有，最远点对这个好像找到了O(n)的方法，祝贺自己。。。
最近点对，这个不是分治么？分治我可真的一窍不通。。。
离散化常用，自己写QSort，然后去重。。。
扫描。。。听这个词像是O(n)的算法。。。




组合数学

（排列与组合，鸽笼原理，容斥原理，递推，Fibonacci数列，Catalan数列，Stirling数，差分序列，生成函数，置换，Polya原理）

这个方面ccccc(差差差差差...)。
基本还都不会。。。




概率论

（简单概率，条件概率，Bayes定理，期望值）

同上，
但是总想写高斯消元或者高斯约当消元，一直未果。。。




矩阵

（矩阵的概念和运算，二分求解线性递推方程，多米诺骨牌棋盘覆盖方案数，高斯消元）

这个稍稍好一点，
原因是用矩阵和QPow来加速DP。。。
其他应用一概不会。。。



字符串处理

（KMP，后缀树，有限状态自动机，Huffman编码，简单密码学）

这个应该比较好了。。
KMP首先是会写了，EXKMP也是。
后缀树没写过（也没想写过），后缀数组可以了，但是一直不熟悉。。。
自动机没用过（包括AC的）。。。
但是写过TrieGraph，其实这个就是自动机，但是没用来写过题。。。
Huffman这个东西，好久没碰了。。。
简单密码学。。。我看到了简单。。但是没看见密码。。。


动态规划

（单调队列，凸完全单调性，树型动规，多叉转二叉，状态压缩类动规，四边形不等式）

这个大多都明白，但是很多东西都不是特别熟练，就这样。。。
四边形不等式真的有很大用处么？




博奕论

（Nim取子游戏，博弈树，Shannon开关游戏）

这个最烂，一窍还不通。。。



搜索

（A*，ID，IDA*，随机调整，遗传算法）

啊哈，
这个应该多做做题了。。


微积分初步

（极限思想，导数，积分，定积分，立体解析几何）

啊哈。。立几的不会，其他的比较惨。。。

 

 总体情况就是这样。。。
经过了一个月的努力，已经进步了不少了，
照原计划，4月份把剩下的东西搞定。。。
话说。。。大哥（肖伊康同学...）进了数学的国家队。。。
我不管这些，我只知道为了一个人我要好好的NOI和高考。。。
我只知道：
我和我最后的倔强，握紧双手绝对不放，下一站是不是天堂，就算失望不能绝望，我和我骄傲的倔强，我在风中大声的唱，这一次为自己疯狂，就这一次我和我的倔强。。。

我相信，在晚上摸黑爬起来，打开电脑的时候，这首歌会一直陪着我，我也相信，以后绝对不会睡的太早，不能睡的太早。。。

加油，我的NOI！！！

PKU3268 Silver Cow Party

     摘要: 话说好久没写上来了。今天比较高兴，她竟然去了我的QZone！！！虽然一点准备都没有，（我都是今天才知道的），但是好高兴。。PKU3268 可以写SPFA，可以写DijkstraWithHeap，反正别傻傻的做n次就行。。 PKU3268Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHi...  阅读全文

PKU3087 Shuffle'm Up

BruteForce，纯模拟吧，无解时会回到初始态。
不过这题好像有数学方法的，
而且任何情况都会回到初始态，
这个应该有证明。
还记得有一道题是求回到初始态的步数。。

总之是用BF秒过了。。
更多深入以后研究。

PKU3087
 1/**//*
 2Task: pku3087
 3Author: DMKaplony
 4Date: 04/03/2010 11:16:17 China Standard Time
 5State: 
 6    6511528    DMKaplony    3087    Accepted    180K    0MS    C++    1729B    2010-03-04 11:32:06
 7Memo: BruteForce--Forxcc0322
 8*/
 9
10#include <iostream>
11
12#define MAXL 3000
13
14using namespace std;
15
16char a[MAXL], b[MAXL], aa[MAXL], bb[MAXL], g[MAXL];
17int n;
18
19bool NoAnswer(){
20    int i;
21    for (i=1; i<n+1; i++){
22        if (a[i] != aa[i] || b[i] != bb[i])
23            return false;
24        }
25    return true;
26    }
27int Check(){
28    if (NoAnswer()){
29        return -1;
30        }
31    for (int i=1; i<n+1; i++){
32        if (a[i] != g[i] || b[i] != g[n + i])
33            return 0;
34        }
35    return 1;
36    }
37
38void Alter(){
39    char tmp[MAXL];
40    int i;
41    for (i=1; i<n+1; i++){
42        tmp[(i << 1) - 1] = b[i];
43        tmp[i << 1] = a[i];
44        }
45    for (i=1; i<n+1; i++){
46        a[i] = tmp[i];
47        b[i] = tmp[n + i];
48        }
49    }
50int main(){
51    int cases;
52    scanf("%d", &cases);
53    for (int o=1; o<cases+1; o++){
54        scanf("%d", &n);
55        int i;
56        for (i=1; i<n+1; i++){
57            scanf(" %c", &a[i]);
58            }
59        for (i=1; i<n+1; i++){
60            scanf(" %c", &b[i]);
61            }
62        //
63        for (i=1; i<(n << 1)+1; i++){
64            scanf(" %c", &g[i]);
65            }
66        //
67        memcpy(aa, a, sizeof(a));
68        memcpy(bb, b, sizeof(b));
69        int ret;
70        int counter = 1;
71        Alter();
72        while (1){
73            ret = Check();
74            if (ret)
75                break;
76            Alter();
77            counter++;
78            }
79        if (ret == -1)
80            printf("%d %d\n", o, ret);
81        else
82            printf("%d %d\n", o, counter);
83        }
84    return 0;
85    }
86

PKU1038 Bugs Integrated, Inc.

     摘要: PKU1038，动态规划，用的三进制压缩状态（不知道和二进制那个快，毕竟计算机这个东西是二进制的），感觉没用的状态有点多，所以改成了记忆化搜索，另外第一次排到了速度的23名。。 PKU1038Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> ...  阅读全文

PKU2663 Tri Tiling

简单的DP，好像NOIP之前就做过这样的题。
这次仍然是很暴力的转移。。（好像我比较喜欢这个，省脑子。）

PKU2663
 1/**//*
 2Task: pku2663
 3Author: DMKaplony
 4Date: 03/03/2010 14:41:52 China Standard Time
 5State: Finish @ 03/03/2010 14:50:14 China Standard Time
 6    6507229    DMKaplony    2663    Accepted    164K    0MS    C++    948B    2010-03-03 14:50:26
 7Memo: DP--Forxcc0322
 8*/
 9
10#include <iostream>
11
12using namespace std;
13
14int f[2][8];
15int n;
16
17int main(){
18    while (1){
19        scanf("%d", &n);
20        if (n == -1)
21            break;
22        memset(f, 0, sizeof(f));
23        f[0][7] = 1;
24        int last7 = 0;
25        for (int i=1; i<n+1; i++){
26            f[i & 1][1] = f[i - 1 & 1][6];
27            f[i & 1][2] = f[i - 1 & 1][5];
28            f[i & 1][3] = f[i - 1 & 1][4];
29            f[i & 1][4] = f[i - 1 & 1][3] + f[i - 1 & 1][7];
30            f[i & 1][5] = f[i - 1 & 1][2];
31            f[i & 1][6] = f[i - 1 & 1][1] + f[i - 1 & 1][7];
32            f[i & 1][7] = f[i - 1 & 1][4] + f[i - 1 & 1][6] + last7;
33            last7 = f[i - 1 & 1][7];
34            }
35        printf("%d\n", f[n & 1][7]);
36        }
37    return 0;
38    }
39

我认为我这个是纯粹的省时省心省脑的方法（话说last7还是后来加上去的）。
其实有更为精妙的数学方法：
【引用PKUDiscuss：
Posted by denghongchao at 2009-08-14 18:43:58 on Problem 2663
先假设没2竖为1 单位。
对当前解a[i] ,有
1.在此处放一单位的积木。等于a[i-1]*3;
2.与前面相连接。连接的方案有 2 * (a[i-2] + a[i-3] +......+a[0]);
a[i] = 3*a[i-1] + 2*(a[i-2] + a[i-3] +......+a[0]);
a[i-1] = 3*a[i-2] + 2*(a[i-3] + a[i-3] +......+a[0]);
a[i-1] - a[i-2] = 2*(a[i-2] + a[i-3] +......+a[0]);

解得a[i] = a[i-1] * 4 - a[i-2];
至于为何要a[0] = 1，从公式中就可看到因为要一直取到最前面一个单位。这时也有2种情况。故a[0] = 1 能从理论上运算。。。。这是我的理解，见笑了。
】
话说我还没怎么懂这个公式。。。

I'm coming...

OI之路继续...准备NOI2010... 有像HQM神牛一样的遭遇，就要有和HQM神牛一样的成绩！