Try   HackMD

線性篩 O(n)

bitset<MAXN> prime_bool; vector<ll> prime; void find_prime(){ prime_bool.set(); for(int i=2;i<MAXN;i++){ if(prime_bool[i]){ prime.push_back(i); } for(auto j:prime){ if(j*i>=MAXN) break; prime_bool[j*i]=0; if(i%j==0) break; } } }

拓展歐基里德

int exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1,y=0; return a; } int gcd=exgcd(b,a%b,y,x); y-=a/b*x; return gcd; }

BIT O(logn)

int n; vi BIT; void update_add(int idx,int val){ while(idx<=n){ BIT[idx]+=val; idx+=(idx&-idx); } } int query(int idx){ int res=0; while(idx>0){ res+=BIT[idx]; idx-=(idx&-idx); } return res; }

常用函式

#include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef tree<int,null_type,less_equal<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; ordered_set.order_of_key(n)//找有幾個數小於n ordered_set.find_by_order(n)//找第n小的數 #include<sstream>string s; stringstream ss(s);//ss<<input ss.str(""),ss.clear();//clear while(getline(ss,str,'m'))//以m分割 cout << str << endl; int a,b; char c; while(ss>>a>>c>>b)//處理像是-2/9+9/7 cout<<a<<" "<<c<<" "<<b<<endl; //輸出 -2 / 9 endl 9 / 7 do {cout << s << "\n";}//排列組合(需sort) while(next_permutation(s.begin(), s.end())); prev_permutation()//逆向排列 #include<cstring>memset()//可用 0 -1 0x3F(1e9左右)

自訂隨機哈希(防卡常)

#include<chrono> struct custom_hash {//Key只能放整數 static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } };

快速冪 O(logn)

int qpow(int a,int b){ int res=1; while(b){ if(b&1) res=res*a%mod; b>>=1; a=a*a%mod; } return res; }

線段樹 O(logn)

const int N=5e5+5; int n; int seg[N<<2],tag[N<<2]; //線段樹與懶惰標記 void merge(int idx){ seg[idx]=seg[idx<<1]+seg[idx<<1|1]; //區間最大要把return x+y改成max(x,y) } void build(int idx=1,int l=1,int r=n){//創建線段樹 if(l==r){ cin>>seg[idx]; return; } int mid=(l+r)>>1; build(idx<<1,l,mid); build(idx<<1|1,mid+1,r); merge(idx); } void push_tag(int idx,int l,int r){ if(tag[idx]){ int mid=(l+r)>>1; seg[idx<<1]+=(mid-l+1)*tag[idx]; seg[idx<<1|1]+=(r-mid)*tag[idx]; tag[idx<<1]+=tag[idx]; tag[idx<<1|1]+=tag[idx]; tag[idx]=0; } } void update_range(int ql,int qr,int val,int idx=1,int l=1,int r=n){//區間加值 if(l!=r) push_tag(idx,l,r); if(ql<=l&&r<=qr){ seg[idx]+=(r-l+1)*val; tag[idx]+=val; return; } int mid=(l+r)>>1; if(qr<=mid) update_range(ql,qr,val,idx<<1,l,mid); else if(ql>mid) update_range(ql,qr,val,idx<<1|1,mid+1,r); else{ update_range(ql,qr,val,idx<<1,l,mid); update_range(ql,qr,val,idx<<1|1,mid+1,r); } merge(idx); } int query(int ql,int qr,int idx=1,int l=1,int r=n){//區間查詢 if(l!=r) push_tag(idx,l,r); //ql~qr為欲查詢的範圍 if(ql<=l&&r<=qr) return seg[idx]; int mid=(l+r)>>1; if(mid>=qr) return query(ql,qr,idx<<1,l,mid); else if(ql>mid) return query(ql,qr,idx<<1|1,mid+1,r); else return query(ql,qr,idx<<1,l,mid)+query(ql,qr,idx<<1|1,mid+1,r); //區間最大要把return x+y改成max(x,y) } void update(int pos,int val,int idx=1,int l=1,int r=n){//單點更新 if(l==r){ seg[idx]+=val; return; } int mid=(l+r)>>1; if(pos<=mid) update(pos,val,idx<<1,l,mid); else update(pos,val,idx<<1|1,mid+1,r); merge(idx); }

01背包問題 O(n)

for(int i=1;i<=n;i++){ for(int j=x;j>=w[i];j--){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } }

無限背包問題 O(n)

