Xorex

LCALCA的Tarjan实现 emmmm最近公共祖先的实现方式有很多，比如倍增和Tarjan……我感觉后者写起来是比较简单的，好吧事实上我只会后者，所以就只讲一下Tarjan实现LCA的方式吧。复杂度玄学，大概是点的个数加上每一个点所连出来边的数量吧，其实是很快的。 算法的本质其实就是利用DFS对整个图进行遍历，然后在访问过后记录下来每个节点的上一个节点father[x]，如果一对需要求出LCA的点中，一个点已经访问过了，另一个点正在访问，那么访问顺序一定就是从已经访问过的点不断往回退，经过两者的LCA之后向另外一个方向拓展，遇到了正在访问的另一个点，那么因为记录上一个节点的数组father[x]是在回退的过程中记录的，那么因为已经访问过的点肯定回退到了其LCA，否则不经过公共祖先是没有办法访问到另外一个点的。 那么我们就可以通过已经访问过的那个点留下的father[]记录来求出来LCA了，我们只需要不断的往前面的节点走，直到前面的点没有被更新，也就是father[x]=x，这个点就是这一对点的最近公共祖先了。 其实LCA是挺简单的，无论是代码还是理解，其实我觉得我解释的不是很 ...

说在前面： 最近一直在刷NOIP历年的题目，感觉还好，快刷完了，最近时间很紧，大概做了一些规划。期中考试又必须要参加，感觉真的药丸，马上就要NOIP了，加油吧！ 在11月之前需要完成的问题： 解决过去NOIP可以解决的问题。 学习LCA并做一些题目练习。 学习欧拉函数，乘法逆元和中国剩余定理，并练习。 然后十一月份之后就要复习了，复习以前所学过的算法模板和题目。 NOIP2012国王游戏题目描述： 恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右 手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排 成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每 位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右 手上的数，然后向下取整得到的结果。国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序， 使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。 输入: 第一行包含一个整数 n，表示大臣的人数。 第二行包含两 ...

