2022.08.31 模拟赛小结

题面

PDF链接

原题题包（计蒜客） 去掉了 T4，其余有部分改动

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

更好的阅读体验戳此进入

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

赛时思路

T1

一个很简单的...思维题？

一个区间有四种操作对应着区间升序、降序、翻转、对应位置交换，求最后序列的最小值位置。

关于对应位置交换的含义：4 l r k：依次对每个 i=l,l+1 , ⋯,r ，执行 swap(a[i], a[i+k])。保证 r + k ≤ n ,≥ 1。

很显然地想到维护最小值的位置，如果当前最小值位置在修改区间内，前两个操作分别代表变为首位和末位，第三个操作意味着将其从位置 $p$$p$ 变为 $l+r-p$$l + r - p$ 第四个操作需要一些简单的思考，显然考虑位置 $p$$p$ 在交换的两个区间内时，可以考虑如果 $k>r-l$$k \gt r - l$ 则直接将 $p$$p$ 一次转移到对应位置，反之则可以考虑判断如果 $p$$p$ 在 $l+k$$l + k$ 以内，一定会被多次等距向右交换直到超出范围，否则则一定会被向回交换有且仅有一次，如此即可线性完成整个题。

需要注意此题数据量极大，建议用读入优化而非 scanf，当然一般比赛不会卡 scanf（虽然我们这次模拟赛卡了，幸亏我习惯用读入优化）。

因为题目较为简单所以赛时顺便打了个对拍，以防思路假掉。

Code:

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

8
using namespace std;
9

10
mt19937 rnd(random_device{}());
11
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
12

13
typedef unsigned int uint;
14
typedef unsigned long long unll;
15
typedef long long ll;
16

17

18

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

22
int arr[210000];
23
int N, Q;
24
int minpos(0), minn(INT_MAX);
25

26

27
int main(){
28
    // freopen("/home/jdoi/cpp/OI/in.txt", "r", stdin);
29
    // freopen("/home/jdoi/cpp/OI/out-std.txt", "w", stdout);
30
    freopen("resort.in", "r", stdin);
31
    freopen("resort.out", "w", stdout);
32
    int T = read();
33
    while(T--){
34
        minpos = 0; minn = INT_MAX;
35
        N = read(), Q = read();
36
        for(int i = 1; i <= N; ++i){
37
            arr[i] = read();
38
            if(arr[i] < minn){
39
                minn = arr[i];
40
                minpos = i;
41
            }
42
        }
43
        for(int q = 1; q <= Q; ++q){
44
            int opt = read();
45
            switch(opt){
46
                case 1:{
47
                    int l = read(), r = read();
48
                    if(l <= minpos && minpos <= r){
49
                        minpos = l;
50
                    }
51
                    break;
52
                }
53
                case 2:{
54
                    int l = read(), r = read();
55
                    if(l <= minpos && minpos <= r){
56
                        minpos = r;
57
                    }
58
                    break;
59
                }
60
                case 3:{
61
                    int l = read(), r = read();
62
                    if(l <= minpos && minpos <= r){
63
                        minpos = l + r - minpos;
64
                    }
65
                    break;
66
                }
67
                case 4:{
68
                    int l = read(), r = read(), k = read();
69
                    if(minpos < l || (minpos > r && minpos < l + k) || r + k < minpos)break;
70
                    for(int i = l; i <= r; ++i){
71
                        if(i == minpos)minpos = i + k;
72
                        else if(i + k == minpos){
73
                            minpos = i;
74
                            break;
75
                        }
76
                    }
77
                    
78
                }
79
            }
80
        }
81
        printf("%d\n", minpos);
82
    }
83

84
    // fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
85
    return 0;
86
}
87

88

89

90
template<typename T>
91
inline T read(void){
92
    T ret(0);
93
    short flag(1);
94
    char c = getchar();
95
    while(c != '-' && !isdigit(c))c = getchar();
96
    if(c == '-')flag = -1, c = getchar();
97
    while(isdigit(c)){
98
        ret *= 10;
99
        ret += int(c - '0');
100
        c = getchar();
101
    }
102
    ret *= flag;
103
    return ret;
104
}

暴力：

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

8
using namespace std;
9

10
mt19937 rnd(random_device{}());
11
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
12

