杂题小记（2023.02.28）

更好的阅读体验戳此进入

SP2713 GSS4 - Can you answer these queries IV

题面

给定序列，区间开方，区间求和。

Solution

考虑对于 ${10}^{18}$$10^{18}$ 的数最多开方 $6$$6$ 次就会变为 $1$$1$，则额外维护一个标记表示是否区间均为 $0$$0$ 或 $1$$1$，遇到标记则不继续修改，可以证明复杂度是对数级的。

Code

xxxxxxxxxx
107
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
int N, M;
29
ll A[110000];
30

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

67
int main(){
68
    int cnt(0);
69
    while(true){
70
        N = read();
71
        // if(!~N)exit(0);
72
        printf("Case #%d:\n", ++cnt);
73
        for(int i = 1; i <= N; ++i)A[i] = read < ll >();
74
        st.Build();
75
        M = read();
76
        while(M--){
77
            int opt = read();
78
            if(opt == 0){
79
                int l = read(), r = read();
80
                st.Modify(min(l, r), max(l, r));
81
            }else{
82
                int l = read(), r = read();
83
                printf("%lld\n", st.Query(min(l, r), max(l, r)));
84
            }
85
        }printf("\n");
86
        st.Clear();
87
    }
88
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
89
    return 0;
90
}
91

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

LG-P4391 [BOI2009]Radio Transmission 无线传输

题面

给定字符串，其是由一个字符串多次重复得到的（是一个串无限重复后串的任意子串），求该字符串的最短长度。

Solution

只能说这题确实高妙！感觉推导过程和 border 的那一套理论差不多。

首先结论就是用 KMP 求出 $nxt$$nxt$ 后 $n-nx{t}_n$$n - nxt_n$ 即为答案。

按照类似 border 某些前置知识的证明思路证明即可，也就是考虑对于减去最长前后缀后剩下的一段，会对应着前缀末尾段，然后再对应到后缀对应段，一直对应下去，发现一定合法。

对于其一定为最优的证明，可以考虑若存在一个更小的循环节，多次循环之后最后会剩一个残块，不考虑这个残块及其影响后一定会形成一个更长前后缀，得证（这东西适合画图李姐一下，口糊肯定很抽象）。

Code

xxxxxxxxxx
60
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
#define S(i) (S.at(i - 1))
24

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

28
int N;
29
string S;
30
int nxt[1100000];
31

