2023.02.17 模拟赛小结

更好的阅读体验戳此进入

赛时思路

T1

有一道类似的 “原题”：LG-P3411 序列变换。

给定排列 $A_n$$A_n$，每次操作可以将任一元素丢到排列头或尾，最小化操作次数，输出最小值并输出任意方案。

签到题，考虑维护数值上连续但位置可以单调不连续的最长上升子序列，简单 DP 即可，方案处理平凡。

对于 “原题” 区别就是序列改为排列，离散化一下处理一下相同的即可。假了，这东西不能 DP，错误性显然，考虑单调队列，正解放在后文。

Code

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

24

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

28
int N;
29
int A[110000];
30
int pos[110000];
31
// bitset < 110000 > vis;
32
int dp[110000];
33
int mx(0), mxv(-1);
34

35
int main(){
36
    freopen("sort.in", "r", stdin);
37
    freopen("sort.out", "w", stdout);
38
    N = read();
39
    for(int i = 1; i <= N; ++i)pos[A[i] = read()] = i;
40
    for(int i = 1; i <= N; ++i){
41
        dp[A[i]] = dp[A[i] - 1] + 1;
42
        if(dp[A[i]] > mx)mx = dp[A[i]], mxv = A[i];
43
    }
44
    int lim1 = mxv - mx + 1, lim2 = mxv;
45
    printf("%d\n", N - mx);
46
    for(int i = lim1 - 1; i; --i)printf("%d 0\n", i);
47
    for(int i = lim2 + 1; i <= N; ++i)printf("%d 1\n", i);
48
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
49
    return 0;
50
}
51

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

T2

原题 LG-P3603 雪辉。

给定 $n$$n$ 个点的树，存在点权，多次询问每次给定多对点分别表示一条树链，求所有树链中有多少不同点权，及其点权的 $\mathrm{mex}$$\operatorname{mex}$。强制在线。

首先看到计算不同点权和求 $\mathrm{mex}$$\operatorname{mex}$ 且值域不大，自然想到 bitset，当我们求得答案的 bitset，我们只需要调用 count() 即可获得点权种类数，将其取反后，调用 _Find_first() 即可获得 $\mathrm{mex}$$\operatorname{mex}$。且上述所有操作均会除去一个 bitset 特有的，$w$$w$ 的复杂度。

这里的 $w$$w$ 根据编译器版本一般为 $32$$32$ 或 $64$$64$，且这里记作 $w$$w$ 而不是 $\omega$$\omega$ 是因为个人认为理解为 word 较为合理。

考虑如何维护，首先提供一个十分显然的思路，对原树进行树剖，然后在线段树上每个节点均开一个 bitset 建树，令 $v$$v$ 表示点权，这样的复杂度显然是 $O({\displaystyle \frac{nv}{w}})$$O(\dfrac{nv}{w})$ 的，而对于每次询问，直接查询并强行合并，分析这样的复杂度：树剖有一只 $O(\log n)$$O(\log n)$，线段树上查询的节点数是 $O(\log n)$$O(\log n)$，每次合并需要 $O({\displaystyle \frac{v}{w}})$$O(\dfrac{v}{w})$，若共 $q$$q$ 次询问则最终复杂度 $O({\displaystyle \frac{qv{\log }^{2}n}{w}})$$O(\dfrac{qv\log^2 n}{w})$，显然无法通过，但是本题似乎限制较小，这样也可以通过。

考虑分析上述做法的空间复杂度，显然为 $O({\displaystyle \frac{nv}{w}})$$O(\dfrac{nv}{w})$，但是线段树一般有一个 $4$$4$ 的空间常数，简单计算发现精细实现后大致需要 $262413$$262413$，这样大致需要 1GiB，考虑优化，显然对于线段树的底层每个点仅维护了一个数，而倒数第二层每个点仅维护了两个数，于是不难想到我们将倒数这两层改为用 pair 维护即可，这样可以去掉 $131072+65536$$131072 + 65536$ 左右个 bitset 的空间复杂度，优化极大，空间冗余较多，实现平凡。

下面提供一个来自 @Zpair 的高妙思路，可以将复杂度去掉一只 $O(\log n)$$O(\log n)$，显然这样的复杂度就是理论正确的了。即考虑在树剖后每个重链上维护这整个重链的 bitset，同时类似上文维护线段树，对于每次询问中，所有整个重链的查询直接调用，容易证明残缺的重链查询最多有 $3$$3$ 次，可以认为是常数，故优化掉一只 $O(\log n)$$O(\log n)$，容易证明这样的复杂度在当前时空限制是可以通过的。同时若空间无法通过还可考虑对于所有点数小于 ${\displaystyle \frac{v}{w}}$$\dfrac{v}{w}$ 的直接用 basic_string 维护，这样可以更进一步地大幅优化空间。

