intpartition(int q[],int l ,int r,int pivot) { int i = l; int j = r; while(i<j) { do i++; while(q[i]<pivot); do j--; while(q[j]>pivot); if(i<j) swap(q[i],q[j]); } return j; }
b. 算法模板
将partition 函数与递归综合到一个函数中
1 2 3 4 5 6 7 8 9 10 11 12 13
voidquickSort(int q[], int l, int r) { if(l>=r) return; int pivot = q[(l+r)/2], i = l-1 , j = r+1; while(i<j) { do i++; while(q[i]<pivot); do j--; while(q[j]>pivot); if(i<j) swap(q[i],q[j]); } quickSort(q,l,j); quickSort(q,j+1,r); }
boolcmp(vector<int>& A, vector<int>& B)// check if A >= B { // digits of A is not equal to that in B if(A.size() != B.size()) return A.size() > B.size() // else compare from high to low, until digits that are // not equal to each other for(int i = A.size()-1; i >= 0; i--) { if(A[i] != B[i]) return A[i] > B[i] } returntrue; //A = B }
vector<int> sub(vector<int>& A, vector<int>& B) { // calculate A - B vector<int> C; int carry = 0; for(int i = 0;i<A.size();i++) // A.size() >= B.size() { carry = A[i] - carry; if(i<B.size()) carry -= B[i]; // handles both situations that carry > 0 or carry <= 0 C.push_back((carry+10) % 10); if(carry < 0) carry = 1; } // delete guiding 0s while(C.size()>1 && C.back() == 0) C.pop_back() // C.back() refers to the last element in C return C;
typedefstructNode{ int val; node* next; Node(int x): val(x), next(nullptr) {} } *LinkedList; // initialize LinkedList head = newNode(); // new operator will be very slow
// definition constint N = 100010; int head; // head // e stores the values of each node while ne stores the next pointer int e[N],ne[N]; int idx; // current allocated index
// initialization voidinit() { head = -1; idx = 0; } // head insertion voidheadInsert(int x) { e[idx] = x; ne[idx] = head; head = idx; idx++; } // insertion after index k voidinsert(int k,int x) { e[idx] = x; ne[idx] = ne[k]; ne[k] = idx; idx++; }
// delete the node right after index k voiddeletion(int k) { if(k == -1) head = ne[head]; // delete the head else ne[k] = ne[ne[k]]; }
int h[N]; // 链表头节点数组 int e[N], ne[N]; memset(h,-1,sizeof(h));
voidinsert(int x) { int k = (x % N + N) % N; // guarantees that k is not negative e[idx] = x; // insert in the head ne[idx] = h[k]; h[k] = idx++; } boolquery(int x) { int k = (x % N + N) % N; int p = h[k]; for(;e[p] != x;p = ne[p]) return p == -1; }
开放寻址法（常用线性探测法）
模板
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
constint N = 200003; // 选择离2的整数次幂较远的质数，可减少冲突概率,一般开2倍 constint MAX = 0x3f3f3f3f; int h[N]; // hash数组 memset(h,MAX,sizeof(h));
voidinsert(int x) { int k = (x % N + N) % N; // guarantees that k is not negative while(h[k] != MAX) k++; h[k] = x; } boolquery(int x) { int k = (x % N + N) % N; while(h[k] != x && h[k] != MAX) k++; if(h[k] == MAX) returnfalse; returntrue; }
intdijkstra_heap(int n) { memset(dist,MAX,sizeof dist); dist[1] = 0; LRH heap; heap.push({0,1}); // {dist, index} while(heap.size()) { PII t = heap.top(); heap.pop(); int v = t.second, d = t.first; if(!s[v]) { s[v] = true; for(int i = h[v]; i != -1; i = ne[i]) // i is the index of edge { int j = e[i]; // j is the finish point of edge i if(dist[j] > d + w[i]) // d <-> dist[t] w[i] <-> graph[t][j] { dist[j] = d + w[i]; heap.push({dist[j],j}); } } } }
constint N = 100010; int h[N],ne[N],e[N],w[N],idx; // adjancent table int dist[N]; int cnt[N]; // cnt[i]: the num of edges of the SP from 1 to i bool s[N]; // 存储节点 i 是否在队列中
boolspfa_judge(int n) { memset(dist,MAX,sizeof dist); dist[1] = 0; queue<int> q; for(int i = 1;i<=n;i++) { s[i] = true; q.push(i); } while(q.size()) { int t = q.front(); q.pop(); s[t] = false; for(int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if(dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if(cnt[j]>=n) { returntrue; } if(!s[j]) // update j and j is not in the queue { s[j] = true; q.push(j); } } } } returnfalse; }
多源汇最短路
Floyd
TC:
算法思想
算法模板
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
constint N = 210; constint MAX = 0x3f3f3f3f;
int dist[N][N]; // dist is both graph and distance
intprim(int n)// returns the sum of weights in the MST { memset(dist,0x3f,sizeof dist); int res = 0; for(int i = 0;i<n;i++) { int t = -1; for(int j = 1;j<=n;j++) { if(!st[j] && (t == -1 || dist[t] > dist[j])) t=j; } if(i && dist[t] == MAX) return MAX; // graph not connected
if(i) res += dist[t]; st[t] = true;
for(int j = 1;j<=n;j++) { dist[j] = min(dist[j],graph[t][j]); // not to the start point } } return res; }
intprim_heap(int n)// returns the sum of weights in the MST { memset(dist,MAX,sizeof dist); LRH heap; heap.push({MAX,1}); // {dist, index} int res = 0, i = 0; while(heap.size()) { PII t = heap.top(); heap.pop(); int v = t.second, d = t.first; if(i && d == MAX) return MAX; // graph not connected if(i) res += d; if(!s[v]) { s[v] = true; for(int i = h[v]; i != -1; i = ne[i]) // i is the index of edge { int j = e[i]; // j is the finish point of edge i if(dist[j] > w[i]) // d <-> dist[t] w[i] <-> graph[t][j] { dist[j] = d + w[i]; heap.push({dist[j],j}); } } } ++i; } return res; }
intkruskal(int n,int m)// returns the sum of weights in the MST { sort(edge,edge + m); int res = 0,cnt = 0; for(int i = 1;i <= n;i++) p[i] = i; for(int i = 0;i < m;i++) { int a = edge[i].a, b = edge[i].b, w = edge[i].w; a = find(a),b = find(b); if(a!=b) { res += w; cnt++; p[a] = b; } } if(cnt != n-1) return MAX; return res; }
constint N = 100010; constint M = 2*N; int h[N],e[M],ne[M],idx; int color[N]; // 染色 voidadd(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; }
booldfs(int u,int c) { color[u] = c; for(int i = h[u];i!=-1;i = ne[i]) { int j = e[i]; if(!color[j]) // not colored { if(!dfs(j,3 - c)) returnfalse; // color a different one } elseif(color[j] == c) returnfalse; // not a bi-partition graph } returntrue; }
booljudge_bipart(int n) { bool flag = true; for(int i = 1;i<=n;i++) { if(!color[i]) { if(!dfs(i,1)) { flag = false; break; } } } return flag; }
constint N = 510; constint M = 100010; int h[N],e[M],ne[M],idx; int match[N]; bool st[N];
voidadd(int a,int b,int n)// n is the size of the left half of the graph { e[idx] = b + n; // this is important as the index is shared ne[idx] = h[a]; h[a] = idx++; }
inthungary(int n) { int res = 0; for(int i = 1;i<=n;i++) { // guarantees the vertex on left has chances to match // a vertex on the right that already matched in previous // loops memset(st,false,sizeof st); if(find(i)) res++; } return res; }
四 数学
26 数论
质数判定
试除法
算法思想：
质数的定义
由于因数是成对出现的，故可以仅枚举n 之前的整数
TC:
算法模板：
1 2 3 4 5 6 7 8 9 10 11 12
boolis_prime(int n) { if(n == 1) { returnfalse; } for(int i = 2; i <= n / i; i++) // i<=sqrt(x) { if(n % i == 0) returnfalse; } returntrue; }
埃氏筛法
筛选中所有质数
算法思想
若是质数，则
不可能是质数，则删除，最终留下的是所有质数
TC: 约为 实际为
算法模板
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
constint N = 1000010; int cnt; // cnt store the number of prime int st[N];
longlong res = 1; for(auto p: power) { res = res * (p.second + 1) % MOD; }
约数之和算法模板：
1 2 3 4 5 6 7 8 9
longlong res = 1; for(auto prime: power) { int p = prime.first; int a = prime.second; longlong t = 1; while(a--) t = (t * p + 1) % MOD; // generate the sum value res = res * t % MOD; }
constint N = 1000010; int cnt; // cnt store the number of prime int st[N],primes[N]; int phi[N]; longlongget_euler(int n) { phi[1] = 1; for(int i = 2;i<=n;i++) { if(!st[i]) { primes[cnt++] = i; phi[i] = i - 1; // i is a prime number } for(int j = 0; primes[j] <= n / i;j++) { st[primes[j] * i] = true; if(i % primes[j] == 0) { phi[primes[j] * i] = primes[j] * phi[i]; // pj included break; } phi[primes[j] * i] = (primes[j] - 1)*phi[i]; // pj not included } } longlong res = 0; for(int i = 1;i<=n;i++) { res += phi[i]; } return res; }
欧拉定理
若与互质，则有
证明图示： 与 模同余
故两组数乘积模同余
同时约去
即得结论
推论：费马定理
若为质数，则
快速幂
在
的时间复杂度中求出
算法原理：
将 算出来
根据
的二进制表示查表得出结果
算法模板
1 2 3 4 5 6 7 8 9 10 11 12
intquick_power(int a,int b,int p) { longlong res = 1; while(b) { if(b & 1) res = (longlong)res * a % p; // last bit of b is 1 b >>=1; a = (longlong) a * a % p; // record the power of each bit
} return res; }
扩展欧几里得算法
裴蜀定理
对于任意整数
有
证明：
令
那么是整数
得证
此算法寻找 使得
算法思想
在欧几里得算法的基础上
若 则
否则不变，,这是因为在递归后：
算法模板
1 2 3 4 5 6 7 8 9 10 11 12
intexgcd(int a,int b,int& x,int& y) { if(!b) // if b is zero then gcd(a,b)=a { x = 1,y = 0; return a; } // ii int d = exgcd(b,a%b,y,x); y -= (a/b)*x; return d; }
typedef pair<int,int> PII; constint N = 1010; int dp[N][N]; // dp[i][j] max value with i items and max volume is j vector<PII> info;
intbackpack(int n, int v) { for(int i = 1;i <= n;i++) { auto d = info[i-1]; for(int j = 1;j <= v; j++) { if (j-d.first>=0) { dp[i][j] = max(dp[i-1][j],dp[i-1][j-d.first] + d.second); } else { dp[i][j] = dp[i-1][j]; } } } return dp[n][v]; }
优化为1维dp:
1 2 3 4 5 6 7 8 9 10 11 12 13
intbackpack_1d(int n, int v) { for(int i = 1;i <= n;i++) { auto d = info[i-1]; for(int j = v;j >= d.first; j--) { // ensure that dp[i-1][j] is not modified dp[j] = max(dp[j],dp[j-d.first]+d.second); } } return dp[v]; }
完全背包
实体：物品
条件：每件物品选择次数不限；不可超过背包容量
目标属性最值：背包中物品最大总价值
操作集合：{选0个，选1个，选2个 , ...，选k个，...}
子集：{不包含当前物品，包含1个当前物品，包含2个
，...，包含k个，...}
算法思想：
此时 i不是物品数量，而是状态编号
算法模板
朴素实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
intbackpack_complete(int n, int v) { for(int i = 1;i <= n;i++) { auto d = info[i-1]; for(int j = 1;j <= v; j++) { for(int k = 0;k * d.first <= j;k++) { // dp[i][j]: more than 1 may be chosen, internal comparsion dp[i][j] = max(dp[i][j],dp[i-1][j-k*d.first]+k*d.second); } } } return dp[n][v]; }
时间复杂度优化：
思路：
模板
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
intbackpack_complete(int n, int v) { for(int i = 1;i <= n;i++) { auto d = info[i-1]; for(int j = 1;j <= v; j++) { dp[i][j] = dp[i-1][j]; if(j>=d.first) { dp[i][j] = max(dp[i][j],dp[i][j-d.first]+d.second); } } } return dp[n][v]; }
1维dp优化
1 2 3 4 5 6 7 8 9 10 11 12 13
intbackpack_complete_1d(int n, int v) { for(int i = 1;i <= n;i++) { auto d = info[i-1]; for(int j = d.first;j <= v; j++) { // doesn't have the problem in 0-1 backpack dp[j] = max(dp[j],dp[j-d.first]+d.second); } } return dp[v]; }
多重背包
实体：物品
条件：每件物品选择次数不限；物品数量有限；不可超过背包容量
目标属性最值：背包中物品最大总价值
操作集合：{选0个，选1个，选2个 , ...，选k个，...}
子集：{不包含当前物品，包含1个当前物品，包含2个
，...，包含k个，...}
算法思想：
状态转移方程与完全背包形式相同
算法模板：
朴素实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
int s[N]; // limitation of number of each item intbackpack_multi(int n, int v) { for(int i = 1;i <= n;i++) { auto d = info[i-1]; for(int j = 1;j <= v; j++) { for(int k = 0;k * d.first <= j && k <= s[i];k++) { // dp[i][j]: more than 1 may be chosen, internal comparsion dp[i][j] = max(dp[i][j],dp[i-1][j-k*d.first]+k*d.second); } } } return dp[n][v]; }
constint N = 100010; // dp[i] stores the smallest number at the end of subsequence iterated to i int nums[N], dp[N]; intmax_increasing_subsequence(int n) { int len = 0; // max length of increasing subsequence for(int i = 0;i < n;i++) { int l = 0, r = len; while(l < r) { int mid = l + r + 1 >> 1; if(dp[mid] < nums[i]) l = mid; else r = mid - 1; } len = max(len, r + 1); // len = max(len,l + 1); dp[r + 1] = nums[i]; // dp[l + 1] = nums[i];
intget(vector<int> digits,int r,int l) { int res = 0; for(int i = r;i>=l;i--) { res = res * 10 + digits[i]; } return res; }
intpow10(int x) { int res = 1; while(x--) res *= 10; return res; }
intcount(int n,int x)// 1~n number of x appearence { if(!n) return0; vector<int> digits; while(n) { digits.push_back(n % 10); n /= 10; } n = digits.size(); int res = 0; for(int i = n - 1 - !x;i >= 0;i--) // 0 will not appear at the highest position { if(i < n - 1) // boundary #1 { res += get(digits,n - 1,i + 1) * pow10(i); if(x == 0) res -= pow10(i); // boundary #2 } if(digits[i] == x) res += (get(digits,i-1,0)+1); elseif(digits[i] > x) res += pow10(i);
voidmax_happy(int u) { dp[u][1] = happy[u]; for(int i = h[u]; i != -1;i = ne[i]) { int j = e[i]; max_happy(j); // not choosing u the children can be chosen dp[u][0] += max(dp[j][0],dp[j][1]); // choosing u the children cannot be chosen dp[u][1] += dp[j][0]; } }
intmin_cost() { int res = 0; while(heap.size()>=2) { int t1 = heap.top(); heap.pop(); int t2 = heap.top(); heap.pop(); res += (t1+t2); heap.push(t1+t2);
