杂题小记（2023.02.25）

更好的阅读体验戳此进入

PJudge-21739 A. 【NOIP Round #5】青鱼和序列

题面

给定初始序列，存在两种操作，将序列复制并接在前面，将序列复制并翻转并接在前面，需要在 $m$$m$ 次操作后最大化：

Solution

“容易” 发现翻转多次与翻转一次等效，“容易” 发现一次的翻转在任意位置都等效，于是模拟跑一下即可。

复杂度最优可以优化到 $O(n+\log m)$$O(n + \log m)$，本题限制十分宽松故写的很丑也没事。

Code

xxxxxxxxxx
91
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

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

28
int N, M;
29
ll A[110000];
30
ll sum[110000], rsum[110000], ssum, srsum;
31
ll pow2s[110000], pow2[110000];
32
ll spow2s[110000];
33

34
int main(){
35
    N = read(), M = read();
36
    for(int i = 1; i <= N; ++i)A[i] = read();
37
    for(int i = 1; i <= N; ++i)sum[i] = (sum[i - 1] + A[i]) % MOD;
38
    for(int i = N; i >= 1; --i)rsum[i] = (rsum[i + 1] + A[i]) % MOD;
39
    for(int i = 1; i <= N; ++i)(ssum += sum[i]) %= MOD, (srsum += rsum[i]) %= MOD;
40
    ll base(N);
41
    for(int i = 1; i <= M - 1; ++i){
42
        ssum = (ssum + ssum + sum[N] * base % MOD) % MOD;
43
        srsum = (srsum + srsum + sum[N] * base % MOD) % MOD;
44
        (sum[N] *= 2) %= MOD;
45
        (base <<= 1) %= MOD;
46
    }
47
    printf("%lld\n", max((ssum + ssum + sum[N] * base % MOD) % MOD, (ssum + srsum + sum[N] * base % MOD) % MOD));
48
    // pow2s[0] = sum[N] * N % MOD, pow2[0] = 1;
49
    // for(int i = 1; i <= M; ++i)pow2s[i] = pow2s[i - 1] * 4 % MOD, pow2[i] = pow2[i - 1] * 2 % MOD;
50
    // for(int i = 0; i <= M; ++i)spow2s[i] = ((i - 1 >= 0 ? spow2s[i - 1] : 0) + pow2s[i]) % MOD;
51
    // ll ans((ssum * pow2[M] % MOD + spow2s[M - 1]) % MOD);
52
    // ssum = (ssum * pow2[M - 1] % MOD + (M - 2 >= 0 ? spow2s[M - 2] : 0)) % MOD;
53
    // srsum = (srsum * pow2[M - 1] % MOD + (M - 2 >= 0 ? spow2s[M - 2] : 0)) % MOD;
54
    // ll tmp = ssum;
55
    // ssum = ((ssum + srsum) % MOD + pow2s[M - 1]) % MOD;
56
    // ans = max(ans, ssum);
57
    // //unreverse todo
58
    // ll origin_ssum = ssum, origin_srsum = srsum;
59
    // for(int rev = 1; rev <= M; ++rev){
60
    //     ssum = origin_ssum, srsum = origin_srsum;
61
    //     int d = rev - 1;
62
    //     ssum = (ssum * pow2[d] % MOD + (rev - 2 >= 0 ? spow2s[rev - 1] : 0)) % MOD;
63
    //     srsum = (srsum * pow2[d] % MOD + (rev - 2 >= 0 ? spow2s[rev - 1] : 0)) % MOD;
64
    //     ll tmp = ssum;
65
    //     (ssum += (srsum + pow2s[rev]) % MOD) %= MOD;
66
    //     (srsum += (tmp + pow2s[rev]) % MOD) %= MOD;
67
    //     d = M - rev;
68
    //     ssum = (ssum * pow2[d] % MOD + (spow2s[M] - spow2s[rev] + MOD) % MOD) % MOD;
69
    //     ans = max(ans, ssum);
70
    //     printf("rev = %d, ssum = %lld\n", rev, ssum);
71
    // }
72
    // printf("%lld\n", ans);
73
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
74
    return 0;
75
}
76

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