当然这里因为前者虽然复杂度错误但常数不大可以通过，于是这里直接挂前者的代码了。

Code

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

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

13
using namespace std;
14

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

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

24
#define LIM (110000)
25

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

29
int N, Q, F;
30
struct Edge{
31
    Edge* nxt;
32
    int to;
33
    OPNEW;
34
}ed[LIM << 1];
35
ROPNEW;
36
Edge* head[LIM];
37
int val[LIM];
38
int lst(0);
39

40
int dep[LIM], hson[LIM], top[LIM], fa[LIM], siz[LIM], dfn[LIM], idx[LIM];
41

42
void dfs_pre(int p = 1, int fa = 0){
43
    ::fa[p] = fa, dep[p] = dep[fa] + 1, siz[p] = 1;
44
    for(auto i = head[p]; i; i = i->nxt){
45
        if(SON == fa)continue;
46
        dfs_pre(SON, p);
47
        siz[p] += siz[SON];
48
        if(siz[SON] > siz[hson[p]])hson[p] = SON;
49
    }
50
}
51
void dfs_make(int p = 1, int top = 1){
52
    static int cdfn(0);
53
    dfn[p] = ++cdfn, idx[cdfn] = p;
54
    ::top[p] = top;
55
    if(hson[p])dfs_make(hson[p], top);
56
    for(auto i = head[p]; i; i = i->nxt){
57
        if(SON == fa[p] || SON == hson[p])continue;
58
        dfs_make(SON, SON);
59
    }
60
}
61

62
class SegTree{
63
private:
64
    //sum is 262143
65
    bitset < 30010 > tr[120000];
66
    pair < int, int > base[LIM << 2];
67
    #define LS (p << 1)
68
    #define RS (LS | 1)
69
    #define MID ((gl + gr) >> 1)
70
public:
71
    void Pushup(int p, int gl, int gr){
72
        if(gr - gl + 1 <= 2)return;
73
        if(MID - gl + 1 == 1)tr[p][base[LS].first] = true;
74
        else if(MID - gl + 1 == 2)tr[p][base[LS].first] = tr[p][base[LS].second] = true;
75
        else tr[p] |= tr[LS];
76
        if(gr - (MID + 1) + 1 == 1)tr[p][base[RS].first] = true;
77
        else if(gr - (MID + 1) + 1 == 2)tr[p][base[RS].first] = tr[p][base[RS].second] = true;
78
        else tr[p] |= tr[RS];
79
    }
80
    void Build(int p = 1, int gl = 1, int gr = N){
81
        if(gl == gr)return base[p] = {val[idx[gl = gr]], -1}, void();
82
        if(gr - gl + 1 == 2)base[p] = {val[idx[gl]], val[idx[gr]]};
83
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
84
        Pushup(p, gl, gr);
85
    }
86
    auto Query(int l, int r, int p = 1, int gl = 1, int gr = N){
87
        bitset < 30010 > ret; ret.reset();
88
        if(l <= gl && gr <= r){
89
            if(gl == gr){ret[base[p].first] = true; return ret;}
90
            if(gr - gl + 1 == 2){ret[base[p].first] = ret[base[p].second] = true; return ret;}
91
            return tr[p];
92
        }
93
        if(l <= MID)ret |= Query(l, r, LS, gl, MID);
94
        if(r >= MID + 1)ret |= Query(l, r, RS, MID + 1, gr);
95
        return ret;
96
    }
97
}st;
98

99
auto Query(int s, int t){
100
    bitset < 30010 > ret; ret.reset();
101
    while(top[s] != top[t]){
102
        if(dep[top[s]] < dep[top[t]])swap(s, t);
103
        ret |= st.Query(dfn[top[s]], dfn[s]);
104
        s = fa[top[s]];
105
    }if(dep[s] < dep[t])swap(s, t);
106
    ret |= st.Query(dfn[t], dfn[s]);
107
    return ret;
108
}
109

110
int main(){
111
    N = read(), Q = read(), F = read();
112
    for(int i = 1; i <= N; ++i)val[i] = read();
113
    for(int i = 1; i <= N - 1; ++i){
114
        int s = read(), t = read();
115
        head[s] = new Edge{head[s], t};
116
        head[t] = new Edge{head[t], s};
117
    }dfs_pre(), dfs_make();
118
    st.Build();
119
    while(Q--){
120
        int M = read();
121
        bitset < 30010 > ans; ans.reset();
122
        for(int i = 1; i <= M; ++i){
123
            int s = read() ^ (lst * F), t = read() ^ (lst * F);
124
            ans |= Query(s, t);
125
        }
126
        int ans1 = ans.count(), ans2 = (~ans)._Find_first();
127
        lst = ans1 + ans2;
128
        printf("%d %d\n", ans1, ans2);
129
    }
130
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
131
    return 0;
132
}
133

