醉心代码无法自拔

程序员的自我修养(?)

0%

一些板子

发表于 更新于 分类于
本文字数： 6.3k 阅读时长 ≈ 12 分钟

Obsidian 不知道为什么直接复制的板子总会有一些莫名其妙的零宽空格。还是放这里吧。

Template.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using pii = pair<int, int>;
template <typename _Tp>
using pgr = priority_queue<_Tp, vector<_Tp>, greater<>>;
using Point = complex<int>; // for geomentry use double
#define x real
#define y imag
mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count()); // usage:i64 x = rnd();
#define all(a) (a).begin(), (a).end()
// #define SINGLE
constexpr int MAXN = 2e5 + 10;
void init()
{
}
void solve()
{
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	init();
	int t;
#ifdef SINGLE
	t = 1;
#else
	cin >> t;
#endif
	while (t--)
		solve();
	cerr << "程序执行用时 " << 1.0 * clock() / CLOCKS_PER_SEC << " 秒。" << endl;
	return 0;
}

数据结构

线段树

模板：扶苏的问题

板子功能：懒惰标记(区间加和区间修改)，查询区间最大值，最小值，和值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
using i64 = long long;
const int MAXN = 2e5 + 10;
struct Node
{
    int l, r;
    i64 w, s, m, t1, t2;
    Node *ls, *rs;

    void makeModifyTag(int x)
    {
        int len = this->r - this->l + 1;
        w = t1 = x;
        s = x * len;
        m = t1 = x;
        t2 = 0;
    }

    void makeAddTag(int x)
    {
        int len = this->r - this->l + 1;
        w += x;
        m += x;
        s += len * x;
        if (t1 != LLONG_MAX)
            t1 += x;
        else
            t2 += x;
    }
    void pushdown()
    {
        if (t1 != LLONG_MAX)
        {
            ls->makeModifyTag(t1);
            rs->makeModifyTag(t1);
            t1 = LLONG_MAX;
        }
        else if (t2)
        {
            ls->makeAddTag(t2);
            rs->makeAddTag(t2);
            t2 = 0;
        }
    }
    void pushup()
    {
        w = max(ls->w, rs->w);
        m = min(ls->m, rs->m);
        s = ls->s + rs->s;
    }

    bool InRange(int L, int R) { return (L <= l) && (r <= R); }
    bool OutofRange(int L, int R) { return (l > R) || (r < L); }

    void update(int L, int R, int x, int op)
    {
        if (InRange(L, R))
        {
            if (op == 1)
                makeModifyTag(x);
            else
                makeAddTag(x);
        }
        else if (!OutofRange(L, R))
        {
            pushdown();
            ls->update(L, R, x, op);
            rs->update(L, R, x, op);
            pushup();
        }
    }

    i64 queryMax(int L, int R)
    {
        if (InRange(L, R))
            return w;
        else if (!OutofRange(L, R))
        {
            pushdown();
            return max(ls->queryMax(L, R), rs->queryMax(L, R));
        }
        else
            return LLONG_MIN;
    }
    i64 queryMin(int L, int R)
    {
        if (InRange(L, R))
            return m;
        else if (!OutofRange(L, R))
        {
            pushdown();
            return min(ls->queryMin(L, R), rs->queryMin(L, R));
        }
        else
            return LLONG_MAX;
    }

    i64 querySum(int L, int R)
    {
        if (InRange(L, R))
            return s;
        else if (!OutofRange(L, R))
        {
            pushdown();
            return ls->querySum(L, R) + rs->querySum(L, R);
        }
        else
            return 0;
    }
};

Node Mem[MAXN << 1], *pool = Mem;

Node *New(int L, int R)
{
    auto u = pool++;
    u->l = L;
    u->r = R;
    u->t1 = LLONG_MAX;
    u->t2 = 0;
    if (L != R)
    {
        int M = (L + R) >> 1;
        u->ls = New(L, M);
        u->rs = New(M + 1, R);
        u->pushup();
    }
    else
    {
        u->w = vec[L];
        u->s = vec[L];
        u->m = vec[L];
    }
    return u;
}

使用例：

1
2
3
4
5
vec.resize(n + 1); // 从 1 开始算
pool = Mem; // 多测重置
auto root = New(1, n); // 初始化根节点
root->queryMax(...);
// ...

