首页 💻 数据结构,📝 算法学习

1.二分查找

展开查看详情

代码:

ll l = x, r = y, ans;
while(l <= r){
    ll mid = l + r >> 1;
    if(check(mid)) ans = mid, r = mid - 1;
    else l = mid + 1;
}

2.并查集

展开查看详情

代码:

ll father(ll x){
    return mp[x] == 0 ? x : mp[x] = father(mp[x]);
}

void marge(ll u, ll v){
    if(father(u) != father(v))
        mp[father(u)] = father(v);
}

3.单调栈

展开查看详情

模板题: https://www.acwing.com/problem/content/832/
代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
ll s[maxn], t, n, x;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    while(n--){
        cin >> x;
        while(t && s[t] >= x) t--;
        if(t) cout << s[t] << " ";
        else cout << -1 << " ";
        s[++t] = x;
    }
    
    return 0;
}

4.单调队列

展开查看详情

模板题: https://www.acwing.com/problem/content/156/
代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e6 + 5;
ll n, k, h, t = -1, a[maxn], q[maxn];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(ll i = 1; i <= n; i++) cin >> a[i];//输入a[i]
    for(ll i = 1; i <= n; i++){
        if(h <= t && i - q[h] + 1 > k) h++;//当队头与当前元素距离大于k时,h++
        while(h <= t && a[q[t]] >= a[i]) t--;//当队尾元素大于等于当前元素时,t--
        q[++t] = i;//加入当前元素
        if(i >= k) cout << a[q[h]] << " ";//输出队头元素(最小)
    }
    cout << endl;
    h = 0, t = -1;
    for(ll i = 1; i <= n; i++){
        if(h <= t && i - q[h] + 1 > k) h++;
        while(h <= t && a[q[t]] <= a[i]) t--;
        q[++t] = i;
        if(i >= k) cout << a[q[h]] << " ";
    }
    cout << endl;
    
    return 0;
}

5.KMP

展开查看详情

模板题: https://www.acwing.com/problem/content/833/
代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
const ll maxm = 1e6 + 5;
char p[maxn], s[maxm];//p->模式串,s->主串
ll n, m, Next[maxn];

void getNext(){
    for(ll i = 2, j = 0; i <= n; i++){
        while(j && p[i] != p[j + 1]) j = Next[j];
        if(p[i] == p[j + 1]) j++;
        Next[i] = j;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> p + 1 >> m >> s + 1;
    getNext();
    for(ll i = 1, j = 0; i <= m; i++){
        while(j && s[i] != p[j + 1]) j = Next[j];
        if(s[i] == p[j + 1]) j++;
        if(j == n){
            cout << i - n << " ";
            j = Next[j];
        }
    }
    
    return 0;
}

6.Trie树

展开查看详情

模板题: https://www.acwing.com/problem/content/837/
代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
ll n, tree[maxn][26], cnt[maxn], idx;
char c, str[maxn];

void insert(){
    int p = 0;
    for(ll i = 0; str[i]; i++){
        int u = str[i] - 'a';
        if(!tree[p][u]) tree[p][u] = ++idx;
        p = tree[p][u];
    }
    cnt[p]++;
}

ll query(){
    int p = 0;
    for(ll i = 0; str[i]; i++){
        int u = str[i] - 'a';
        if(!tree[p][u]) return 0;
        p = tree[p][u];
    }
    return cnt[p];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    while(n--){
        cin >> c >> str;
        if(c == 'I') insert();
        else cout << query() << endl;
    }
    
    return 0;
}

7.BFS(迷宫,板子)

展开查看详情

模板题: https://www.acwing.com/problem/content/1078/
代码:

#include <bits/stdc++.h>
#define PLL pair<ll, ll>
using namespace std;
typedef long long ll;
const ll maxn = 1e3 + 5;
ll n, mp[maxn][maxn], a[maxn][maxn];
ll mv[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};
PLL p[maxn][maxn];
vector<PLL> v;
queue<PLL> q;

bool judge(ll dx, ll dy){
    return dx >= 0 && dy >= 0 && dx < n && dy < n && a[dx][dy] != -1 && mp[dx][dy] != 1;
}

void bfs(){
    a[0][0] = -1; q.push({0, 0});
    while(!q.empty()){
        PLL head = q.front(); q.pop();
        if(head.first == n - 1 && head.second == n - 1) return;
        for(ll i = 0; i < 4; i++){
            ll dx = head.first + mv[i][0];
            ll dy = head.second + mv[i][1];
            if(judge(dx, dy)){
                a[dx][dy] = -1;
                p[dx][dy] = {head.first, head.second};
                PLL temp = {dx, dy};
                q.push(temp);
            }
        }
    }
}

int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0); cout.tie(0);
    cin >> n;
    for(ll i = 0; i < n; i++)
        for(ll j = 0; j < n; j++)
            scanf("%lld", &mp[i][j]);
    bfs(); v.push_back({n - 1, n - 1});
    PLL pr = p[n - 1][n - 1];
    while(pr.first != 0 || pr.second != 0){
        v.push_back(pr);
        pr = p[pr.first][pr.second];
    }
    printf("%lld %lld\n", 0, 0);
    for(ll i = v.size() - 1; i >= 0; i--){
        printf("%lld %lld\n", v[i].first, v[i].second);
    }
    
    return 0;
}

