2022.09.14 模拟赛小结(互测)

题面

PDF链接

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

更好的阅读体验戳此进入

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

赛时思路

T1

一道还算可做的大模拟，sssmzy 的 std 也锅了两次，本来以为切了，然后最后一个小细节上两行代码顺序变了，然后直接 TLE 寄掉了。

Code

xxxxxxxxxx
272
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3
#ifdef __linux__
4
#include <unistd.h>
5
#endif
6
#define PI M_PI
7
#define E M_E
8
#define npt nullptr
9

10
/******************************
11
abbr
12

13
******************************/
14

15
using namespace std;
16

17
mt19937 rnd(random_device{}());
18
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
19

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

24

25

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

29
int N;
30
int winner(false); //0-A, 1-B
31
#define att(x) at(x - 1)
32
#define A P[0]
33
#define B P[1]
34
#define CP P[cpl] //current-player
35
vector < int > P[2];
36
int tmp[20];
37

38
void Clear(void){
39
    A.clear(), B.clear();
40

41
}
42
int Win(void){
43
    bool flag(false);
44
    for(int i = 1; i <= 15; ++i)
45
        if(B.att(i)){flag = true; break;}
46
    if(!flag)return -1;
47
    flag = false;
48
    for(int i = 1; i <= 15; ++i)
49
        if(A.att(i)){flag = true; break;}
50
    if(!flag)return 1;
51
    return 0;
52
}
53
bool Play(bool _cpl){
54
    int cst(6);//current-status
55
    int cpl(_cpl); //current-player: 0-A, 1-B
56
    int lst(0);
57
    int s5len(-1);
58
    while(true){
59
        switch(cst){
60
            case 1:{
61
                bool flag(false);
62
                for(int i = lst + 1; i <= 15; ++i){
63
                    if(CP.att(i)){
64
                        CP.att(i)--;
65
                        lst = i;
66
                        cpl = !cpl;
67
                        flag = true;
68
                        break;
69
                    }
70
                }
71
                if(!flag){
72
                    lst = 0;
73
                    cst = 6;
74
                    cpl = !cpl;
75
                }
76
                break;
77
            }
78
            case 2:{
79
                bool flag(false);
80
                for(int i = lst + 1; i <= 15; ++i){
81
                    if(CP.att(i) >= 2){
82
                        CP.att(i) -= 2;
83
                        lst = i;
84
                        cpl = !cpl;
85
                        flag = true;
86
                        break;
87
                    }
88
                }
89
                if(!flag){
90
                    lst = 0;
91
                    cst = 6;
92
                    cpl = !cpl;
93
                }
94
                break;
95
            }
96
            case 3:{
97
                bool flag(false);
98
                for(int i = lst + 1; i <= 15; ++i){
99
                    if(CP.att(i) >= 3){
100
                        CP.att(i) -= 3;
101
                        lst = i;
102
                        cpl = !cpl;
103
                        flag = true;
104
                        break;
105
                    }
106
                }
107
                if(!flag){
108
                    lst = 0;
109
                    cst = 6;
110
                    cpl = !cpl;
111
                }
112
                break;
113
            }
114
            case 4:{
115
                bool flag(false);
116
                for(int i = lst + 1; i <= 15; ++i){
117
                    if(CP.att(i) >= 4){
118
                        CP.att(i) -= 4;
119
                        lst = i;
120
                        cpl = !cpl;
121
                        flag = true;
122
                        break;
123
                    }
124
                }
125
                if(!flag){
126
                    lst = 0;
127
                    cst = 6;
128
                    cpl = !cpl;
129
                }
130
                break;
131
            }
132
            case 5:{
133
                bool flag(false);
134
                for(int i = lst + 1; i <= 13; ++i){
135
                    if(i > 13 - s5len + 1)break;
136
                    for(int j = i; j <= i + s5len - 1; ++j){
137
                        if(CP.att(j) != 1)break;
138
                        if(j == i + s5len - 1){
139
                            for(int k = i; k <= j; ++k){
140
                                CP.att(k)--;
141
                            }
142
                            lst = i;
143
                            cpl = !cpl;
144
                            flag = true;
145
                        }
146
                    }
147
                    if(flag)break;
148
                }
149
                if(!flag){
150
                    if(CP.att(14) && CP.att(15)){
151
                        CP.att(14) = CP.att(15) = 0;
152
                        lst = 0;
153
                        cst = 6;
154
                        flag = true;
155
                    }
156
                }
157
                if(!flag){
158
                    lst = 0;
159
                    cst = 6;
160
                    cpl = !cpl;
161
                }
162
                break;
163
            }
164
            case 6:{
165
                for(int i = 1; i <= 15; ++i){
166
                    if(!CP.att(i))continue;
167
                    bool flag = true;
168
                    int len(0);
169
                    if(i > 9 || CP.att(i) != 1){flag = false;}
170
                    else 
171
                        for(int j = i; j <= 13; ++j){
172
                            if(CP.att(j) != 1){break;}
173
                            else ++len;
174
                        }
175
                    if(flag && len >= 5){
176
                        for(int j = i; j <= i + len - 1; ++j)CP.att(j)--;
177
                        cst = 5;
178
                        lst = i;
179
                        s5len = len;
180
                        cpl = !cpl;
181
                        break;
182
                    }
183
                    cst = CP.att(i);
184
                    CP.att(i) = 0;
185
                    cpl = !cpl;
186
                    lst = i;
187
                    break;
188
                }
189
                break;
190
            }
191
        }
192
        if(Win())
193
            return Win() == 1 ? false : true;
194
        // printf("A: ");
195
        // for(auto i : A)printf("%d ", i);
196
        // printf("\n");
197
        // printf("B: ");
198
        // for(auto i : B)printf("%d ", i);
199
        // printf("\n");
200
        // printf("Status: cst = %d, lst = %d, cpl = %d, s5len = %d\n", cst, lst, cpl ,s5len);
201
        // sleep(1);
202
    }
203

204

205
}
206
int main(){
207
    freopen("card.in", "r", stdin);
208
    freopen("card.out", "w", stdout);
209
    N = read();
210
    for(int n = 1; n <= N; ++n){
211
        fprintf(stderr, "%d\n", n), fflush(stderr);
212
        Clear();
213
        for(int i = 1; i <= 15; ++i)tmp[i] = read();
214
        for(int i = 3; i <= 13; ++i)A.push_back(tmp[i]);
215
        for(int i = 1; i <= 2; ++i)A.push_back(tmp[i]);
216
        for(int i = 14; i <= 15; ++i)A.push_back(tmp[i]);
217
        for(int i = 1; i <= 15; ++i)tmp[i] = read();
218
        for(int i = 3; i <= 13; ++i)B.push_back(tmp[i]);
219
        for(int i = 1; i <= 2; ++i)B.push_back(tmp[i]);
220
        for(int i = 14; i <= 15; ++i)B.push_back(tmp[i]);
221
        // printf("A: ");
222
        // for(auto i : A)printf("%d ", i);
223
        // printf("\n");
224
        // printf("B: ");
225
        // for(auto i : B)printf("%d ", i);
226
        // printf("\n");
227
        int posl, posw;
228
        if(!winner){
229
            for(int i = 15; i >= 1; --i)
230
                if(B.att(i)){B.att(i)--; posl = i; break;}
231
            for(int i = 1; i <= 15; ++i)
232
                if(A.att(i)){A.att(i)--; posw = i; break;}
233
            A.att(posl)++, B.att(posw)++;
234
        }else{
235
            for(int i = 15; i >= 1; --i)
236
                if(A.att(i)){A.att(i)--; posl = i; break;}
237
            for(int i = 1; i <= 15; ++i)
238
                if(B.att(i)){B.att(i)--; posw = i; break;}
239
            B.att(posl)++, A.att(posw)++;
240
        }
241
        // printf("A: ");
242
        // for(auto i : A)printf("%d ", i);
243
        // printf("\n");
244
        // printf("B: ");
245
        // for(auto i : B)printf("%d ", i);
246
        // printf("\n");
247
        bool ret = Play(!winner);
248
        printf("%d\n", ret ? 1 : 0);
249
        winner = ret;
250
    }
251

252
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
253
    return 0;
254
}
255

