2022.08.24 模拟赛小结

题面

链接

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

更好的阅读体验戳此进入

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

赛时思路

T1

原题是 LG-P1533 可怜的狗狗，但是数据弱化了，$n\le 2\times {10}^4,m\le 1\times {10}^4$$n \le 2 \times 10^4, m \le 1 \times 10^4$，本来是一道很明显的主席树区间第 k 大（不过 std 用的是莫队+线段树），但是这个数据量的话似乎 $O(nm)$$O(nm)$ 随便切，于是考虑到排序后遍历整个数组找到第 k 个序号符合要求的即可，于是切掉了，不过 luogu 上只有 60pts。

Code:

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

4
using namespace std;
5

6
#define PI M_PI
7
#define E M_E
8
#define npt nullptr
9

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

13
typedef long long ll;
14
typedef unsigned long long unll;
15

16
template <typename T = int>
17
inline T read(void);
18

19
int N, M;
20
// priority_queue < pair< int, int >, vector < pair < int, int > >, greater < pair < int, int > > >a;
21
vector < pair < int, int > > a;
22

23
int main(){
24
    freopen("dog.in", "r", stdin);
25
    freopen("dog.out", "w", stdout);
26
    N = read(), M = read();
27
    for(int i = 1; i <= N; ++i)a.push_back(make_pair(read(), i)); //a.push(make_pair(read(), i));
28
    sort(a.begin(), a.end());
29
    while(M--){
30
        int f = read(), t = read(), k = read();
31
        int cnt(0);
32
        for(auto i : a){
33
            if(f <= i.second && i.second <= t)++cnt;
34
            if(cnt == k){printf("%d\n", i.first); break;}
35
        }
36
    }
37

38

39
    // fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
40
    return 0;
41
}
42

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

59
/* Examples:
60
7 2
61
1 5 2 6 3 7 4
62
1 5 3
63
2 7 1
64

65

66
*/

T2

是一道状压 DP，从数据量就可以很显然的看出来，但是赛时没考虑到用最短路来写，因为过程中是可以重复访问已经经过的点，就被这一点卡住了没写出来转移方程，最后没什么想法了就写了个 BFS + 乱搞 + 卡时，20pts，原题是 HDU5418 Victor and World。

Code:

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

4
using namespace std;
5

6
#define PI M_PI
7
#define E M_E
8
#define npt nullptr
9
#define MAXJ ((1 << i) - 1)
10

11
#define MAXTIME (1.90000)
12
#define SUBTIME ((MAXTIME / (double)_T) * 0.90000)
13

14
// #define MAXK ((1 << i) - 1)
15

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

19
typedef long long ll;
20
typedef unsigned long long unll;
21

22
template <typename T = int>
23
inline T read(void);
24
int T, _T;
25
int G[20][20];
26
// int dp[20][1 << 16];
27
// int dp[20][20][100 * 20];
28
int N, M;
29
bool used[20];
30
int ans(INT_MAX);
31
void Clear(void){
32
    memset(G, -1, sizeof(G));
33
    // memset(dp, 0x3f, sizeof(dp));
34
    memset(used, 0, sizeof(used));
35
    ans = INT_MAX;
36
}
37

38
struct que{
39
    int pos;
40
    int pri;
41
    bitset < 17 > used;
42
    que(int _pos, int _pri):pos(_pos), pri(_pri){used.reset();}
43
    void operator=(que x){
44
        this->pos = x.pos;
45
        this->pri = x.pri;
46
        this->used = x.used;
47
    }
48
};
49
void BFS(void){
50
    double begT = (double)clock() / CLOCKS_PER_SEC;
51
    queue < que > q;
52
    que top(1, 0);
53
    top.used[1] = true; 
54
    q.push(top);
55
    while( ( (double)clock() / CLOCKS_PER_SEC - begT ) <= SUBTIME && !q.empty()){
56
        // printf("BFS\n");
57
        for(int i = 1; i <= 100 && !q.empty(); ++i){
58
            auto tmp = q.front(); q.pop();
59
            if((int)tmp.used.count() == N && tmp.pos == 1){
60
                // printf("FIND ANS pos = %d, cost = %d\n", tmp.pos, tmp.pri); cout<<tmp.pri<<endl;
61
                ans = min(ans, tmp.pri);
62
                continue;
63
            }
64
            for(int j = 1; j <= N; ++j){
65
                auto tmpp = tmp;
66
                if(~G[tmpp.pos][j]){
67
                    tmpp.pri += G[tmpp.pos][j];
68
                    tmpp.used[j] = 1;
69
                    tmpp.pos = j;
70
                    q.push(tmpp);
71
                }
72
            }
73
        }
74
    }
75
}
76

