2022.10.14 模拟赛小结

大概是相对来讲补的比较全的一场了。。。

题面PDF链接

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

更好的阅读体验戳此进入

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

赛时思路

T1

排列 $A_n$$A_n$ 种进行若干次操作，每次删去相邻两个数较大的那个，求最终可能得到的序列数量

原题 LG-P7972 [KSN2021] Self Permutation

大概就是想到了一些性质（不过没用），想到了一些 DP 状态（然后没转移出来），总之最后的最后推了一个来小时，啥也没推出来，只能想到十分 nt 的 $O(n!)$$O(n!)$ 做法，直接爆零，我是 fw。

T2

对于正整数序列 $A_n$$A_n$，每次求区间 $[l,r]$$\left[ l, r \right]$ 内值域在 $[a,b]$$\left[ a, b \right]$ 的数和数值个数。

原题 LG-P4396 [AHOI2013]作业

能依稀感觉有点像莫队但是依然不会，然后也没想到值域分块，最后糊了个暴力上去，$O(nm)$$O(nm)$ 感觉好像也能过？不过最后好像是数据锅了还是怎么，总之最后 LemonLime 上爆零了。

Code

xxxxxxxxxx
80
1
#define USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
using namespace std;
5

6
mt19937 rnd(random_device{}());
7
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
8
bool rnddd(int x){return rndd(1, 100) <= x;}
9

10
#define SON i->to
11
#define OPNEW void* operator new(size_t)
12
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
13

14
typedef long long ll;
15
typedef unsigned long long unll;
16
typedef unsigned int uint;
17
typedef long double ld;
18

19
template < typename T = int >
20
T read(void);
21

22
int N, M;
23
int a[110000];
24
// bool vis[110000];
25
bitset < 101000 > vis;
26
// int buc100[1100][110000];
27
// vector < int > arr;
28
int main(){
29
    freopen("interval.in", "r", stdin);
30
    freopen("interval.out", "w", stdout);
31
    N = read(), M = read();
32
    for(int i = 1; i <= N; ++i)a[i] = read();
33
    // sort(arr.begin(), arr.end());
34
    // for(int i = 1; i <= N; ++i)a[i] = distance(arr.begin(), lower_bound(arr.begin(), arr.end(), a[i])) + 1;
35
    // for()
36
    if(M <= 1000){
37
        while(M--){
38
            int l = read(), r = read(), x = read(), y = read();
39
            int ans1(0), ans2(0);
40
            vis.reset();
41
            for(int i = l; i <= r; ++i){
42
                if(x <= a[i] && a[i] <= y){
43
                    ++ans1;
44
                    if(!vis[a[i]])vis.set(a[i]), ++ans2;
45
                }
46
            }
47
            printf("%d %d\n", ans1, ans2);
48
        }
49
        return 0;
50
    }
51
    if(N <= 1000){
52
        while(M--){
53
            int l = read(), r = read(), x = read(), y = read();
54
            int ans1(0);
55
            vector < int > tmp;
56
            for(int i = l; i <= r; ++i)
57
                if(x <= a[i] && a[i] <= y)++ans1, tmp.push_back(a[i]);
58
            auto endpos = unique(tmp.begin(), tmp.end());
59
            printf("%d %d\n", ans1, (int)distance(tmp.begin(), endpos));
60
        }
61
        return 0;
62
    }
63

64
    return 0;
65
}
66

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

T3

构造一棵有 $2n$$2n$ 节点的树，对于节点 $i$$i$ 和 $i+n$$i + n$ 记值为 $i$$i$，要求满足任意 $i$$i$ 和 $i+n$$i + n$ 之间的路径的值异或起来为 $i$$i$。

原题 AT5140 [AGC035C] Skolem XOR Tree

阴间构造，只推出来了 $2^t$$2^t$ 的数是无解的，不过没啥用，puts("No") 也能过。