Pjudge-21743 B. 【NOIP Round #5】青鱼和怪兽

题面

存在怪兽，你有 $n$$n$ 点血怪兽有 $m$$m$，每次可以选择攻击，会有 $p$$p$ 的概率使怪兽掉一滴血，反之则有 $1-p$$1 - p$ 的概率使自己掉一滴血吗，会消耗 $1$$1$ 单位时间，也可以选择 remake，不消耗时间但会使你和怪兽恢复为初始的血量，求击杀怪兽的期望时间。

Solution

考虑一个朴素的 DP，令 $dp(i,j)$$dp(i, j)$ 表示你剩 $i$$i$ 怪兽剩 $j$$j$ 的状态时击杀的期望时间，不考虑 remake 的转移为 $dp(i,j)=dp(i-1,j)\times (1-p)+dp(i,j-1)\times p$$dp(i, j) = dp(i - 1, j) \times (1 - p) + dp(i, j - 1) \times p$，然后考虑到 remake，不难想到二分答案 $tim$$tim$，也就是二分一个 $dp(n,m)$$dp(n, m)$，此时我们不难发现边界，对于 $dp(i,0)$$dp(i, 0)$，此时已经结束，赋值为 $0$$0$，对于 $dp(0,j)$$dp(0, j)$ 则只能重开，赋值为 $tim$$tim$，然后转移过程中在朴素转移的基础上对 $tim$$tim$ 取 $min$$\min$，即如果正常的期望不如重开，那么就直接重开。然后最终判断求得得 $dp(n,m)$$dp(n, m)$ 与我们二分出来的 $tim$$tim$ 是否相同，相同则说明不合法，可以上调下界，反之一定有更优的低于 $tim$$tim$ 的时间，下调上界。

Code

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

5
#define PI M_PI
6
#define E M_E
7
#define npt nullptr
8
#define SON i->to
9
#define OPNEW void* operator new(size_t)
10
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
11
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
12

13
using namespace std;
14

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

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

24
#define EPS (1e-9)
25

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

29
int N, M, C;
30
ld P;
31
ld dp[1100][1100];
32

33
bool Check(ld tim){
34
    for(int i = 0; i <= N + 10; ++i)
35
        dp[i][0] = 0.0;
36
    for(int j = 0; j <= M + 10; ++j)
37
        dp[0][j] = tim;
38
    for(int i = 1; i <= N; ++i)
39
        for(int j = 1; j <= M; ++j)
40
            dp[i][j] = min(tim, (dp[i - 1][j] + 1) * (1.0 - P) + (dp[i][j - 1] + 1) * P);
41
    return dp[N][M] < tim;
42
}
43

44
int main(){
45
    N = read(), M = read(), C = read();
46
    P = (ld)C / 100.0;
47
    ld l = EPS, r = 1e9, ans(-1.0);
48
    while(fabs(l - r) > EPS){
49
        ld mid = (l + r) / 2.0;
50
        ans = mid;
51
        if(Check(mid))r = mid - EPS;
52
        else l = mid + EPS;
53
    }printf("%.8Lf\n", ans);
54

55
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
56
    return 0;
57
}
58

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

LG-P4097 [HEOI2013]Segment

题面

插线段，求点对应最大值且序号最小的线段。

Solution

李超线段树模板解决。

Code

xxxxxxxxxx
115
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 EPS (1e-6)
24
#define LIM (41000)
25

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

