杂题小记（2023.02.22）

更好的阅读体验戳此进入

好吧这一天刷了好几道大水题，大概就是写某道题的时候延申延申又延申出来一大堆奇怪的没怎么写过的小知识点，就丢到杂题里了。

HDU-3038 How Many Answers Are Wrong

题面

$n$ $m$ $l, r, s$ $\sum_{i = l}^r = s$ ，你需要判断有多少限制与其之前的限制矛盾。

Solution

$dis$ ，每次判断是否合法即可。

然后 HDU 默认多测题面里不写，我还以为代码写错了找了半天。。。

Code


xxxxxxxxxx
83
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template < typename T = int >
24
inline T read(void);
25

26
int N, M;
27
int ans(0);
28

29
class UnionFind{
30
private:
31
    int fa[210000];
32
    ll dis[210000];
33
public:
34
    UnionFind(void){for(int i = 1; i <= 201000; ++i)fa[i] = i, dis[i] = 0;}
35
    void Clear(void){for(int i = 1; i <= 201000; ++i)fa[i] = i, dis[i] = 0;}
36
    int Find(int x){
37
        if(x == fa[x])return x;
38
        int cfa = fa[x];
39
        fa[x] = Find(fa[x]);
40
        dis[x] += dis[cfa];
41
        return fa[x];
42
    }
43
    void Union(int s, int t, ll d){
44
        int fs = Find(s), ft = Find(t);
45
        if(fs == ft)return;
46
        fa[fs] = ft;
47
        dis[fs] = d + dis[t] - dis[s];
48
    }
49
    bool CheckDis(int s, int t, ll d){
50
        return dis[s] != d + dis[t];
51
    }
52
}uf;
53

54
int main(){
55
    while(true){
56
        ans = 0, uf.Clear();
57
        N = read(), M = read();
58
        while(M--){
59
            int s = read(), t = read() + 1, d = read();
60
            if(uf.Find(s) != uf.Find(t))uf.Union(s, t, d);
61
            else ans += uf.CheckDis(s, t, d);
62
        }printf("%d\n", ans);
63
    }
64
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
65
    return 0;
66
}
67

68
template < typename T >
69
inline T read(void){
70
    T ret(0);
71
    int flag(1);
72
    int c = getchar();
73
    if(!~c)exit(0);
74
    while(c != '-' && !isdigit(c))c = getchar();
75
    if(c == '-')flag = -1, c = getchar();
76
    while(isdigit(c)){
77
        ret *= 10;
78
        ret += int(c - '0');
79
        c = getchar();
80
    }
81
    ret *= flag;
82
    return ret;
83
}

LG-P1525 [NOIP2010 提高组] 关押罪犯

题面

$n$ $m$ $s, t, w$ $s$ $t$ $w$ $n$ 个人分到两个监狱中，以最小化最大贡献，输出最小值，若不存在贡献则输出 0。

Solution

扩展域并查集。与其说扩展域并查集，也可以认为其就是利用了 2-SAT 的思想，每个点拆成两个，然后贪心地优先取更大的限制，尽量去安排即可。

Code


xxxxxxxxxx
71
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template < typename T = int >
24
inline T read(void);
25

26
int N, M;
27
struct Node{int s, t, w;};
28
basic_string < Node > rels;
29

30
class UnionFind{
31
private:
32
    int fa[410000];
33
public:
34
    UnionFind(void){for(int i = 1; i <= 401000; ++i)fa[i] = i;}
35
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
36
    void Union(int s, int t){
37
        int fs = Find(s), ft = Find(t);
38
        if(fs == ft)return;
39
        fa[fs] = ft;
40
    }
41
}uf;
42

43
int main(){
44
    N = read(), M = read();
45
    for(int i = 1; i <= M; ++i){
46
        int s = read(), t = read(), w = read();
47
        rels += Node{s, t, w};
48
    }sort(rels.begin(), rels.end(), [](const Node &a, const Node &b)->bool{return a.w > b.w;});
49
    for(auto rel : rels){
50
        if(uf.Find(rel.s << 1) != uf.Find(rel.t << 1))uf.Union(rel.s << 1, (rel.t << 1) | 1), uf.Union((rel.s << 1) | 1, rel.t << 1);
51
        else printf("%d\n", rel.w), exit(0);
52
    }printf("0\n");
53
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
54
    return 0;
55
}
56

