思路: 线段树 (区间更新)

区间更新模板

参考: 题解: AcWing 243. 一个简单的整数问题2 (线段树区间插入)

把 插入 操作 换成 更新 操作;

代码实现:

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

#define lson rt<<1
#define rson rt<<1|1
#define mid (l+r)>>1

const int N = 1e5 + 10;
int _, n, m;

typedef long long ll;

ll tr[N << 2], lz[N << 2];

void up(int rt) {
    tr[rt] = tr[lson] + tr[rson];
}

void down(int rt, int l, int r) {
    if (lz[rt] != 0) {
        int m = mid;

        lz[lson] = lz[rt];
        tr[lson] = (m - l + 1) * lz[rt];

        lz[rson] = lz[rt];
        tr[rson] = (r - m) * lz[rt];

        lz[rt] = 0;
    }
}

void insert(int rt, int l, int r, int x, int y, ll v) {
    if (l == x && r == y) {
        tr[rt] = (r - l + 1) * v;
        lz[rt] = v;
        return;
    }

    down(rt, l, r);
    int m = mid;

    if (y <= m)
        insert(lson, l, m, x, y, v);
    else if (x > m)
        insert(rson, m + 1, r, x, y, v);
    else
        insert(lson, l, m, x, m, v),
        insert(rson, m + 1, r, m + 1, y, v);
    up(rt);
}

ll calc(int rt, int l, int r, int x, int y) {
    if (x == l && r == y) 
       return tr[rt];

    down(rt, l, r);
    int m = mid;
    if (y <= m)
        return calc(lson, l, m, x, y);
    else if (x > m)
        return calc(rson, m + 1, r, x, y);
    else 
        return calc(lson, l, m, x, m) + calc(rson, m + 1, r, m + 1, y);

}

void solve(int index) {
    memset(tr, 0, sizeof tr);
    memset(lz, 0, sizeof lz);
    cin >> n >> m;
    insert(1, 1, n, 1, n, 1);
    while (m--) {
        int x, y, t;
        cin >> x >> y >> t;
        insert(1, 1, n, x, y, t);
    }

    printf("Case %d: The total value of the hook is %lld.\n", index, calc(1, 1, n, 1, n));
}

int main() {
    cin >> _;
    for (int i = 1; i <= _; i++) 
        solve(i);
    return 0;
}

思路: 线段树 (区间插入, 区间查询)

区间插入板子

还不会线段树的看这里: https://www.bilibili.com/video/BV1qY411n7Qs/?share_source=copy_web&vd_source=fcfe5417126b8b1ac8277353f33dc3e0

线段树节点:

struct Node {
    int L, R;
    ll lazy;    // 懒标记 
    ll val;     // 区间和 
} tr[N << 2];

懒标记的作用: 我们进行区间插入的时候, 比如说我们在 [1, 223] 这个区间插入 5, 那么在线段树中, 这个 [1, 223] 区间可能会被分解成 [1,128], [129, 192], [193, 208], [209, 216], [217, 220], [221, 222], [223, 223] 这样几个区间; 我们递归到 [1, 128] 这个节点时, 当前节点的区间被包含在插入区间 [1, 223] 中, 也就是当前区间的每一位我们都插入一个 5, 我们令当前区间的lazy += 5, 表示当前区间的每一位都插入一个 5, 这样就不需要再往下递归;

看 insert() 方法, 就是实现上述的逻辑:

// 插入 
void insert(int rt, int x, int y, int v) {
    if (l == x && r == y) {
        tr[rt].lazy += v;
        tr[rt].val += (r - l + 1L) * v;
        return;
    }

    down(rt);
    int m = mid;

    if (y <= m)
        insert(lson, x, y, v);
    else if (x > m)
        insert(rson, x, y, v);
    else 
        insert(lson, x, m, v), 
        insert(rson, m + 1, y, v);

    up(rt);
}

可以发现, 除了上述逻辑, 每到一个节点, 我们都会做一个 down() 的动作:

