2023.01.06 模拟赛小结

更好的阅读体验戳此进入

今天的题是 sssmzy 组的，他的题居然有一道签到，真的，我哭死。

这次模拟赛没有太寄。

赛时思路

T1

CF359B Permutation。

要求你构造一个序列，满足对应条件。具体条件略。

比较简单，构造方案很多且均不难想到，总之简单想一下就知道了，妥妥的签到题。

Code

xxxxxxxxxx
61
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

22

23

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

27
int N, K;
28
basic_string < int > ans;
29
deque < int > values;
30

31
int main(){
32
    freopen("structure.in", "r", stdin);
33
    freopen("structure.out", "w", stdout);
34
    N = read(), K = read();
35
    if(!K){
36
        for(int i = 1; i <= N * 2; ++i)printf("%d%c", i, i == N * 2 ? '\n' : ' ');
37
        exit(0);
38
    }
39
    ans += {K + 1, 1};
40
    for(int i = 1; i <= N * 2; ++i)if(i != K + 1 && i != 1)values.emplace_back(i);
41
    while(!values.empty())ans += {values.front(), values.back()}, values.pop_front(), values.pop_back();
42
    for(auto it = ans.begin(); it != ans.end(); ++it)printf("%d%c", *it, it == prev(ans.end()) ? '\n' : ' ');
43
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
44
    return 0;
45
}
46

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

checker

xxxxxxxxxx
64
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

22

23

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

27
int a[111000];
28

29
int main(){
30
    while(true){
31
        FILE* input = fopen("in.txt", "w");
32
        int N = rndd(1, 50000), K = rndd(0, N >> 1);
33
        fprintf(input, "%d %d\n", N, K);
34
        fcloseall();
35
        system("./std < in.txt > my.out");
36
        FILE* output = fopen("my.out", "r");
37
        for(int i = 1; i <= N * 2; ++i)fscanf(output, "%d", &a[i]);
38
        fcloseall();
39
        ll sum1(0), sum2(0);
40
        for(int i = 1; i <= N * 2; i += 2)sum1 += abs(a[i + 1] - a[i]), sum2 += a[i + 1] - a[i];
41
        sum2 = abs(sum2);
42
        if(sum1 - sum2 == K << 1)printf("Accept!\n");
43
        else printf("Wrong!\n"), exit(0);
44
    }
45

46
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
47
    return 0;
48
}
49

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

T2

LG-P4884 多少个 1？。

给定 $m,k$$m, k$，求满足 $111\cdots 111\equiv k(\mathrm{mod}m)$$111 \cdots 111 \equiv k \pmod{m}$（共 $n$$n$ 个 $1$$1$）的最小 $n$$n$。

读完题之后想到的思路是把所有 $1$$1$ 拆分为 ${10}^{n-1}+{10}^{n-2}+\cdots +{10}^0$$10^{n - 1} + 10^{n - 2} + \cdots + 10^0$，于是问题就转换为了对每个数取模之后加起来再取模，然后通过欧拉定理将幂次对 $\phi (m)=m-1$$\varphi(m) = m - 1$ 取模即可，这样的话就是 $[0,m-2]$$[0, m - 2]$ 循环，循环长度为 $m-1$$m - 1$，然后记录一下 ${10}^{i}modm(i\in [0,m-2])$$10^i \bmod{m}(i \in [0, m - 2])$ 的值即可，这样时空复杂度都是 $O(n)$$O(n)$ 的，唯一有一个问题就是不知道会循环多少次，虽然结论似乎是 $n\le m$$n \le m$ 的，不过总之赛时我用了一个类似卡时的思路去限定了一下。无论如何最后 $m\le 5\times {10}^7$$m \le 5 \times 10^7$ 的部分分过了，最终 $60\mathtt{\text{pts}}$$60\texttt{pts}$。

Code

xxxxxxxxxx
67
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

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

25
ll K, MOD;
26
ll pow10[51000000];
27
ll sum(1);
28
ll ans(LONG_LONG_MAX);
29
const ll mxCnt = (ll)(1e8 + 114514);
30