57
template < typename T >
58
inline T read(void){
59
    T ret(0);
60
    int flag(1);
61
    char c = getchar();
62
    while(c != '-' && !isdigit(c))c = getchar();
63
    if(c == '-')flag = -1, c = getchar();
64
    while(isdigit(c)){
65
        ret *= 10;
66
        ret += int(c - '0');
67
        c = getchar();
68
    }
69
    ret *= flag;
70
    return ret;
71
}

LG-P2024 [NOI2001] 食物链

题面

$A \to B \to C$ $n$ $m$ $s, t$ $s \to t$ ，求有多少条与之前矛盾（包括本身不合法）。

Solution

$P_i$ $P_{i, A}, P_{i, B}, P_{i, C}$ 然后从意义上处理即可，同样类似于 2-SAT 的思想。

Code


xxxxxxxxxx
91
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
// #define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define SON(i, x) (i + N * x)
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N, M;
29
int ans(0);
30

31
class UnionFind{
32
private:
33
    int fa[210000];
34
public:
35
    UnionFind(void){for(int i = 1; i <= 201000; ++i)fa[i] = i;}
36
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
37
    void Union(int s, int t){
38
        int fs = Find(s), ft = Find(t);
39
        if(fs == ft)return;
40
        fa[fs] = ft;
41
    }
42
}uf;
43

44
int main(){
45
    N = read(), M = read();
46
    while(M--){
47
        int opt = read(), s = read(), t = read();
48
        if(s > N || t > N){++ans; continue;}
49
        if(opt == 1){
50
            if(
51
                uf.Find(SON(s, 0)) == uf.Find(SON(t, 1)) ||
52
                uf.Find(SON(s, 0)) == uf.Find(SON(t, 2)) ||
53
                uf.Find(SON(s, 1)) == uf.Find(SON(t, 0)) ||
54
                uf.Find(SON(s, 1)) == uf.Find(SON(t, 2)) ||
55
                uf.Find(SON(s, 2)) == uf.Find(SON(t, 0)) ||
56
                uf.Find(SON(s, 2)) == uf.Find(SON(t, 1))
57
            )++ans;
58
            else uf.Union(SON(s, 0), SON(t, 0)), uf.Union(SON(s, 1), SON(t, 1)), uf.Union(SON(s, 2), SON(t, 2));
59
        }else{
60
            if(s == t){++ans; continue;}
61
            if(
62
                uf.Find(SON(s, 0)) == uf.Find(SON(t, 0)) ||
63
                uf.Find(SON(s, 0)) == uf.Find(SON(t, 2)) ||
64
                uf.Find(SON(s, 1)) == uf.Find(SON(t, 1)) ||
65
                uf.Find(SON(s, 1)) == uf.Find(SON(t, 0)) ||
66
                uf.Find(SON(s, 2)) == uf.Find(SON(t, 2)) ||
67
                uf.Find(SON(s, 2)) == uf.Find(SON(t, 1))
68
            )++ans;
69
            else uf.Union(SON(s, 0), SON(t, 1)), uf.Union(SON(s, 1), SON(t, 2)), uf.Union(SON(s, 2), SON(t, 0));
70
        }
71
    }printf("%d\n", ans);
72

73
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
74
    return 0;
75
}
76

77
template < typename T >
78
inline T read(void){
79
    T ret(0);
80
    int flag(1);
81
    char c = getchar();
82
    while(c != '-' && !isdigit(c))c = getchar();
83
    if(c == '-')flag = -1, c = getchar();
84
    while(isdigit(c)){
85
        ret *= 10;
86
        ret += int(c - '0');
87
        c = getchar();
88
    }
89
    ret *= flag;
90
    return ret;
91
}

LG-P5787 二分图 /【模板】线段树分治

题面

$k$ $m$ $n$ 个点的图是否为二分图。