// push_down(), 父节点懒标记下传 
void down(int rt) {
    // 当前区间有懒标记 
    if (tr[rt].lazy != 0) {
        ll lz = tr[rt].lazy;
        // 下传给左孩子 
        tr[lson].lazy += lz;
        tr[lson].val += (tr[lson].R - tr[lson].L + 1) * lz; 
        // 下传给右孩子 
        tr[rson].lazy += lz;
        tr[rson].val += (tr[rson].R - tr[rson].L + 1) * lz; 
        // 下传完清空当前节点的懒标记 
        tr[rt].lazy = 0;
    }
}

它的作用是把父节点懒标记下传, 通过这样 懒住 和 下传 的操作, 我们才能实现 区间插入 的操作的时间复杂度趋近于 log 级别

完整代码实现:

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define lson rt<<1                  // 左孩子下标 
#define rson rt<<1|1                // 右孩子下标 
#define mid (tr[rt].L+tr[rt].R)>>1  // 区间 [L, R] 的中点 
#define l tr[rt].L                  // 节点区间 [L, R] --> [l, r] , coding 比较方便 
#define r tr[rt].R

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 10;
int _, n, m;

struct Node {
    int L, R;
    ll lazy;    // 懒标记 
    ll val;     // 区间和 
} tr[N << 2];

// 建树 
void build(int rt, int L, int R) {
    tr[rt] = {L, R};
    if (l == r)
        return ;
    int m = mid;
    build(lson, l, m);
    build(rson, m + 1, r);
}

// push_up() 方法, 孩子向父节点传递数据 
void up(int rt) {
    tr[rt].val = tr[lson].val + tr[rson].val;
}

// push_down(), 父节点懒标记下传 
void down(int rt) {
    // 当前区间有懒标记 
    if (tr[rt].lazy != 0) {
        ll lz = tr[rt].lazy;
        // 下传给左孩子 
        tr[lson].lazy += lz;
        tr[lson].val += (tr[lson].R - tr[lson].L + 1) * lz; 
        // 下传给右孩子 
        tr[rson].lazy += lz;
        tr[rson].val += (tr[rson].R - tr[rson].L + 1) * lz; 
        // 下传完清空当前节点的懒标记 
        tr[rt].lazy = 0;
    }
}

// 插入 
void insert(int rt, int x, int y, int v) {
    if (l == x && r == y) {
        tr[rt].lazy += v;
        tr[rt].val += (r - l + 1L) * v;
        return;
    }

    down(rt);
    int m = mid;

    if (y <= m)
        insert(lson, x, y, v);
    else if (x > m)
        insert(rson, x, y, v);
    else 
        insert(lson, x, m, v), 
        insert(rson, m + 1, y, v);

    up(rt);
}

// 查询方法 
ll calc(int rt, int x, int y) {
    if (x == l && y == r)
        return tr[rt].val;
    down(rt);
    int m = mid;
    if (y <= m)
        return calc(lson, x, y);
    else if (x > m)
        return calc(rson, x, y);
    else 
        return calc(lson, x, m) + calc(rson, m + 1, y);
}

void solve() {
    cin >> n >> m;
    build(1, 1, n);
    ll t;
    for (int i = 1; i <= n; i++) {
        cin >> t;
        insert(1, i, i, t);
    }

    while (m--) {
        string op;
        ll x, y, t;
        cin >> op;

        if ("C" == op) {
            cin >> x >> y >> t;
            insert(1, x, y, t);
        } else {
            cin >> x >> y;
            cout << calc(1, x, y) << endl;
        }
    }
}

int main() {
//  IOS
//  cin >> _;
//  for (int i = 1; i <= _; i++)
    solve();
    return 0;
}

stack

#include <cstdio>
#include <iostream>
#include <stack>
#include <unordered_map>

using namespace std;
stack<char> stk;
unordered_map<char, char> mapping = {
    {'>', '<'}, {')', '('}, {'}', '{'}, {']', '['}
};
bool flag = true;

bool check(char c) {
    if ( c == '<' || c == '(' || c == '{' || c == '[' ) return true;
    return false;
}