77
// void DFS(int dep, int pos, int cost){
78
//     if(dep > N)return (void)(ans = min(ans, cost));
79
//     for(int i = 1; i <= N; ++i){
80
//         if(~G[pos][i] && !used[i]){
81
//             used
82
//         }
83
//     }
84
// }
85

86
int main(){
87
    freopen("travel.in", "r", stdin);
88
    freopen("travel.out", "w", stdout);
89
    T = read();
90
    _T = T;
91
    while(T--){
92
        Clear();
93
        // printf("TEST:  %d\n", dp[1][1]);
94
        N = read(), M = read();
95
        for(int i = 1; i <= M; ++i){
96
            int f = read(), t = read(), w = read();
97
            if(!~G[f][t])G[f][t] = G[t][f] = w;
98
            else G[f][t] = G[t][f] = min(G[f][t], w);
99
        }
100
        BFS();
101
        // printf("%.6lf", (MAXTIME / (double)T));
102
        printf("%d\n", ans);
103
        // for(int i = 1; i <= N; ++i){
104
        //     for(int j = 0; j <= MAXJ; ++j){
105
        //         // for(int k = 0; k <= MAXJ; ++k){
106
        //         //     dp[i][j] = min(dp[i][j], dp[i - 1][])
107
        //         // }
108
        //         for(int k = 0; k < i; ++k){
109
        //             if(dp[])
110
        //         }
111
        //     }
112
        // }
113
        // for(int i = 1; i <= N; ++i){
114
        //     for(int j = 1; j <= N; ++i){
115

116
        //     }
117
        // }
118

119
    }
120

121

122

123
    // fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
124
    return 0;
125
}
126

127
template < typename T >
128
inline T read(void){
129
    T ret(0);
130
    T flag(1);
131
    char c = getchar();
132
    while(!isdigit(c) && c != '-')c = getchar();
133
    if(c == '-')flag = 1, c = getchar();
134
    while(isdigit(c)){
135
        ret *= 10;
136
        ret += int(c - '0');
137
        c = getchar();
138
    }
139
    ret *= flag;
140
    return ret;
141
}
142

143
/* Examples:
144

145

146

147
*/

T3

一道根号分治的数学题，因为看到输入数据只有一个数所以考虑本地 $O(n^2)$$O(n^2)$ 跑结果然后写个数据库拿部分分（外加随机生成的几个大数据碰运气），不过因为本地电脑性能和代码长度限制打的表并不大，不过最后因为求 log 的时候没有手写用的换底公式，精度炸了，导致直接爆零。

原题是 ICPC2019 银川 F，似乎在计蒜客上有，链接。

Code:

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

4
using namespace std;
5

6
#define PI M_PI
7
#define E M_E
8
#define npt nullptr
9

10
#define MOD 998244353
11

12
#define logg(a, b) ((double)log(b) / log(a))
13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15

16
typedef long long ll;
17
typedef unsigned long long unll;
18

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

22

23
ll CAL(int N){
24
    ll ans(0ll);
25
    for(int a = 2; a <= N; ++a){
26
        ll tmp(0);
27
        for(int b = a; b <= N; ++b){
28
            tmp = ( tmp + (int)(floor(logg(a, b)) * ceil(logg(b, a))) % MOD ) % MOD; 
29
        }
30
        ans = (ans + (a * tmp) % MOD ) % MOD;
31
    }
32
    return ans;
33
}
34

35
int ans[6000010] = {0, 0, 2,7,18,34,56,85,124,175,236,308,392,489,600,726,874,1039,1222,1424,1646,1889,2154,2442,2754,3096,3464,3862,4288,4743,5228,5744,6294,6877,7494,8146,8840,9571,10340,11148,11996,12885,13816,14790,15808,16871,17980,19136,20340,21600,22910,24271,25684,27150,28670,30245,31876,33564,35310,37115,38980,40906,42894,44945,47074,49268,51528,53855,56250,58714,61248,63853,66530,69280,72104,75003,77978,81030,84160,87369,90658,94040,97504,101051,104682,108398,112200,116089,120066,124132,128288,132535,136874,141306,145832,150453,155170,159984,164896,169907,175028,
36

37
 //这中间是不到1e4条数据，太长了我就删了
38
                    943867507,971865423,1626469,29639352,57659720,85687574,113722915,141765744,169816062,197873870,225939169,254011960,282092244,310180022,338275295};