256

257

258
template<typename T>
259
inline T read(void){
260
    T ret(0);
261
    short flag(1);
262
    char c = getchar();
263
    while(c != '-' && !isdigit(c))c = getchar();
264
    if(c == '-')flag = -1, c = getchar();
265
    while(isdigit(c)){
266
        ret *= 10;
267
        ret += int(c - '0');
268
        c = getchar();
269
    }
270
    ret *= flag;
271
    return ret;
272
}

T2

看着题目不太可做就直接跳了。。。

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

8
/******************************
9
abbr
10

11
******************************/
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

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21

22

23

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

27

28

29
int main(){
30
freopen("scrimmage.in", "r", stdin);
31
freopen("scrimmage.out", "w", stdout);
32
    int N = read(), Q = read();
33
    for(int i = 1; i <= N; ++i)(void)read();
34
    for(int i = 1; i <= Q; ++i){
35
        int opt = read();
36
        switch(opt){
37
            case 1:{(void)read();(void)read();break;}
38
            case 2:{(void)read();(void)read();printf("1\n");break;}
39
            case 3:{(void)read();(void)read();(void)read();(void)read();printf("1\n"); break;}
40
        }
41
    }
42

43
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
44
    return 0;
45
}
46

47

48

49
template<typename T>
50
inline T read(void){
51
    T ret(0);
52
    short 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
}

