2022.09.16 模拟赛小结

题面

PDF链接

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

更好的阅读体验戳此进入

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

赛时思路

T1

赛时写了个暴力 + 卡时 + 随机化 + 贪心的纯纯乱搞，Luogu 能过一大半的点，不过数据被 zpair 加强之后直接除了暴力分全部寄掉了。

Code

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

4
namespace input{
5
    int seed,lst=1;
6
    const int prime1=163337,prime2=998244353;
7
    void init(){
8
        scanf("%d",&seed);
9
    }
10
    int read(){
11
        //return lst=((lst*prime1+seed)%prime2+prime2)%prime2;
12
    }
13
}
14

15
#define PI M_PI
16
#define E M_E
17
#define npt nullptr
18
#define SON i->to
19

20
/******************************
21
abbr
22

23
******************************/
24

25
using namespace std;
26

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

31
typedef unsigned int uint;
32
typedef unsigned long long unll;
33
typedef long long ll;
34

35

36

37
template<typename T = int>
38
inline T read(void);
39

40
int a[6100000];
41
int N, D;
42
ll P;
43
namespace BL{
44
    int ans(0);
45
    int len(0);
46
    ll sum(0);
47
    deque < int > deq;
48
    int Make(void){
49
        for(int i = 1; i <= N - D + 1; ++i){
50
            len = 0;
51
            sum = 0;
52
            deq.clear();
53
            for(int j = 1; j <= N; ++j){
54
                ll val = (j >= i && j <= i + D - 1) ? 0 : a[j];
55
                while(!deq.empty() && sum + val > P)--len, sum -= deq.front(), deq.pop_front();
56
                if(sum + val <= P)deq.push_back(val), sum += val, ++len, ans = max(ans, len);
57
                // printf("%d ", len);
58
            }
59
            // printf("%d\n", ans);
60
        }
61
        return ans;
62
    }
63
}
64

65

66
int main(){
67
    // freopen("T1.in", "r", stdin);
68
    // freopen("T1.out", "w", stdout);
69
    N = read(); P = read<ll>(); D = read(); //input::init();
70
    for(int i = 1; i <= N; ++i)a[i] = read();
71
    if(N <= 1000){printf("%d\n", BL::Make()); return 0;}
72
    // printf("%d\n", BL::Make());
73
    int ans(0);
74
    ll cur(0);
75
    for(int i = 1; i <= D - 1; ++i)cur += a[i];
76
    ll maxx(-1), maxp;
77
    for(int i = 1; i <= N - D + 1; ++i){
78
        cur -= a[i - 1], cur += a[i + D - 1];
79
        if(cur > maxx){
80
            maxx = cur;
81
            maxp = i;
82
        }
83
    }
84
    // printf("%d\n", maxp);
85
    // for(int i = maxp; i <= maxp + D - 1; ++i)
86
    deque < int > deq;
87
    int len = 0;
88
    int sum = 0;
89
    deq.clear();
90
    for(int j = 1; j <= N; ++j){
91
        // printf("Caling p = %d\n", maxp);
92
        ll val = (j >= maxp && j <= maxp + D - 1) ? 0 : a[j];
93
        while(!deq.empty() && sum + val > P)--len, sum -= deq.front(), deq.pop_front();
94
        if(sum + val <= P)deq.push_back(val), sum += val, ++len, ans = max(ans, len);
95
        // printf("%d ", len);
96
    }
97
        int pos(0);
98
    while((double)clock() / CLOCKS_PER_SEC < 0.3){
99
        pos = 0;
100
        while(pos < 1 || pos > N - D + 1)pos = maxp - rndd(1, D - 1);
101
        // printf("Caling p = %d\n", pos);
102
        len = 0;
103
        sum = 0;
104
        deq.clear();
105
        for(int j = 1; j <= N; ++j){
106
            ll val = (j >= pos && j <= pos + D - 1) ? 0 : a[j];
107
            while(!deq.empty() && sum + val > P)--len, sum -= deq.front(), deq.pop_front();
108
            if(sum + val <= P)deq.push_back(val), sum += val, ++len, ans = max(ans, len);
109
            // printf("%d ", len);
110
        }
111
    }
112
    while((double)clock() / CLOCKS_PER_SEC < 0.5){
113
        pos = 0;
114
        while(pos < 1 || pos > N - D + 1)pos = int((double)maxp * ((double)rndd(1, 100) / 100) * (rnddd(50) ? 1 : -1));
115
        // printf("Caling p = %d\n", pos);
116
        len = 0;
117
        sum = 0;
118
        deq.clear();
119
        for(int j = 1; j <= N; ++j){
120
            ll val = (j >= pos && j <= pos + D - 1) ? 0 : a[j];
121
            while(!deq.empty() && sum + val > P)--len, sum -= deq.front(), deq.pop_front();
122
            if(sum + val <= P)deq.push_back(val), sum += val, ++len, ans = max(ans, len);
123
        }
124
    }
125
    while((double)clock() / CLOCKS_PER_SEC < 0.7){
126
        pos = rndd(1, N - D + 1);
127
        // printf("Caling p = %d\n", pos);
128
        len = 0;
129
        sum = 0;
130
        deq.clear();
131
        for(int j = 1; j <= N; ++j){
132
            ll val = (j >= pos && j <= pos + D - 1) ? 0 : a[j];
133
            while(!deq.empty() && sum + val > P)--len, sum -= deq.front(), deq.pop_front();
134
            if(sum + val <= P)deq.push_back(val), sum += val, ++len, ans = max(ans, len);
135
            // printf("%d ", len);
136
        }
137
    }
138
    printf("%d\n", ans);
139

140
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
141
    return 0;
142
}
143

