2023.02.11 模拟赛小结

更好的阅读体验戳此进入

考的还是比较炸的，前两道已经想的差不多了，不过最后还是挂了。。

赛时思路

T1

#6178. 「美团 CodeM 初赛 Round B」景区路线规划。

签到题，随便设一下状态转移一下即可，然后我大概就是想了很久总觉得这个玩意不符合无后效性，于是写了个十分复杂的分步考虑互相转移两个 DP 分别搞，一个是从该点起始再回到该点恰好时间的概率，然后再转移互相之间的概率，很 nt 的思路，甚至后面的互相转移的过程就是答案的式子，麻了麻了。

最后不知道时正确性的问题还是什么，总之只有 $10\mathtt{\text{pts}}$$10\texttt{pts}$。

Code

xxxxxxxxxx
106
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
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

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

23

24

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

28
struct Edge{
29
    Edge* nxt;
30
    int to;
31
    int val;
32
    OPNEW;
33
}ed[26000];
34
ROPNEW;
35
Edge* head[110];
36

37
int N, M, K;
38
int c[110], h1[110], h2[110];
39
int deg[110][500];
40
ld expA(0.0), expB(0.0);
41
ld dp[110][500];
42
ld rdp[110][500];
43

44
int main(){
45
    freopen("park.in", "r", stdin);
46
    freopen("park.out", "w", stdout);
47
    N = read(), M = read(), K = read();
48
    for(int i = 1; i <= N; ++i)c[i] = read(), h1[i] = read(), h2[i] = read();
49
    for(int i = 1; i <= M; ++i){
50
        int s = read(), t = read(), v = read();
51
        head[s] = new Edge{head[s], t, v};
52
        head[t] = new Edge{head[t], s, v};
53
    }
54
    for(int p = 1; p <= N; ++p)
55
        for(int j = 0; j <= K; ++j)
56
            for(auto i = head[p]; i; i = i->nxt)
57
                    if(j + i->val + c[SON] <= K)++deg[p][j];
58
    for(int p = 1; p <= N; ++p){
59
        dp[p][c[p]] = 1.0 / (ld)N;
60
        for(int cost = 0; cost <= K; ++cost)
61
            for(auto i = head[p]; i; i = i->nxt)
62
                if(deg[p][cost] && deg[SON][cost + i->val + c[SON]] && cost + i->val * 2 + c[SON] + c[p] <= K)
63
                    dp[p][cost + i->val * 2 + c[SON] + c[p]] += dp[p][cost] * (1.0 / (ld)deg[p][cost]) * (1.0 / (ld)deg[SON][cost + i->val + c[SON]]);
64
    }
65
    memcpy(rdp, dp, sizeof dp);
66
    for(int p = 1; p <= N; ++p)
67
        for(int j = 0; j <= K; ++j)
68
            for(auto i = head[p]; i; i = i->nxt)
69
                if(deg[p][j] && j + i->val + c[SON] <= K)
70
                    rdp[SON][j + i->val + c[SON]] += dp[p][j] * (1.0 / (ld)deg[p][j]);
71
    for(int i = 1; i <= N; ++i)
72
        for(int j = 0; j <= K; ++j)
73
            // printf("dp[%d][%d] = %.5Lf, rdp[%d][%d] = %.5Lf\n", i, j, dp[i][j], i, j, rdp[i][j]),
74
            expA += (ld)h1[i] * rdp[i][j], expB += (ld)h2[i] * rdp[i][j];
75
    printf("%.5Lf %.5Lf\n", expA, expB);
76
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
77
    return 0;
78
}
79

80
template < typename T >
81
inline T read(void){
82
    T ret(0);
83
    int flag(1);
84
    char c = getchar();
85
    while(c != '-' && !isdigit(c))c = getchar();
86
    if(c == '-')flag = -1, c = getchar();
87
    while(isdigit(c)){
88
        ret *= 10;
89
        ret += int(c - '0');
90
        c = getchar();
91
    }
92
    ret *= flag;
93
    return ret;
94
}
95
/*
96
5 4 60
97
25 12 83
98
30 38 90
99
16 13 70
100
22 15 63
101
50 72 18
102
2 1 7
103
3 1 7
104
4 3 1
105
5 3 10
106
*/

T2

#6169. 相似序列。

想到随机权值，想到哈希，然后考虑将其划分集合之后作个差直接在每个数的随机权值构成的 unordered_set 里查一下，然后想到这东西可能不是差一个数，于是就寄了，也想过直接前缀异或然后二分，但是判不了个数，也想过前缀哈希，但是判不了顺序。

所以最后挂了个暴力上去，$30\mathtt{\text{pts}}$$30\texttt{pts}$。

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
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

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

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

26
int N, Q;
27
basic_string < int > A;
28

29
int main(){
30
    freopen("sequence.in", "r", stdin);
31
    freopen("sequence.out", "w", stdout);
32
    int T = read();
33
    while(T--){
34
        A.clear(); A += -1;
35
        N = read(), Q = read();
36
        for(int i = 1; i <= N; ++i)A += read();
37
        while(Q--){
38
            int a = read(), b = read(), c = read(), d = read();
39
            basic_string < int > s1(A.substr(a, b - a + 1)), s2(A.substr(c, d - c + 1));
40
            sort(s1.begin(), s1.end()), sort(s2.begin(), s2.end());
41
            bool diff(false);
42
            for(int i = 0; i < (int)s1.size(); ++i){
43
                if(s1.at(i) != s2.at(i)){
44
                    if(!diff)diff = true;
45
                    else{printf("NO\n"); break;}
46
                }
47
                if(i == (int)s1.size() - 1)printf("YES\n");
48
            }
49
        }
50
    }
51
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
52
    return 0;
53
}
54

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