for(int i=1;i<=W;i++){ // 從小到大遍歷重量 for(int j=1;j<=n;j++){ // 遍歷每個物品 if(i>=w[j]) dp[i]=max(dp[i],dp[i-w[j]]+v[j]); } }

LIS 最長遞增子序列(DP為求得LIS實際子序列)

for(int i=0;i<num.size();i++){ if(lis.empty()||lis.back()<num[i]){ lis.push_back(num[i]); dp[i]=lis.size(); } else{ auto iter=lower_bound(all(lis),num[i]); dp[i]=iter-lis.begin()+1; *iter=num[i]; } } int length=lis.size(); for(int i=num.size()-1;i>=0;i--){ if(dp[i]==length){ ans.push_back(num[i]); length--; } }

拓樸排序 O(V+E)

void Topological_sorting(){ queue<int> que; for(int i=1;i<=n;i++){ if(!in[i]){ que.push(i); } } while(!que.empty()){ int cur=que.front(); que.pop(); ans.push_back(cur); for(const auto &i:out[cur]){ in[i]--; if(!in[i]) que.push(i); } } }

樹直徑

void DFS(int cur,int last,int dis=0){ if(dis>mx) mx=dis,r=cur; for(const auto &i:routs[cur]){ if(i==last) continue; DFS(i,cur,dis+1); } }

一般並查集

int f(int cur){ return num[cur]==cur?cur:num[cur]=f(num[cur]); } void merge(int a,int b){ a=f(a),b=f(b); if(a!=b){ cnt--; num[b]=a; } } for(int i=0;i<n;i++)//初始化 num[i]=i;

並查集(連通塊與最大連接數)

int f(int cur){ return num[cur]<0?cur:num[cur]=f(num[cur]); } void connect(int a,int b){ a=f(a),b=f(b); if(a!=b){ num[a]+=num[b]; mx=max(mx,-num[a]); num[b]=a; heap--; } }

最小生成樹 MST

sort(all(cost),cmp);//a.cost<b.cost for(const auto &i:cost){ int a=f(i.a),b=f(i.b);//使用一般並查集 if(a!=b){ num[b]=a; counter--; ans+=i.cost; } }

Dijkstra

void Dijkstra(){ priority_queue<pii,vector<pii>,greater<>> pq; pq.push({0,1}),ans[1]=0; while(!pq.empty()){ pii cur=pq.top(); pq.pop(); if(cur.first>ans[cur.second]) continue; for(const auto &i:routs[cur.second]){ if(ans[i.second]>cur.first+i.first){ ans[i.second]=cur.first+i.first; pq.push({ans[i.second],i.second}); } } } }

Floyd warshall(DP)

void Floyd_warshall(){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=n;k++){ dp[j][k]=min(dp[j][k],dp[j][i]+dp[i][k]); } } } }

找cycle

void DFS(int cur,int last=0){ if(cur==last||found) return; visited[cur]=1; for(const auto &i:routs[cur]){ if(visited[i]==0){ pre[i]=cur; DFS(i,cur); } else if(visited[i]==1){ print_cycle(i,cur); found=1; return; } } visited[cur]=2; }

單調隊列(求最大最小)

deque<int> mx,mn; for(int i=0;i<n;i++){ if(!mx.empty()&&i-mx.front()>=window) mx.pop_front(); if(!mn.empty()&&i-mn.front()>=window) mn.pop_front(); while(!mx.empty()&&num[mx.back()]<num[i]) mx.pop_back(); while(!mn.empty()&&num[mn.back()]>num[i]) mn.pop_back(); mx.push_back(i),mn.push_back(i); if(i>=window-1){ ans_max.push_back(num[mx.front()]); ans_min.push_back(num[mn.front()]); } }

字串編輯距離(DP)

for(int i=1;i<=a;i++){ for(int j=1;j<=b;j++){ if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]; else dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1; } }

LCS 最長公共子序列(DP)

for(int i=1;i<=s1.size();i++){ for(int j=1;j<=s2.size();j++){ if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } }

二元樹(以preorder和inorder建成)

class Node{ public: char data; Node* left; Node* right; Node(char value){ data=value; right=nullptr; right=nullptr; } }; class Tree{ public: Node* root; Tree(){ root=nullptr; } Node* build_tree(vector<char>& preorder,vector<char>& inorder){ if(preorder.empty()||inorder.empty()){ return nullptr; } Node* point=new Node(preorder[0]); auto findit=find(all(inorder),preorder[0]); int length=findit-inorder.begin(); vector<char> inorder_left(inorder.begin(),findit); vector<char> inorder_right(findit+1,inorder.end()); vector<char> preorder_left(preorder.begin()+1,preorder.begin()+1+length); vector<char> preorder_right(preorder.begin()+1+length,preorder.end()); point->left=build_tree(preorder_left,inorder_left); point->right=build_tree(preorder_right,inorder_right); return point; } void Postorder(Node* x){ if(x){ Postorder(x->left); Postorder(x->right); cout<<x->data; } } void del_tree(Node* x){ if(x==nullptr) return; del_tree(x->left); del_tree(x->right); delete x; } };

線段樹上二分搜

void st_bsearch(int pos,int idx=1,int l=1,int r=n){ if(l==r&&seg[idx]>=pos){ seg[idx]-=pos; ans=l; return; } int mid=(l+r)>>1; if(seg[idx<<1]>=pos) check_in(pos,idx<<1,l,mid); else if(seg[idx<<1|1]>=pos) check_in(pos,idx<<1|1,mid+1,r); merge(idx); }

