前言

看起来很快就可以把挖的坑填完了。

打到尾声了，感觉自己距离大佬们差距真的是太大了…

今晚$CF$，希望渡劫成功。

复盘

E - Eyjafjalla

一道类似的题目：Problem - E. Party Company - Codeforces

这一题和前几场多校的某一题一样，也可以用线段树维护$Dfs$序来实现。

首先，预处理所有树上节点的$Dfs$序，并用$Dfs$序和所对应的节点的温度进行线段树建树维护最值。

然后，对于每次询问，做树上倍增，找到第一个满足$\leq R$条件的节点。由题目的单调性，知道对于目前以这个节点为根的子树，其中权值$\geq L$节点的个数就是当前询问所求数目。

最后，为了求出$\geq L$节点的个数的数目，对子树对应的$Dfs$序进行查找，返回最小值$\geq L$的区间，各个区间的元素个数的总和就是当前询问的答案。

可以作为板子，感觉写的蛮好看的这次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/* vegetable1024 | liushan.site | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
#define lson(x) (x << 1)
#define rson(x) (x << 1 | 1)
using namespace std;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
    std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
    std::cout << head << ", ";
    Print(rail...);
}

int read(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9')    ch = getchar();
    while(ch >= '0' && ch <= '9')  x = x * 10 + ch - '0', ch = getchar();
    return x;
}

struct SegTree{
    struct Node{
        int lf, rt, mx, mn;
    } tr[maxn];
    void Build(int now, int lf, int rt, int a[]){
        tr[now].lf = lf;
        tr[now].rt = rt;
        if(lf == rt){
            tr[now].mx = tr[now].mn = a[lf];
            return;
        }
        int mid = (lf + rt) / 2;
        Build(lson(now), lf, mid, a);
        Build(rson(now), mid + 1, rt, a);
        tr[now].mx = max(tr[lson(now)].mx, tr[rson(now)].mx);
        tr[now].mn = min(tr[lson(now)].mn, tr[rson(now)].mn);
    }
    int Query(int now, int lf, int rt, int k){
        if(tr[now].lf >= lf && tr[now].rt <= rt){
            if(tr[now].mn >= k){
                return tr[now].rt - tr[now].lf + 1;
            }
            else if(tr[now].mx < k){
                return 0;
            }
            else{
                return Query(lson(now), lf, rt, k) + Query(rson(now), lf, rt, k);
            }
        }
        if(tr[now].lf > rt || tr[now].rt < lf)    return 0;
        return Query(lson(now), lf, rt, k) + Query(rson(now), lf, rt, k);
    }
} mt;
int n, q, t[maxn], dfnt[maxn];
int cnt, in[maxn], out[maxn], id[maxn];
vector<int> G[maxn];

int tt, d[maxn], f[maxn][35];
void pre(int now){
    tt = (int)(log(n) / log(2)) + 1;
    queue<int> q1; q1.push(now); d[now] = 1;
    while(!q1.empty())
    {
        int x = q1.front(); q1.pop();
        for(auto nxt : G[x]){
            if(d[nxt])    continue; 
            f[nxt][0] = x;
            d[nxt] = d[x] + 1;
            for(int j = 1; j <= tt; j++){
                f[nxt][j] = f[f[nxt][j - 1]][j - 1];
            }
            q1.push(nxt);
        }
    }
}
int gettop(int x, int R){
    int now = x;
    for(int i = tt; i >= 0; i--){
        if(t[f[now][i]] <= R && f[now][i]){
            now = f[now][i];
        }
    }
    return now;
}
void dfs1(int now, int fa){
    in[now] = ++cnt;
    id[cnt] = now;
    for(auto x : G[now]){
        if(x == fa)    continue;
        dfs1(x, now);
    }
    out[now] = cnt;
}

signed main(void)
{
    n = read();
    for(int i = 1; i <= n - 1; i++){
        int u = read(), v = read();
        G[u].push_back(v), G[v].push_back(u);
    }
    for(int i = 1; i <= n; i++)    t[i] = read(); 
    pre(1);
    dfs1(1, 0);
    for(int i = 1; i <= n; i++)    dfnt[i] = t[id[i]];
    mt.Build(1, 1, n, dfnt);
    q = read();
    for(int i = 1; i <= q; i++)
    {
        int x = read(), l = read(), r = read();
        if(!(t[x] >= l && t[x] <= r))
        {
            printf("%lld\n", 0LL);
            continue;
        }
        int subrt = gettop(x, r);
        //Print(subrt, x, l, r, in[subrt], out[subrt]);
        //Print(dfnt[1], dfnt[2], dfnt[3], dfnt[4]);
        printf("%lld\n", mt.Query(1, in[subrt], out[subrt], l));
    }
    return 0;
}

H - Happy Number

签到题，类似三进制的表现方式。

最开始以为直接三进制就行，好在样例给的强

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/* vegetable1024 | liushan.site | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

int read(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9')    ch = getchar();
    while(ch >= '0' && ch <= '9')  x = x * 10 + ch - '0', ch = getchar();
    return x;
}

signed main(void)
{
    int n = read();
    vector<int> v1;
    int bas = 3;
    //while(3 * (1 - bas) / (1 - 3) < n)
    while(n > 0)
    {
        int lim = bas / 3;
        if(n % bas == 0)
            v1.push_back(3);
        else if(n % bas <= lim)
            v1.push_back(1);
        else if(n % bas <= 2 * lim)
            v1.push_back(2);
        else
            v1.push_back(3);
        n -= (n % bas) == 0 ? bas : n % bas;
        bas *= 3;
    }   
    reverse(v1.begin(), v1.end());
    for(int i = 0; i < v1.size(); i++)
    {
        if(v1[i] == 1)    putchar('1');
        if(v1[i] == 2)    putchar('4');
        if(v1[i] == 3)    putchar('7');
    }
    return 0;
}

I - Incentive Model

阅读理解题，难点主要在阅读上…

题意截图来自：2021牛客暑期多校训练营9 I题: Incentive Model_Spy_Savior的博客-CSDN博客

image-20210905201219389

然后我们可以这么分析：

设$A$在挖了第$i$块矿后，拥有的期望股权为$S_i$​。

为了方便表述，我们可以设：$S_0 = a$​，可推出$S_1 = S_0 + \frac{S_0}{a + b} \ast w, S_2 = S_1 + \frac{S_1}{a + b + w} \ast w$

为了便于化简，推出$S_i=S_{i-1} + \frac{S_{i-1} } {a + b + (i-1)w} =S_{i-1} + \frac{S_{i-1} }{1 + (i - 1)w} = \frac{(1+iw)S_{i-1} }{1+(i-1)w}$​

又有：$S_{i-1} = S_{i-2} + \frac{S_{i-2} }{1 + (i - 2)w} = \frac{(1+(i-1)w)S_{i-2} }{1+(i-2)w}$​​

即可得：$S_n = \frac{(1+wn) S_{n-1} }{1+(n-1) w} \ast \frac{(1+(n-1)w) S_{n-2} }{1+(n-2) w} \ast \dots$

推导得$S_n = (1 + wn) * a$

那么，期望获得的矿数为$ANS = \frac{S_n - a}{w} = a * n = \frac{x}{y} \ast n$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/* vegetable1024 | liushan.site | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

clock_t START_TIME, END_TIME;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
    std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
    std::cout << head << ", ";
    Print(rail...);
}

int read(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9')    ch = getchar();
    while(ch >= '0' && ch <= '9')  x = x * 10 + ch - '0', ch = getchar();
    return x;
}

int qpow(int a, int b, int p){
    if(b == 0)    return 1;
    int tmp = qpow(a, b / 2, p);
    if(b & 1)    tmp = (tmp * a) % p;
    return tmp;
}

signed main(void)
{
    const int mod = 998244353;
    int n = read(), w = read(), x = read(), y = read();
    printf("%lld\n", n * x * qpow(y, mod - 2, mod));
    return 0;
}