2022.09.21 模拟赛小结

题面

PDF链接

(这个链接只是为了自己方便找，页面设置权限了，不要尝试访问)

更好的阅读体验戳此进入

（建议您从上方链接进入我的个人网站查看此 Blog，在 Luogu 中图片会被墙掉，部分 Markdown 也会失效）

赛时思路

大寄特寄

是的这场模拟赛机房大佬基本都接近 ak 了，然后我直接 90pts。

T1

一道奇奇怪怪的题，推了很久感觉想到了什么但是好像又没想到什么，最开始还想着对于每个左括号记录匹配的右括号，或者反过来，但是赛时一直没想到具体怎么实现，然后就寄掉了，写了个不完全算暴力暴力，60pts。

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

9
/******************************
10
abbr
11

12
******************************/
13

14
using namespace std;
15

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

20
typedef unsigned int uint;
21
typedef unsigned long long unll;
22
typedef long long ll;
23

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

27
int N, M;
28
int stk[210000];
29

30
int main(){
31
    freopen("wood.in", "r", stdin);
32
    freopen("wood.out", "w", stdout);
33
    N = read(), M = read();
34
    stk[1] = -1, stk[N] = 1;
35
    while(M--){
36
        int opt = read();
37
        if(opt == 1){
38
            int x = read();
39
            char c = getchar(); while(c != 'X' && c != '(' && c != ')')c = getchar();
40
            stk[x] = c == 'X' ? 0 : (c == '(' ? -1 : 1);
41
        }else{
42
            int l = read(), r = read();
43
            stack < int > s;
44
            int cnt(0);
45
            for(int i = l; i <= r; ++i){
46
                if(stk[i] == -1 && s.empty())s.push(-1);
47
                if(stk[i] == 1 && !s.empty())++cnt, s.pop();
48
            }
49
            printf("%d\n", cnt);
50
        }
51
    }
52

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
    short 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
}

T2

这个确实不会，好像能想到一点方法或者部分分，但是最后都证伪了，然后这题就寄掉了。

T3

不会，尤其差比数列这玩意真心没印象了，如果最后不要求取模或许还能大力 float128 水过暴力分，取模的话基本就直接寄掉了。

T4

依然不会，能想到一些奇奇怪怪的性质但是没啥用，最后部分分跑路。

Code

xxxxxxxxxx
75
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

9
/******************************
10
abbr
11

12
******************************/
13

14
using namespace std;
15

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

20
typedef unsigned int uint;
21
typedef unsigned long long unll;
22
typedef long long ll;
23

24

25

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

29
int N, M;
30
int stk[210000];
31

32
int main(){
33
    freopen("wood.in", "r", stdin);
34
    freopen("wood.out", "w", stdout);
35
    N = read(), M = read();
36
    stk[1] = -1, stk[N] = 1;
37
    while(M--){
38
        int opt = read();
39
        if(opt == 1){
40
            int x = read();
41
            char c = getchar(); while(c != 'X' && c != '(' && c != ')')c = getchar();
42
            stk[x] = c == 'X' ? 0 : (c == '(' ? -1 : 1);
43
        }else{
44
            int l = read(), r = read();
45
            stack < int > s;
46
            int cnt(0);
47
            for(int i = l; i <= r; ++i){
48
                if(stk[i] == -1 && s.empty())s.push(-1);
49
                if(stk[i] == 1 && !s.empty())++cnt, s.pop();
50
            }
51
            printf("%d\n", cnt);
52
        }
53
    }
54

55
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
56
    return 0;
57
}
58

59

60

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

正解

T1

原题 LG-P3797 妖梦斩木棒。

维护一个奇怪的线段树，每个节点维护区间内已经形成几对合法括号以及左右第一个非 X 的符号是什么，合并的时候可以重载加号判断左右子区间是否可以合并为一个新的合法括号对，然后查询的时候可以直接合并线段树点的结构体，然后返回这个结构体，需要注意判断时的优先级问题。

xxxxxxxxxx
131
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

9
/******************************
10
abbr
11

12
******************************/
13

