3.4k 3 分钟

今天学习了容斥原理,感觉智商又一次遭到了蹂躏(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...
666 1 分钟

# 应用 一些题目需要读取的数据量十分庞大,很可能读取数据次数高达几十万次,而这时用 cin 或者 scanf 时间上就有了一些差距(scanf 比 cin 要快),当输入数据更加庞大,scanf 时间上也有些乏力,毕竟有些题目就是考你会不会快读快写,C 语言输入输出字符时是要比数字输出的快的,我们可以利用这一点来把数字转化成字符来输出 下面的 inline 是内联函数的意思,小伙伴可以看 https://blog.csdn.net/hyqsong/article/details/51857833 了解一下 # 快读代码 inline int read(){ int...
7.3k 7 分钟

查并集也是一种比较常用的算法,有必要掌握 下面文章转载于 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...
4.1k 4 分钟

# 原理 先举个例子,比如说算 36, 你要怎么算,用 6 个 6 相乘对不对,那要是 31000 呢?1000 个 3 相乘,复杂度为 O (N),现在我们这样算,6 的二进制是 110,所以 6=1 (22)+1(21)+0(20),那么 36 就变成了 3^( 1 (22)+1(21)+0(20) )=3(1*(22^)) * 3(1*(21)) * 3(0*(20)),这其实就是快速幂的原理,看起来麻烦了对吗?OK,先不看复杂度,先看用代码如何实现,我们可以用一个数来充当 3(1*(22))、3(1*(21))、3(0*(20)),在下面的代码中 y...
2.3k 2 分钟

上一篇文章讲了 dfs 的记忆化搜索,来看看上一道题 “仙岛求药” # 仙岛求药 少年李逍遥的婶婶病了,王小虎介绍他去一趟仙灵岛,向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛,克服了千险万难来到岛的中心,发现仙药摆在了迷阵的深处。迷阵由 M×NM \times NM×N 个方格组成,有的方格内有可以瞬秒李逍遥的怪物,而有的方格内则是安全。现在李逍遥想尽快找到仙药,显然他应避开有怪物的方格,并经过最少的方格,而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。 输入格式 第一行输入两个非零整数 MMM 和 NNN,两者均不大于 202020。MMM 表示迷阵行数,NNN...
3.6k 3 分钟

今天学习了记忆化搜索,也练习了许多题,我果然是一个蒟蒻(qwq) 希望下面的讲解对您有所帮助 # 仙岛求药 少年李逍遥的婶婶病了,王小虎介绍他去一趟仙灵岛,向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛,克服了千险万难来到岛的中心,发现仙药摆在了迷阵的深处。迷阵由 M×NM \times NM×N 个方格组成,有的方格内有可以瞬秒李逍遥的怪物,而有的方格内则是安全。现在李逍遥想尽快找到仙药,显然他应避开有怪物的方格,并经过最少的方格,而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。 输入格式 第一行输入两个非零整数 MMM 和 NNN,两者均不大于 202020。MMM...
1.7k 2 分钟

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

# 我的第一篇博客 # 我对博客的态度 每次做题不会的时候上网查总是能看到一群大佬们发布的各种博客文章,布局十分漂亮,我 就在想什么时候我也能有一个这样的博客,现在我的愿望实现了,在我看来博客不只是推送 一篇文章这么简单,它也是对生活的一种记录,我不想在我以后工作了或者给别人将述我的 成长经历时,没有实实在在的东西,因为我本人写字不太好看,所以我希望博客能代替日记 陪伴我走下去,希望我能在博客的陪伴下努力生长,虽然现在的我是一只蒟蒻,但几年后的 今天我相信我一定可以成为我想成为的人! #...