DMKaplony's OI Blog

Fly my OI Dreams with CC...

公告

OI...
<2019年4月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

统计

  • 随笔 - 6
  • 文章 - 0
  • 评论 - 0
  • 引用 - 0

常用链接

留言簿(2)

随笔分类(7)

随笔档案(6)

文章分类

搜索

  •  

最新评论

阅读排行榜

评论排行榜

置顶随笔

[置顶]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!!!

posted @ 2010-03-31 08:46 DMKaplony 阅读(187) | 评论 (0)编辑 收藏
[置顶]I'm coming...

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

posted @ 2010-03-03 10:57 DMKaplony 阅读(63) | 评论 (0)编辑 收藏

2010年3月31日

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!!!

posted @ 2010-03-31 08:46 DMKaplony 阅读(187) | 评论 (0)编辑 收藏

2010年3月15日

PKU3268 Silver Cow Party

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

posted @ 2010-03-15 19:34 DMKaplony 阅读(165) | 评论 (0)编辑 收藏

2010年3月4日

PKU3087 Shuffle'm Up

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

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

PKU3087

posted @ 2010-03-04 11:36 DMKaplony 阅读(163) | 评论 (0)编辑 收藏

2010年3月3日

PKU1038 Bugs Integrated, Inc.

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

posted @ 2010-03-03 15:03 DMKaplony 阅读(216) | 评论 (0)编辑 收藏
PKU2663 Tri Tiling

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

PKU2663



我认为我这个是纯粹的省时省心省脑的方法(话说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 能从理论上运算。。。。这是我的理解,见笑了。

话说我还没怎么懂这个公式。。。

posted @ 2010-03-03 15:00 DMKaplony 阅读(180) | 评论 (0)编辑 收藏
I'm coming...

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

posted @ 2010-03-03 10:57 DMKaplony 阅读(63) | 评论 (0)编辑 收藏
仅列出标题