144

145

146
template<typename T>
147
inline T read(void){
148
    T ret(0);
149
    short flag(1);
150
    char c = getchar();
151
    while(c != '-' && !isdigit(c))c = getchar();
152
    if(c == '-')flag = -1, c = getchar();
153
    while(isdigit(c)){
154
        ret *= 10;
155
        ret += int(c - '0');
156
        c = getchar();
157
    }
158
    ret *= flag;
159
    return ret;
160
}

T2

写了个奇怪的暴力，写挂了，爆零。

Code

xxxxxxxxxx
70
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
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
25
char buf[1<<20],*p1=buf,*p2=buf;
26
inline void read(int &r){
27
    r=0;bool w=0;char ch=getchar();
28
    while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
29
    while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
30
    r=w?-r:r;
31
}
32
int N, Q;
33
int a[51000];
34
namespace BL{
35
    int lbuc[51000], rbuc[51000];
36
    int sum[51000];
37
    void Init(void){
38
        memset(sum, 0, sizeof(sum));
39
        for(int i = 1; i <= N; ++i)sum[i] = sum[i - 1] + a[i];
40
        for(int i = 1; i <= N; ++i){
41
            for(int j = i; j <= N; ++j){
42
                int val = sum[j] - sum[i - 1];
43
                lbuc[val] = i, rbuc[val] = j;
44
            }
45
        }
46
    }
47
    void Make(void){
48
        for(int i = 1; i <= Q; ++i){
49
            int q;
50
            read(q);
51
            // scanf("%d", &q);
52
            printf("%d %d\n", lbuc[q] ? lbuc[q] : -1, rbuc[q] ? rbuc[q] : -1);
53
        }
54
    }
55
}
56

57
int main(){
58
    freopen("T2.in", "r", stdin);
59
    freopen("T2.out", "w", stdout);
60
    read(N), read(Q);
61
    // scanf("%d%d", &N, &Q);
62
    for(int i = 1; i <= N; ++i)read(a[i]), --a[i];
63
    if(N <= 20000){BL::Init(); BL::Make(); return 0;}
64
    
65

66
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
67
    return 0;
68
}
69

70

T3

很乱搞的一个暴力，我以为能过不少点，结果全被卡掉了，拿了暴力分跑路。

Code

xxxxxxxxxx
84
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3
#include <unordered_map>
4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8

9
#define MOD (1000000007ll)
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

21
typedef unsigned int uint;
22
typedef unsigned long long unll;
23
typedef long long ll;
24

25

26

27
template<typename T = ll>
28
inline T read(void);
29

30
map < pair < int, int >, ll > add;
31

32
int N, M;
33
ll a[210000];
34
ll sum[210000];
35
int main(){
36
    freopen("T3.in", "r", stdin);
37
    freopen("T3.out", "w", stdout);
38
    N = read(), M = read();
39
    for(int i = 1; i <= N; ++i)a[i] = read() % MOD, sum[i] = (sum[i - 1] + a[i]) % MOD;
40

41
    while(M--){
42
        int opt = read();
43
        if(opt == 1){
44
            int x = read(), y = read(), val = read() % MOD;
45
            auto tmp = add.find(make_pair(x, y));
46
            if(tmp == add.end())add.insert(make_pair(make_pair(x, y), val));
47
            else tmp->second = (tmp->second + val) % MOD;
48
        }else{
49
            int l = read(), r = read();
50
            ll ans = (sum[r] - sum[l - 1] + MOD) % MOD;
51
            for(auto i : add){
52
                int tl = l - i.first.second, tr = r - i.first.second;
53
                if(tr < 0)continue;
54
                int by = max(tl / i.first.first, 0);
55
                tl -= by * i.first.first;
56
                tr -= by * i.first.first;
57
                if(tl <= 0)ans = (ans + i.second) % MOD;
58
                ans = (ans + int(tr / i.first.first) * i.second % MOD) % MOD;
59
            }
60
            printf("%lld\n", ans % MOD);
61
        }
62
    }
63

64
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
65
    return 0;
66
}
67

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
}

T4

暴力跑路。

Code

xxxxxxxxxx
78
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;
29
//x < y => -1, x > y => 1
30
vector < tuple < int, int, int > > relations;
31
int ans(0);
32
int a[110];
33
int main(){
34
    freopen("T4.in", "r", stdin);
35
    freopen("T4.out", "w", stdout);
36
    N = read();
37
    for(int i = 1; i <= N - 1; ++i){
38
        int x = read(), y = read(), op = read();
39
        relations.push_back(make_tuple(x, y, op));
40
    }
41
    int frac(1);
42
    for(int i = 1; i <= N; ++i)frac *= i, a[i] = i;
43
    --frac;
44
    for(int i = 1; i <= frac; ++i){
45
        bool flag(true);
46
        for(auto j : relations){
47
            int x, y, op; tie(x, y, op) = j;
48
            if((op && a[x] <= a[y]) || (!op && a[x] >= a[y])){
49
                flag = false;
50
                break;
51
            }
52
        }
53
        if(flag)++ans;
54
        next_permutation(a + 1, a + N + 1);
55
    }
56
    printf("%d\n", ans);
57

58
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
59
    return 0;
60
}
61

62

63

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

是的四道乱搞且挂分，好像是 T3 还是哪道来着想了半天感觉很接近正解，不过依然寄

正解

T1

LG-P3594 [POI2015] WIL

咕咕咕

UPD

update-2022_09_16 初稿