对拍
C++对拍详解——EdisonBa’s Blog
生成随机数12345678910#include<bits/stdc++.h>int main(){ struct _timeb T; _ftime(&T); srand(T.millitm); //获得毫秒 int a = rand(); printf("%d\n", a);}
对拍eg: A+B problem正确代码(需要验证的代码) std.cpp
123456789#include <cstdio>using namespace std;int main(){ int a, b; scanf("%d%d", &a, &b); printf("%d\n", a + b); return 0;}
暴力代码：baoli.cpp
123456789101112131415#include <cstdio>us ...
排序
sort123456789101112131415//数组int a[10]={1,1,2,4,2,4,7,3,2,6};sort(a,a+10);//等价于 sort(a,a+10,less<int>()); 从小到大//vectorvector<int> a={1,1,2,4,2,4,7,3,2,6};sort(a.begin(),a.end(),greater<int>());//自定义比较bool cmp(vector a,vector b){ return a<b;}sort(a.begin(),a.end(),cmp);
Bubble sortn-1趟排序，每趟遍历n个元素，把大的往后排
1234567891011// O(n^2)void bubblesort(){ for(int i=1;i<=n-1;i++) { for(int j=1;j<=n-i;j++) { ...
分解质因数
知乎|数论——质数：分解质因数
1234567891011121314151617//O(n)暴力private static void divide(int n){ for(int i = 2; i <= n; i++)//遍历从 2 到 n 的所有数 { if(n % i == 0)//如果 i 是 n 的因数 { int k = 0; while(n % i == 0)//除尽 (使i只会是x的质因数) { n /= i; k++; } } }}
n的因数的质因数，肯定也是n的质因数n的任何一个因数x,假如x是合数，那么x可以由n的小于x的质因数所相乘而得一个数的因数，从小到大排序，最开始的因数肯定是质因数，后面才有合数x是n的因数，且x是合数，那么n的质因数不一定是x的质因数，而x的质因数 ...
数学
欧拉函数欧拉函数是小于x的整数中与x互质的数的个数,一般用φ(x)表示。特殊的,φ(1)=1。当n>1时，小于n的数中，与n互质的数的总和为：(φ(n)∗n)/2若n互质的数有一个是m，那么还存在另一个数n−m也与n互质。所以与n互质的数的平均数是n/2，而个数又是φ(n)，可以得到这些数的和就是(φ(n)∗n)/2
q
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef double db;const int N =1e5+10;const ll mod = 1e9+7;void deer(){ ll n,ans=2; cin>>n;//[欧拉函数] 算出'比i小的'与i互素的'数的个数 ...
线段树
结构和思想
作用常用来维护区间信息，可在 O(log2 (n)) 的时间复杂度内实现单点修改，区间修改，区间查询（区间求和，区间最大值，区间最小值）等操作
线段树的基本结构（以区间加为例）使用堆式存储结构，将每个长度不为 的区间划分为左右俩个区间递归求解，并通过合并左右俩个子区间得到该区间信息
单点修改+区间查询1n个数：a1,a2,a3,…,anq个操作： 1. 1 x d 修改ax=d 2. 2 l r 查询[l,r]最小值，并求出最小值出现了多少次
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109#include <bits/stdc++.h> ...
离散化
将大数据映射到一个较小的值域来处理
STL实现离散化（1）排序（sort函数）（2）去重（unique函数）：返回去重之后的尾迭代器（或指针），即去重之后末尾元素的下一个位置（3）二分索引（lower_bound或upper_bound函数）
1234567891011121314151617181920#include <bits/stdc++.h>using namespace std;int n,res,tot,a[MAXN],b[MAXN];int main() { scanf("%d",&n); for(register int i=1;i<=n;i++) { scanf("%d",&a[i]); b[++tot]=a[i]; //b[]是a[]的副本 } sort(b+1,b+1+tot); //第一步：排序 res=unique(b+1,b+1+tot)-(b+1); //unique函数计算出去重后的元素个数，存在res中 for(regist ...
树状数组
lowbit运算二进制数右端第一位1的位权
lowbit(x) = x&(-x)
定义、查询、修改
树状数组是一种支持 单点修改 和 区间查询 的，代码量小的数据结构。初步感受————oi_wiki管辖区间我们记 x 二进制最低位 1 以及后面的 0 组成的数为 lowbit(x)，那么 c[x] 管辖的区间就是 [x-lowbit(x)+1, x]
树状数组1
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll N = 5e5+10;ll a[N]; //原数组ll c[N]; //树状数组int n,q;//O(log n)ll query(int x) //区间查询求和 a[1...x]{ ll sum=0; fo ...
栈Stack
栈是一种先进后出的数据结构
基本概念定义只允许在一端进行插入或删除操作的线性表
栈顶（Top）：线性表允许进行插入和删除的一端。栈底（Bottom）：固定的，不允许进行插入和删除的另一端。空栈：不含任何元素。
基本操作s.empty() 返回栈是否为空s.size() 返回栈的元素个数s.top() 返回栈顶元素s.pop() 弹出栈顶元素s.push(x) 将 x 压入栈中
顺序存储结构顺序栈采用顺序存储的栈称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶的位置。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647//初始化void InitStack(SqStack& S){ S.top = -1; //初始化栈顶指针}//判栈空bool StackEmpty(SqStack& S){ if( S.top == -1) ...
最短路
最短路有向图中的最短路、无向图中的最短路单源最短路、每对结点之间的最短路
任意两个结点之间的最短路Floyd用来求任意两个结点之间的最短路。复杂度比较高，但是常数小，容易实现（只有三个 for）。适用于任何图，不管有向无向，边权正负，但是最短路必须存在（不能有负环）
与坐标结合应用的最短路Nearest Excluded Points
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef double db;const int N = 1e5 + 10;const ll mod = 1e9 + 7;int dx[] = { 0,0,-1,1 };int dy[] = { -1,1,0,0 } ...