134
template < typename T >
135
inline T read(void){
136
    T ret(0);
137
    int flag(1);
138
    char c = getchar();
139
    while(c != '-' && !isdigit(c))c = getchar();
140
    if(c == '-')flag = -1, c = getchar();
141
    while(isdigit(c)){
142
        ret *= 10;
143
        ret += int(c - '0');
144
        c = getchar();
145
    }
146
    ret *= flag;
147
    return ret;
148
}

T3

题意懒得写了，一道奇怪题，暴力思路容易想到，正解大概是要用到一点智慧，不太喜欢这道题。

但是该说不说，这题数据真的水，常数不是大的离谱的暴力直接过了 $80\mathtt{\text{pts}}$$80\texttt{pts}$。

Code

xxxxxxxxxx
94
1
/*
2
2
3
5 1 49
4
8
5
2
6
1
7
7
8
9
9
5 1 64
10
8
11
2
12
1
13
7
14
9
15
*/
16
#define _USE_MATH_DEFINES
17
#include <bits/stdc++.h>
18

19
#define PI M_PI
20
#define E M_E
21
#define npt nullptr
22
#define SON i->to
23
#define OPNEW void* operator new(size_t)
24
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
25
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
26

27
using namespace std;
28

29
mt19937 rnd(random_device{}());
30
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
31
bool rnddd(int x){return rndd(1, 100) <= x;}
32

33
typedef unsigned int uint;
34
typedef unsigned long long unll;
35
typedef long long ll;
36
typedef long double ld;
37

38

39

40
template < typename T = int >
41
inline T read(void);
42

43
int N, M; ll K;
44
ll A[510000];
45
int ans(0);
46
// deque < ll > q1, q2;
47
// basic_string < ll > tmp;
48

49
int main(){
50
    freopen("cont.in", "r", stdin);
51
    freopen("cont.out", "w", stdout);
52
    int T = read();
53
    while(T--){
54
        // q1.clear(), q2.clear(), tmp.clear();
55
        ans = 0;
56
        N = read(), M = read(), K = read < ll >();
57
        for(int i = 1; i <= N; ++i)A[i] = read();
58
        int cur(1);
59
        basic_string < ll > vals;
60
        while(cur <= N){
61
            ++ans;
62
            vals.clear();
63
            vals += A[cur];
64
            // tmp += A[cur];
65
            for(int i = cur + 1; i <= N; ++i){
66
                vals.insert(lower_bound(vals.begin(), vals.end(), A[i]), A[i]);
67
                ll sum(0);
68
                for(int l = 1, r = vals.size(), c = 1; l <= r && c <= M; ++l, --r, ++c)
69
                    sum += (vals.at(r - 1) - vals.at(l - 1)) * (vals.at(r - 1) - vals.at(l - 1));
70
                if(sum > K)break;
71
                cur = i;
72
            }++cur;
73
        }printf("%d\n", ans);
74
    }
75
    
76
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
77
    return 0;
78
}
79

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

正解

T1

我们思考一下要找的序列的本质，整个序列需要保证不降，且对于值域为 $[l,r]$$[l, r]$，所有值域在 $[l+1,r-1]$$[l + 1, r - 1]$ 的元素都需要完全在队列内。

考虑维护，不难想到记录每个数的每个位置，当我们插一个数时，枚举插入数量，或者说最大的插入位置，当插入该位置的时候需要将单调队列末尾所有位置在此之后的都弹出，而当弹出一个值的时候，因为偶我们要将当前数插入，所以弹出的值一定会被删得不完全，所以全部不大于那个数得都要丢掉，以此处理一下即可。

Code

xxxxxxxxxx
63
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 A[1100000];
28
basic_string < int > vals[1100000];
29
int mx(0);
30

31
int main(){
32
    N = read();
33
    for(int i = 1; i <= N; ++i)vals[A[i] = read()] += i;
34
    deque < int > cur;
35
    for(int i = 1; i <= 1000000; ++i){
36
        for(int j = vals[i].size(); j >= 1; --j){
37
            int v = vals[i].at(j - 1);
38
            while(!cur.empty() && cur.back() > v){
39
                while(!cur.empty() && A[cur.front()] < A[cur.back()])cur.pop_front();
40
                cur.pop_back();
41
            }mx = max(mx, (int)cur.size() + (int)vals[i].size() - j + 1);
42
        }
43
        for(int j = 1; j <= (int)vals[i].size(); ++j)cur.emplace_back(vals[i].at(j - 1));
44
    }printf("%d\n", N - mx);
45
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
46
    return 0;
47
}
48

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

T2

正解上文写过了（值得一提的是出题人造数据的时候没加强制在线锅掉了，导致大多数人都爆零。。

UPD

update-2023_02_17 初稿