31
int main(){
32
    freopen("date_struct.in", "r", stdin);
33
    freopen("date_struct.out", "w", stdout);
34
    K = read < ll >(), MOD = read < ll >();
35
    ll lim = mxCnt / (MOD - 1);
36
    pow10[0] = 1;
37
    for(int i = 1; i <= MOD - 2; ++i)pow10[i] = pow10[i - 1] * 10 % MOD, (sum += pow10[i]) %= MOD;
38
    ll cur(0);
39
    for(int i = 0; i <= MOD - 2; ++i){
40
        (cur += pow10[i]) %= MOD;
41
        if(cur == K)printf("%d\n", i + 1), exit(0);
42
    }cur = 0;
43
    for(int i = 0; i <= MOD - 2; ++i){
44
        (cur += pow10[i]) %= MOD;
45
        for(int j = 1; j <= lim; ++j)
46
            if((cur + sum * j % MOD) % MOD == K)ans = min(ans, (ll)i + 1 + (MOD - 1) * j);
47
    }
48
    printf("%lld\n", ans);
49
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
50
    return 0;
51
}
52

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

T3

CF494C Helping People。

有一个长为 $n$$n$ 的数列，初始时为 $a_{1..n}$$a_{1..n}$。

给你 $q$$q$ 个操作，第 $i$$i$ 个操作将 $[l_i,r_i]$$[l_i,r_i]$ 内的数全部加一，有 $p_i$$p_i$ 的概率被执行。保证区间不会交错。

求操作完成后数列的最大值的期望。

一眼没什么思路，糊了个暴力 $20\mathtt{\text{pts}}$$20\texttt{pts}$ 跑路。

Code

xxxxxxxxxx
125
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

22

23

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

27
int N, Q;
28
int a[110000];
29
int l[5100], r[5100];
30
ld p[5100];
31
ld expect(0.0);
32

33
class SegTree{
34
private:
35
    int tr[110000 << 2];
36
    int lz[110000 << 2];
37
    #define LS (p << 1)
38
    #define RS (LS | 1)
39
    #define MID ((gl + gr) >> 1)
40
public:
41
    void Pushup(int p){
42
        tr[p] = max(tr[LS], tr[RS]);
43
    }
44
    void Pushdown(int p){
45
        if(!lz[p])return;
46
        lz[LS] += lz[p], lz[RS] += lz[p];
47
        tr[LS] += lz[p], tr[RS] += lz[p];
48
        lz[p] = 0;
49
    }
50
    void Build(int p = 1, int gl = 1, int gr = N){
51
        if(gl == gr)return tr[p] = a[gl = gr], void();
52
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
53
        Pushup(p);
54
    }
55
    void Modify(int l, int r, int v = 1, int p = 1, int gl = 1, int gr = N){
56
        if(l <= gl && gr <= r)return tr[p] += v, lz[p] += v, void();
57
        Pushdown(p);
58
        if(l <= MID)Modify(l, r, v, LS, gl, MID);
59
        if(MID + 1 <= r)Modify(l, r, v, RS, MID + 1, gr);
60
        Pushup(p);
61
    }
62
    int Query(void){
63
        return tr[1];
64
    }
65
}st;
66

67
void dfs(int dep = 1, ld cur = 1.0){
68
    if(dep > Q){
69
        expect += cur * (ld)st.Query();
70
        return;
71
    }
72
    st.Modify(l[dep], r[dep]);
73
    dfs(dep + 1, cur * p[dep]);
74
    st.Modify(l[dep], r[dep], -1);
75
    dfs(dep + 1, cur * (1.0 - p[dep]));
76
}
77

78
int main(){
79
    freopen("expectation.in", "r", stdin);
80
    freopen("expectation.out", "w", stdout);
81
    N = read(), Q = read();
82
    for(int i = 1; i <= N; ++i)a[i] = read();
83
    st.Build();
84
    for(int i = 1; i <= Q; ++i)l[i] = read(), r[i] = read(), scanf("%Lf", &p[i]);
85
    dfs();
86
    printf("%.9Lf\n", expect);
87
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
88
    return 0;
89
}
90

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

