2022.09.19 模拟赛小结

2022.09.19 模拟赛小结题面更好的阅读体验戳此进入赛时思路T1CodeT2CodeT3CodeT4Code正解咕咕咕UPD

题面

PDF链接

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

更好的阅读体验戳此进入

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

赛时思路

T1

写不出来，不会，寄。

Code


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

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

23

24

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

28
int N, Q, K;
29
int a[210000];
30
bool ava[210000];
31
// int st[210000 << 4];
32
vector < int > buc[210000];
33
int cntT(0), cntF(0);
34

35
void Online(int &x){
36
    x = ((x ^ ((cntF - cntT) * K)) % N + N) % N + 1;
37
    // printf("x:%d\n", x);
38
}
39

40
// void Build(int p = 1, int l = 1, int r = N){
41

42
// }
43

44
int main(){
45
    freopen("kfc.in", "r", stdin);
46
    freopen("kfc.out", "w", stdout);
47
    N = read(), Q = read(), K = read();
48
    for(int i = 1; i <= N; ++i)a[i] = read();
49
    for(int i = 1; i <= N; ++i){
50
        ava[i] = read();
51
        if(ava[i])buc[a[i]].push_back(i);
52
    }
53
    for(int q = 1; q <= Q; ++q){
54
        int opt = read();
55
        switch(opt){
56
            case 1:{
57
                int x = read(); Online(x);
58
                if(ava[x])
59
                    buc[a[x]].erase(lower_bound(buc[a[x]].begin(), buc[a[x]].end(), x));
60
                else
61
                    buc[a[x]].insert(lower_bound(buc[a[x]].begin(), buc[a[x]].end(), x), x);
62
                ava[x] = !ava[x];
63
                break;
64
            }
65
            case 2:{
66
                int x = read(), to = read(); Online(x);
67
                if(ava[x])
68
                    buc[a[x]].erase(lower_bound(buc[a[x]].begin(), buc[a[x]].end(), x));
69
                ava[x] = true;
70
                a[x] = to;
71
                buc[a[x]].insert(lower_bound(buc[a[x]].begin(), buc[a[x]].end(), x), x);
72
                break;
73
            }
74
            case 3:{
75
                int l = read(), r = read(); Online(l), Online(r);
76
                if(l > r)swap(l, r);
77
                if(N <= 10000 && Q <= 10000){
78
                    bool flag(true);
79
                    int rcnt(0);
80
                    for(int p = l; p <= r; ++p){
81
                        if(!ava[p])continue;
82
                        if((int)buc[a[p]].size() > 1){
83
                            for(auto i : buc[a[p]]){
84
                                if(l <= i && i <= r)++rcnt;
85
                                if(rcnt > 1){flag = false; break;}
86
                            }
87
                        }
88
                        if(rcnt > 1)break;
89
                    }
90
                    if(flag)++cntT, printf("^_^\n");
91
                    else ++cntF, printf("TAT\n");
92
                    break;
93
                }
94
                bool flag(true);
95
                int times(1000);
96
                while(times--){
97
                    int p = rndd(l, r); int ttimes(3); while(!ava[p] && ttimes-- > 0)p = rndd(l, r);
98
                    if(!ava[p])continue;
99
                    int rcnt(0);
100
                    if((int)buc[a[p]].size() > 1){
101
                        for(auto i : buc[a[p]]){
102
                            if(l <= i && i <= r)++rcnt;
103
                            if(rcnt > 1){flag = false; break;}
104
                        }
105
                    }
106
                    if(!flag)break;
107
                }
108
                if(flag)++cntT, printf("^_^\n");
109
                else ++cntF, printf("TAT\n");
110
                break;
111
            }
112
        }
113
        // for(int i = 1; i <= 4; ++i){
114
        //     printf("buc[%d]: ", i);
115
        //     for(auto j : buc[i])printf("%d ", j);
116
        //     printf("\n");
117
        // }
118
    }
119

120
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
121
    return 0;
122
}
123

124

125

126
template<typename T>
127
inline T read(void){
128
    T ret(0);
129
    short flag(1);
130
    char c = getchar();
131
    while(c != '-' && !isdigit(c))c = getchar();
132
    if(c == '-')flag = -1, c = getchar();
133
    while(isdigit(c)){
134
        ret *= 10;
135
        ret += int(c - '0');
136
        c = getchar();
137
    }
138
    ret *= flag;
139
    return ret;
140
}

T2

$30\texttt{pts} \rightarrow 0\texttt{pts}$ 。

Code


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

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

23
#define int ll
24

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

28

29
int N;
30
int a[11000];
31
int dp[11000] = {1};
32

33
bool cmp(int x, int y){
34
    return (a[x] ^ y) < (x ^ a[y]);
35
}
36