32
int main(){
33
    N = read();
34
    cin >> S;
35
    int lst(0);
36
    for(int i = 2; i <= N; ++i){
37
        while(lst && S(lst + 1) != S(i))lst = nxt[lst];
38
        if(S(lst + 1) == S(i))++lst;
39
        nxt[i] = lst;
40
    }printf("%d\n", N - nxt[N]);
41

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

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

LG-P2375 [NOI2014] 动物园

题面

给定字符串 $S$$S$，求 $S$$S$ 的每个前缀子串的相同且不重叠前后缀的数量。

Solution

想麻烦了，找了半天性质，实际上很简单。

首先不考虑重叠，对于一般的求数量我们只需要在求 $nxt$$nxt$ 的时候同时转移一下 $num$$num$ 即可，然后考虑重叠，不难想到重新跑一遍 KMP，对于每次求出来的 $nx{t}_i$$nxt_i$ 一直跳到 $nx{t}_i\le \lfloor {\displaystyle \frac{i}{2}}\rfloor$$nxt_i \le \lfloor \dfrac{i}{2} \rfloor$，然后取 $nu{m}_{nx{t}_i}$$num_{nxt_i}$ 即为答案。

Code

xxxxxxxxxx
76
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
#define MOD (ll)(1e9 + 7)
24
#define S(i) (S.at(i - 1))
25

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

29
string S;
30
int nxt[1100000];
31
int num[1100000];
32

33
int main(){
34
    int T = read();
35
    while(T--){
36
        ll ans(1);
37
        cin >> S;
38
        int N = S.length();
39
        int lst(0);
40
        nxt[0] = nxt[1] = num[0] = 0, num[1] = 1;
41
        for(int i = 2; i <= N; ++i){
42
            while(lst && S(lst + 1) != S(i))lst = nxt[lst];
43
            if(S(lst + 1) == S(i))++lst;
44
            nxt[i] = lst, num[i] = num[lst] + 1;
45
        }lst = 0;
46
        for(int i = 2; i <= N; ++i){
47
            while(lst && S(lst + 1) != S(i))lst = nxt[lst];
48
            if(S(lst + 1) == S(i))++lst;
49
            while(lst > (i >> 1))lst = nxt[lst];
50
            (ans *= (num[lst] + 1)) %= MOD;
51
        }
52
        // int same(1);
53
        // while(same + 1 <= N && S(same + 1) == S(same))++same;
54
        // ll ans(1);
55
        // for(int i = 1; i <= N; ++i)(ans *= nxt[i] ? (S(1) == S(i) ? min(nxt[i] + 1, same + 1) : 2) : 1) %= MOD;
56
        printf("%lld\n", ans);
57
    }
58
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
59
    return 0;
60
}
61

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

LG-P3193 [HNOI2008]GT考试

题面

求长度为 $n$$n$ 的序列中不存在长度为 $m$$m$ 的子串的方案数。

Solution

首先按照一般思路考虑一个朴素 DP，即令 $dp(i,j)$$dp(i, j)$ 表示匹配了文本串的前 $i$$i$ 位与模式串的前 $j$$j$ 位的方案数，发现并不好进行转移，可能性太多，于是想到可以预处理出 $g(i,j)$$g(i, j)$ 表示对于模式串，从匹配了前 $i$$i$ 转移到匹配了前 $j$$j$ 的方案数，则转移显然：

显然可以等效写成：

发现其满足矩阵形式，且 $g$$g$ 为定值，可以通过矩阵快速幂优化。

对于 $g$$g$ 的预处理，考虑 KMP，先朴素跑一遍 KMP，然后枚举每一位，钦定当前的最长前后缀为目前的整个前缀，这是显然的，然后按照一般的 KMP 的匹配思路往前跳到合法能匹配的最长，如此大概统计一下复杂度卡满应该是 $O(m^{2}v)$$O(m^2v)$ 的，其中 $v=10$$v = 10$ 为值域。

Code

xxxxxxxxxx
107
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
#define S(i) (S.at(i - 1))
24
#define MOD (K)
25

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

29
int N, M, K;
30
string S;
31
int nxt[30];
32
int G[30][30];
33

34
class Matrix{
35
private:
36
public:
37
    int v[20][20];
38
    Matrix(void){memset(v, 0, sizeof v);}
39
    friend Matrix operator * (const Matrix &a, const Matrix &b){
40
        Matrix ret;
41
        for(int i = 0; i < M; ++i)
42
            for(int j = 0; j < M; ++j)
43
                for(int k = 0; k < M; ++k)
44
                    (ret.v[i][j] += a.v[i][k] * b.v[k][j] % MOD) %= MOD;
45
        return ret;
46
    }
47
    void Print(void){
48
        printf("Matrix:\n");
49
        for(int i = 0; i < M; ++i)
50
            for(int j = 0; j < M; ++j)
51
                printf("%d%c", v[i][j], j == M - 1 ? '\n' : ' ');
52
    }
53
}base, ans;
54

55
Matrix qpow(Matrix a, ll b){
56
    Matrix ret, mul(a);
57
    for(int i = 0; i < M; ++i)ret.v[i][i] = 1;
58
    while(b){
59
        if(b & 1)ret = ret * mul;
60
        b >>= 1;
61
        mul = mul * mul;
62
    }return ret;
63
}
64

65
int main(){
66
    N = read(), M = read(), K = read();
67
    cin >> S;
68
    int lst(0);
69
    for(int i = 2; i <= M; ++i){
70
        while(lst && S(lst + 1) != S(i))lst = nxt[lst];
71
        if(S(lst + 1) == S(i))++lst;
72
        nxt[i] = lst;
73
    }
74
    for(int i = 0; i < M; ++i)
75
        for(int j = '0'; j <= '9'; ++j){
76
            int lst = i;
77
            while(lst && S(lst + 1) != j)lst = nxt[lst];
78
            if(S(lst + 1) == j)++lst;
79
            ++G[i][lst];
80
        }
81
    for(int i = 0; i < M; ++i)
82
        for(int j = 0; j < M; ++j)
83
            base.v[i][j] = G[i][j] % MOD;
84
    ans.v[0][0] = 1;
85
    ans = ans * qpow(base, N);
86
    int rans(0);
87
    for(int i = 0; i < M; ++i)(rans += ans.v[0][i]) %= MOD;
88
    printf("%d\n", rans);
89
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
90
    return 0;
91
}
92

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

LG-P4180 [BJWC2010] 严格次小生成树

题面

求连通图的严格次小生成树。

Solution

存在如下方法，正确性可感性理解，理性证明未知。

考虑任意建出一棵 MST，然后枚举所有没有在 MST 中的边，分别找出每条边的 $s,t$$s, t$ 对应路径中与该边权值不同的最大权值，本次的答案即为原来 MST 的权值和减去该边的权值加上枚举的原本不在 MST 的边的权值，最终取答案最小值即可。

对于维护可以考虑用树剖 + 线段树，边权下放到点权，然后合并时可以强行讨论，也可无脑开 basic_string 排序后 unique 实现，此写法常数较大但可以通过。

Code

xxxxxxxxxx
182
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, M;
27
struct Edge{
28
    Edge* nxt;
29
    int to;
30
    int val;
31
    OPNEW;
32
}ed[210000];
33
ROPNEW;
34
Edge* head[110000];
35

36
class UnionFind{
37
private:
38
    int fa[110000];
39
public:
40
    UnionFind(void){for(int i = 0; i <= 101000; ++i)fa[i] = i;}
41
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
42
    void Union(int s, int t){int fs = Find(s), ft = Find(t); fa[fs] = ft;}
43
}uf;
44

45
struct Edg{int s, t, v;};
46
basic_string < Edg > edgs;
47
basic_string < Edg > trash;
48

49
int dep[110000], fa[110000], hson[110000], siz[110000], dfn[110000], idx[110000], top[110000];
50

51
void dfs_pre(int p = 1, int fa = 0){
52
    ::fa[p] = fa, dep[p] = dep[fa] + 1, siz[p] = 1;
53
    for(auto i = head[p]; i; i = i->nxt){
54
        if(SON == fa)continue;
55
        dfs_pre(SON, p);
56
        siz[p] += siz[SON];
57
        if(siz[SON] > siz[hson[p]])hson[p] = SON;
58
    }
59
}
60
void dfs_make(int p = 1, int top = 1){
61
    static int cdfn(0);
62
    dfn[p] = ++cdfn, idx[cdfn] = p, ::top[p] = top;
63
    if(hson[p])dfs_make(hson[p], top);
64
    for(auto i = head[p]; i; i = i->nxt)
65
        if(SON != fa[p] && SON != hson[p])dfs_make(SON, SON);
66
}
67

68
ll ans(LONG_LONG_MAX);
69
int val[110000];
70

71
void PushdownVal(int p = 1, int fa = 0){
72
    for(auto i = head[p]; i; i = i->nxt)
73
        if(SON != fa)
74
            val[SON] = i->val, PushdownVal(SON, p);
75
}
76

77
class SegTree{
78
private:
79
    int mx[110000 << 2], mx2[110000 << 2];
80
    #define LS (p << 1)
81
    #define RS (LS | 1)
82
    #define MID ((gl + gr) >> 1)
83
public:
84
    SegTree(void){memset(mx, -1, sizeof mx), memset(mx2, -1, sizeof mx2);}
85
    void Pushup(int p){
86
        basic_string < int > vals;
87
        if(~mx[LS])vals += mx[LS];
88
        if(~mx[RS])vals += mx[RS];
89
        if(~mx2[LS])vals += mx2[LS];
90
        if(~mx2[RS])vals += mx2[RS];
91
        sort(vals.begin(), vals.end(), greater < int >());
92
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
93
        mx[p] = (int)vals.size() >= 1 ? *vals.begin() : -1;
94
        mx2[p] = (int)vals.size() >= 2 ? *next(vals.begin()) : -1;
95
    }
96
    void Build(int p = 1, int gl = 1, int gr = N){
97
        if(gl == gr)return mx[p] = val[idx[gl = gr]], void();
98
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
99
        Pushup(p);
100
    }
101
    pair < int, int > Query(int l, int r, int p = 1, int gl = 1, int gr = N){
102
        if(l <= gl && gr <= r)return {mx[p], mx2[p]};
103
        if(l > gr || r < gl)return {-1, -1};
104
        basic_string < int > vals;
105
        auto ret = Query(l, r, LS, gl, MID);
106
        if(~ret.first)vals += ret.first;
107
        if(~ret.second)vals += ret.second;
108
        ret = Query(l, r, RS, MID + 1, gr);
109
        if(~ret.first)vals += ret.first;
110
        if(~ret.second)vals += ret.second;
111
        sort(vals.begin(), vals.end(), greater < int >());
112
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
113
        return {(int)vals.size() >= 1 ? *vals.begin() : -1, (int)vals.size() >= 2 ? *next(vals.begin()) : -1};
114
    }
115
}st;
116

117
ll origin(0);
118

119
int QueryMx2(int s, int t, int ban){
120
    basic_string < int > vals;
121
    while(top[s] != top[t]){
122
        if(dep[top[s]] < dep[top[t]])swap(s, t);
123
        auto ret = st.Query(dfn[top[s]], dfn[s]);
124
        if(~ret.first)vals += ret.first;
125
        if(~ret.second)vals += ret.second;
126
        // printf("Querying %d->%d, [%d, %d], ret %d %d\n", top[s], s, dfn[top[s]], dfn[s], ret.first, ret.second);
127
        s = fa[top[s]];
128
    }if(dep[s] < dep[t])swap(s, t);
129
    auto ret = st.Query(dfn[hson[t]], dfn[s]);
130
    // printf("Querying %d->%d, [%d, %d], ret %d %d\n", hson[t], s, dfn[hson[t]], dfn[s], ret.first, ret.second);
131
    if(~ret.first)vals += ret.first;
132
    if(~ret.second)vals += ret.second;
133
    sort(vals.begin(), vals.end(), greater < int >());
134
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
135
    int mx = (int)vals.size() >= 1 ? *vals.begin() : -1, mx2 = (int)vals.size() >= 2 ? *next(vals.begin()) : -1;
136
    return mx != ban ? mx : mx2;
137
}
138

139
int main(){
140
    N = read(), M = read();
141
    for(int i = 1; i <= M; ++i){
142
        int s = read(), t = read(), v = read();
143
        if(s == t)continue;
144
        edgs += Edg{s, t, v};
145
    }sort(edgs.begin(), edgs.end(), [](const Edg &a, const Edg &b)->bool{return a.v < b.v;});
146
    for(auto edg : edgs){
147
        auto [s, t, v] = edg;
148
        if(uf.Find(s) != uf.Find(t))
149
            head[s] = new Edge{head[s], t, v},
150
            head[t] = new Edge{head[t], s, v},
151
            origin += v,
152
            uf.Union(s, t);
153
        else trash += edg;
154
    }dfs_pre(), dfs_make(), PushdownVal();
155
    st.Build();
156
    // printf("origin is %lld\n", origin);
157
    for(auto edg : trash){
158
        auto [s, t, v] = edg;
159
        int ret = QueryMx2(s, t, v);
160
        if(!~ret)continue;
161
        // printf("[%d - %d], v = %d, ret = %d\n", s, t, v, ret);
162
        ans = min(ans, origin - ret + v);
163
    }printf("%lld\n", ans);
164
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
165
    return 0;
166
}
167

168
template < typename T >
169
inline T read(void){
170
    T ret(0);
171
    int flag(1);
172
    char c = getchar();
173
    while(c != '-' && !isdigit(c))c = getchar();
174
    if(c == '-')flag = -1, c = getchar();
175
    while(isdigit(c)){
176
        ret *= 10;
177
        ret += int(c - '0');
178
        c = getchar();
179
    }
180
    ret *= flag;
181
    return ret;
182
}

LG-P3403 跳楼机

题面

给定 $x,y,z,h$$x, y, z, h$，求有多少 $k\in [1,h]$$k \in [1, h]$ 满足 $ax+by+cz=k$$ax + by + cz = k$。

Solution

经典同余最短路问题，令 $f(i)$$f(i)$ 表示由 $y,z$$y, z$ 凑成的模 $x$$x$ 余 $i$$i$ 的最小楼层，则有转移 $f((i+y)modx)=f(i)+y,f((i+z)modx)=f(i)+z$$f((i + y) \bmod x) = f(i) + y, f((i + z) \bmod x) = f(i) + z$，发现其满足最短路松弛操作的形式，直接以此建图跑一遍，每个 $dis$$dis$ 对答案的贡献即为 $\lfloor {\displaystyle \frac{h-dis}{x}}\rfloor +1$$\lfloor \dfrac{h - dis}{x} \rfloor + 1$，最后的 $+1$$+1$ 则是取不选 $x$$x$ 的方案，同时注意判断每个是否满足 $h\ge dis$$h \ge dis$。

Code

xxxxxxxxxx
86
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
ll H;
27
int x, y, z;
28

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

38
bitset < 110000 > vis;
39
ll dis[110000];
40
ll ans(0);
41

42
void Dijkstra(void){
43
    memset(dis, 0x3f, sizeof dis);
44
    static priority_queue < pair < ll, int >, vector < pair < ll, int > >, greater < pair < ll, int > > > cur;
45
    dis[1] = 1, cur.push({0, 1});
46
    while(!cur.empty()){
47
        int p = cur.top().second; cur.pop();
48
        if(vis[p])continue;
49
        vis[p] = true;
50
        for(auto i = head[p]; i; i = i->nxt)
51
            if(dis[p] + i->val < dis[SON])
52
                dis[SON] = dis[p] + i->val, cur.push({dis[SON], SON});
53
    }
54
}
55

56
int main(){
57
    H = read < ll >();
58
    x = read(), y = read(), z = read();
59
    if(x == 1 || y == 1 || z == 1)printf("%lld\n", H), exit(0);
60
    for(int i = 0; i < x; ++i)
61
        head[i] = new Edge{head[i], (i + y) % x, y},
62
        head[i] = new Edge{head[i], (i + z) % x, z};
63
    Dijkstra();
64
    for(int i = 0; i < x; ++i)
65
        if(H >= dis[i])
66
            ans += (H - dis[i]) / x + 1;
67
    printf("%lld\n", ans);
68
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
69
    return 0;
70
}
71

72
template < typename T >
73
inline T read(void){
74
    T ret(0);
75
    int flag(1);
76
    char c = getchar();
77
    while(c != '-' && !isdigit(c))c = getchar();
78
    if(c == '-')flag = -1, c = getchar();
79
    while(isdigit(c)){
80
        ret *= 10;
81
        ret += int(c - '0');
82
        c = getchar();
83
    }
84
    ret *= flag;
85
    return ret;
86
}

UPD

update-2023_02_28 初稿