8.DFS(池塘个数,板子)

展开查看详情

模板题: https://www.acwing.com/problem/content/1099/
代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e3 + 5;
ll n, m, ans, mp[maxn][maxn];
char ch;

void dfs(ll l, ll r){
    mp[l][r] = -1;
    if(!mp[l - 1][r - 1]) dfs(l - 1, r - 1);
    if(!mp[l - 1][r]) dfs(l - 1, r);
    if(!mp[l - 1][r + 1]) dfs(l - 1, r + 1);
    if(!mp[l][r - 1]) dfs(l, r - 1);
    if(!mp[l][r + 1]) dfs(l, r + 1);
    if(!mp[l + 1][r - 1]) dfs(l + 1, r - 1);
    if(!mp[l + 1][r]) dfs(l + 1, r);
    if(!mp[l + 1][r + 1]) dfs(l + 1, r + 1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m; memset(mp, -1, sizeof(mp));
    for(ll i = 1; i <= n; i++){
        for(ll j = 1; j <= m; j++){
            cin >> ch;
            mp[i][j] = (ch == '.' ? 1 : 0);
        }
    }
    for(ll i = 1; i <= n; i++){
        for(ll j = 1; j <= m; j++){
            if(mp[i][j] == 0) dfs(i, j), ans++;
        }
    }
    cout << ans << endl;
    
    return 0;
}

9.拓扑排序

展开查看详情

模板题: https://www.acwing.com/problem/content/description/850/
代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
vector<ll> v, edge[maxn];
ll n, m, in[maxn];
queue<ll> q;

ll topSort(){
    for(ll i = 1; i <= n; i++) if(!in[i]) q.push(i), v.push_back(i);
    while(!q.empty()){
        ll head = q.front();
        q.pop();
        for(auto item : edge[head]){
            in[item]--;
            if(!in[item]) q.push(item), v.push_back(item);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    while(m--){
        ll x, y;
        cin >> x >> y; in[y]++;
        edge[x].push_back(y);
    }
    if(topSort() == -1 || v.size() != n) cout << -1 << endl;
    else for(auto item : v) cout << item << " ";
    
    return 0;
}

10.堆优化的Dijkstra

展开查看详情

模板题: https://www.acwing.com/problem/content/852/

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
vector<pair<ll, ll> > edge[maxn];
ll n, m, d[maxn];
bool vis[maxn];

ll spfa(){
    memset(d, 0x3f, sizeof(d)); d[1] = 0;
    queue<ll> q; q.push(1); vis[1] = true;
    while(!q.empty()){
        ll t = q.front();
        q.pop(); vis[t] = false;
        for(auto it : edge[t]){
            if(d[it.first] > d[t] + it.second){
                d[it.first] = d[t] + it.second;
                if(!vis[it.first]){
                    vis[it.first] = true;
                    q.push(it.first);
                }
            }
        }
    }
    if(d[n] > 1e9) return -1;
    return d[n];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    while(m--){
        ll u, v, w;
        cin >> u >> v >> w;
        edge[u].push_back({v, w});
    }
    ll ans = spfa();
    cout << ans << endl;
    
    return 0;
}

11.最小生成树(Kruskal)

展开查看详情

模板题: https://www.acwing.com/problem/content/861/
代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, m; int fa[maxn];
struct node{ int u, v, w; }edge[maxn];

bool cmp(node a, node b){ return a.w < b.w; }

int Father(int x){ return fa[x] == x ? x : fa[x] = Father(fa[x]); }

void Mark(int u, int v){ int uu = Father(u); int vv = Father(v); if(uu != vv) fa[uu] = vv; }

bool judge(int u, int v){ int uu = Father(u); int vv = Father(v); if(uu != vv) return true; return false; }

void kruskal(){
    int ans = 0, cnt = 0;
    sort(edge, edge + m, cmp);
    for(int i = 0; i < m; i++){
        int u = edge[i].u;
        int v = edge[i].v;
        if(judge(u, v)){
            Mark(u, v);
            ans += edge[i].w;
            if(++cnt == n - 1)
                break;
        }
    }
    if(cnt == n - 1) printf("%d\n", ans);
    else printf("impossible\n");
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++)
        scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
    for(int i = 0; i <= n; i++) fa[i] = i;
    kruskal();
    
    return 0;
}




文章评论

目录