T3

大模拟写了两个多小时，这个题推了两个多小时，没推出来，所有算法都假了，寄。

Code

xxxxxxxxxx
116
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
/******************************
9
abbr
10

11
******************************/
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

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21

22
template<typename T = int>
23
inline T read(void);
24

25
#define MOD 998244353
26
ll qpow(ll a, ll b){
27
    ll ret(1), mul(a);
28
    while(b){
29
        if(b & 1)ret = ret * mul % MOD;
30
        b >>= 1;
31
        mul = mul * mul % MOD;
32
    }
33
    return ret;
34
}
35
ll frac[5100], inv[5100];
36
void Init(void){
37
    frac[0] = 1;
38
    for(int i = 1; i <= 5010; ++i)frac[i] = frac[i - 1] * i % MOD;
39
    inv[5010] = qpow(frac[5010], MOD - 2);
40
    for(int i = 5010 - 1; i >= 0; --i)inv[i] = inv[i + 1] * (i + 1) % MOD;
41
}
42
ll GetC(int n, int m){
43
    if(m > n)return 0;
44
    return frac[n] * inv[m] % MOD * inv[n - m] % MOD;
45
}
46
ll ans(0);
47
int tier[5100];
48
vector < int > v;
49
void dfs(int mdep, int dep, int connect, int board){
50
    // if(dep > mdep)return;
51
    if(dep == mdep){
52
        v.push_back(connect);
53
        for(int i = 1; i <= (int)v.size(); ++i){
54
            if(v.at(i - 1) > i + 1 || v.at(i - 1) > (int)v.size() - i + 1 + 1){
55
                v.pop_back();
56
                return;
57
            }
58
        }
59
        v.pop_back();
60
        ++tier[board];
61
        return;
62
    } //0 ~ mdep - 1
63
    v.push_back(connect);
64
    dfs(mdep, dep + 1, 1, board + 1);
65
    v.pop_back();
66
    if(connect <= board + 1)dfs(mdep, dep + 1, connect + 1, board);
67
}
68
// int mtier[5100];
69
// void dfss(int mdep, int dep, int connect, int board, bool mark = false){
70
//     // if(dep > mdep)return;
71
//     if(dep == mdep){if(mark)++mtier[board]; return;} //0 ~ mdep - 1
72
//     dfss(mdep, dep + 1, 1, board + 1, mark);
73
//     if(connect <= board + 1)dfss(mdep, dep + 1, connect + 1, board, mark);
74
//     else dfss(mdep, dep + 1, connect + 1, board, true);
75
// }
76

77
int main(){
78
    freopen("alkane.in", "r", stdin);
79
    freopen("alkane.out", "w", stdout);
80
    Init();
81
    int N = read();
82
    int ans10[20] = {0, 1, 1, 1, 2, 3, 5, 9, 18, 25};
83

84
    if(N <= 9){printf("%d\n", ans10[N]); return 0;}
85

86

87
    N -= 2;
88
    for(int i = 0; i <= N - 1; ++i)ans = (ans + (ll)ceil((double)GetC(N - 1, i) / 2.0)) % MOD;
89
    // dfs(N, 1, 1, 0);
90
    // dfss(N, 1, 1, 0);
91
    // for(int i = 0; i <= N; ++i)printf("tier[%d] = %d\n", i, tier[i]);
92
    // for(int i = 0; i <= N; ++i)printf("mtier[%d] = %d\n", i, mtier[i]);
93
    // for(int i = 0; i <= N; ++i)ans = (ans + (ll)ceil((double)tier[i] / 2.0)) % MOD;
94
    // for(int i = 0; i <= N; ++i)ans = (ans + tier[i]) % MOD;
95
    printf("%lld\n", (ll)((double)ans * (double)rndd(90, 110) / 100.0));
96
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
97
    return 0;
98
}
99

100

101

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

T4

没时间写就没做，寄。

正解

T1

简单改了一下就切了

T2

似乎是个带修莫队，或者树套树。

zpair 调了很久然后分块的幂没开 double 直接零次幂变成暴力，然后 TLE 40pts

T3

一道很阴间的 DP。

T4

思维题，更恶心。

UPD

update-2022_09_14 初稿