Doraemon's Blog

原理先举个例子，比如说算3^6^,你要怎么算，用6个6相乘对不对，那要是3^1000^呢？1000个3相乘，复杂度为O(N)，现在我们这样算，6的二进制是110，所以6=1(2^2^)+1(2^1^)+0(2^0^)，那么3^6^就变成了3^( 1(2^2^)+1(2^1^)+0(2^0^) )=3^(1(2^2^)) 3^(1(2^1^))^ 3^(0*(2^0^))^，这其实就是快速幂的原理，看起来麻烦了对吗？OK，先不看复杂度，先看用代码如何实现，我们可以用一个数来充当3^(1*(2^2^))^、3^(1*(2^1^))^、3^(0*(2^0^))^，在下面的代码中y就是这个变量，不是每一次都要算的，比如3^(0*(2^0^))^=1，乘不乘都一样，那怎么判断呢？我们每次取二进制数的最后一位，要么是0要么是1，如果是0，就不用不用乘，否则就乘，先看代码：12345678910int p(int a,int b){ int t,y; //定义两个变量，t起到类乘的作用，而y则就是每一次要乘的数 t=1; y=a; //注意一定要初始化 while (b!=0 ...

上一篇文章讲了dfs的记忆化搜索，来看看上一道题 “仙岛求药” 仙岛求药少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由 M×NM \times NM×N 个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。 输入格式 第一行输入两个非零整数 MMM 和 NNN，两者均不大于 202020。MMM 表示迷阵行数, NNN 表示迷阵列数。 接下来有 MMM 行, 每行包含 NNN 个字符,不同字符分别代表不同含义: 1) ‘@’：少年李逍遥所在的位置；2) ‘.’：可以安全通行的方格；3) ‘#’：有怪物的方格；4) ‘*’：仙药所在位置。 输出格式 输出一行，该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 −1-1−1。 输出时每行末尾的多余空格，不影响答案正确性 样 ...

今天学习了记忆化搜索，也练习了许多题，我果然是一个蒟蒻（qwq） 希望下面的讲解对您有所帮助 仙岛求药少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由 M×NM \times NM×N 个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。 输入格式 第一行输入两个非零整数 MMM 和 NNN，两者均不大于 202020。MMM 表示迷阵行数, NNN 表示迷阵列数。 接下来有 MMM 行, 每行包含 NNN 个字符,不同字符分别代表不同含义: 1) ‘@’：少年李逍遥所在的位置；2) ‘.’：可以安全通行的方格；3) ‘#’：有怪物的方格；4) ‘*’：仙药所在位置。 输出格式 输出一行，该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 −1-1−1。 输出时每行末尾的多 ...

暴力筛选这种方法我就不多说了，一个数是素数则其只能被1和它本身整除，抓住这个特性，从2开始遍历到这个数减1，如果该数能整除其中任意一个数，则其都不是素数，如果想筛选某个范围内的，则遍历这个区间，从左端点遍历到右端点，该数是素数则将其标记为0，遍历完以后，数组中是0的就是合数，非0是素数，时间复杂度On^2 1234567891011121314151617 判断一个数是不是质数 for(int i=2;i<n;i++){ if(n%i==0){ break; } }筛选一个区间的质数 memset(arr,1,sizeof arr); for(int j=x;j<=y;j++){ for(int i=2;i<n;i++){ if(n%i==0){ arr[j]=0; break; } ...

我的第一篇博客 我对博客的态度 每次做题不会的时候上网查总是能看到一群大佬们发布的各种博客文章，布局十分漂亮，我 就在想什么时候我也能有一个这样的博客，现在我的愿望实现了，在我看来博客不只是推送 一篇文章这么简单，它也是对生活的一种记录，我不想在我以后工作了或者给别人将述我的 成长经历时，没有实实在在的东西，因为我本人写字不太好看，所以我希望博客能代替日记 陪伴我走下去，希望我能在博客的陪伴下努力生长，虽然现在的我是一只蒟蒻，但几年后的 今天我相信我一定可以成为我想成为的人！ 我对分享的看法 我本人是希望与别人分享一些东西的，无论是知识或是一些平常琐事，虽然我只是一只蒟 蒻，我会把一些自己认为有必要记录的东西都写下来，也是对知识的一种巩固吧。 目标 成为像马云那样的有钱人，呸呸！成为一个能养的起自己，照顾好家庭，服务好社会的好公 民，顺便成为一个计算机大佬，哈哈！ ——超链接【奋斗】(http://img.08087.cc/uploads/20190819/20/1566217745-WgQljednVf.jpg)