39

40
int main(){
41
    
42
    freopen("function.in", "r", stdin);
43
    freopen("function.out", "w", stdout);
44
    ans[10483]=423591818,ans[18804]=371933020,ans[21915]=628094753,ans[15108]=922305915,ans[28044]=8382477,ans[15834]=992863592,ans[13795]=451174431,
45
 //这中间也是很多数据，太长了我就删了
46
   ans[22615]=477214908,ans[10408]=323781780,ans[12145]=205002082,ans[14837]=486795542,ans[29535]=195266508,ans[24719]=232233760,
47
ans[26203]=282953812,ans[18512]=447383303,ans[20765]=214864064,ans[21034]=75964550,ans[26885]=9951939,ans[26692]=628205313;
48
    int tmp = read();
49
    if(ans[tmp]){printf("%d\n", ans[tmp]); return 0;}
50
    printf("%lld\n", CAL(tmp));
51
    // printf("%d\n", ans[read()]);
52
    // fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);fflush(stderr);
53
    return 0;
54
}
55

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

72
/* Examples:
73

74

75

76
*/

T4

这题本来我还以为能切掉了呢，非常显然的网络流求最小割和最小割集（或者说不需要割集，算边数就行）。没想到一次 Dinic 的做法所以写了个两次 Dinic 的，理论上是可以切的不过在第二次 Dinic 的时候，对于如何改边权有点问题所以炸了，最后 40pts。

原题 LG-P1344 [USACO4.4]追查坏牛奶Pollutant Control

Code:

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

4
using namespace std;
5

6
#define PI M_PI
7
#define E M_E
8
#define npt nullptr
9

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

13
typedef long long ll;
14
typedef unsigned long long unll;
15

16
template <typename T = int>
17
inline T read(void);
18
int N, M;
19
struct Edge{
20
    Edge* nxt;
21
    Edge* rev;
22
    int to;
23
    ll val;
24
    void* operator new(size_t);
25
    Edge(Edge* _nxt, Edge* _rev, int _to, ll _val):nxt(_nxt), rev(_rev), to(_to), val(_val){;}
26
    Edge(void) = default;
27
}eData[3100];
28
void* Edge::operator new(size_t){static Edge* P = eData; return ++P;}
29
Edge *head[50], *cur[50];
30

31
int S = 1, T;
32
int dep[50];
33

34
ll dfs(int p = S, ll curFlow = INT_MAX){
35
    if(p == T)return curFlow;
36
    ll cost(0);
37
    for(auto &i = cur[p]; i; i = i->nxt){
38
        if(i->val > 0 && dep[i->to] == dep[p] - 1){
39
            ll icost = dfs(i->to, min(curFlow - cost, i->val));
40
            cost += icost;
41
            i->val -= icost;
42
            i->rev->val += icost;
43
        }
44
        if(cost == curFlow)break;
45
    }
46
    if(!cost)dep[p] = INT_MAX;
47
    return cost;
48
}
49

50
bool bfs(void){
51
    copy(head + 1, head + N + 1, cur + 1);
52
    memset(dep, 0, sizeof(dep));
53
    queue < int > q;
54
    q.push(T);
55
    dep[T] = 1;
56
    while(!q.empty()){
57
        int t = q.front(); q.pop();
58
        for(auto i = head[t]; i; i = i->nxt){
59
            if(!dep[i->to] && i->rev->val > 0){
60
                dep[i->to] = dep[t] + 1;
61
                q.push(i->to);
62
            }
63
        }
64
    }
65
    return dep[S];
66
}
67

68
ll Dinic(void){
69
    ll ret(0), tmp;
70
    while(bfs())while((tmp = dfs()))ret += tmp;
71
    return ret;
72
}
73

74
int main(){
75
    freopen("control.in", "r", stdin);
76
    freopen("control.out", "w", stdout);
77
    N = read(), M = read();
78
    T = N;
79
    for(int i = 1; i <= M; ++i){
80
        int f = read(), t = read(), v = read<ll>();
81
        head[f] = new Edge(head[f], npt, t, v);
82
        head[t] = new Edge(head[t], npt, f, 0);
83
        head[f]->rev = head[t];
84
        head[t]->rev = head[f];
85
    }
86
    printf("%lld", Dinic());
87
    for(int i = 1; i <= N; ++i){
88
        for(auto j = head[i]; j; j = j->nxt){
89
            if(!j->val && !j->rev->val)j->rev->val = 1, j->val = 0;
90
        }
91
    }
92
    for(int i = 1; i <= N; ++i){
93
        for(auto j = head[i]; j; j = j->nxt){
94
            // if(!j->val && !j->rev->val)continue;
95
            if(!j->val)j->val = 1;
96
            else j->val = 0;
97
        }
98
    }
99
    printf(" %lld\n", Dinic());
100
    // fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
101
    return 0;
102
}
103

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