总之最后手动构造的 $1-10$$1-10$ 过了，然后有两个 No 过了，成为了本场所有题里唯一的 $40\mathtt{\text{pts}}$$40\texttt{pts}$。

Code

xxxxxxxxxx
95
1
#define USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
using namespace std;
5

6
mt19937 rnd(random_device{}());
7
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
8
bool rnddd(int x){return rndd(1, 100) <= x;}
9

10
#define SON i->to
11
#define OPNEW void* operator new(size_t)
12
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
13

14
typedef long long ll;
15
typedef unsigned long long unll;
16
typedef unsigned int uint;
17
typedef long double ld;
18

19
template < typename T = int >
20
T read(void);
21

22
bool is2k[110000];
23

24
int main(){
25
    freopen("xortree.in", "r", stdin);
26
    freopen("xortree.out", "w", stdout);
27
    int N = read();
28
    int cur(1);
29
    while(cur <= 101000)is2k[cur] = true, cur <<= 1;
30
    if(is2k[N])printf("No\n"), exit(0);
31
    switch(N){
32
        // case 1:{
33
        //     printf("No\n");
34
        //     break;
35
        // }
36
        // case 2:{
37
        //     printf("No\n");
38
        //     break;
39
        // }
40
        case 3:{
41
            printf("Yes\n1 2\n2 3\n3 4\n4 5\n5 6\n");
42
            break;
43
        }
44
        // case 4:{
45
        //     printf("");
46
        //     break;
47
        // }
48
        case 5:{
49
            printf("Yes\n4 5\n5 1\n1 9\n9 10\n4 6\n6 8\n8 7\n6 2\n2 3\n");
50
            break;
51
        }
52
        case 6:{
53
            printf("Yes\n4 5\n5 1\n1 10\n4 7\n7 9\n9 8\n7 2\n2 3\n7 11\n10 6\n9 12\n");
54
            break;
55
        }
56
        case 7:{
57
            printf("Yes\n4 5\n5 1\n1 11\n4 8\n8 10\n10 9\n8 2\n2 3\n8 12\n11 6\n10 13\n12 14\n10 7\n");
58
            break;
59
        }
60
        // case 8:{
61
        //     printf("");
62
        //     break;
63
        // }
64
        case 9:{
65
            printf("10 8\n8 9\n10 18\n18 17\n10 5\n10 13\n13 15\n5 4\n4 1\n1 14\n1 2\n1 12\n14 7\n2 3\n12 11\n12 6\n12 16\n");
66
            break;
67
        }
68
        case 10:{
69
            printf("10 8\n8 9\n8 11\n11 19\n19 18\n11 5\n11 14\n5 4\n14 16\n4 1\n1 13\n1 2\n1 15\n15 7\n2 3\n3 12\n3 6\n3 17\n12 20\n");
70
            break;
71
        }
72
        default:{
73
            puts("No");
74
            break;
75
        }
76
    }
77

78
    
79
    return 0;
80
}
81

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

T4

原题 LG-P3750 [六省联考 2017] 分手是祝愿

期望题，不会，不过实际上不是很难，不是不可做的题。

正解

T1

把每个点建立一个区间，左右分别是第一个比它小的数的位置向中心移动一位，用单调栈从左到右从右到左各自维护一遍，令 $dp(i)$$dp(i)$ 表示以 $a_i$$a_i$ 结尾有多少种可能的最终排列，转移就是从 $j<i$$j \lt i$ 种找到所有 $i$$i$ 和 $j$$j$ 的区间有交的来求和，这个东西可以用树状数组维护一下，最终复杂度 $O(n\log n)$$O(n \log n)$，可以通过。

Code

xxxxxxxxxx
89
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 MOD (ll)(1e9 + 7)
29
#define MAXN 310000
30

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

34
int N;
35
int a[MAXN];
36
int lft[MAXN], rht[MAXN];
37
ll dp[MAXN];
38
ll ans(0);
39
stack < int > cur;
40

