2021牛客多校第九场复盘

前言

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

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

今晚$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;
}
如果你觉得还不错,就请咕咕的作者喝杯咖啡吧QAQ