算法回顾板子

欧拉函数

#include <iostream>

using namespace std;

int phi(int x){
    int ans = x;
    for(int i = 2; i*i <= x; i++){
        if(x%i == 0){
            ans = ans - ans/i;
            while(x%i == 0)
                x /= i;
        }
    }
    if(x > 1)
        ans = ans - ans/x;
    return ans;
}

int n;
int main(){
    cin >> n;
    cout << phi(n) << endl;
    return 0;
}

矩阵快速幂

#include <iostream>
#define mod 1000000000
#define N 100
#define ll long long int
using namespace std;
struct Node{
    int vis[N][N];
}node;

Node mul(Node a, Node b){
    Node c;
    for(int i = 0; i < 2; i++){
        for(int k = 0; k < 2; k++){
            for(int j = 0; j < 2; j++){
                c.vis[i][j] = (c.vis[i][j] + a.vis[i][k]*b.vis[k][j])%mod;
            }
        }
    }
    return c;    
}

Node quick_pow(Node a, ll b){
    Node c;
    for(int i = 0; i < 2; i++)
        c.vis[i][i] = 1;
    while(b){
        if(b&1)
            c = mul(a, c);
        a = mul(a, a);
        b >>= 1;
    }
    return c;
}



int main(){
    Node ans;
    ans.vis[0][0] = 1; ans.vis[0][1] = 1;
    ans.vis[1][0] = 1; ans.vis[1][1] = 0;
    Node cnt = quick_pow(ans, 20);
    for(int i = 0; i < 2; i++){
        for(int j = 0 ; j < 2; j++){
            cout << cnt.vis[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}

快速幂

#include <iostream>
#define mod 1000000000
#define N 100000
#define ll long long int
using namespace std;

ll quick_pow(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b&1)
            ans = (ans*a)%mod;
        a = (a*a)%mod;
        b >>= 1;
    }
    return ans;
}

int main(){
    ll n, m;
    cin >> n >> m;
    cout << quick_pow(n,m)<<endl;
    return 0;
}

 kmp

#include <bits/stdc++.h>
#define N 100000
using namespace std;
int Next[N];

void getNext(string s){
    int j = -1;
    int i = 0;
    int len = s.length();
    Next[0] =-1;
    while(i < len){
        if(j == -1 || s[i] == s[j]){
            i++;
            j++;
            Next[i] = j;
        }else
            j = Next[j];
    }
}

int kmp(string s, string ss){
    getNext(ss);
    int i = 0, j = 0;
    int slen = s.length();
    int sslen = ss.length();
    while( i < slen && j < sslen){
        if(j == -1 || s[i] == ss[j]){
            i ++; j++;
        }else
            j = Next[j];
    }
    if(j == sslen){
        return i - j + 1;
    }
    return -1;
}

string s, ss;
int main(){
    cin >> s >> ss;
    int an = kmp(s, ss);
    if(an == -1){
        cout << "NO" << endl;
    }else{
        cout << "YES" <<" " << an <<  endl;
    }
    return 0;
}

树状数组

#include <bits/stdc++.h>
#define N 50005
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
struct Node{
    int a,b;
}node[N];
int tree[N];
bool cmp(Node x,Node y){
    return x.a>y.a;
}
int lowbit(int x){ return x&(-x);}

int update(int x){
    while(x<N){
        tree[x]++;
        x+=lowbit(x);
    }
}
int sum(int x){
    int sum=0;
    while(x){
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}
int main() {
    int n;
    cin>>n;
    mem(tree);
    mem(node);
    for(int i=1;i<=n;i++){
        cin>>node[i].a;
        node[i].b=i;
    }
    sort(node+1,node+1+n,cmp);
    int cnt=0;
    for(int i=1;i<=n;i++){
        cnt+=sum(node[i].b);
        update(node[i].b);
    }
    cout<<cnt<<endl;
    return 0;
}

字典树

#include <bits/stdc++.h>
#define N 100000
using namespace std;
int tree[N][26];
int val[N];
string s;
int pos = 1;

void insert(string s){
    int root = 0;
    for(int i = 0; s[i]; i++){
        int an = s[i] - 'a';
        if(!tree[root][an]){
            tree[root][an] = pos++;
        }
        root = tree[root][an];
    }
    val[root] = 1;
}

bool find(string s){
    int root = 0;
    for(int i = 0; s[i]; i++){
        int an = s[i] - 'a';
        if(!tree[root][an])
            return 0;
        root = tree[root][an];
    }
    return 1;
}

int main(){
    cin >> s;
    insert(s);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> s;
        if(find(s))
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;

    }
    return 0;
}

最小生成树

#include <iostream>
#include <algorithm>
#define N 50005
using namespace std;

int n, m;
struct Node{
    int x, y, val;
    friend bool operator <(const Node &a, const Node &b){
        return a.val < b.val;
    }
}node[N];

int fa[N];
int sum = 0;
int find(int x){
    return fa[x] == x? x: fa[x] = find(fa[x]);
}
int cnt = 0;
void kruskal(){
    for(int i = 0; i <= n; i++)
        fa[i] = i;
    for(int i = 0; i < m; i++){
        int ax = find(node[i].x);
        int ay = find(node[i].y);
        if(ax != ay){
            fa[ax] = ay;
            sum += node[i].val;
            cnt++;
        }
        if(cnt == n-1)
            break;
    }
}


int main(){    
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> node[i].x >> node[i].y >> node[i].val;
    }
    sort(node, node+m);
    kruskal();
    cout << sum << endl;
    return 0;
}