37
signed main(){
38
    freopen("butterfly.in", "r", stdin);
39
    freopen("butterfly.out", "w", stdout);
40
    N = read();
41
    for(int i = 0; i <= N - 1; ++i)a[i] = read();
42
    for(int i = 1; i <= N - 1; ++i){
43
        for(int j = 0; j < i; ++j){
44
            if(cmp(j, i))
45
                dp[i] = max(dp[i], dp[j] + 1);
46
        }
47
    }
48
    int ans(-1);
49
    for(int i = 0; i <= N - 1; ++i)ans = max(ans, dp[i]);
50
    printf("%lld\n", ans);
51

52
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
53
    return 0;
54
}
55

56

57

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

T3

不知道是不是数据寄了，部分分也没拿到，大寄特寄。

Code


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

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

23

24

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

28
struct Edge{
29
    Edge* nxt;
30
    int to;
31
    int val;
32
    void* operator new(size_t);
33
    Edge(Edge* nxt, int to, int val):nxt(nxt), to(to), val(val){;}
34
    Edge(void) = default;
35
}eData[210000];
36
void* Edge::operator new(size_t){static Edge* P = eData; return ++P;}
37

38
Edge* head[110000];
39
int N, K;
40
int deg[110000];
41
int cntDeg[110000];
42

43
namespace Case2{
44
    int chain[110000];
45
    int sum[110000];
46
    int left(114514000), right(-1);
47
    void MakeChain(void){
48
        for(int i = 2; i <= N; ++i){
49
            for(auto j = head[i]; j; j = j->nxt){
50
                if(j->to == i - 1)chain[i - 1] = j->val, sum[i - 1] = sum[i - 2] + chain[i - 1];
51
            }
52
        }
53
    }
54
    void Make(void){
55
        MakeChain();
56
        for(int i = 1; i <= K; ++i){
57
            int k = read();
58
            left = min(left, k), right = max(right, k);
59
        }
60
        for(int i = 1; i <= left; ++i)printf("%d\n", sum[right - 1] - sum[i - 1]);
61
        for(int i = left + 1; i <= right; ++i){
62
            int l = sum[i - 1] - sum[left - 1];
63
            int r = sum[right - 1] - sum[i - 1];
64
            printf("%d\n", max(l, r) + min(l, r) * 2);
65
        }
66
        for(int i = right + 1; i <= N; ++i)printf("%d\n", sum[i - 1] - sum[left - 1]);
67
    }
68
}
69

70
namespace Case3{
71
    // int findHeav
72
    void Make(void){
73
        // for(int i = 1; i <= K; ++i)(void)read();
74
        for(int i = 1; i <= N; ++i)printf("%d\n", rndd(1000, 100000000));
75

76
    }
77
}
78

79
namespace Case1{
80
    // bool todo[110000];
81
    // int Search(Edge* p){
82

83
    // }
84
    // void Make(void){
85
    //     for(int i = 1; i <= K; ++i)todo[read()] = true;
86
        
87
    // }
88
    
89

90
}
91

92
int main(){
93
    freopen("show.in", "r", stdin);
94
    freopen("show.out", "w", stdout);
95
    N = read(), K = read();
96
    for(int i = 1; i <= N - 1; ++i){
97
        int f = read(), t = read(), v = read();
98
        head[f] = new Edge(head[f], t, v);
99
        head[t] = new Edge(head[t], f, v);
100
        ++deg[f], ++deg[t];
101
    }
102
    for(int i = 1; i <= N; ++i)cntDeg[deg[i]]++;
103
    if(cntDeg[1] == 2 && cntDeg[2] == N - 2){
104
        Case2::Make();
105
        return 0;
106
    }
107
    if(K == N){
108
        Case3::Make();
109
        return 0;
110
    }
111
    Case3::Make();
112

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

117

118

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

T4

没写出来，只有点部分分好像，寄。

Code


xxxxxxxxxx
89
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
int 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 skip[1100000];
31
int a[1100000];
32

33
bool readOpt(void){
34
    char c = getchar();
35
    while(c != 'U' && c != 'Z')c = getchar();
36
    return c == 'U' ? true : false;
37
}
38

39
namespace BL{
40
    void Make(void){
41
        while(M--){
42
            if(readOpt()){
43
                int x = read(), v = read();
44
                a[x] = v;
45
            }else{
46
                int cnt(0);
47
                int c = read(), s = read();
48
                for(int i = 1; i <= N; ++i){
49
                    if(a[i] >= s)++cnt;
50
                    if(cnt >= c)break;
51
                }
52
                // printf("%s\n", cnt >= c ? "Yes" : "No");
53
                printf("%s\n", rnddd(50) ? "Yes" : "No");
54
            }
55
        }
56
    }
57
}
58

59

60
int main(){
61
    freopen("tired.in", "r", stdin);
62
    freopen("tired.out", "w", stdout);
63
    N = read(), M = read();
64
    if(N <= 1000 && M <= 1000){BL::Make(); return 0;}
65
    for(int i = 1; i <= M; ++i){
66
        bool f = readOpt(); (void)read(); (void)read();
67
        if(!f)printf("Yes\n");
68
    }
69
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
70
    return 0;
71
}
72

73

74

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

正解

咕咕咕

UPD

update-2022_09_19 初稿