2022.10.17 模拟赛小结

一场 ACM 模拟赛

题面PDF链接

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

更好的阅读体验戳此进入

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

赛时思路

T1

对于 $n$$n$ 个正整数的序列 $a_n$$a_n$，给定 $k$$k$，每次操作选择大于 $k$$k$ 的 $a_i$$a_i$，使 $a_i\leftarrow a_i-1$$a_i \leftarrow a_i - 1$，然后会使 $a_{i-1}\leftarrow a_{i-1}+1$$a_{i - 1} \leftarrow a_{i - 1} + 1$ 或 $a_{i+1}\leftarrow a_{i+1}+1$$a_{i + 1} \leftarrow a_{i + 1} + 1$。求任意次操作后最大能选出多长的子串满足每个数都不小于 $k$$k$，$T$$T$ 组询问。

原题 LG-P3503 [POI2010]KLO-Blocks。

赛时没想出来，最后糊了一个乱搞上去，然后乱搞也寄了，直接 $0\mathtt{\text{pts}}$$0\texttt{pts}$。

一直在考虑维护把大于 $k$$k$ 的数推平然后补齐小于 $k$$k$ 的数，然后口糊证明了一下对于每一个大于 $k$$k$ 的数优先向右或向左一定不劣于左右各自推平一部分，不过这玩意依然是 $O(2^n)$$O(2^n)$ 的，然后设计了一个类似并查集的东西来维护向左向右的下一个未满足要求的数，然后常数也巨大。。

Code

xxxxxxxxxx
174
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
/******************************
12
abbr
13

14
******************************/
15

16
using namespace std;
17

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

22
typedef unsigned int uint;
23
typedef unsigned long long unll;
24
typedef long long ll;
25
typedef long double ld;
26

27
#define TIME_LIMIT ((double)clock() / CLOCKS_PER_SEC <= 0.9 / (double)M)
28

29
template<typename T = int>
30
inline T read(void);
31

32
int N, M;
33
int cnt;
34
int k;
35
int base[1100000], a[1100000];
36
int ans(0);
37
bool finished(false);
38

39
vector < int > high;
40

41
struct UnionFind{
42
    int fal[1100000], far[1100000];
43
    int FindL(int x){return fal[x] == x ? x : fal[x] = FindL(fal[x]);}
44
    int FindR(int x){return far[x] == x ? x : far[x] = FindR(far[x]);}
45
    void UnionL(int f, int s){fal[s] = FindL(f);}
46
    void UnionR(int f, int s){far[s] = FindR(f);}
47
    void reset(int N, int k){
48
        memset(fal, 0, sizeof(fal));
49
        memset(far, 0, sizeof(far));
50
        for(int i = 1; i <= N; ++i)
51
            if(a[i] < k)fal[i] = i;
52
            else if(a[i] > k)high.push_back(i), fal[i] = FindL(i - 1);
53
            else fal[i] = FindL(i - 1);
54
        for(int i = N; i >= 1; --i){
55
            if(a[i] < k)far[i] = i;
56
            else far[i] = FindR(i + 1);
57
        }
58
    }
59
}uf;
60