120
/* Examples:
121

122

123

124
*/

正解

T4

别问为什么不是按顺序来的

主要是出现了以下几个问题

1. 第二次 Dinic 应该判断是否为反悔边并分类讨论。
2. 数据应该因为是随机生成的，所以会有自环的存在，因为我用的存图方式的问题，自环会 RE。
3. Luogu 的数据有一个点是错的，N 点的值有问题，需要特判。

AC Code:

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

4
using namespace std;
5

6
#define PI M_PI
7
#define E M_E
8
#define npt nullptr
9

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

13
typedef long long ll;
14
typedef unsigned long long unll;
15

16
template <typename T = int>
17
inline T read(void);
18
int N, M;
19
struct Edge{
20
    Edge* nxt;
21
    Edge* rev;
22
    int to;
23
    ll val;
24
    bool isRev;
25
    void* operator new(size_t);
26
    Edge(Edge* _nxt, Edge* _rev, int _to, ll _val):nxt(_nxt), rev(_rev), to(_to), val(_val), isRev(false){;}
27
    Edge(void) = default;
28
}eData[3100];
29
void* Edge::operator new(size_t){static Edge* P = eData; return ++P;}
30
Edge *head[50], *cur[50];
31

32
int S = 1, T;
33
int dep[50];
34

35
ll dfs(int p = S, ll curFlow = INT_MAX){
36
    if(p == T)return curFlow;
37
    ll cost(0);
38
    for(auto &i = cur[p]; i; i = i->nxt){
39
        if(i->val > 0 && dep[i->to] == dep[p] - 1){
40
            ll icost = dfs(i->to, min(curFlow - cost, i->val));
41
            cost += icost;
42
            i->val -= icost;
43
            i->rev->val += icost;
44
        }
45
        if(cost == curFlow)break;
46
    }
47
    if(!cost)dep[p] = INT_MAX;
48
    return cost;
49
}
50

51
bool bfs(void){
52
    copy(head + 1, head + N + 1, cur + 1);
53
    memset(dep, 0, sizeof(dep));
54
    queue < int > q;
55
    q.push(T);
56
    dep[T] = 1;
57
    while(!q.empty()){
58
        int t = q.front(); q.pop();
59
        for(auto i = head[t]; i; i = i->nxt){
60
            if(!dep[i->to] && i->rev->val > 0){
61
                dep[i->to] = dep[t] + 1;
62
                q.push(i->to);
63
            }
64
        }
65
    }
66
    return dep[S];
67
}
68

69
ll Dinic(void){
70
    ll ret(0), tmp;
71
    while(bfs())while((tmp = dfs()))ret += tmp;
72
    return ret;
73
}
74

75
int main(){
76
    // freopen("control.in", "r", stdin);
77
    // freopen("control.out", "w", stdout);
78
    N = read(), M = read();
79
    for(int i = 1; i <= M; ++i){
80
        int f = read(), t = read(), v = read<ll>();
81
        N = max(N, max(f, t));
82
        if(f == t)continue;
83
        head[f] = new Edge(head[f], npt, t, v);
84
        head[t] = new Edge(head[t], npt, f, 0);
85
        head[f]->rev = head[t];
86
        head[t]->rev = head[f];
87
        head[t]->isRev = true;
88
    }
89
    T = N;
90
    printf("%lld", Dinic());
91
    for(int i = 1; i <= N; ++i){
92
        for(auto j = head[i]; j; j = j->nxt){
93
            if(!j->isRev && !j->val)j->val = 1, j->rev->val = 0;
94
            else if(!j->isRev && j->val)j->val = 32767, j->rev->val = 0;
95
        }
96
    }
97
    printf(" %lld\n", Dinic());
98
    // fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
99
    return 0;
100
}
101