Solution

首先二分图可以通过扩展与并查集判断，同时并查集需要支持可撤销并进行按秩合并，对于询问进行线段树分治即可。

Code


xxxxxxxxxx
106
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template < typename T = int >
24
inline T read(void);
25

26
int N, M, K;
27

28
class UnionFind{
29
private:
30
    int fa[410000], siz[410000];
31
    struct Mdf{int s; int fs; int t; int sizt;};
32
    stack < Mdf > mdfs;
33
public:
34
    UnionFind(void){for(int i = 0; i <= 401000; ++i)fa[i] = i, siz[i] = 1;}
35
    auto GetTop(void){return mdfs.empty() ? Mdf() : mdfs.top();}
36
    int Find(int x){return x == fa[x] ? x : Find(fa[x]);}
37
    void Union(int s, int t){
38
        int fs = Find(s), ft = Find(t);
39
        if(siz[fs] > siz[ft])swap(fs, ft);
40
        if(fs == ft)return;
41
        mdfs.push(Mdf{fs, fa[fs], ft, siz[ft]});
42
        siz[ft] += siz[fs];
43
        fa[fs] = ft;
44
    }
45
    void Repeal(Mdf endp){
46
        while(!mdfs.empty() && (mdfs.top().s != endp.s || mdfs.top().t != endp.t))
47
            fa[mdfs.top().s] =mdfs.top().fs, siz[mdfs.top().t] = mdfs.top().sizt, mdfs.pop();
48
    }
49
}uf;
50

51
class SegTree{
52
private:
53
    struct Line{int s, t;};
54
    basic_string < Line > tr[110000 << 2];
55
    #define LS (p << 1)
56
    #define RS (LS | 1)
57
    #define MID ((gl + gr) >> 1)
58
public:
59
    void Insert(int l, int r, int s, int t, int p = 1, int gl = 0, int gr = K - 1){
60
        if(l <= gl && gr <= r)return tr[p] += Line{s, t}, void();
61
        if(l <= MID)Insert(l, r, s, t, LS, gl, MID);
62
        if(r >= MID + 1)Insert(l, r, s, t, RS, MID + 1, gr);
63
    }
64
    void dfs(int p = 1, int gl = 0, int gr = K - 1){
65
        bool legal(true);
66
        auto lst = uf.GetTop();
67
        for(auto line : tr[p]){
68
            int fs = uf.Find(line.s << 1), ft = uf.Find(line.t << 1);
69
            if(fs == ft){
70
                legal = false;
71
                for(int i = gl; i <= gr; ++i)printf("No\n");
72
                break;
73
            }uf.Union(line.s << 1, (line.t << 1) | 1), uf.Union((line.s << 1) | 1, line.t << 1);
74
        }
75
        if(legal){
76
            if(gl != gr)dfs(LS, gl, MID), dfs(RS, MID + 1, gr);
77
            else printf("Yes\n");
78
        }uf.Repeal(lst);
79
    }
80
}st;
81

82
int main(){
83
    N = read(), M = read(), K = read();
84
    while(M--){
85
        int s = read(), t = read(), l = read(), r = read() - 1;
86
        st.Insert(l, r, s, t);
87
    }st.dfs();
88
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
89
    return 0;
90
}
91

92
template < typename T >
93
inline T read(void){
94
    T ret(0);
95
    int flag(1);
96
    char c = getchar();
97
    while(c != '-' && !isdigit(c))c = getchar();
98
    if(c == '-')flag = -1, c = getchar();
99
    while(isdigit(c)){
100
        ret *= 10;
101
        ret += int(c - '0');
102
        c = getchar();
103
    }
104
    ret *= flag;
105
    return ret;
106
}

LG-P2627 [USACO11OPEN]Mowing the Lawn G

题面

$A_n$ $k$ 个。

Solution

$dp(i)$ $i$ 个数的最大值，有转移：

d p (i) = max {d p (j - 1) + \sum_{k = j + 1}^{i} E_{k}, j \in [i - k, i]}

预处理前缀和后有：