107
/*
108
5 2
109
1 7 2 4 3
110
1 3 0.500
111
2 2 0.500
112

113
5 2
114
281 280 279 278 282
115
1 4 1.000
116
1 4 0.000
117

118
3 5
119
1 2 3
120
1 3 0.500
121
2 2 0.250
122
1 2 0.800
123
1 1 0.120
124
2 2 0.900
125
*/

T4

COT3 - Combat on a tree。

Alice和Bob在一棵$n$$n$个节点的树上玩游戏。每个节点最初都是黑色或白色。 他们轮流执行以下操作: 从当前树中选择一个白色节点$v$$v$,将路径$(1,v)$$(1,v)$上的所有白色节点都变为黑色.最后操作的玩家获胜.爱丽丝先手。当他们都使用最佳策略时,求是否能够必胜,并求出第一步的方案.

树上博弈论，较为阴间，赛时感觉暴力过于麻烦就没写，实际上这题的暴力精细实现的话也没有太麻烦。

正解

T2

尝试进行转化，对 $\mathtt{\text{LHS}}\leftarrow \mathtt{\text{LHS}}\times 9+1$$\texttt{LHS} \leftarrow \texttt{LHS} \times 9 + 1$ 即可转换为 $10$$10$ 的幂，即：

然后套一下 BSGS 模板即可。

依然可以不使用光速幂，最终复杂度 $O(\sqrt{m}\log m)$$O(\sqrt{m} \log m)$。

注意过程中部分需要使用 __int128_t。

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
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

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

25
ll K, M;
26
unordered_map < ll, ll > mp;
27

28
ll qpow(ll a, ll b){
29
    ll ret(1), mul(a);
30
    while(b){
31
        if(b & 1)ret = (__int128_t)ret * mul % M;
32
        b >>= 1;
33
        mul = (__int128_t)mul * mul % M;
34
    }return ret;
35
}
36

37
int main(){
38
    K = read < ll >(), M = read < ll >();
39
    ll lim = (ll)ceil(sqrt(M));
40
    for(int i = 1; i <= lim; ++i)mp.insert({(__int128_t)(9 * K + 1) % M * qpow(10, i) % M, i});
41
    for(int i = 1; i <= lim; ++i){
42
        ll val = qpow(10, (ll)i * lim);
43
        if(mp.find(val) != mp.end())printf("%lld\n", (ll)i * lim - mp[val]), exit(0);
44
    }
45
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
46
    return 0;
47
}
48

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

有一个很高妙的转化，即因为区间无交错，所以考虑将所有操作区间抽象成森林的结构，可以加一个操作 $[1,n]$$[1, n]$ 但概率为 $0$$0$，这样可以保证结构为树而非森林。

转化之后就是经典的 树形DP 了，首先一个较为显然的状态就是 $dp(p,i)$$dp(p, i)$ 表示 $p$$p$ 子树中最大值为 $i$$i$ 的概率，发现难以转移，于是考虑设 $dp(p,i)$$dp(p, i)$ 表示 $p$$p$ 子树中最大值 $\le i$$\le i$ 的概率，这样易于转移但第二维状态过多。不难发现最大值一定不小于序列本身的最大值，并且不大于最大值加上 $q$$q$，所以考虑修改状态为 $dp(p,i)$$dp(p, i)$ 表示 $p$$p$ 子树内最大值 $\le ma{x}_p+i$$\le max_p + i$ 的概率，于是转移显然，对于节点 $p$$p$ 加上其最大值减去子节点最大值，然后考虑 $p$$p$ 的操作是否执行即可。

对于没有子节点的点自然为 $dp(p,i)=P_p+(1-P_p)=1$$dp(p, i) = P_p + (1 - P_p) = 1$。

最终答案即为枚举所有 $i$$i$，由于建树时需要排序，排序后根节点应为 $1$$1$ 那么答案即为 $\sum _{i=0}^q(dp(1,i)-dp(1,i-1))\times (ma{x}_1+i)$$\sum_{i = 0}^{q}(dp(1, i) - dp(1, i - 1)) \times (max_{1} + i)$。

