Category: 算法笔记

【算法笔记】O(1)快速乘

Qizy Leave a comment

对于大整数乘法来讲，一般使用快速乘
但不论是按10进制拆分或是二进制拆分，其复杂度均有log
今天鏼爷提供了一种O(1)的方法：
设所求为：a*b (%c)

1) a%c, b%c <= 1e9
这样的话，O(1)直接算就好

2) 其他情况
用long double计算\(k = \left\lfloor {\frac{{ab}}{c}} \right\rfloor\)
之后输出a*b-c*k即可
因为这样的话，不会出现一个分母特别大，分子特别小的情况，所以long double的精度能够满足要求了

【算法笔记】杜教筛

Qizy 17 Comments

首先安利两篇Blog：
http://blog.csdn.net/skywalkert/article/details/50500009
http://www.cnblogs.com/joyouth/p/5517734.html

自己对于杜教筛的理解就是下面这个式子：
\(\left\{ {\begin{array}{*{20}{l}}
{f(n) = \sum\limits_{i = 1}^n {\varphi (i)} }\\
{(\varphi \times I)(x) = id}\\
{g(n) = \sum\limits_{i = 1}^n {id(i)} }
\end{array}} \right. \Rightarrow f(n) = g(n) – \sum\limits_{i = {\rm{2}}}^n {f(\frac{n}{i})} \)

【算法笔记】再看线性基

Qizy 3 Comments

线性基 -> 线性无关 -> 如果有一个新向量与当前的基线性无关，则加入后当前基底表示的空间更大
判断线性相关与否 -> 当前向量能否被当前基底表示 -> 如果不能，加入当前的基底中
线性基的大小 -> 空间的维度 -> 空间的大小 -> 空间最大，即线性基的个数越多 -> 线性基的大小与其插入顺序不相关 -> 线性基的插入顺序不会影响答案

因为线性基属于线性代数范畴，其深入理解又与拟阵挂钩，而拟阵则更为高深
所以今晚再一次回看线性基，仍然没有大彻大悟，不过确实有更深入的理解
感觉wiki上的这一段话或许能说明插入顺序不影响结果：
96453144

【算法笔记】网络流相关·第二波冲刺

Qizy 14 Comments

近日，花了4天时间再一次进行了网络流相关的专题
已经将总体进度推进到了hzwer的第四页
虽不能说硕果累累，但也是略有成效了

做题的相关感悟如下：
1）最小路径覆盖（路径问题）：出度入度拆点后跑二分图匹配
2）最大独立集：二分图建图后跑最小割
3）供求关系可以考虑二分图
4）棋盘类问题可以考虑染色
5）最大权闭合子图
6）列出数学等式，按等式的正负配合流量平衡进行建图

这一次虽然做了很多题，但注定只是一次阶段性的冲刺
因为之前有所听闻的一些经典建模方式仍然没有接触到
所以一定会有下一次冲刺哒！

【Tricks】isdigit

Qizy Leave a comment

判断一个字符c是否为阿拉伯数字，常用的写法有两种：
1）’0′ <= c && c <= ‘9’
2) isdigit(c)

编程复杂度差不多，让我们来从效率上对比一下：
1)随机的数字串（字符串中全是数字）
789456453415
2）随机的字符串（字符串的每一个字符的ascal码从1—127随机）
78945454478
3)作为流读入的判断语句
945648
ps：上述结果在不同环境下可能会有不同结果，故上述结果仅供参考

结论：
这两种写法，对于常数的影响不大，可以随便用

【算法笔记】仙人掌

Qizy 2 Comments

仙人掌这个东西，肯定是前排膜拜VFK:http://vfleaking.blog.uoj.ac/slide/89#/
然后嘛，就是狂膜一波CA爷：http://blog.csdn.net/creationaugust/article/details/48007069
仍然膜拜CA爷：http://blog.csdn.net/creationaugust/article/details/48022291

反正我的仙人掌栽培技术就这水平了
什么世界领先的动态仙人掌栽培技术，还是算了吧QAQ
ps：感觉CA的东西比VFK的实用？
psx2：感觉wc上这张图还是很带感的，贴上来 =￣ω￣=
21467125346712

【算法笔记】群论

Qizy 2 Comments

首先是强烈推荐hht的bolg：http://techotaku.lofter.com/post/4856f0_59d4957
感觉看了之后群论就有了概念了啊!

至于细节方面，可以参考这篇blog：
http://blog.csdn.net/xuzengqiang/article/details/7476671

一些要点我还是写一写，免得以后忘了吧：
1）因为Polya只能解决不限使用次数的染色问题，所以Burnside也是有用的
2）Burnside用的是不动点的个数，Polya用的是置换的循环节
3）很多题目，给出的置换，不足以组成一个置换群，所以要先补足置换群

其实一些比较难的题都还没有做，比如:BZOJ_1488
所以，以后还要花时间再做一次专题才行啊！
另外，定理的证明还一点都不会，只能留到下一次专题一起做了吧！

【算法笔记】博弈论

Qizy 252 Comments

这货，做了一点题，看了一点论文，觉得有以下几个要点：
1）先猜结论，之后再想办法证明
2）不要试图手玩，玩不出来的
3）SG值相同的子游戏，对于游戏和来说可以相互替换
4）以上都不行的时候，就先找一种比较宽泛的必胜/必败状态，再试图推广

另外，还学到了一点绍一的黑科技，现在先暂时不研究，特意截图以供以后研究：
sg_min_one