d p (i) = max {d p (j - 1) + s u m_{i} - s u m_{j}}

$sum_i$ 提出：

d p (i) = s u m_{i} + max {d p (j - 1) - s u m_{j}}

$k$ $dp(i - 1) - sum_i$ 即可。

$j = 0 : dp(0) - sum_0$ 的情况。

Code


xxxxxxxxxx
60
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template < typename T = int >
24
inline T read(void);
25

26
int N, K;
27
ll A[110000];
28
ll sum[110000];
29
ll dp[110000];
30
deque < pair < int, ll > > cur;
31

32
int main(){
33
    N = read(), K = read();
34
    for(int i = 1; i <= N; ++i)sum[i] = sum[i - 1] + (A[i] = read());
35
    cur.push_back({0, 0});
36
    for(int i = 1; i <= N; ++i){
37
        while(!cur.empty() && cur.front().first < i - K)cur.pop_front();
38
        while(!cur.empty() && cur.back().second < dp[i - 1] - sum[i])cur.pop_back();
39
        cur.push_back({i, dp[i - 1] - sum[i]});
40
        dp[i] = sum[i] + (cur.empty() ? 0 : cur.front().second);
41
    }printf("%lld\n", dp[N]);
42
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
43
    return 0;
44
}
45

46
template < typename T >
47
inline T read(void){
48
    T ret(0);
49
    int flag(1);
50
    char c = getchar();
51
    while(c != '-' && !isdigit(c))c = getchar();
52
    if(c == '-')flag = -1, c = getchar();
53
    while(isdigit(c)){
54
        ret *= 10;
55
        ret += int(c - '0');
56
        c = getchar();
57
    }
58
    ret *= flag;
59
    return ret;
60
}

LG-P4954 [USACO09OPEN]Tower of Hay G

题面

$n$ $w_i$ ，按序给定每个砖块，你需要按序将其搭高，必须满足上层的宽度不小于下层，且所有砖块都必须被使用。

Solution

$s_i$ $f(i)$ $i$ $g(i)$ $i$ $w_i$ $j$ $s_i - s_{j} \ge g(j)$ $f(i) = f(j) + 1, g(i) = s_i - s_j$ $s_i \ge s_j + g(j)$ $j$ $k \lt j$ $s_k + g(k) \ge s_j + g(j)$ $k$ 一定不优，可以直接忽略，以此维护递增的单调队列并转移即可。

Code


xxxxxxxxxx
65
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template < typename T = int >
24
inline T read(void);
25

26
int N;
27
int w[110000];
28
ll s[110000];
29
ll F[110000], G[110000];
30
deque < pair < int, ll > > cur;
31

32
int main(){
33
    N = read();
34
    for(int i = 1; i <= N; ++i)w[i] = read();
35
    reverse(w + 1, w + N + 1);
36
    for(int i = 1; i <= N; ++i)s[i] = s[i - 1] + w[i];
37
    cur.push_back({0, 0});
38
    for(int i = 1; i <= N; ++i){
39
        pair < int, ll > lst = {-1, -1ll};
40
        while(!cur.empty() && cur.front().second <= s[i])lst = cur.front(), cur.pop_front();
41
        if(~lst.first)cur.push_front(lst);
42
        F[i] = F[cur.empty() ? 0 : cur.front().first] + 1;
43
        G[i] = s[i] - s[cur.empty() ? 0 : cur.front().first];
44
        while(!cur.empty() && cur.back().second > s[i] + G[i])cur.pop_back();
45
        cur.push_back({i, s[i] + G[i]});
46
    }printf("%lld\n", F[N]);
47
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
48
    return 0;
49
}
50

51
template < typename T >
52
inline T read(void){
53
    T ret(0);
54
    int flag(1);
55
    char c = getchar();
56
    while(c != '-' && !isdigit(c))c = getchar();
57
    if(c == '-')flag = -1, c = getchar();
58
    while(isdigit(c)){
59
        ret *= 10;
60
        ret += int(c - '0');
61
        c = getchar();
62
    }
63
    ret *= flag;
64
    return ret;
65
}

UPD

update-2023_02_22 初稿