同时需要注意对于 $dp(p,0)$$dp(p, 0)$，其应为 $(1-P_p)\times \prod _{u\in so{n}_p}dp(u,i+ma{x}_p-ma{x}_u)$$(1 - P_p) \times \prod_{u \in son_p}dp(u, i + max_p - max_u)$。

Code

xxxxxxxxxx
113
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

22

23

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

27
struct Edge{
28
    Edge* nxt;
29
    int to;
30
    OPNEW;
31
}ed[11000];
32
ROPNEW(ed);
33
Edge* head[5100];
34

35
int N, Q;
36
int A[110000];
37
struct Mdf{
38
    int L, R;
39
    double P;
40
    int mx;
41
}mdf[5100];
42
double dp[5100][5100];
43
double ans(0.0);
44

45
class SegTree{
46
private:
47
    int tr[110000 << 2];
48
    #define LS (p << 1)
49
    #define RS (LS | 1)
50
    #define MID ((gl + gr) >> 1)
51
public:
52
    void Pushup(int p){
53
        tr[p] = max(tr[LS], tr[RS]);
54
    }
55
    void Build(int p = 1, int gl = 1, int gr = N){
56
        if(gl == gr)return tr[p] = A[gl = gr], void();
57
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
58
        Pushup(p);
59
    }
60
    int Query(int l, int r, int p = 1, int gl = 1, int gr = N){
61
        if(l <= gl && gr <= r)return tr[p];
62
        if(gr < l || r < gl)return -1;
63
        return max(Query(l, r, LS, gl, MID), Query(l, r, RS, MID + 1, gr));
64
    }
65
}st;
66

67
void TreeDP(int p = 1, int fa = 0){
68
    for(auto i = head[p]; i; i = i->nxt)if(SON != fa)TreeDP(SON, p);
69
    for(int j = 0; j <= Q; ++j){
70
        double D1 = mdf[p].P, D2 = (1.0 - mdf[p].P);
71
        for(auto i = head[p]; i; i = i->nxt){
72
            if(SON == fa)continue;
73
                if(j + mdf[p].mx - mdf[SON].mx - 1 >= 0)D1 *= dp[SON][min(Q, j + mdf[p].mx - mdf[SON].mx - 1)];
74
                if(j + mdf[p].mx - mdf[SON].mx >= 0)D2 *= dp[SON][min(Q, j + mdf[p].mx - mdf[SON].mx)];
75
        }dp[p][j] = j ? D1 + D2 : D2;
76
    }
77
}
78

79
int main(){
80
    N = read(), Q = read();
81
    for(int i = 1; i <= N; ++i)A[i] = read();
82
    st.Build();
83
    for(int i = 1; i <= Q; ++i)mdf[i].L = read(), mdf[i].R = read(), scanf("%lf", &mdf[i].P), mdf[i].mx = st.Query(mdf[i].L, mdf[i].R);
84
    mdf[++Q] = {1, N, 0.0, st.Query(1, N)};
85
    sort(mdf + 1, mdf + Q + 1, [](const Mdf &a, const Mdf &b)->bool{return a.L == b.L ? a.R > b.R : a.L < b.L;});
86
    for(int i = 1; i <= Q; ++i)
87
        for(int j = i - 1; j; --j)
88
            if(mdf[j].L <= mdf[i].L && mdf[i].R <= mdf[j].R){
89
                head[i] = new Edge{head[i], j}, head[j] = new Edge{head[j], i};
90
                break;
91
            }
92
    TreeDP();
93
    for(int i = 0; i <= Q; ++i)ans += (dp[1][i] - (i ? dp[1][i - 1] : 0.0)) * (double)(mdf[1].mx + i);
94
    printf("%.6lf\n", ans);
95
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
96
    return 0;
97
}
98

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

T4

Code

xxxxxxxxxx
1
1

UPD

update-2022__ 初稿