Doraemon's Blog

今天学习了容斥原理，感觉智商又一次遭到了蹂躏（eoe），百度了CSDN上面的讲解，感觉讲的都不是很详细（或许真的是我笨吧，哎~），还是结合题目来讲吧，上题： I - Co-prime Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer. Input The first line on input contains T (0 < T <= 100) the ...

应用一些题目需要读取的数据量十分庞大，很可能读取数据次数高达几十万次，而这时用cin或者scanf时间上就有了一些差距（scanf比cin要快），当输入数据更加庞大，scanf时间上也有些乏力，毕竟有些题目就是考你会不会快读快写，C语言输入输出字符时是要比数字输出的快的，我们可以利用这一点来把数字转化成字符来输出 下面的inline是内联函数的意思，小伙伴可以看 https://blog.csdn.net/hyqsong/article/details/51857833 了解一下 快读代码inline int read(){ int x=1,y=0; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') x=-1; ch=getchar(); //这里的循环是为了避免输入数字之前的空格造成影响 } while(ch>='0'&&ch<=' ...

查并集也是一种比较常用的算法，有必要掌握下面文章转载于CSDN上的一篇博客，我觉得写的很详细，就把它贴出来吧地址：https://blog.csdn.net/Hacker_ZhiDian/article/details/60965556 基础 对于今天要总结的算法，我想先通过一道题目来看一下： 假设现在我有一个任务交给你：要求你查看 id 为 x 和 id 为 y 的两个人是不是朋友，在一开始我会在第一行中输入 3 个数字 n、m 、k。n 是代表总人数。接下来 m 行，每一行我会输入两个数字： Xi 、 Yi， 代表 id 为 Xi 和 id 为 Yi 的两个人是朋友（注意：朋友的朋友也是朋友）， 接下来 k 行，每一行我也会输入两个数字： a 和 b ，代表我要你查询 id 为 a 和 id 为 b 的两个人是不是朋友， 如果这两个人是朋友，那么在一行中输出“yes”否则在一行中输出“no”。 数据约束：0 < n, m, k < 10000， 所有人的 id 都是正整数，并且 id 不会超过 n 样例输入： 7 5 4 1 3 2 4 3 4 1 4 5 6 1 ...

原理先举个例子，比如说算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)