2022.08.27 模拟赛小结

2022.08.27 模拟赛小结题面更好的阅读体验戳此进入赛时思路T1T2T3T4正解T2T1T3T4UPD

题面

链接

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

更好的阅读体验戳此进入

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

赛时思路

T1

原题是 LOJ-535 「LibreOJ Round #6」花火，题意大概是一个序列，然后可以将其中任意两个值调换位置一次，然后再求逆序对个数。

$O(n log n)$ $O(n^3logn)$ $30\%$ $O(n^4)$ 做得了，反正得分应该没区别，就没必要多浪费时间了。

然后呢和我预料的差不多，25pts，小点里有一个 WA 了，不知道是哪里寄掉了。

Code:


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

4
using namespace std;
5

6
typedef long long ll;
7
typedef unsigned long long unll;
8
typedef long double ld;
9
typedef unsigned int uint;
10

11
#define npt nullptr
12
#define PI M_PI
13
#define E M_E
14

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

18
// struct Tree{
19
//     int arr[61000];
20
//     int lim;
21
//     int lowbit(int x){return x & (-x);}
22
//     void push(int v){while(x <= lim){arr[x] += x}}
23
// }
24
int N;
25
int a[610000];
26
int main(){
27
    freopen("swaq.in", "r", stdin);
28
    freopen("swaq.out", "w", stdout);
29
    N = read();
30
    for(int i = 1; i <= N; ++i)a[i] = read();
31
    if(N <= 500){
32
        // int times(0);
33
        // for(int i = 1; i <= N; ++i){
34
        //     for(int j = i + 1; j <= N; ++j){
35
        //         if(i > j)++times;
36
        //     }
37
        // }
38
        // int maxx(0);
39
        // for(int i = 1; i <= N; ++i){
40
        //     for(int j = 1; j <= N; ++j){
41

42
        //     }
43
        // }
44
        int minn = INT_MAX;
45
        for(int i = 1; i <= N; ++i){
46
            for(int j = i + 1; j <= N; ++j){
47
                swap(a[i], a[j]);
48
                int sum(0);
49
                for(int k = 1; k <= N; ++k){
50
                    for(int l = k + 1; l <= N; ++l){
51
                        if(a[l] < a[k])++sum;
52
                    }
53
                }
54
                // for(int i_ = 1; i_ <= N; ++i_)printf("%d ", a[i_]);
55
                // printf(" ans is %d\n", sum);
56
                swap(a[i], a[j]);
57
                minn = min(minn, sum);
58
            }
59
        }
60
        printf("%d\n", minn + 1);
61
    }
62

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

67
template < typename T >
68
inline T read(void){
69
    T ret(0);
70
    T 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
    }
79
    ret *= flag;
80
    return ret;
81
}

T2

原题是 HDU-7262 三角函数（为了方便就给个 vjudge 的链接吧），是一个欧几里得的题，或者说的更准确应该是个更相减损的题，有很多性质然后最后可以转化为更相减损，很考验思维。不过赛时雀食没推出来，用了一些乱搞的做法最终拿到了 10pts，~~（如果是 NOILinux 评测环境的话有可能会高一点，用到的 __float128 在 MinGW 里会失效）~~。

$1 \times 10^{-5}$ $arctan$ $1 \times 10^{-20}$ 应该都行。

回到我的乱搞做法，观察发现输入数据只有两个数，而且部分分范围很低，所以考虑数据库思想自动生成一个大表，用一些奇怪的 BFS，（这题的状态用宽搜确实难搜，我最后用队列里套 pair 套 __float128 和枚举类型的 vector ），或者迭代加深 DFS 似乎也行？？？


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

4
using namespace std;
5

6
typedef long long ll;
7
typedef unsigned long long unll;
8
typedef long double ld;
9
typedef unsigned int uint;
10
typedef __float128 f128;
11

12
#define npt nullptr
13
#define PI M_PI
14
#define E M_E
15

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

19

20
#define eps (f128)(1e-5)
21

22
bool cmp(f128 a, f128 b){return fabs((double)a - (double)b) <= eps;}
23
f128 x;
24
f128 ans;
25

26
#define vf vector < func > 
27

28
enum func{sinn = 1, coss, atann, out_of_range__};
29
vf oper;
30