说在前面 我原本只知道求逆序对可以用归并排序，但是现在在做一道DP的题目的时候，需要通过求逆序对来优化，然后就意外的知道了树状数组求逆序对的方法…… 其实，其实这篇博客本来应该合并在最开始写的树状数组里面的，但是懒得找了，直接开一篇新的吧，这样比较方便。 其实逆序对是可以用归并排序来写的，复杂度和树状数组是一样的都是O(NlogN),但是树状数组要好写一些，常数也比较的小…… 然后就是这几天一直在刷NOIP的题目，超级爽…… 树状数组求逆序对树状数组：首先我要重复一些树状数组的思路，因为我在写树状数组求逆序对的时候，一直想不通为什么，emmmmm其实是忘掉了树状数组是单点修改，区间查询的条件，以为是区间修改，区间查询。然后就死活都理解不了为什么这样可以求出来逆序对。 树状数组的本质上是单点修改，区间查询。一定要记得这一点。然后树状数组的c[i]保存的是它所属的下属元素的累加和,每次查询区间的时候都是从1到x这个区间里面的所有元素的和。每次在更新的时候也是不断的将控制它的c[i]也更新一下。emmmmm仔细想想其实是很简单的。 策略： 其实策略是比较简单的，我们遍历这个数组，将a[ ...

说在前面 我为什么要写这篇博客呢，其实说什么是机器学习什么是人工智能可能连我自己都说不清楚，但是就是想写下来： 一切的一切来自于她，小冰…… 听首歌吧：网易云音乐链接 关于小冰 emmmmm，最开始是在知乎上看到了讨论小冰道歉的事情，是关于小冰的运营人员在宣传过程中针对了V家，说了很多新技术必将碾压旧技术什么的……然后就突然感兴趣起来。 原来微软小冰出道了，而且出道了很久，我就开始听了首她的歌，第一感觉就是震惊…… 没错就是震惊，因为有着长时间混居bilibili鬼畜区和音乐区的我来说，这种声音怎么可能是机器发出来的，声音柔和，连贯，抑扬顿挫把握的非常好，声音的甜美甚至能超过很多很多歌星。 初音和洛天依感觉被秒了……尤其是在唱到One two three four 的时候，最后的four听起来就像傲娇的’哼’，每一句歌词的最后声线都能很完美的收回来。和初音洛天依的电音完全不同，真的可以说是动听。 我想经常使用语音助手的人应该明白，无论是苹果的Siri还是微软的Cortana，声音很容易就能听出来是机器发出来的，生涩，断断续续，听起来就像是毫无感情的外国大妈用生硬的汉语念出 ...

说在前面 emmmm这次考试啊，真的是爆炸了，炸的连渣都不剩，顿时觉得自己的DP已经弱的不能再弱了QAQ 首先是看成绩： 这个真的是炸的超级惨啊，直接GG……rank6-30分 :s 说说是为什么炸掉的，主要是T1，T1其实是非常简单的一个区间DP，自己在考场上面也是想到了的，但是当时苦于推DP式子，我还是对DP的理解不是太深，主要是没有想到状态转移的实质是什么。区间DP是如何完美转移式子的，还好想到了，但是写挂了。 式子是对的，但是状态转移错了，犯了一个不该犯的错误，F[i][j]在不断更新是建立在自己原来的值的，每次找到比F[i][j]更优的解然后更新，但是我转移都是当前转移方式的最优值，我的DP要重修了。 然后就是T3的暴力没写，其实是很简单的。 然后说说考试状态吧： 感觉这是一个非常失败的考试时间安排，对的超级失败。自己首先拿到了题目，然后看T1，看完题没有任何思路。然后继续看T2，找到了一些思路，但是实际上这个思路是错的，很容易就可以找到反例来推翻，但是也没有去找反例来验证结论的争取性…… 于是我就快速写了错误的T2，然后开始看T3，这时候节奏还是不错的，发现T3可以用 ...

考试总结 今天焦老师让我们写总结，我决定开始写总结，以前除了大型的考试意外都没有写过，以后怕不是要天天写了…… 这次考试……emmmmmm 先看第一次测评的成绩： 然后第一题谜之爆炸，第三题丢了一个点，还好还好没有炸的太狠…… 这次考试过程是非常爽的，感觉节奏不错，首先先看第一题，然后花了一个半小时的时间写完了第一题，用的时间有些长了，其实应该控制在一个小时之内，但是这个第一题有些复杂……真的是不好写。以后尽量控制在一个小时以内。 写完第一题之后，开始看第二题，虽说是省选题，但是是比较简单的，问了帆神Map的使用方法，构建一个Topsort就能AC了，然后造了几个大数据，跑了跑没有问题。 写完前两题之后还剩下一个小时，看是看第三题，一眼秒暴力。想到原来黄山学长讲过怎么写，但是需要求组合数，虽然Century告诉了我组合数的公式，但是并不会求，就开始写暴力，复杂度O(n^2).二十分钟写完加调试。检查了一遍之后去吃饭了。 这次考试期望成绩是100+100+30，实际成绩是30+100+20。实力爆炸。 T1的爆炸: T2的爆炸： T3的爆炸： 爆炸之后大家修改过 ...

扩展欧几里德算法关于不定方程ax+by=c 扩展欧几里德算法其实就是用来求出一组关于ax+by=c的解，复杂度比较稳定，是建立在欧几里德算法上面进行计算的。 首先需要考虑一下这个不定方程是否有解判断的方法就是：对于一个方程ax+by=c来说，如果 c%GCD(a,b)!=0 那么这个方程就是无解的。其实扩展欧几里德算法解出来的就是丢番图方程的解（好像是丢番图方程）。 首先我们需要看一下这个不定方程是否有解，如果有解的话，就进行计算，很显然的，如果b=0的时候，那么ax=c，那么x一定等于c/a。此时x=c/a,y=0; 然后，然后我们可以列出来两个方程： a*x1+b*y1=GCD(a,b); b*x2+(a%b)*y2=GCD(b,a%b); 然后根据欧几里德算法：GCD(a,b)=GCD(b,a%b); 所以就可以得到：a*x1+b*y1=b*x2+a%b*y2; 然后解得: x1=y2 y1=x2-a/b*y2; 然后我们就可以利用GCD的迭代解出来不定方程ax+by=c的一组解！ 注意这里是一组解！！！！！！ 但是你需要求出来其他解（比如大于零的最小解） 你就需要明白一 ...

分解质因数方法 分解质因数就是把一个数，用自己所有的质因数的ai次方的乘积表示出来，而且这种表示方式是唯一的，格式如下： $ n={a_{1}}^{b1} * {a_{2}}^{b2} * {a_{3}}^{b3} * cdots * {a_{i}}^{bi} $ 其中，a都为质数，切为递增。 分解的方法为依次枚举因数ai，然后看n%ai是否可以为0，若可以，则为其中的一个质因数，然后不停地n/=ai，直到n%ai不为零，n/=ai的次数也就是bi的数。因为每次的n/=ai把非质数都给筛掉了，所以不需要担心ai不为质数。 一定要记得从2开始枚举，枚举到n的开方就行。如果发现质因数为0，则n=n^1; 代码1234567891011Now=n;for(int i=2;i<=sqrt(double(n))+1;i++)if(!(Now%i)){ First[++all].Prime=i; while(!(Now%i)) { Now/=i; First[all].Number++; }} 一 ...

互质定理 GCD(a,b)=GCD(a,b-a*c)=GCD(a-b*c,b); 一定存在整数x、y，使得a*x+b*y=GCD(a,b); m*GCD(a,b)=GCD(a*m,b*m); 若GCD(a,b)=d,GCD(a/d,b/d)=1; m*LCM(a,b)=LCM(a*m,b*m); 同余定理 同余概念：对于两个数a、b,对m取余后相等，则称a和b同余。记作a≡b(mod m); 或者是对于两个数a、b,若m|(a-b) 则称a和b同余。 若a≡b(mod m),b≡c(mod m).则 a≡c(mod m); 若a≡b(mod m),c≡d(mod m).则 a±c≡b±d(mod m)，a*c≡b*d(mod m); (a-b)%m=(a%m-b%m+m)%m; 若n|m,a≡b(mod m),则 a≡b(mod m); 若GCD(n,m)=1,a≡b(mod m),a≡b(mod n),则a≡b(mod n*m); a≡b(mod m), n∈n*, 则 a^n≡b^n(mod m); a*c≡b*c(mod m),GCD(c,m)=d,则a≡b(mod m/ ...

说在前面 其实就是挖一个坑而已，NOIP之前要赶快填上，不能再颓废了。 GCD和LCMGCD GCD的原理就是辗转相除法。 其实就是运用到了这是欧几里得算法，和其中一个定理：GCD(x,y)=GCD(y,x%y); 也就是两个数:x和y的最大公约数等于y,x%y这两个数的最大公约数。 证明如下： a=k*b+r,则r=a-k*b;a%b=(k*b+r)%b所以a%b=r;设d为a和b的公约数。则 a|d , b|d因为(a-k*b)|d,所以r|d以为a%b|d且b|d所以d为(b,a%b)的公约数又因为d为(a,b)的公约数所以GCD(a,b)=GCD(b,a%b);(所有公约数都相等那么最大公约数必然相等) 1234567891011int GCD(int x,int y){ int This=x%y; while(This) { x=y; y=This; This=x%y; } return y;} LCMLCM的原理就是一个公式，LCM*GCD=X*Y 也就 ...