int main() {
    string s;
    cin >> s;

    for ( int i = 0; i < s.size(); i++ ) {
        if ( check(s[i]) ) {
            stk.push(s[i]);
        }
        else {
            if ( stk.size() && stk.top() == mapping[s[i]] ) stk.pop();
            else flag = false;
        }
        if ( !flag ) break;
    }
    if ( stk.size() ) flag = false;
    if ( flag ) puts("yes");
    else puts("no");

    return 0;
}

题目描述

筛质数

算法1

埃氏筛法

Python 代码

# 埃氏筛选
# n = int(input())
# st = [False] * (n + 1)  # st[i]有没有被筛过
# primes = []
# cnt = 0  # 第几个质数
# for i in range(2, n + 1):
#     if not st[i]:  # 第i个没有被筛掉，说明ta是质数
#         primes.append(i)
#         cnt += 1
#     j = 2
#     while j * i <= n:
#         st[j * i] = True
#         j += 1
# print(cnt)

# 优化
n = int(input())
st = [False] * (n + 1)  # st[i]有没有被筛过
cnt = 0  # 第几个质数
for i in range(2, n + 1):
    if not st[i]:  # 第i个没有被筛掉，说明ta是质数
        cnt += 1
        # 优化：将这个循环放进来
        # 只用将质数的j倍筛掉
        j = 2
        while j * i <= n:
            st[j * i] = True
            j += 1
print(cnt)

算法2

线性筛法

Python 代码

# 埃氏筛选
n = int(input())
# n = 36
st = [False] * (n + 1)  # st[i]有没有被筛过
primes = []
cnt = 0  # 第几个质数
for i in range(2, n + 1):
    if not st[i]:  # 第i个没有被筛掉，说明ta是质数
        cnt += 1
        primes.append(i)

    j = 0
    while primes[j] <= n // i:
        st[primes[j] * i] = True
        # print(i, j, primes[j], primes[j] * i)
        if i % primes[j] == 0:
            break
        j += 1

print(cnt)
# print(primes)
"""
和埃氏筛法的区别在于
埃氏筛法里有些数字会被筛多次，
比如14，质数选到2的时候会被筛一次，选到7的时候又会被筛一次
而线性筛法就会避免掉这种情况，保证每个合数都是被它最小的质因子筛掉
比如14，只会在i=7，然后primes[j]是2的时候被筛掉
也就是每一次都是拿i去遍历乘primes中的质数，筛掉数字 st[primes[j] * i] = True
i % primes[j] == 0:成立，说明primes[j] 的质因子，
再向后遍历到primes[j+1]得到的 primes[j+1] * i 的最小质因子就不是primes[j+1]了
比如，primes[j] =2，i = 6，primes[j] * i = 12
primes[j + 1] * i = 3 * 6 = 18，
3不是18的最小质因子，因为 i=6里面有2了
"""

二分+字符串哈希

#include <cstdio>
#include <iostream>

using namespace std;
typedef unsigned long long ULL;
const int N = 110, P = 13331;
ULL h1[2*N], h2[2*N], p[2*N];
string s1, s2, res;


ULL get_hash(int l, int r, int target) {
    if ( target == 1 ) {
        return h1[r] - h1[l - 1] * p[r - l + 1];
    }
    else if ( target == 2 ) {
        return h2[r] - h2[l - 1] * p[r - l + 1];
    }
    else {
        puts("Error target number");
        system("pause");
    }
}

bool check(int mid) {
    for ( int i = 1; i < s1.size() - mid + 1; i++ ) {
        for ( int j = 1; j < s2.size() - mid + 1; j++ ) {
            if ( get_hash(i, i + mid - 1, 1) == get_hash(j, j + mid - 1, 2) ) return true;
        }
    }
    return false;
}

int main() {

    cin >> s1 >> s2;
    p[0] = 1;
    for ( int i = 1; i <= N; i++ ) {
        h1[i] = h1[i - 1] * P + s1[i - 1];
        h2[i] = h2[i - 1] * P + s2[i - 1];
        p[i] = p[i - 1] * P;
    }
    int l = 0, r = min(s1.size(), s2.size());
    while ( l < r ) {
        int mid = l + r + 1 >> 1;
        if ( check(mid) ) l = mid;
        else r = mid - 1;
    }
    for ( int i = 1; i < s1.size() - r + 1; i++ ) 
        for ( int j = 1; j < s2.size() - r + 1; j++ )  
            if ( get_hash(i, i + r - 1, 1) == get_hash(j, j + r - 1, 2) )
                res = s1.substr(i - 1, r);

    cout << r << endl << res << endl;

    return 0;
}