102
template < typename T >
103
inline T read(void){
104
    T ret(0);
105
    T flag(1);
106
    char c = getchar();
107
    while(!isdigit(c) && 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
}
117

118
/* Examples:
119

120

121

122
*/

T1

对于 Luogu 上的数据，由于这题主席树是在太裸了，所以直接交以前写的板子就行。

(该说不说这题 128MB 如果用主席树的话空间卡的特别死，用指针写法可能会 MLE，没有 oop 的感觉了很烦)

AC Code:

xxxxxxxxxx
106
1
#include <bits/stdc++.h>
2
using namespace std;
3

4
#define lV lastVersion
5
#define rn realN
6
#define oarr origin_array
7

8
typedef unsigned int uint;
9
typedef unsigned long long unll;
10
typedef long long ll;
11

12
#define MAXN 310000
13

14
template<typename T = int>
15
inline T read(void);
16

17
struct Tree{
18
    int ls, rs, val;
19
}t[MAXN << 5];
20
int root[MAXN];
21
int tot(0);
22
int Build(int l, int r){
23
    int vert(++tot);
24
    t[vert].val = 0;
25
    if(l == r)return vert;
26
    int mid = (l + r) >> 1;
27
    t[vert].ls = Build(l, mid);
28
    t[vert].rs = Build(mid + 1, r);
29
    return vert;
30
}
31
int Create(int l, int r, int val, int lV){
32
    int vert(++tot);
33
    t[vert].val = t[lV].val + 1, t[vert].ls = t[lV].ls, t[vert].rs = t[lV].rs;
34
    if(l == r)return vert;
35
    int mid = (l + r) >> 1;
36
    if(val <= mid)t[vert].ls = Create(l, mid, val, t[vert].ls);
37
    else t[vert].rs = Create(mid + 1, r, val, t[vert].rs);
38
    return vert;
39
}
40
int Query(int l, int r, int qx, int qy, int k){//return position
41
    if(l == r)return l;
42
    int leftVal(t[t[qy].ls].val - t[t[qx].ls].val);
43
    int mid = (l + r) >> 1;
44
    if(k <= leftVal)return Query(l, mid, t[qx].ls, t[qy].ls, k);
45
    else return Query(mid + 1, r, t[qx].rs, t[qy].rs, k - leftVal);
46
}
47
int N, M;
48
// vector<int>arr;
49
// vector<int>oarr;
50
int arr[310000], oarr[310000];
51
int main(){
52
    // freopen("in.txt", "r", stdin);
53

54

55
    N = read(), M = read();
56
    for(int i = 1; i <= N; ++i)arr[i] = oarr[i] = read();
57
    sort(arr + 1, arr + N + 1, less<int>());
58
    int rn = unique(arr + 1, arr + N + 1) - (arr + 1);
59
    root[0] = Build(1, rn);
60
    for(int i = 1; i <= N; ++i){
61
        int pos = lower_bound(arr + 1, arr + rn + 1, oarr[i]) - arr;
62
        root[i] = Create(1, rn, pos, root[i - 1]);
63
    }
64
    for(int i = 1; i <= M; ++i){
65
        int l = read(), r = read(), k = read();
66
        printf("%d\n", arr[Query(1, rn, root[l - 1], root[r], k)]);
67
    }
68

69

70
    // for(int i = 1; i <= N; ++i)arr.push_back(read()), oarr.push_back(arr.at(i - 1));
71
    // sort(arr.begin(), arr.end());
72
    // int rn = unique(arr.begin(), arr.end()) - arr.begin();
73
    // printf("%d\n", arr.end() - arr.begin());
74
    // root[0] = Build(1, rn);
75
    // for(int i = 1; i <= N; ++i){
76
    //     int pos = lower_bound(arr.begin(), arr.begin() + rn, oarr.at(i - 1)) - arr.begin();
77
    //     root[i] = Create(1, rn, pos, root[i - 1]);
78
    // }
79
    // for(int i = 1; i <= M; ++i){
80
    //     int l = read(), r = read(), k = read();
81
    //     // int pos1 = lower_bound(arr.begin(), arr.end(), oarr.at(l - 1 - 1)) - arr.begin();
82
    //     // int pos2 = lower_bound(arr.begin(), arr.end(), oarr.at(r - 1)) - arr.begin();
83
    //     printf("Query: %d\n", Query(1, rn, root[l - 1], root[r], k));
84
    //     printf("%d\n", oarr.at(Query(1, rn, root[l - 1], root[r], k) - 1));
85
    // }
86

87
    return 0;
88
}
89

90

91

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

T3

这题感觉挺好的（所以单独写了一篇题解）

戳此查看

T2

咕咕咕

UPD

update-2022_08_25 初稿 别问我为什么8.24模拟赛8.25初稿