31
/*void bfs(int q__){
32
    double begT = (double)clock() / CLOCKS_PER_SEC;
33
    queue < pair < f128, vf > > q;
34
    vf empt;
35
    q.push(make_pair((f128)0.0, empt));
36
    while(!q.empty()){
37
        auto head = q.front(); q.pop();
38
        // if(cmp(head.first, ans)){
39
        //     oper = head.second;
40
        //     return;
41
        // }
42
        // if((double)clock() / CLOCKS_PER_SEC >= 0.90)return;
43
        for(func f = sinn; f <= atann; f = func(f + 1)){
44

45
            head.second.push_back(f);
46
            // printf("current: %.5lf\n", (double)head.first);
47
            f128 tmp(0.0);
48
            switch(f){
49
                case sinn:{
50
                    tmp = sinf128(head.first);
51
                    break;
52
                }
53
                case coss:{
54
                    tmp = cosf128(head.first);
55
                    break;
56
                }
57
                case atann:{
58
                    tmp = atanf128(head.first);
59
                    break;
60
                }
61
                default:{
62
                    printf("error\n");
63
                    break;
64
                }
65
            }
66
            if(cmp(tmp, ans)){
67
                oper = head.second;
68
                return;
69
            }
70
            if((int)head.second.size() > q__ * 2 + 1 || (double)clock() / CLOCKS_PER_SEC >= 0.80){
71
                printf("None");
72
                oper.clear();
73
                return;
74
            }
75
            // head.first = tmp;
76
            q.push(make_pair(tmp, head.second));
77
            head.second.pop_back();
78
        }
79
    }
80
}
81

82

83
void CAL(int p, int q){
84
    // fprintf(stderr, "caling p=%d, q=%d\n", p, q);
85
    oper.clear();
86
    ans = sqrtf128((f128)p / (f128)q);
87
    // printf("%.7lf\n%.7lf\n", (double)ans, (double)(sin(atan(cos(0.0)))));
88
    // printf("else if(p==%d&&q==%d)printf(\"", p, q);
89
    bfs(q);
90
    // reverse(oper.begin(), oper.end());
91
    for(auto i : oper){
92
        switch(i){
93
            case sinn:{
94
                printf("s");
95
                break;
96
            }
97
            case coss:{
98
                printf("c");
99
                break;
100
            }
101
            case atann:{
102
                printf("t");
103
                break;
104
            }
105
            default:{
106
                printf("error\n");
107
                break;
108
            }
109
        }
110
    }
111
    // printf("\\n\");\n");
112
    printf("\n");
113
    // if(p % 5 == 0 || q % 5 == 0){
114
    //     printf("\n");
115
    //     // fprintf(stderr, "Complete p=%d, q=%d\n", p, q);
116
    //     // fflush(stderr);
117
    // }
118
    // fflush(stdout);
119
}
120
*/
121

122

123
//这里因为测评用的MinGW，所以我用的__float128会CE，所以只能注释掉了
124

