Xorex

说在前面 最近脑子一抽去学Python了，感觉自己好智障。Python很多东西都和C++不一样，所以特意记录下来。 输入输出input()和raw_input() 简单的说，input()读入的是数字，而raw_input()读入的是字符串。 然后神奇的就是input()其实是可以读入字符串的，不过必须要用''或者""来括起来，不然你就会RE。 所以说你就需要用raw_input()来解决读入字符串的问题，input()来解决读入非字符串的问题。 具体用法： 12a=input()b=raw_input() 但是这里注意的是，如果你读入的是 1123456 YunYuanXiang 那么你就GG了，因为Python只能读一行也就是说，这个读入是错误的。 正确的读法是这样的： 12123456YunYuanXiang 空格隔开的正确读法1234def splitStr(initStr,splitFlag=' '): tmpList=initStr.split(splitFlag) tmpList=li ...

快速幂 及其不要脸的Xorex终于要开始认真学习了QAQ，补一下前面漏下来的算法知识！ 快速幂方法 顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高，所以说这是一种二分的体现。 首先当我们计算一个数的次方的时候，比如2^10.那么我们按照常理的话，一定是这样计算的， 123long long ans=1;for(int i=1;i<=10;i++)ans=ans*2; 这样的话我们一共计算了10次。但是如果要求2^10000000000次幂的时候我们用地推就有可能超时了，那么我们可不可以优化一下呢。 将2^10转换为2^8*2^2的话，计算的次数就是最少的，也就是说，计算出来2^2需要1次，计算2^8需要计算2次，那么一共就需要计算4次就可以了。这样就大大增加了计算速度。 那么我们该如何拆分出来最简的计算呢，参照二进制，10的二进制就是1010，也就是10=2,1000=8，所以是2^2*2^8. 也就是说我们在计算的时候，只需要求出来指数的二进制形式，根据每一位上，如果存在1就计算这一位为1时表 ...

暑假安排话说我是来写暑假安排的，然后莫明的写了很多其他的东西（雾 暑假的话，因为其他人都去了雅礼中学参加培训，实力相比会进步很快的吧，所以我也不能够落下来了呢！住进了机房……就要努力的联系算法啊，所以说给自己列出来一个表，慢慢加油吧！ 暑假学习顺序表于是就要列出来一些神奇的东西要学习和复习： 莫队算法（看起来不是特别难） 矩阵乘法（模拟赛吃亏啊） 提高篇书上的数论和组合数学（NOIP常考） 高精度算法（一定要将板子敲熟！） 复习各种算法+做一两道水题 组合数学顺序表然后组合数学决定单独列出来整一整： 加法原理和乘法原理 排列组合基础 组合数计算 排列和组合的产生（无重集元素） 排列和组合的产生（有重集元素） 秦九昭算法 解线性方程组 数论顺序表数论也是单独列出来整一整： 整数/余数 GCD和LCM 素数和素数表 互质和同余 分解质因数 欧拉函数 扩展欧几里德 莫比乌斯反演 好了大概就是这样，暑假的一些目标QAQ

所在前面： 其实很久以前就听说对拍了，但是一直没有去学习。临近NOIP，随手写了两道题，都是因为一些小问题而GG，这要是NOIP我就挂掉了，所以为了能更稳一些，彻底践行对拍保平安的思想，去学习了如何进行对拍。 过程首先你需要一个暴力算法，非常暴力的暴力算法（没有任何技巧而言的暴力！！！） 注意，你的暴力程序需要保证一定是对的，一定是对的！！！所以说在写暴力的时候不能有任何的技巧或者算法（对于我来说），然后认真的检查暴力程序是不是真正的正确。 然后拿出来你写的比较高级的算法QAQ，和一个数据生成器。 关于数据生成器的写法如下： 123456789101112131415161718192021222324252627#include<iostream>#include<cstdio>#include<ctime>#include<cstdlib>using namespace std;int n,a,b,m,S;int main(){ srand((int)time(NULL)); freopen("All ...

说在前面今天在知乎上面看到了一个有趣的问题，就开始颓废了（最后一次颓废） 来源于知乎，随机分配钱求财富分布问题描述： 房间内有 100 人，每人有 100 块，每分钟随机给另一个人 1 块，最后这个房间内的财富分布怎样？ 链接：来自知乎 刚刚开始拿到这个题目的时候，我想，既然是随机的，那么就一定会分配均匀了啊。然而并不是我想的这样，在提问者给出来的代码跑出来的数据中，情况确实恰恰相反，随着数据的范围不断的扩大，反而贫富差距越来越大了。 实验操作然后就自己尝试着跑了一下代码，一个很垃圾的C++代码。 12345678910111213141516171819202122232425262728293031323334353637383940#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cctype>using namespace ...