29
struct Interval{
30
    bool flag;
31
    int idx;
32
    double k, b;
33
    double CalVal(int x){
34
        return k * x + b;
35
    }
36
};
37
class LCSegTree{
38
private:
39
    Interval tr[LIM << 2];
40
    #define LS (p << 1)
41
    #define RS (LS | 1)
42
    #define MID ((gl + gr) >> 1)
43
public:
44
    void Update(Interval line, int p, int gl, int gr){
45
        if(!tr[p].flag)return tr[p] = line, void();
46
        if(fabs(line.CalVal(MID) - tr[p].CalVal(MID)) < EPS){
47
            if(line.idx < tr[p].idx)swap(tr[p], line);
48
        }else if(line.CalVal(MID) > tr[p].CalVal(MID))swap(tr[p], line);
49
        if(gl != gr && (fabs(line.CalVal(gl) - tr[p].CalVal(gl)) < EPS || line.CalVal(gl) > tr[p].CalVal(gl)))Update(line, LS, gl, MID);
50
        if(gl != gr && (fabs(line.CalVal(gr) - tr[p].CalVal(gr)) < EPS || line.CalVal(gr) > tr[p].CalVal(gr)))Update(line, RS, MID + 1, gr);
51
    }
52
    void UpdatePoint(int pos, int val, int idx, int p = 1, int gl = 1, int gr = LIM){
53
        if(gl == gr){
54
            if(!tr[p].flag)tr[p] = Interval{true, idx, 0.0, (double)val};
55
            else if(fabs(tr[p].CalVal(pos) - (double)val) < EPS)tr[p].idx = min(tr[p].idx, idx);
56
            else if(tr[p].CalVal(pos) < (double)val)tr[p] = Interval{true, idx, 0.0, (double)val};
57
            return;
58
        }
59
        if(pos <= MID)UpdatePoint(pos, val, idx, LS, gl, MID);
60
        else UpdatePoint(pos, val, idx, RS, MID + 1, gr);
61
    }
62
    void Insert(Interval line, int l, int r, int p = 1, int gl = 1, int gr = LIM){
63
        if(l <= gl && gr <= r)return Update(line, p, gl, gr);
64
        if(l <= MID)Insert(line, l, r, LS, gl, MID);
65
        if(r >= MID + 1)Insert(line, l, r, RS, MID + 1, gr);
66
    }
67
    pair < int, double > Query(int pos, int p = 1, int gl = 1, int gr = LIM){
68
        auto ret = tr[p].idx; auto mxv = tr[p].CalVal(pos);
69
        if(gl != gr){
70
            auto vals = pos <= MID ? Query(pos, LS, gl, MID) : Query(pos, RS, MID + 1, gr);
71
            if(fabs(vals.second - mxv) < EPS)ret = min(ret, vals.first);
72
            else if(vals.second > mxv)ret = vals.first, mxv = vals.second;
73
        }return {ret, mxv};
74
    }
75
}lcst;
76

77
int N;
78
int cnt(0);
79
int lst(0);
80

81
int main(){
82
    N = read();
83
    for(int i = 1; i <= N; ++i){
84
        int opt = read();
85
        if(opt == 0){
86
            int ans = lcst.Query((read() + lst - 1) % 39989 + 1).first;
87
            lst = ans;
88
            printf("%d\n", ans);
89
            continue;
90
        }
91
        int sx = (read() + lst - 1) % 39989 + 1, sy = (read() + lst - 1) % (int)(1e9) + 1;
92
        int tx = (read() + lst - 1) % 39989 + 1, ty = (read() + lst - 1) % (int)(1e9) + 1;
93
        if(sx == tx)lcst.UpdatePoint(sx = tx, max(sy, ty), ++cnt);
94
        else lcst.Insert(Interval{true, ++cnt, (double)(ty - sy) / (tx - sx), (double)ty - (double)(ty - sy) / (tx - sx) * tx}, min(sx, tx), max(sx, tx));
95
    }
96

97
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
98
    return 0;
99
}
100

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

LG-P5249 [LnOI2019]加特林轮盘赌

题面

存在加特林，存在 $n$$n$ 个人围城一圈轮流使用加特林并每次均有 $P$$P$ 的概率被打死，求第 $k$$k$ 个人是最终唯一的幸存者的概率。

Solution

很有意思的一道题，和一般的朴素概率 DP 不尽相同。

前面的思路和其它题解差不多，主要细说一下最后推式子的步骤。

对于 $n=1$$n = 1$ 平凡解决，对于 $n=2$$n = 2$ 考虑，发现不能用一般的线性递推的思路，不难想到对于处于第一位的人，若其没有被打死，那么下一次的时候枪指向下一个人，局面与初始时原来处于第一位的人处于第二位等效，那么不难想到我们令 $dp(2,i)$$dp(2, i)$ 表示 $2$$2$ 个人时处于第 $i$$i$ 位的人幸存的概率，不难发现转移：