KMP演算法

string a; // 文本串 string b; // 模板串(将被匹配的子串) int kmp_next[N]; // next数组 void getNext(int m=b.size()){//初始化 int j = 0; kmp_next[0] = 0; for(int i=1; i<m; ++i){ while(j>0 && b[i]!=b[j]) j=kmp_next[j-1]; if(b[i]==b[j]) ++j; kmp_next[i] = j; } } int kmp(int n=a.size(),int m=b.size()){//使用KMP寻找匹配位置 int i, j = 0; int p = -1; getNext(m); for(i=0; i<n; ++i){ while(j>0 && b[j]!=a[i]) j=kmp_next[j-1]; if(b[j]==a[i]) ++j; if(j==m){ p = i - m + 1; break; } } return p; } int kmp(int n=a.size(),int m=b.size()){//使用KMP计算匹配次数 int i, j = 0, res = 0; getNext(m); for(i=0; i<n; ++i){ while(j>0 && b[j]!=a[i]) j=kmp_next[j-1]; if(b[j]==a[i]) ++j; if(j==m) ++res; } return res; }

動態開點+懶惰標記線段樹

class Node { public: Node* left; Node* right; int l; int r; int mid; int v; int add; Node(int l, int r) { this->l = l; this->r = r; this->mid = (l + r) >> 1; this->left = this->right = nullptr; v = add = 0; } }; class SegmentTree { private: Node* root; public: SegmentTree() { root = new Node(1, 1e9); } void modify(int l, int r, int v) { modify(l, r, v, root); } void modify(int l, int r,int v, Node* node) { if(node->l>r||node->r<l) return; if (node->l >= l && node->r <= r) { node->v += (node->r - node->l + 1) * v; node->add += v; return; } pushdown(node); modify(l, r, v, node->left); modify(l, r, v, node->right); merge(node); } int query(int l, int r) { return query(l, r, root); } int query(int l, int r, Node* node) { if(node->l>r||node->r<l) return 0; if (node->l >= l && node-> r <= r) return node->v; pushdown(node); return query(l, r, node->left)+query(l, r, node->right); } void merge(Node* node) { node->v = node->left->v+node->right->v; } void pushdown(Node* node) { if (!node->left) node->left = new Node(node->l, node->mid); if (!node->right) node->right = new Node(node->mid + 1, node->r); if (node->add) { Node* left = node->left; Node* right = node->right; left->v += node->add; left->add += node->add; right->v += node->add; right->add += node->add; node->add = 0; } } };

SPFA(用於判斷負權環)

vector<pii> routs[N]; int dis[N],n,cnt[N]; bool SPFA(const int &start){ fill(dis,dis+n,1e9); memset(cnt,0,sizeof(cnt)); dis[start]=0; queue<int> que; bitset<N> in_que; que.push(start); while(!que.empty()){ int cur=que.front(); que.pop(); cnt[cur]++; if(cnt[cur]>n){ return 1; } in_que[cur]=0; for(const auto &i:routs[cur]){ if(dis[i.second]>dis[cur]+i.first){ dis[i.second]=dis[cur]+i.first; if(!in_que[i.second]){ que.push(i.second); in_que[i.second]=1; } } } } return 0; }

稀疏表

constexpr int N=500; int dp[N+5][32]; int a[N]={1,2,3,4,5}; void build(){ for(int i=1;i<=N;i++) dp[i][0]=a[i-1]; for(int k=1;k<32;k++){ for(int i=1;i+(1<<(k-1))<=N;i++){ dp[i][k]=max(dp[i][k-1],dp[i+(1<<(k-1))][k-1]); } } } int query(int l,int r){ int idx=__lg(r-l+1); return max(dp[l][idx],dp[r-(1<<idx)+1][idx]); }

Z-Function

string s="123_123456789"; const int n=s.size(); vi z(n); for (int i = 1, l = 0, r = 0; i < n; ++i) { if (z[i - l] < r - i + 1) z[i] = z[i - l]; else { z[i] = max(r - i + 1, 0); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++; l = i, r = i + z[i] - 1; } }

Trie

struct TrieNode { int nxt[26]; //遇到a~z時的節點編號(idx) int cnt; //以此結尾的字串個數 } node[1000005]; int idx = 2; //root = 1 void insert(string s){ int cur = 1; //從root開始 for(auto i:s) { if(node[cur].nxt[i-'a'] == 0){ node[cur].nxt[i-'a'] = idx; //開一個新的node cur = idx; idx++; } else { cur = node[cur].nxt[i-'a']; } } node[cur].cnt++; } int query(string s){ int cur = 1; for(auto i:s) { if(node[cur].nxt[i-'a'] == 0){ return 0; } else { cur = node[cur].nxt[i-'a']; } } return node[cur].cnt; }