刷题柱Jul/1 被赶回去学文化课 Jul/2 被赶回去学文化课 Jul/3 被赶回去学文化课 Jul/4 被赶回去学文化课 Jul/5 被赶回去学文化课 Jul/6 被赶回去学文化课 Jul/7 被赶回去学文化课 Jul/8 考试 Jul/9 考试 Jul/10 放假 Jul/11 放假 Jul/12 听山神讲课 Jul/13 听闵神讲课 Jul/14 听山神讲课 Jul/15 听闵神讲课 Jul/16 听闵神讲课 Jul/17 听山神讲课 Jul/18 放假 Jul/19 NOI网上同步赛 Jul/20 NOI网上同步赛 由于各种不可抗拒因素，刷题柱暂封……

说在前面： 自从被刘老师赶出来机房了，没有办法好好在OJ上刷题，于是就借着各种闲杂课看看各种知识点吧，题目等到暑假的时候一定要刷个够。昨天老师基本没有讲什么课，所以就用来学习算法了。 Trie树Trie树定义： Trie,又称单词查找树,是一种树形结构，用于保存大量的字符串。它的优点是：利用字符串的公共前缀来节约存储空间。 Trie树构建： Trie树拥有有3个基本性质： 根节点不包含字符，除根节点外每一个节点都只包含1个字符,每个节点都有26个分叉。 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 每个节点的所有子节点包含的字符都不相同。 下面是个trie树的例子： 这里运用了非常巧妙的方法因为可能会出现各种字符重复，所以说这样就可以非常棒的进行存储，通过解决各种重复性的问题从而节约空间和查询的时间（效率是和字符串的重复度有关的） 在这个Trie结构中，保存了t、to、te、tea、ten、i、in、inn这8个字符串，仅占用8个字节 Trie树的每个节点下面应该有26[‘a’..’z’]个分支。当然，如果要区分大小写，就要多开了！一般都用指针来写， ...

二叉树遍历前序遍历：1234567void First_traversal(int p)//前序遍历{ if(p==0) return; cout<<a[i].now; First_traversal(a[i].leftchild); First_traversal(a[i].rightchild);} 中序遍历：1234567void Second_traversal(int p)//中序遍历{ if(p==0) return; First_traversal(a[i].leftchild); cout<<a[i].now; First_traversal(a[i].rightchild);} 后序遍历：1234567void Third_traversal(int p)//后序遍历{ if(p==0) return; First_traversal(a[i].leftchild); First_traversal(a[i].rightchi ...

转段考试的成绩已经出来了，还是老样子，年级1000+，所以说，为了暑假可以在机房学到更多的知识，未来一个月，我要真的在文化课方面进行努力了，我已经做好了不来机房的觉悟了，加油吧，用自己每一天的一点一点努力换来回报。 刷题柱Jun/1 （转段考试） Jun/2 五道题：P1733，P1672，P1673，P1674，P1675； Jun/3 两道题：P1361，P1362； Jun/4 被赶回去学文化课（偷偷看了Trie树和AC自动机） Jun/5 被赶回去学文化课（偷偷留在机房补了补博客） Jun/6 高考放假 Jun/7 高考放假 Jun/8 高考放假 Jun/9 被赶回去学文化课 Jun/10 被赶回去学文化课 Jun/11 被赶回去学文化课 Jun/12 被赶回去学文化课 Jun/13 被赶回去学文化课 Jun/14 被赶回去学文化课 Jun/15 被赶回去学文化课 Jun/16 被赶回去学文化课 Jun/17 被赶回去学文化课 Jun/18 被赶回去学文化课 Jun/19 被赶回去学文化课 Jun/20 被赶回去学文化课 Jun/21 被赶回去学文化课 Jun/22 被赶回 ...

说在前面：我要开字符串了，加油吧！↖(^ω^)↗ KMP算法 KMP算法用来解决的问题就是字符串匹配的问题（感觉和搜索引擎有些像），用来查找两个字符串中的子串归属的问题，感觉就像找关键字QAQ，不同于 O(N*M) 的暴力来说，KMP算法的复杂度为 O(n+m) 效率还是挺高的。 KMP算法的核心就是一个预处理，全靠一个叫Next的数组，他会告诉你在匹配失败的时候，应该回到那里进行再次匹配。这样可以节约很多的时间，但是实际感觉KMP的算法并不能快非常多，所以说字符串的处理是非常重要的，感觉光读入一个字符串所需要的时间都够 KMP 算法跑好几遍了…… 具体原因请看《HAOI2017相同暴力算法为何差距如此之大》，一个80分一个10分，具体原因竟是C++的string的锅。 算法原理我们在平常进行字符串查找的算法中，一般是直接进行枚举比对，但是如果当前比对错误，就直接在下一位从首位开始了，这无疑是浪费啊，如果我们能接着一段显然已经匹配好的进行匹配，无疑可以节约很多的时间。 而KMP算法之所以跑的飞快就是充分利用了目标字符串的性质（比如里面部分字符串的重复性，即使不存在重复字段，在 ...