也就是说考虑其原本处于第 $1$$1$ 位，被打死则无贡献，没有被打死并且在下一次被移动到 $2$$2$ 位置后仍然幸存即为答案。

写到这就不难发现这东西是存在后效性的，或者说不存在初值，但是仍然存在显然的 $dp(2,1)+dp(2,2)=1$$dp(2, 1) + dp(2, 2) = 1$，所以也可以计算。

于是考虑扩展到 $dp(n,i)$$dp(n, i)$，不难想到最朴素地：

此时我们仔细想一下刚才的过程，不难发现意义就是我们每次只崩首位的人，崩完之后不移动枪，而是将整个圆排列对应旋转。

然后我们考虑对于中间的转移，不难想到对于 $dp(n,k)$$dp(n, k)$，我们如果 $P$$P$ 的概率崩掉首位了，则 $k\leftarrow k-1,n\leftarrow n-1$$k \leftarrow k - 1, n \leftarrow n - 1$，即 $P\times dp(n-1,k-1)$$P \times dp(n - 1, k - 1)$，如果 $1-P$$1 - P$ 地没崩掉，那么人虽然没有减少但是圆排列仍然需要转一下 $k\leftarrow k-1$$k \leftarrow k - 1$，也就是 $(1-P)\times dp(n,k-1)$$(1 - P) \times dp(n, k - 1)$，于是转移即为：

当然我们这东西是没有初值的，不能直接递推，但是共存在 $n$$n$ 个方程，可以直接解 $n$$n$ 元 $1$$1$ 次方程组，用高斯消元即可，但是这个是 $O(n^4)$$O(n^4)$ 的，考虑优化。

考虑对于 $P\times dp(n-1,k-1)$$P \times dp(n - 1, k - 1)$ 此时已经为常量了，令其为 $\xi$$\xi$，则有：

令 $f(k)=dp(n,k)$$f(k) = dp(n, k)$，令 $\xi (k)$$\xi(k)$ 表示 $dp(n-1,k-1)\times P\times (1-P{)}^{k-1}$$dp(n - 1, k - 1) \times P \times (1 - P)^{k - 1}$，则有：

这样我们可以用 $f(1)$$f(1)$ 表示出所有 $f(k)$$f(k)$，然后带入 $\sum f(k)=1$$\sum f(k) = 1$ 求出 $f(1)$$f(1)$，再 $O(n)$$O(n)$ 求出所有的 $f(k)$$f(k)$。

注意需要特判 $P=0$$P = 0$ 的情况，且注意需要滚动数组优化空间。

最终时间复杂度 $O(n^2)$$O(n^2)$，空间复杂度 $O(n)$$O(n)$。

Code

xxxxxxxxxx
65
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 EPS (1e-10)
24

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

28
ld P;
29
int N, K;
30
ld dp[2][11000];
31

32
int main(){
33
    scanf("%Lf", &P), N = read(), K = read();
34
    if(P < EPS)printf("%.10Lf\n", N == 1 ? (ld)1 : (ld)0), exit(0);
35
    dp[1][1] = 1.0;
36
    bool cur(false);
37
    for(int i = 2; i <= N; ++i){
38
        ld K(1.0), B(0.0), base1(1.0), base2(0.0);
39
        for(int j = 2; j <= i; ++j)
40
            base1 *= (1 - P), base2 = base2 * (1 - P) + P * dp[cur ^ 1][j - 1],
41
            K += base1, B += base2;
42
        dp[cur][1] = (1 - B) / K;
43
        for(int j = 2; j <= i; ++j)
44
            dp[cur][j] = (1 - P) * dp[cur][j - 1] + P * dp[cur ^ 1][j - 1];
45
        cur ^= 1;
46
    }printf("%.10Lf\n", dp[cur ^ 1][K]);
47
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
48
    return 0;
49
}
50

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

UPD

update-2023_02_25 初稿