思路: 线段树

还不会线段树的看这里: https://www.bilibili.com/video/BV1qY411n7Qs/?share_source=copy_web&vd_source=fcfe5417126b8b1ac8277353f33dc3e0

代码实现:

/*
    Author: Cai 
    Date: 27/05/23 10:55
    Description: 
*/
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

#define endl "\n"
#define lson rt<<1
#define rson rt<<1|1
#define mid (l+r)>>1
//#define l tr[rt].L
//#define r tr[rt].R

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 10;
int _, n, m;

int tr[N << 2]; 

void insert(int rt, int l, int r, int x, int v) {
    if (l == r) {
        tr[rt] = v;
        return;
    }
    int m = mid;
    if (x <= m)
        insert(lson, l, m, x, v);
    else 
        insert(rson, m + 1, r, x, v);
    tr[rt] = max(tr[lson], tr[rson]);
}

int calc(int rt, int l, int r, int x, int y) {
    if (l == x && y == r) {
        return tr[rt];
    }
    int m = mid;

    if (y <= m)
        return calc(lson, l, m, x, y);
    else if (x > m) 
        return calc(rson, m + 1, r, x, y);
    else {
        return max(calc(lson, l, m, x, m), calc(rson, m + 1, r, m + 1, y));
    }
}

void solve() {

    while (cin >> n >> m) {
        memset(tr, 0, sizeof tr);
        int t;
        for (int i = 1; i <= n; i++) {
            cin >> t;
            insert(1, 1, n, i, t);
        }

        while (m--) {

            string op;
            int x, y;

            cin >> op >> x >> y;
            if ("U" == op) 
                insert(1, 1, n, x, y);
            else
                cout << calc(1, 1, n, x, y) << endl;
        }
    }   
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//  cin >> _;
//  for (int i = 1; i <= _; i++)
    solve();
    return 0;
}

思路: 线段树模板

还不会线段树的看这里: https://www.bilibili.com/video/BV1qY411n7Qs/?share_source=copy_web&vd_source=fcfe5417126b8b1ac8277353f33dc3e0

写题过程中一定要学会 画图! 画图! 画图!

线段树在我理解就是 把一个大区间划分成 一个个小区间 去维护, 本质上是 树形 dp 的问题, 通过 push_up() 和 push_down() 维护父子节点之间的关系;

代码实现:

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

#define endl "\n"
#define lson rt<<1
#define rson rt<<1|1
#define mid (l+r)>>1
//#define l tr[rt].L
//#define r tr[rt].R

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 10;
int _, n, m;

int tr[N << 2]; 

void insert(int rt, int l, int r, int x, int v) {
    if (l == r) {
        tr[rt] += v;
        return;
    }
    int m = mid;
    if (x <= m)
        insert(lson, l, m, x, v);
    else 
        insert(rson, m + 1, r, x, v);
    tr[rt] = tr[lson] + tr[rson];   // push_up() 方法, 比较简单就不抽取为方法了
}

int calc(int rt, int l, int r, int x, int y) {
    if (l == x && y == r) {
        return tr[rt];
    }
    int m = mid;

    if (y <= m)
        return calc(lson, l, m, x, y);
    else if (x > m) 
        return calc(rson, m + 1, r, x, y);
    else {
        return calc(lson, l, m, x, m) + calc(rson, m + 1, r, m + 1, y);
    }
}

void solve(int index) {
    memset(tr, 0, sizeof tr);
    cin >> n;

    int t;
    for (int i = 1; i <= n; i++) {
        cin >> t;
        insert(1, 1, n, i, t);
    }

    string op;
    int x, y;
    cout << "Case " << index << ":" << endl;
    while (cin >> op) {

        if ("End" == op)
            break;
        cin >> x >> y;
        if ("Add" == op) 
            insert(1, 1, n, x, y);
        else if ("Sub" == op)
            insert(1, 1, n, x, -y);
        else
            cout << calc(1, 1, n, x, y) << endl;
    }

}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> _;
    for (int i = 1; i <= _; i++)
    solve(i);
    return 0;
}