61
void dfs(int dep = 1){
62
    // printf("in dfs, dep = %d\n", dep);
63
    if(finished)return;
64
    if(!TIME_LIMIT)return finished = true, void();
65
    if(dep > (int)high.size()){
66
        int len(0);
67
        for(int i = 1; i <= N; ++i){
68
            if(a[i] >= k)++len;
69
            else len = 0;
70
        }
71
        ans = max(ans, len);
72
        return;
73
    }
74
    int p = high.at(dep - 1);
75
    vector < pair < int, int > > editA, editL, editR;
76
    if(rnddd(50)){
77
        int val = p - k;
78
        int cp = uf.FindR(p);
79
        while(cp && val > 0){
80
            editA.emplace_back(cp, a[cp]);
81
            editR.emplace_back(cp, uf.FindR(cp));
82
            val -= k - a[cp];
83
            a[cp] = k;
84
            int tcp = cp;
85
            if(val < 0)a[cp] += val;
86
            else cp = uf.FindR(cp + 1), uf.UnionR(cp, tcp);
87
        }
88
        cp = uf.FindL(p);
89
        while(cp && val > 0){
90
            editA.emplace_back(cp, a[cp]);
91
            editL.emplace_back(cp, uf.FindL(cp));
92
            val -= k - a[cp];
93
            a[cp] = k;
94
            int tcp = cp;
95
            if(val < 0)a[cp] += val;
96
            else cp = uf.FindL(cp - 1), uf.UnionL(cp, tcp);
97
        }
98
        if(val > 0){
99
            ans = N;
100
            finished = true;
101
            return;
102
        }
103
        dfs(dep + 1);
104
        for(auto i : editA)a[i.first] = i.second;
105
        for(auto i : editL)uf.fal[i.first] = i.second;
106
        for(auto i : editR)uf.far[i.first] = i.second;
107
    }else{
108
        int val = p - k;
109
        int cp = uf.FindL(p);
110
        while(cp && val > 0){
111
            editA.emplace_back(cp, a[cp]);
112
            editL.emplace_back(cp, uf.FindL(cp));
113
            val -= k - a[cp];
114
            a[cp] = k;
115
            int tcp = cp;
116
            if(val < 0)a[cp] += val;
117
            else cp = uf.FindL(cp - 1), uf.UnionL(cp, tcp);
118
        }
119
        cp = uf.FindR(p);
120
        while(cp && val > 0){
121
            editA.emplace_back(cp, a[cp]);
122
            editR.emplace_back(cp, uf.FindR(cp));
123
            val -= k - a[cp];
124
            a[cp] = k;
125
            int tcp = cp;
126
            if(val < 0)a[cp] += val;
127
            else cp = uf.FindR(cp + 1), uf.UnionR(cp, tcp);
128
        }
129
        if(val > 0){
130
            ans = N;
131
            finished = true;
132
            return;
133
        }
134
        dfs(dep + 1);
135
        for(auto i : editA)a[i.first] = i.second;
136
        for(auto i : editL)uf.fal[i.first] = i.second;
137
        for(auto i : editR)uf.far[i.first] = i.second;
138
    }
139

140
}
141
int main(){
142
    freopen("TOMO.in", "r", stdin);
143
    freopen("TOMO.out", "w", stdout);
144
    N = read(), M = read();
145
    for(int i = 1; i <= N; ++i)base[i] = read();
146
    while(M--){
147
        memcpy(a, base, sizeof(base));
148
        cnt = ans = finished = 0;
149
        high.clear();
150
        k = read();
151
        uf.reset(N, k);
152
        dfs();
153
        printf("%d\n", ans);
154
    }
155

156
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
157
    return 0;
158
}
159

160
template<typename T>
161
inline T read(void){
162
    T ret(0);
163
    short flag(1);
164
    char c = getchar();
165
    while(c != '-' && !isdigit(c))c = getchar();
166
    if(c == '-')flag = -1, c = getchar();
167
    while(isdigit(c)){
168
        ret *= 10;
169
        ret += int(c - '0');
170
        c = getchar();
171
    }
172
    ret *= flag;
173
    return ret;
174
}

T2

原题 AT5146 [AGC036C] GP 2。

写了个 DP，假了，爆零，寄。

T3

原题 CF840E In a Trap。

大概就是写了个暴力，然后数据比较奇怪，还多过了几个点。。最后本场唯一的 $60\mathtt{\text{pts}}$$60\texttt{pts}$。

Code

xxxxxxxxxx
112
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
/******************************
12
abbr
13

14
******************************/
15

16
using namespace std;
17

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

22
typedef unsigned int uint;
23
typedef unsigned long long unll;
24
typedef long long ll;
25
typedef long double ld;
26

27

28

29
template<typename T = int>
30
inline T read(void);
31

32
struct Edge{
33
    Edge* nxt;
34
    int to;
35
    OPNEW;
36
}ed[310000];
37
ROPNEW(ed);
38

39
Edge* head[150000];
40
int N, Q;
41
int val[150000];
42
int dep[150000];
43
int pre[150000];
44
void dfs(int p = 1, int fa = 0){
45
    dep[p] = dep[fa] + 1;
46
    pre[p] = fa;
47
    for(auto i = head[p]; i; i = i->nxt)
48
        if(SON != fa)dfs(SON, p);
49
}
50
int Make(int S, int T){
51
    int ret(-1);
52
    if(dep[S] >= dep[T]){
53
        int SS = S;
54
        while(T != SS){
55
            ret = max(ret, val[SS] ^ abs(dep[SS] - dep[S]));
56
            // printf("val: %d xor %d = %d\n", val[S], abs(dep[T] - dep[S]), val[S] ^ abs(dep[T] - dep[S]));
57
            SS = pre[SS];
58
        }ret = max(ret, val[SS] ^ abs(dep[SS] - dep[S]));
59
    }else{
60
        while(S != T){
61
            ret = max(ret, val[S] ^ abs(dep[T] - dep[S]));
62
            // printf("val: %d xor %d = %d\n", val[S], abs(dep[T] - dep[S]), val[S] ^ abs(dep[T] - dep[S]));
63
            T = pre[T];
64
        }ret = max(ret, val[S] ^ abs(dep[T] - dep[S]));
65
    }
66
    // int len = abs(dep[S] - dep[T]);
67
    // printf("len s = %d, t = %d, is %d\n", S, T, len);
68
    // if(dep[s] < dep[t])swap(s, t);
69
    // while(S != T){
70
    //     ret = max(ret, val[S] ^ abs(dep[T] - dep[S]));
71
    //     printf("val: %d xor %d = %d\n", val[S], abs(dep[T] - dep[S]), val[S] ^ abs(dep[T] - dep[S]));
72
    //     S = pre[S];
73
    // }ret = max(ret, val[S] ^ 0);
74
    return ret;
75
}
76