41
class TreeArray{
42
    private:
43
        int lim;
44
        ll tr[MAXN];
45
    public:
46
        void set(int lim){this->lim = lim;}
47
        int lowbit(int x){return x & -x;}
48
        void add(int x, ll v){while(x <= lim)tr[x] = (tr[x] + v) % MOD, x += lowbit(x);}
49
        ll query(int x){ll ret(0); while(x)ret = (ret + tr[x]) % MOD, x -= lowbit(x); return ret;}
50
}tr;
51

52
int main(){
53
    N = read();tr.set(N);
54
    for(int i = 1; i <= N; ++i)a[i] = read();
55
    for(int i = 1; i <= N; ++i){
56
        while(!cur.empty() && a[cur.top()] > a[i])rht[cur.top()] = i - 1, cur.pop();
57
        cur.push(i);
58
    }while(!cur.empty())rht[cur.top()] = N, cur.pop();
59
    for(int i = N; i >= 1; --i){
60
        while(!cur.empty() && a[cur.top()] > a[i])lft[cur.top()] = i + 1, cur.pop();
61
        cur.push(i);
62
    }while(!cur.empty())lft[cur.top()] = 1, cur.pop();
63
    tr.add(1, 1);
64
    for(int i = 1; i <= N; ++i){
65
        dp[i] = (tr.query(N) - tr.query(lft[i] - 1) + MOD) % MOD;
66
        tr.add(rht[i], dp[i]);
67
    }
68
    int cmn(INT_MAX);
69
    for(int i = N; i >= 1; --i){cmn = min(cmn, a[i]); if(cmn == a[i])ans = (ans + dp[i]) % MOD;}
70
    printf("%lld\n", ans);
71
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
72
    return 0;
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
}

T2

说实话这题确实不难，不过以前好像几乎没写过莫队，也没怎么写过值域分块，考场上是在是没想出来。

通过莫队维护区间 $[l,r]$$\left[ l, r \right]$ 的答案，具体的答案维护套一个值域分块，实现起来确实不难，细节也不是很多，挺板子的。

确实是没啥可说的。

Code

xxxxxxxxxx
126
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 BLOCK(x) (x / B + 1)
29
#define MAXN 110000
30

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

34
int N, M;
35
int B;
36
int maxV(-1);
37
int blk[MAXN], blkv[MAXN];
38
int a[MAXN];
39
int sum_pos[MAXN];
40
int sum_blk[MAXN], sum_blk_exist[MAXN];
41
pair < int, int > ans[MAXN];
42

43
struct Query{
44
    int l, r;
45
    int a, b;
46
    int idx;
47
    friend const bool operator < (const Query x, const Query y){
48
        if(blk[x.l] != blk[y.l])return x.l < y.l;
49
        return blk[x.l] & 1 ? x.r < y.r : x.r > y.r;
50
    }
51
};
52
vector < Query > Q;
53
pair < int, int > QueryBlk(int l, int r){
54
    if(l > maxV)return {0, 0};
55
    r = min(r, maxV);
56
    int bl = blkv[l], br = blkv[r];
57
    int ret1(0), ret2(0);
58
    if(bl == br){
59
        for(int i = l; i <= r; ++i)ret1 += sum_pos[i], ret2 += (bool)sum_pos[i];
60
        return {ret1, ret2};
61
    }
62
    if(blkv[l - 1] == bl){
63
        for(int i = l; blkv[i] == bl && i <= maxV; ++i)
64
            ret1 += sum_pos[i], ret2 += (bool)sum_pos[i];
65
        ++bl;
66
    }
67
    if(blkv[r + 1] == br){
68
        for(int i = r; blkv[i] == br && i >= 1; --i)
69
            ret1 += sum_pos[i], ret2 += (bool)sum_pos[i];
70
        --br;
71
    }
72
    for(int i = bl; i <= br; ++i)
73
        ret1 += sum_blk[i], ret2 += sum_blk_exist[i];
74
    return {ret1, ret2};
75
}
76
void add(int x){
77
    ++sum_blk[blkv[x]];
78
    if(++sum_pos[x] == 1)++sum_blk_exist[blkv[x]];
79
}
80
void del(int x){
81
    --sum_blk[blkv[x]];
82
    if(--sum_pos[x] == 0)--sum_blk_exist[blkv[x]];
83
}
84
int main(){
85
    N = read(), M = read();
86
    B = (double)N / sqrt(M) + 1;
87
    for(int i = 1; i <= N; ++i)
88
        a[i] = read(), blk[i] = i / B + 1, maxV = max(maxV, a[i]);
89
    B = sqrt(maxV) + 1;
90
    for(int i = 1; i <= maxV; ++i)
91
        blkv[i] = i / B + 1;
92
    for(int i = 1; i <= M; ++i){
93
        int l = read(), r = read(), a = read(), b = read();
94
        Q.emplace_back(Query{l, r, a, b, i});
95
    }sort(Q.begin(), Q.end());
96
    int gl(0), gr(0);
97
    for(auto ask : Q){
98
        while(gl > ask.l)add(a[--gl]);
99
        while(gr < ask.r)add(a[++gr]);
100
        while(gl < ask.l)del(a[gl++]);
101
        while(gr > ask.r)del(a[gr--]);
102
        ans[ask.idx] = QueryBlk(ask.a, ask.b);
103
    }
104
    for(int i = 1; i <= M; ++i)printf("%d %d\n", ans[i].first, ans[i].second);
105

106
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
107
    return 0;
108
}
109