堆优化dijkstra

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 810, M = 3010, INF = 0x3f3f3f3f;
int n, m, p;
int cow[N];
int h[N], ne[M], w[M], e[M], idx;
bool st[N];
int dist[N];
inline void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
inline int dijkstra(int s)
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, s});
    while (!heap.empty ())
    {
        auto var = heap.top().second;
        heap.pop();
        if (st[var]) continue;
        st[var] = true;
        for (int i = h[var]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[var] + w[i])
            {
                dist[j] = dist[var] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (dist[cow[i]] == INF) return INF;
        res += dist[cow[i]];
    }  
    return res;
}
inline void solve()
{
    memset(h, -1, sizeof h);
    cin >> n >> p >> m;
    for (int i = 1; i <= n; i ++ ) cin >> cow[i];
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    int res = INF;
    for (int i = 1; i <= p; i ++ )
        res = min(res, dijkstra(i));
    cout << res << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}

思路:

最小生成树, 加边时, 如果 边长 d > 1000 || d < 10 直接设距离为 INF, 表示两点间不可达, 生成树时, 如果遇见 INF 的边, 说明图时不连通的, 输出 oh!

代码实现:

/*
    Author: Cai
    Date: 04/06/23 15:54
*/
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 110, INF = 0x3f3f3f3f;
int _, n, m;

int id[N];
pii ps[N];

struct Edge {
    int x, y;
    double w;
} es[1223 << 4];

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

int find(int x) {
    if (x != id[x])
        id[x] = find(id[x]);
    return id[x];
}

void init() {
    for (int i = 0; i <= n; i++) 
        id[i] = i;
}

double get_min_tree() {
    sort(es, es + m, cmp);

    init();
    double res = 0;
    for (int i = 0; i < m; i++) {
        if (res > INF / 2)
            return INF;

        int fx = find(es[i].x);
        int fy = find(es[i].y);

        if (fx != fy) {
            id[fy] = fx;
            res += es[i].w;
        }

    }
    return res;
}

double get_dist(pii a, pii b) {
    double x = a.first - b.first;
    double y = a.second - b.second;
    return sqrt(x * x + y * y);
}

void solve() {
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> ps[i].first >> ps[i].second;

    m = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            double d = get_dist(ps[i], ps[j]);
//          cout << i << " " << j << " " << d << endl;

            if (10 <= d && d <= 1000)
                es[m++] = {i, j, d};
            else 
                es[m++] = {i, j, INF};
        }

    double ans = get_min_tree();
    if (ans == INF)
        puts("oh!");
    else
        printf("%.1lf\n", (ans * 100));

}

int main() {
//  IOS
    cin >> _;
    for (int i = 1; i <= _; i++)
    solve();
    return 0;
}

代码实现:

/*
    Author: Cai
    Date: 04/06/23 15:48
*/
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 10;
int _, n, m;

int id[N];

struct Edge {
    int x, y;
    int w;
} es[1223 << 4];

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

int find(int x) {
    if (x != id[x])
        id[x] = find(id[x]);
    return id[x];
}

void init() {
    for (int i = 0; i <= n; i++) 
        id[i] = i;
}

int get_min_tree() {
    sort(es, es + m, cmp);

    init();
    int res = 0;
    for (int i = 0; i < m; i++) {
        int fx = find(es[i].x);
        int fy = find(es[i].y);

        if (fx != fy) {
            id[fy] = fx;
            res += es[i].w;
        }

    }
    return res;
}

void solve() {
    while (cin >> n) {

        if (n == 0)
            break;

        m = (n - 1) * n / 2;

        for (int i = 0; i < m; i++) 
            cin >> es[i].x >> es[i].y >> es[i].w;

        int ans = get_min_tree();

        cout << ans << endl;

    }
}

int main() {
//  IOS
//  cin >> _;
//  for (int i = 1; i <= _; i++)
    solve();
    return 0;
}