好久没有见到这种清新脱俗的算法了!
刘汝佳的白书上面有这个东西,所以基础部分就自行翻阅啦!
唯一想说的是,有一种O(M)判定是否存在解的算法:
直接求一个SCC,然后看那两个点是否在同一个SCC里即可
当然这种算法也可以求出一组可行解,
但貌似刘汝佳的算法时间勉强够用了,所以就不管了吧( •̀ ω •́ )y
好久没有见到这种清新脱俗的算法了!
刘汝佳的白书上面有这个东西,所以基础部分就自行翻阅啦!
唯一想说的是,有一种O(M)判定是否存在解的算法:
直接求一个SCC,然后看那两个点是否在同一个SCC里即可
当然这种算法也可以求出一组可行解,
但貌似刘汝佳的算法时间勉强够用了,所以就不管了吧( •̀ ω •́ )y
get_phi_prime_mu_in_linear_time
好像之前说过sqrt(n)求phi(n)没用?
ps:之前好像说必须先O(n)筛出素数?现在发现好像不需要QAQ(模板参考BZOJ_2705)
现在发现这货好像有用QAQ,比如BZOJ_2705
话说那题真的是好丧心病狂QAQ特别是那个DFS的version
近日,有幸看到一点黑科技,是一些函数:
— Built-in Function: int __builtin_popcount (unsigned int x) Returns the number of 1-bits in x. 返回‘1’的个数。 — Built-in Function: int __builtin_ffs (unsigned int x) Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero. 返回右起第一个‘1’的位置。
对于这些函数,他们全是O(1)的
不仅如此,你还会发现你不包含任何库都可以编译通过
而且你会发现,它们也不是宏 QAQ
是不是感觉很神奇?
经过多方查证,这些是GCC编译器提供的函数
换一句话来,这些下划线函数NOI系列赛可以用QAQ
参见:https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
该系列的其他函数,可以在上面的网址全部查到
最后附上据说是 __builtin_popcount 的源码:
int count(unsigned u){ u = (u & 0x55555555) + ((u >> 1) & 0x55555555); u = (u & 0x33333333) + ((u >> 2) & 0x33333333); u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F); u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF); u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF); return u; }
我真的是好菜啊!之前一直以为高斯消元只能用来求解n元一次方程组QAQ 赶快来补一点:
Gauss advance
这个算法,时间复杂度是玄学,可以被卡到指数级别。
所以感觉不太可能会是std(校内互测除外QAQ)
所以,就弃坑了! 不学啦!(╯-_-)╯╧╧
连去清华的学长hht都说不用学,那就放心地腾出时间学有用的东西吧!
不过,还是给一份资料吧:http://pan.baidu.com/s/1o783G2e
另外《算法导论》上也有讲,有远大志向的同学可以去看看哦!
最近几天,重新来看网络流的相关题目,发现之前看的基本上都忘了 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可能会爆系统栈。
当然手写栈可以解决这个问题,但是我不会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; } } }
代码虽然长一点,但是可以接受,链剖也是可以搞的
至于空间代价,这个只是多了一个当前弧的数组
至于时间代价,有图有真相:
问题一:在凸包上,选三个点使围成的面积最大
结论:一直不停的转一转,O(n)可过
证明:YYY的不严密的反证法
问题二:在凸包上,选四个点使围成的面积最大
结论:最优解一定是由两组对踵点对构成,于是旋转卡壳卡一卡也是O(n)的
证明:可以一步步证到,一般的点,一定不是最优解,进而证到,最优解一定是由两对对踵点对构成
哎,今晚好想睡觉,先简单写写,过几天再来填坑QAQ
Ⅰ. 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/
PS:貌似也有人喜欢把快速乘叫成慢速乘?比如我