110

111

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

T3

确实算是一道很神奇的构造。

首先显然若 $n=2^t$$n = 2^t$，或者说 $n=\mathrm{lowbit}(n)$$n = \operatorname{lowbit}(n)$，那么显然无解。

考虑到对于 $\mathrm{\forall }i\in [2,n-1]$$\forall i \in \left[ 2, n - 1 \right]$ 且 $2\mid i$$2 \mid i$，有 $i\oplus 1\oplus (i+1)\oplus i=i$$i \oplus 1 \oplus (i + 1) \oplus i = i$，对于 $i+1$$i + 1$ 同理，所以可以以 $1$$1$ 为根，在 $1$$1$ 上挂两个链，$i\to i+1$$i \rightarrow i + 1$，$i+1+n\to i+n$$i + 1 + n \rightarrow i + n$。然后考虑把 $1+n$$1 + n$ 挂在 $3$$3$ 或者 $2+n$$2 + n$ 上即可，这个很显然。

然后若 $2\mid n$$2 \mid n$，对于最后剩下的 $n$$n$，挂一条 $n\to \mathrm{lowbit}(n)+1+n\to 1\to n-\mathrm{lowbit}(n)\to n+n$$n \rightarrow \operatorname{lowbit}(n) + 1 + n \rightarrow 1 \rightarrow n - \operatorname{lowbit}(n) \rightarrow n + n$ 的链即可。

xxxxxxxxxx
67
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
template<typename T = int>
29
inline T read(void);
30

31
int lowbit(int x){return x & -x;}
32

33
int main(){
34
    int N = read();
35
    if(lowbit(N) == N)puts("No"), exit(0);
36
    puts("Yes");
37
    for(int i = 2; i <= N - 1; i += 2){
38
        printf("%d %d\n", 1, i);
39
        printf("%d %d\n", i, i + 1);
40
        printf("%d %d\n", 1, i + 1 + N);
41
        printf("%d %d\n", i + 1 + N, i + N);
42
    }
43
    printf("%d %d\n", 3, 1 + N);
44
    if(!(N & 1)){
45
        printf("%d %d\n", N, lowbit(N) + 1 + N);
46
        printf("%d %d\n", N - lowbit(N), N + N);
47
    }
48

49
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
50
    return 0;
51
}
52

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

T4

咕咕咕，不过这题还不错，加到题单里了，laterrrrrrrrrrrr 可以做一做。

UPD

update-2022_10_14 初稿