14
using namespace std;
15

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

20
typedef unsigned int uint;
21
typedef unsigned long long unll;
22
typedef long long ll;
23
typedef long double ld;
24

25

26

27
template<typename T = int>
28
inline T read(void);
29

30
int N, M;
31

32
struct Sec{
33
    int val;
34
    int l, r;
35
    Sec(int val, int l, int r):val(val), l(l), r(r){;}
36
    Sec(void) = default;
37
    Sec operator+(const Sec t){
38
        return Sec(
39
            this->val + t.val + (this->r == -1 && t.l == 1 ? 1 : 0),
40
            this->l ? this->l : t.l,
41
            t.r ? t.r : this->r
42
        );
43
    }
44
};
45

46
class SegTree{
47
    private:
48
        #define MID ((gl + gr) >> 1)
49
        #define LS (p << 1)
50
        #define RS (p << 1 | 1)
51
        Sec st[210000 << 4];
52
    public:
53
        void Pushup(int p){
54
            // st[p] = Sec(
55
            //     st[LS].val + st[RS].val + st[LS].r == -1 && st[RS].l == 1 ? 1 : 0,
56
            //     st[LS].l ? st[LS].l : st[RS].l,
57
            //     st[RS].r ? st[RS].r : st[LS].r,
58
            //     st[LS].pl ? st[LS].pl : st[RS].pl,
59
            //     st[RS].pr ? st[RS].pr : st[LS].pr
60
            // );
61
            st[p] = st[LS] + st[RS];
62
        }
63
        void Build(int p = 1, int gl = 1, int gr = N){
64
            if(gl == gr){
65
                st[p] =
66
                    gl == 1 ? Sec(0, -1, -1)
67
                            : (
68
                                gl == N ? Sec(0, 1, 1)
69
                                        : Sec(0, 0, 0)
70
                            );
71
                return;
72
            }
73
            Build(LS, gl, MID);
74
            Build(RS, MID + 1, gr);
75
            Pushup(p);
76
        }
77
        void Modify(int mp, int val, int p = 1, int gl = 1, int gr = N){
78
            if(gl == gr){
79
                st[p] = Sec(0, val, val);
80
                return;
81
            }
82
            if(mp <= MID)Modify(mp, val, LS, gl, MID);
83
            else Modify(mp, val, RS, MID + 1, gr);
84
            Pushup(p);
85
        }
86
        Sec Query(int l, int r, int p = 1, int gl = 1, int gr = N){
87
            if(l <= gl && gr <= r)return st[p];
88
            return
89
                (l <= MID ? Query(l, r, LS, gl, MID) : Sec(0, 0, 0)) +
90
                (r >= MID + 1 ?  Query(l, r, RS, MID + 1, gr) : Sec(0, 0, 0));
91
        }
92
}st;
93

94
int main(){
95
    // freopen("in.txt", "r", stdin);
96
    // freopen("out.txt", "w", stdout);
97
    N = read(), M = read();
98
    st.Build();
99
    while(M--){
100
        int opt = read();
101
        if(opt == 1){
102
            int x = read();
103
            char c = getchar(); while(c != 'X' && c != '(' && c != ')')c = getchar();
104
            st.Modify(x, c == 'X' ? 0 : (c == '(' ? -1 : 1));
105
        }else{
106
            int l = read(), r = read();
107
            printf("%d\n", st.Query(l, r).val);
108
        }
109
    }
110

111
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
112
    return 0;
113
}
114

115

116

117
template<typename T>
118
inline T read(void){
119
    T ret(0);
120
    short flag(1);
121
    char c = getchar();
122
    while(c != '-' && !isdigit(c))c = getchar();
123
    if(c == '-')flag = -1, c = getchar();
124
    while(isdigit(c)){
125
        ret *= 10;
126
        ret += int(c - '0');
127
        c = getchar();
128
    }
129
    ret *= flag;
130
    return ret;
131
}

T2

暂时咕咕咕，太多前置知识点需要补了。。。

T3

T4

UPD

update-2022_09_21 初稿