图论

Dijkstra

原版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int MAXN = 1e6;
struct Edge
{
    int to, weight;
};
struct Node
{
    int dis, from;
    bool operator>(const Node &a) const { return dis > a.dis; }
};
vector<Edge> edges[MAXN];
vector<int> dis(MAXN), vis(MAXN);
priority_queue<Node, vector<Node>, greater<Node>> que;
void dijkstra(int n, int s)
{
    dis = vector<int>(MAXN, INT_MAX);
    dis[s] = 0;
    que.push({0, s});
    while (!que.empty())
    {
        int from = que.top().from;
        que.pop();
        if (vis[from])
            continue;
        vis[from] = 1;
        for (auto edge : edges[from])
        {
            int to = edge.to, weight = edge.weight;
            if (dis[to] > dis[from] + weight)
            {
                dis[to] = dis[from] + weight;
                que.push({dis[to], to});
            }
        }
    }
}

带点权

出现于24睿抗省赛，QLU24秋排第二场，第四场

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
const int MAXN = 1e6;
struct Edge
{
    int to, weight;
};
struct Node
{
    int dis, from;
    bool operator>(const Node &a) const { return dis > a.dis; }
};
vector<Edge> edges[MAXN];
vector<int> dis(MAXN), vis(MAXN);
vector<int> value(MAXN);
vector<int> vec(MAXN);
priority_queue<Node, vector<Node>, greater<Node>> que;
void dijkstra(int n, int s)
{
    dis = vector<int>(MAXN, INT_MAX);
    vis = vector<int>(MAXN, 0);
    dis[s] = 0;
    value[s] = vec[s];
    que.push({0, s});
    while (!que.empty())
    {
        int from = que.top().from;
        que.pop();
        if (vis[from])
            continue;
        vis[from] = 1;
        for (auto edge : edges[from])
        {
            int to = edge.to, weight = edge.weight;
            if (dis[to] > dis[from] + weight)
            {
                dis[to] = dis[from] + weight;
                value[to] = value[from] + vec[to];
                que.push({dis[to], to});
            }
            else if (dis[to] == dis[from] + weight && value[to] < value[from] + vec[to])
            {
                value[to] = value[from] + vec[to];
                que.push({dis[to], to});
            }
        }
    }
}

分层图（以CF2014E为例）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
using i64 = long long;
template <typename _Tp>
using pgr = priority_queue<_Tp, vector<_Tp>, greater<>>;
constexpr int MAXN = 2e5 + 10;
int n, m, h, u, v, w;
vector<int> horse;
vector<vector<i64>> dis, vis;
struct Edge
{
    int to, weight;
};
vector<vector<Edge>> edges;
struct Node
{
    int dis, from;
    bool status;
    Node(int dis, int from, bool status) : dis(dis), from(from), status(status) {}
    bool operator>(const Node &a) const { return dis > a.dis; }
};
pgr<Node> que;

void dijkstra(int n, int s)
{
    dis.assign(2ll, vector<i64>(n + 1ll, LLONG_MAX / 2));
    vis.assign(2ll, vector<i64>(n + 1ll, false));
    dis[0][s] = 0;
    que.push(Node(0, s, false));
    while (!que.empty())
    {
        auto [dist, from, status] = que.top();
        que.pop();
        if (vis[status][from])
            continue;
        vis[status][from] = true;
        for (auto &edge : edges[from])
        {
            int to = edge.to, weight = edge.weight;
            // 已经骑马，这个点可以骑马和不能不能骑马，一共三种状态
            if (status)
            {
                if (dis[1][to] > dis[1][from] + weight / 2)
                {
                    dis[1][to] = dis[1][from] + weight / 2;
                    que.push(Node(dis[1][to], to, true));
                }
            }
            else if (horse[from])
            {
                if (dis[1][to] > dis[0][from] + weight / 2)
                {
                    dis[1][to] = dis[0][from] + weight / 2;
                    que.push(Node(dis[1][to], to, true));
                }
            }
            else
            {
                if (dis[0][to] > dis[0][from] + weight)
                {
                    dis[0][to] = dis[0][from] + weight;
                    que.push(Node(dis[0][to], to, false));
                }
            }
        }
    }
}