71
/*
72
1
73
6 3
74
1 3 4 2 3 4
75
1 3 4 6
76
1 2 5 6
77
3 5 2 4
78
*/

T3

hihoCoder 1047 Random Tree。

这个 OJ 挂了，所以链接也没用了。

给定无向带权完全图，等概率随机生成树，求任意两点间路径长度期望。

部分分很足，详细推导后可以拿到 $60\mathtt{\text{pts}}$$60\texttt{pts}$，剩下的正解分是一些根 Prufer 序列相关的奇怪东西，不会，当然或者也可以学习 @sssmzy 的高妙做法，发现答案与不连通要求两点的边的边权和一定成线性关系，且仅与 $n$$n$ 相关，由部分分可知。于是直接通过除法粗略计算斜率，然后实数二分提升精度即可。

正解

T1

如上所说，将多出来的转移删掉然后先枚举时间再枚举点，就可以直接消除后效性了。

Code

xxxxxxxxxx
110
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
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

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

23

24

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

28
struct Edge{
29
    Edge* nxt;
30
    int to;
31
    int val;
32
    OPNEW;
33
}ed[26000];
34
ROPNEW;
35
Edge* head[110];
36

37
int N, M, K;
38
int c[110], h1[110], h2[110];
39
int deg[110][500];
40
ld expA(0.0), expB(0.0);
41
ld dp[110][500];
42
ld rdp[110][500];
43

44
int main(){
45
    // freopen("park.in", "r", stdin);
46
    // freopen("park.out", "w", stdout);
47
    N = read(), M = read(), K = read();
48
    for(int i = 1; i <= N; ++i)c[i] = read(), h1[i] = read(), h2[i] = read();
49
    for(int i = 1; i <= M; ++i){
50
        int s = read(), t = read(), v = read();
51
        head[s] = new Edge{head[s], t, v};
52
        head[t] = new Edge{head[t], s, v};
53
    }
54
    for(int p = 1; p <= N; ++p)
55
        for(int j = 0; j <= K; ++j)
56
            for(auto i = head[p]; i; i = i->nxt)
57
                    if(j + i->val + c[SON] <= K)++deg[p][j];
58
    // for(int p = 1; p <= N; ++p){
59
    //     dp[p][c[p]] = 1.0 / (ld)N;
60
    //     for(int cost = 0; cost <= K; ++cost)
61
    //         for(auto i = head[p]; i; i = i->nxt)
62
    //             if(deg[p][cost] && deg[SON][cost + i->val + c[SON]] && cost + i->val * 2 + c[SON] + c[p] <= K)
63
    //                 dp[p][cost + i->val * 2 + c[SON] + c[p]] += dp[p][cost] * (1.0 / (ld)deg[p][cost]) * (1.0 / (ld)deg[SON][cost + i->val + c[SON]]);
64
    // }
65
    // memcpy(rdp, dp, sizeof dp);
66
    for(int i = 1; i <= N; ++i)rdp[i][c[i]] = 1.0 / (ld)N;
67
    for(int j = 0; j <= K; ++j)
68
        for(int p = 1; p <= N; ++p){
69
            // rdp[p][c[p]] = 1.0 / (ld)N;
70
            
71
                for(auto i = head[p]; i; i = i->nxt)
72
                    if(deg[p][j] && j + i->val + c[SON] <= K)
73
                        rdp[SON][j + i->val + c[SON]] += rdp[p][j] * (1.0 / (ld)deg[p][j]);
74
        }
75
    for(int i = 1; i <= N; ++i)
76
        for(int j = 0; j <= K; ++j)
77
            // printf("dp[%d][%d] = %.5Lf, rdp[%d][%d] = %.5Lf\n", i, j, dp[i][j], i, j, rdp[i][j]),
78
            expA += (ld)h1[i] * rdp[i][j], expB += (ld)h2[i] * rdp[i][j];
79
    printf("%.5Lf %.5Lf\n", expA, expB);
80
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
81
    return 0;
82
}
83

84
template < typename T >
85
inline T read(void){
86
    T ret(0);
87
    int flag(1);
88
    char c = getchar();
89
    while(c != '-' && !isdigit(c))c = getchar();
90
    if(c == '-')flag = -1, c = getchar();
91
    while(isdigit(c)){
92
        ret *= 10;
93
        ret += int(c - '0');
94
        c = getchar();
95
    }
96
    ret *= flag;
97
    return ret;
98
}
99
/*
100
5 4 60
101
25 12 83
102
30 38 90
103
16 13 70
104
22 15 63
105
50 72 18
106
2 1 7
107
3 1 7
108
4 3 1
109
5 3 10
110
*/

T2

（权值、动态开点）主席树维护和哈希即可，这样就可以快速处理无序哈希，很朴素的思路，当然我是 sb 所以没想到。

code 懒得补了，主要欠的题太多，以后复习主席树的时候或许再来写写

T3

代码咕了。

UPD

update-2023_02_11 初稿