加一个prim板子

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define N 1005
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m;
int an = inf;
struct Node{
    int to, val;
    friend bool operator <(const Node &a, const Node &b){
        return a.val > b.val;
    }
};
int vis[N];
vector<Node> v[N];
priority_queue<Node> q;
void prim(){
    int cnt = 2;
    while(!q.empty()){
        Node ans = q.top();
        q.pop();
        if(vis[ans.to])
            continue;
        cnt ++;
        an += ans.val;
        vis[ans.to] = 1;
        if(cnt == n)
            break;
        for(int i = 0; i < v[ans.to].size(); i++){
            Node p = v[ans.to][i];
            if(vis[p.to])
                continue;
            q.push({p.to, p.val});
        }
    }
}

int main(){
    cin >> n >> m;
    int xx,yy;
    int x, y, z;
    for(int i = 0; i < m; i++){
        cin >> x >> y >> z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
        if(z < an) xx = x, yy = y, an = z;
    }
    vis[xx] = vis[yy] = 1;
    for(int i = 0; i < v[xx].size(); i++)
        q.push({v[xx][i].to, v[xx][i].val});
    for(int i = 0; i < v[yy].size(); i++)
        q.push({v[yy][i].to, v[yy][i].val});
    prim();
    cout << an <<endl;
    return 0;
}

最短路

#include <bits/stdc++.h>
#define N 1000
#define inf 0x3f3f3f3f
using namespace std;
int n, m;
struct Node{
    int to, value;
    friend bool operator<(const Node &a , const Node &b)
    {
        return a.value > b.value;   // ascending sort
    }
};
vector<Node> v[N];
int vis[N];
int val[N];
int ans = 0;

void short_path(int x){
    priority_queue<Node> q;
    q.push({x,0});
    while(!q.empty()){
        Node node = q.top();
         q.pop();
         if(vis[node.to] == 1)
            continue;
        vis[node.to] = 1;
        val[node.to] = min(val[node.to], node.value);
        ans ++;
        if(ans == n) break;

        for(int i = 0; i < v[node.to].size(); i ++){
            Node an = v[node.to][i];
            if(vis[an.to] == 0){
                q.push({an.to, val[node.to]+an.value});
            }
        }
    }
}

int main(){
    int x, y, z;
    while(cin >> n >> m && n != 0 && m != 0){
        memset(vis, 0, sizeof(vis));
        memset(val, inf, sizeof(val));
        ans = 0;
        for(int i = 0; i < 1000; i++)
            v[i].clear();
        for(int i = 0; i < m; i ++){
            cin >> x >> y >> z;
            v[x].push_back({y, z});
            v[y].push_back({x, z});
        }
        short_path(1);
        cout<< val[n] << endl;
    }
    return 0;
}