77
int main(){
78
    freopen("CP0A.in", "r", stdin);
79
    freopen("CP0A.out", "w", stdout);
80
    N = read(), Q = read();
81
    for(int i = 1; i <= N; ++i)val[i] = read();
82
    for(int i = 1; i <= N - 1; ++i){
83
        int s = read(), t = read();
84
        head[s] = new Edge{head[s], t};
85
        head[t] = new Edge{head[t], s};
86
    }dfs();
87
    while(Q--){
88
        int s = read(), t = read();
89
        printf("%d\n", Make(t, s));
90
    }
91

92
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
93
    return 0;
94
}
95

96

97

98
template<typename T>
99
inline T read(void){
100
    T ret(0);
101
    short flag(1);
102
    char c = getchar();
103
    while(c != '-' && !isdigit(c))c = getchar();
104
    if(c == '-')flag = -1, c = getchar();
105
    while(isdigit(c)){
106
        ret *= 10;
107
        ret += int(c - '0');
108
        c = getchar();
109
    }
110
    ret *= flag;
111
    return ret;
112
}

T4

原题 LG-P8386 [PA 2021] Od deski do deski。

不会，寄。

正解

T1

首先问题显然可以转化为，找一段最长的区间，满足区间的平均数大于等于 $k$$k$。然后再转化为把每个数减去 $k$$k$，然后要找最长的一段区间，满足区间加和大于 $0$$0$。再转化为前缀和后就是要找最长的一段 $s_j-s_i\ge 0$$s_j - s_i \ge 0$，显然 $O(n^2)$$O(n^2)$ 枚举会寄，考虑单调栈，对于左端点，显然若有 $i<j\wedge s_i\le s_j$$i \lt j \land s_i \le s_j$ 那么 $i$$i$ 一定优于 $j$$j$，或者说一定不会选择到 $j$$j$，证明显然。于是单调栈维护左端点，单调递减，右端点单调递增，这样可以对于每个左端点二分右端点，反之亦然，复杂度 $O(Qn\log n)$$O(Q n \log n)$ 不正确。考虑维护左端点的单调栈后，对于右端点从 $n$$n$ 向 $1$$1$ 枚举，若 $s_i\ge 0$$s_i \ge 0$ 那么 $[0,i]$$[0, i]$ 一定合法，否则考虑如果当前点符合右端点单调栈的规则，那么开始和左端点的单调栈相匹配，然后左端点出栈，并更新答案，显然这里出栈的左端点一定在后面不会再用到了。

Code

xxxxxxxxxx
84
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
/******************************
12
abbr
13

14
******************************/
15

16
using namespace std;
17
using namespace __gnu_pbds;
18

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

23
typedef unsigned int uint;
24
typedef unsigned long long unll;
25
typedef long long ll;
26
typedef long double ld;
27

28
#define int ll
29

30
template<typename T = int>
31
inline T read(void);
32

33
int N, Q;
34
int K;
35
int s[1100000];
36
stack < int > lft;
37
int ans(0);
38
void Solve(void){
39
    ans = 0;
40

41
    for(int i = 1; i <= N; ++i){
42
        s[i] -= K * i;
43
        if(lft.empty() || s[i] < s[lft.top()])lft.push(i);
44
    }
45
    // for(int i = 1; i <= N; ++i)printf("%d%c", s[i], i == N ? '\n' : ' ');
46
    int tpr(INT_MIN);
47
    for(int i = N; i >= 1; --i){
48
        if(s[i] >= 0)ans = max(ans, i);
49
        if(i == N || s[i] > tpr){
50
            while(!lft.empty() && s[i] - s[lft.top()] >= 0)
51
                ans = max(ans, i - lft.top()), lft.pop();
52
            tpr = s[i];
53
        }
54
    }
55
    for(int i = 1; i <= N; ++i)s[i] += K * i;
56
    while(!lft.empty())lft.pop();
57
}
58
signed main(){
59
    N = read(), Q = read();
60
    for(int i = 1; i <= N; ++i)s[i] = read() + s[i - 1];
61
    while(Q--){
62
        K = read();
63
        Solve();
64
        printf("%lld%c", ans, Q ? ' ' : '\n');
65
    }
66
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
67
    return 0;
68
}
69

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

T2

咕咕咕。

T3

咕咕咕。

T4

咕咕咕。

UPD

update-2022_10_17 初稿