998244353

基础知识

Atcoder(3) C/C++(21) Codeforces(6) study(2) 动态规划(2) 图论(1) 字符串(2) 思维(15) 技巧(1) 搜索(1) 搜索基础(1) 数论(5) 未归档(14) 简单题解(1) 线段树(8) 贪心(1) 题解(34)

/ 注册

全部文章 / 基础知识（共30篇）

从三码理解lowbit运算

lowbit运算是树状数组中常用的一种运算，它的直观含义就是得到从二进制的第一位开始的第一个1的位置基本运算形式为 1.x&(~x+1） 2.x & -x 由于之前的三码也是懵懵懂懂的，导致这里理解这两种等价的lowbit运算时出现了问题这里我通过一个样例呈现慢慢地明...

2020-05-08

0 963

栈与队列and单调栈与单调队列的应用

最近学习了用数组模拟单调栈和单调队列，相较于STL，手动模拟栈和队列可以使印象更深。下面是栈和队列的简单模拟。首先我们理解下栈，栈是后进先出的。即可以类似一个有底的箱子，最底部的东西是最先放入的，那么最底部的东西就会在其上的所有全部都被拿走后，才能被拿出。关于栈有这几个操作 ...

2020-05-08

0 600

并查集

对于并查集生动且易理解的解释在这里 →传送门：https://blog.csdn.net/niushuai666/article/details/6662911 可以说这篇博客读完后，基本的理解就没问题了。在这里还是膜拜大神！！下面主要是对于并查集的实现作一个总结吧 1. 求...

2020-05-08

0 614

scanf输入的细微差别

众所周知scanf在输入单个字符时可用%c格式化输入但是有个缺点是当你需要输入多个字符（用字符串）或者用字符与数字叠加输入时，用%c格式化输入可能会读入一些空格或者其他字符，导致难以找到的bug。所以输入时用单个字符尽量使用字符串输入，比如 char s[2]; scanf("...

2020-05-08

0 471

Trie树

一种经典的数据结构用于存储查找一个集合中有多少相同的字符串如下是5个字符串的Trie树：其中红色星星代表有以该字符结尾的字符串存在，root是他们的根结点，默认根结点存在26个字母，只有以该根结点存在的字幕存在时才有显示，但默认所有根结点的值都为1，如a和b和c都是根结点，作为根结点的值都为...

2020-05-08

0 515

DFS

DFS即深度优先搜索适用于将一个问题的所有方面全部展开 acwing842即这么一个问题：问题传送门：https://www.acwing.com/activity/content/problem/content/905/1/ 主要是记录下没有基本模板的dfs需要注意的基本问题，也...

2020-05-08

0 610

贸然用string比较的后果

众所周知string是采用字典序来比较两个字符串的大小因此我们就不能单纯的使用str1 > str2 来比较两个字符数字的大小，因为11 > 8但是在字典序中1 < 8故不可以判断前可以先比较长度，长度相等再比较字典序即可。

2020-05-08

0 508

求解平方根（牛顿迭代法与二分搜索）

求解一个数的平方根在C/C++中是有库函数sqrt(n)的，那么除此之外我们自己实现有哪些方式呢？下面介绍牛顿迭代法和二分搜索两种思想，其共同点都是不断逼近目标值，直至到最后可以得到最接近目标值的范围，从而得到目标值。这里是参考的大佬博客：https://www.cnblogs.com/ql...

2020-05-08

0 729

高精度乘法（仅整数位）

All in code. //实现任意位的大整数相乘，修改N和M即可 #include<stdio.h> #include<string.h> const int N = 10010; const int M = 2 * 10010; char sn1[N], s...

2020-05-08

0 515

线性筛

线性筛一般是接近线性的速度去进行素数筛，所以时间接近O(n) 而线性筛的原理是处理掉埃筛的不完美问题，即使被重复筛选过的数只被筛选过一次而每个大于等于2的数都具有的特性是每个数都可以分解为n个素数相乘，即唯一分解定理。结合代码实际来看： const int N = 20010; ...

2020-05-08

0 510