125
int main(){
126
    freopen("luckysct.in", "r", stdin);
127
    freopen("luckysct.out", "w", stdout);
128
    int p = read(), q = read();
129
    if(p==1&&q==1)printf("c\n");
130
    else if(p==1&&q==2)printf("cts\n");
131
    else if(p==2&&q==2)printf("c\n");
132
    else if(p==1&&q==3)printf("ctsts\n");
133
    else if(p==2&&q==3)printf("ctstc\n");
134
    else if(p==3&&q==3)printf("c\n");
135
    else if(p==1&&q==4)printf("ctststs\n");
136
    else if(p==2&&q==4)printf("cts\n");
137
    //......
138
    //剩下的就先删掉了，一大片表
139

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

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

Build Code: （生成表用的程序）


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

4

5
using namespace std;
6

7
typedef long long ll;
8
typedef unsigned long long unll;
9
typedef long double ld;
10
typedef unsigned int uint;
11
typedef __float128 f128;
12

13
#define npt nullptr
14
#define PI M_PI
15
#define E M_E
16

17
#define eps (f128)(1e-5)
18

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

22
bool cmp(f128 a, f128 b){return fabsf128(a - b) <= eps;}
23
f128 x;
24
f128 ans;
25

26
#define vf vector < func > 
27

28
enum func{sinn = 1, coss, atann, out_of_range__};
29
vf oper;
30

31
void bfs(int q__){
32
    double begT = (double)clock() / CLOCKS_PER_SEC;
33
    queue < pair < f128, vf > > q;
34
    vf empt;
35
    q.push(make_pair((f128)0.0, empt));
36
    while(!q.empty()){
37
        auto head = q.front(); q.pop();
38
        // if(cmp(head.first, ans)){
39
        //     oper = head.second;
40
        //     return;
41
        // }
42
        // if((double)clock() / CLOCKS_PER_SEC >= 0.90)return;
43
        for(func f = sinn; f <= atann; f = func(f + 1)){
44

45
            head.second.push_back(f);
46
            // printf("current: %.5lf\n", (double)head.first);
47
            f128 tmp(0.0);
48
            switch(f){
49
                case sinn:{
50
                    tmp = sinf128(head.first);
51
                    break;
52
                }
53
                case coss:{
54
                    tmp = cosf128(head.first);
55
                    break;
56
                }
57
                case atann:{
58
                    tmp = atanf128(head.first);
59
                    break;
60
                }
61
                default:{
62
                    printf("error\n");
63
                    break;
64
                }
65
            }
66
            if(cmp(tmp, ans)){
67
                oper = head.second;
68
                return;
69
            }
70
            if((int)head.second.size() > q__ * 2 + 1 || (double)clock() / CLOCKS_PER_SEC - begT >= 5.00){
71
                printf("None");
72
                oper.clear();
73
                return;
74
            }
75
            // head.first = tmp;
76
            q.push(make_pair(tmp, head.second));
77
            head.second.pop_back();
78
        }
79
    }
80
}
81

82

83
void CAL(int p, int q){
84
    fprintf(stderr, "caling p=%d, q=%d\n", p, q);
85
    oper.clear();
86
    ans = sqrtf128((f128)p / (f128)q);
87
    // printf("%.7lf\n%.7lf\n", (double)ans, (double)(sin(atan(cos(0.0)))));
88
    printf("else if(p==%d&&q==%d)printf(\"", p, q);
89
    bfs(q);
90
    // reverse(oper.begin(), oper.end());
91
    for(auto i : oper){
92
        switch(i){
93
            case sinn:{
94
                printf("s");
95
                break;
96
            }
97
            case coss:{
98
                printf("c");
99
                break;
100
            }
101
            case atann:{
102
                printf("t");
103
                break;
104
            }
105
            default:{
106
                printf("error\n");
107
                break;
108
            }
109
        }
110
    }
111
    printf("\\n\");\n");
112
    // if(p % 5 == 0 || q % 5 == 0){
113
    //     printf("\n");
114
    //     // fprintf(stderr, "Complete p=%d, q=%d\n", p, q);
115
    //     // fflush(stderr);
116
    // }
117
    fflush(stdout);
118
}
119
bool check(int p, int q){
120
    for(int i = 2; i * i <= min(p, q); ++i){
121
        if(p % i == 0 && q % i == 0)return false;
122
    }
123
    return true;
124
}
125

126

127
int main(){
128
    // int p = read(), q = read();
129
    
130
    // printf("\n");
131
    //     fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
132
    freopen("/home/jdoi/cpp/OI/Exams/Monkey/luckysct/build.txt", "w", stdout);
133
    for(int q = 10; q <= 1000; ++q){
134
        for(int p = 1; p <= q; ++p){
135
            if(check(p, q))CAL(p, q);
136
        }
137
    }
138

139

140

141
    return 0;
142
}
143

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

T3

一个我感觉挺离谱的整体二分+树形 DP，思路奇奇怪怪，赛时我是没想出来，不过给的几个特殊性质点还是非常容易就能想到的。

然后考虑暴力~~我不会写~~不好写，所以想到了个很奇怪的贪心，大概就是考虑只删 dist 相同的一层，然后显然能删的数量和 dist 相同，排序之后找对应的第 dist 大的数，简而言之就是个很奇怪的乱搞~~（我都不知道怎么想到的）~~，不过最后居然对了好几个点，直接 35pts。

Code:


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

4
using namespace std;
5

6
typedef long long ll;
7
typedef unsigned long long unll;
8
typedef long double ld;
9
typedef unsigned int uint;
10

11
#define npt nullptr
12
#define PI M_PI
13
#define E M_E
14

15

16
#define int ll
17

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

21

22

23
int N;
24

25
struct Edge{
26
    Edge* nxt;
27
    // int val;
28
    int to;
29
    void* operator new(size_t);
30
    Edge(Edge* nxt, int to):nxt(nxt), to(to){;}
31
    Edge(void) = default;
32
}eData[210000];
33
void* Edge::operator new(size_t){static Edge* P = eData; return ++P;}
34
Edge* head[210000];
35
int deg[210000], val[210000];
36
int maxdeg(0);
37
const int root(1);
38

39
int dist[210000];
40

41
vector < int > nums[210000];
42

43
int maxdist(0);
44
void dfs_dist(int p){
45
    
46
    for(auto i = head[p]; i; i = i->nxt){
47
        dist[i->to] = dist[p] + 1;
48
        dfs_dist(i->to);
49
        nums[dist[i->to]].push_back(val[i->to]);
50
        maxdist = max(maxdist, dist[i->to]);
51
    }
52
}
53

54
signed main(){
55
    freopen("ssq.in", "r", stdin);
56
    freopen("ssq.out", "w", stdout);
57
    N = read();
58
    for(int i = 2; i <= N; ++i)val[i] = read();
59
    for(int i = 1; i <= N - 1; ++i){
60
        int f = read(), t = read();
61
        head[f] = new Edge(head[f], t);
62
        deg[f]++, deg[t]++;
63
        maxdeg = max(maxdeg, max(deg[f], deg[t]));
64
    }
65
    if(deg[1] == 1 && maxdeg <= 2){
66
        printf("0\n");
67
        return 0;
68
    }
69
    if(deg[1] <= 2 && maxdeg <= 2){
70
        int ans(0);
71
        for(auto i = head[1]; i; i = i->nxt){
72
            ans = max(ans, val[i->to]);
73
        }
74
        printf("%lld\n", ans);
75
        return 0;
76
    }
77
    int ans(0);
78
    dfs_dist(1);
79
    for(int i = 1; i <= maxdist; ++i){
80
        if(nums[i].size() <= i)continue;
81
        sort(nums[i].begin(), nums[i].end(), greater<int>());
82
        ans = max(ans, nums[i].at(i));
83
    }
84
    printf("%lld\n", ans);
85
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
86
    return 0;
87
}
88

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

T4

大概是做的最崩的一道题，首先写这题的时候人已经困傻了，大概梦游了 0.5~1.0h 然后开始写，最后开始写暴力，然后就是没写出来，感觉题意都没完全理解，所以最后无奈直接写了个输出 rand()，然后不出所料 0pts。


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

4
using namespace std;
5

6
typedef long long ll;
7
typedef unsigned long long unll;
8
typedef long double ld;
9
typedef unsigned int uint;
10

11
#define npt nullptr
12
#define PI M_PI
13
#define E M_E
14

15
#define MOD 998244353
16

17

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

21
mt19937 _rnd(random_device{}());
22
int rnd(void){return _rnd() % INT_MAX;}
23
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
24

25

26
int N, M;
27
int atk[11000], def[11000];
28
int pos[11000], l[11000], r[11000];
29

30
int cnt(0);
31

32
vector < int > opt;
33

34
bool vis[110000];
35
bool used[110000];
36

37
void explode(int x, int w){
38
    if(!used[x] && w > def[x]){
39
        if(x != 1 && !used[x - 1]){
40
            used[x - 1] = true;
41
            vis[x - 1] = true;
42
            explode(x - 1, atk[x] - l[x]);
43
        }
44
        if(x != N && !used[x + 1]){
45
            used[x + 1] = true;
46
            vis[x + 1] = true;
47
            explode(x + 1, atk[x] - r[x]);
48
        }
49
    }
50
} 
51
bool check(){
52
    
53
    memset(vis, false, sizeof(vis));
54
    for(auto i : opt){
55
        memset(used, false, sizeof(used));
56
        explode(pos[i], INT_MAX);
57
    }
58
    for(int i = 1; i <= N; ++i){
59
        if(!vis[i])return false;
60
    }
61
    return true;
62
}
63
void dfs(int dep){
64
    if(dep > M){
65
        if(check())++cnt;
66
        return;
67
    }
68
    dfs(dep + 1);
69
    opt.push_back(dep);
70
    dfs(dep + 1);
71
    opt.pop_back();
72
}
73

74

75

76

77

78
int main(){
79
    freopen("dota.in", "r", stdin);
80
    freopen("dota.out", "w", stdout);
81
    int T = read();
82
    while(T--){
83
        cnt = 0;
84
        N = read(), M = read();
85
        for(int i = 1; i <= N; ++i)atk[i] = read(), def[i] = read();
86
        for(int i = 1; i <= M; ++i)pos[i] = read(), l[i] = read(), r[i] = read();
87
        // dfs(1);
88
        //  printf("%d\n", cnt);
89
        printf("%d\n", rndd(1, 315));
90
    }
91
   
92

93
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
94
    return 0;
95
}
96

97
template < typename T >
98
inline T read(void){
99
    T ret(0);
100
    T flag(1);
101
    char c = getchar();
102
    while(!isdigit(c) && c != '-')c = getchar();
103
    if(c == '-'){flag = -1; c = getchar();}
104
    while(isdigit(c)){
105
        ret *= 10;
106
        ret += int(c - '0');
107
        c = getchar();
108
    }
109
    ret *= flag;
110
    return ret;
111
}

正解

T2

这题我挺喜欢，单独写一个 Blog 吧，戳此进入。

T1

咕咕咕

T3

咕咕咕

T4

咕咕咕

UPD

update-2022_8_27 初稿