13
typedef unsigned int uint;
14
typedef unsigned long long unll;
15
typedef long long ll;
16

17

18

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

22
int arr[210000];
23
int N, Q;
24
int minpos(0), minn(INT_MAX);
25

26

27
int main(){
28
    int T = read();
29
    while(T--){
30
        minpos = 0; minn = INT_MAX;
31
        N = read(), Q = read();
32
        for(int i = 1; i <= N; ++i){
33
            arr[i] = read();
34
            // if(arr[i] < minn){
35
            //     minn = arr[i];
36
            //     minpos = i;
37
            // }
38
        }
39
        for(int q = 1; q <= Q; ++q){
40
            int opt = read();
41
            switch(opt){
42
                case 1:{
43
                    int l = read(), r = read();
44
                    sort(arr + l, arr + r + 1, less<int>());
45
                    break;
46
                }
47
                case 2:{
48
                    int l = read(), r = read();
49
                    sort(arr + l, arr + r + 1, greater<int>());
50
                    break;
51
                }
52
                case 3:{
53
                    int l = read(), r = read();
54
                    reverse(arr + l, arr + r + 1);
55
                    break;
56
                }
57
                case 4:{
58
                    int l = read(), r = read(), k = read();
59
                    for(int i = l; i <= r; ++i)swap(arr[i], arr[i + k]);
60
                }
61
            }
62
        }
63
        for(int i = 1; i <= N; ++i){
64
            if(arr[i] < minn){
65
                minn = arr[i];
66
                minpos = i;
67
            }
68
        }
69
        printf("%d\n", minpos);
70
    }
71

72
    // fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
73
    return 0;
74
}
75

76

77

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

对拍：

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

8
using namespace std;
9

10
mt19937 rnd(random_device{}());
11
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
12

13
typedef unsigned int uint;
14
typedef unsigned long long unll;
15
typedef long long ll;
16

17

18

19
template<typename T = int>
20
inline T read(void);
21
int N, Q;
22
void BuildVal(void){
23
    freopen("/home/jdoi/cpp/OI/in.txt", "w", stdout);
24
    int T = rndd(1, 10);
25
    printf("%d\n", T);
26
    while(T--){
27
        N = rndd(3, 10000), Q = rndd(1, 10000);
28
        printf("%d %d\n", N, Q);
29
        for(int i = 1; i <= N; ++i)printf("%d%c", rndd(1, 100000000), i == N ? '\n' : ' ');
30
        for(int q = 1; q <= Q; ++q){
31
            int opt = rndd(1, 4);
32
            int l = rndd(1, N - 2);
33
            int r = rndd(l + 1, N - 1);
34
            printf("%d %d %d", opt, l, r);
35
            if(opt == 4){
36
                int k = rndd(1, N - r);
37
                printf(" %d\n", k);
38
            }else{
39
                printf("\n");
40
            }
41
            fflush(stdout);
42
        }
43
    }
44
    fflush(stdout);
45
}
46

47
int main(){
48
    // BuildVal();
49
    while(true){
50
        BuildVal();
51
        freopen("/home/jdoi/cpp/OI/log.txt", "a", stdout);
52
        // fprintf(stderr, "Caling std...\n");
53
        system("/home/jdoi/cpp/OI/std < /home/jdoi/cpp/OI/in.txt > /home/jdoi/cpp/OI/out-std.txt");
54
        // fprintf(stderr, "Caling bl...\n");
55
        system("/home/jdoi/cpp/OI/bl < /home/jdoi/cpp/OI/in.txt > /home/jdoi/cpp/OI/out-bl.txt");
56
        fflush(stdout);
57
        if(!system("diff /home/jdoi/cpp/OI/out-bl.txt /home/jdoi/cpp/OI/out-std.txt")){
58
            fflush(stdout);
59
            fprintf(stderr, "Compare Successful! Which N = %d, Q = %d\n", N, Q);
60
        }else{
61
            fprintf(stderr, "Wrong! Which N = %d, Q = %d\n", N, Q);
62
            break;
63
        }
64
    }
65
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
66
    return 0;
67
}
68

69

70

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

T2

咕咕咕

T3

咕咕咕

正解

咕咕咕

UPD

update-2022_8_31 初稿