Shelter
0%

2022牛客多校训练营09

发表于 更新于
详细题解 我与队友一起在比赛 2022牛客多校训练营09 完成的题目

A-Car Show

来源: 牛客多校训练营9 算法: 双指针, 模拟 题目链接: https://ac.nowcoder.com/acm/contest/33194/A 补完: Yes 完成时间: August 16, 2022

题目链接

题意简述

有\(n\)个城市，\(m\)种汽车，对第\(i\)个城市，第\(T_i\)种的汽车最受欢迎。选择连续的区间，让编号区间内的城市一起办汽车展，均展示本城市最受欢迎的汽车。要求每种汽车都出现，求满足条件的区间总数。\(m\)和\(n\)的范围在\(1e5\)内。

题目分析

根据题意，\([1,m]\)内所有数字都出现的区间是有效的区间。

怎么判断数字是否都出现呢？

根据数据范围，汽车种类编号在\(1e5\)以内，这意味着我们可以直接使用一个访问数组进行类似桶排序的操作来统计目前遍历的区间的各个种类的数量，再另外使用一个计数变量来记录目前共有多少种不同的汽车在区间内出现。即遍历新的区间成员时，访问数组若为\(0\)，则这是一个新的汽车，计数变量值\(+1\)，否则值不变。当计数变量为\(m\)，这段区间合法。

\(1e5\)的范围显然不支持暴力遍历所有的区间。然而我们需要遍历所有的区间吗？

显然是没有必要的。

有效区间只要求了数字均出现，而没有其他的附加要求。这意味着如果有一个区间\([l,r]\)是合法区间，那么\([l-i,r+j]\)一定也是合法的区间，i和j是使得区间在总区间范围内的所有非负整数。

如果我们固定了左节点\(l\)，就意味着找到一个最小的\([l,r]\)是合法区间后，\([l,r+i]\)均合法，一直到右节点\(=n\)为止。总共的区间数量就是\(n-j+1\)，直接计算即可。

也就是说，我们使用一个双指针型结构来找到对于每个左节点而言最小的满足区间有效的右节点即可。

操作起来也就是，标记左节点，右节点不断向下遍历，过程中更新访问数组，直到计数变量等于\(m\)，这就是一个合法的区间，统计答案。找到合法区间之后，先尝试直接右移动左节点，暂时不移动右节点。

如果计数变量没有变化，这就是对新的左节点而言的解。（由于一找到合法区间右节点就停滞，所以最后加入的这个右节点在的数值是前面区间范围内都没出现的，对构成合法答案是必不可少的。故而不存在左移右节点仍然合法的情况。）可以继续右移左节点进行下一次尝试。

如果计数变量变小，这意味着上一个左节点退出区间之后，它关联的节点值不存在了，那么就需要继续向右移动右节点找到这个关键的数字，让区间内的种类再回到\(m\)。

右节点到了尽头\(n\)，如果条件不满足，那就可以直接跳出循环了：\([l,n]\)已经不是合法区间了，\([l-i,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
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<stdio.h>
using namespace std;
int vis[100010]={0};
int t[100010];
inline int read(){
	int x=0;
	char c=getchar();
	int flag=1;
	while(c<'0'||c>'9')if(c=='-')flag=0,c=getchar();
	while(c>='0'&&c<='9'){
		x=x*10+(c-'0');
		c=getchar();
	}
	if(flag==1)
	return x;
	else return x*(-1);
}

int main(){
	int n=read(),m=read();
	
	for(int i=1;i<=n;i++){
		t[i]=read();
	}
	int head=1;
	int cnt=0;
	long long ans=0;
	int i=1;
	while(n-head+1>=m&&i<=n){
		if(vis[t[i]]==0) cnt++;
		vis[t[i]]++;
		if(cnt==m){
			ans+=n-i+1;//区间数计入答案贡献
			while(true){
				vis[t[head]]--;//原先的左节点退出区间
				head++;
				if(vis[t[head-1]]==0){
					cnt--;//区间里没有原来的值了，种类计数更新
					i++;//右节点往下遍历，找到这个值来补充
					break;
				}
				else{
					ans+=n-i+1;//仍然满足直接计入答案
				}
			}
		}
		else i++;
	}
	cout<<ans;
	return 0;
}

B-Two Frogs

来源: 牛客多校训练营9 算法: 动态规划, 差分 题目链接: https://ac.nowcoder.com/acm/contest/33194/B 补完: Yes 完成时间: August 15, 2022

题解

给\(n\)片荷叶, 每片有最大跳远距离\(a_i\), 从\(荷叶i\)起跳可以到达\(荷叶i+1~荷叶i+a_i\).

Alice和Bob从\(荷叶1\)开始, 目的地是\(荷叶n\), 问到达时步数相同的概率.

设\(dp[i][j]\)为走了\(i\)步后到达\(荷叶j\)的概率,

显然以相同步数到达\(荷叶n\)时的概率平方和即为答案.

\[ ans=\sum_{i=1}^{n-1} dp[i][n] \]

从\(荷叶i\)起跳可以到达\(荷叶i+1\sim荷叶i+a_i\), 则跳到每片荷叶的概率有\(\frac1{a_i}\).

题目保证\(1≤a_i≤n-i\), 故每片荷叶都有机会向后跳, 最大只能跳到\(荷叶n\).

故每片荷叶都对其后的荷叶有贡献, \(荷叶i\)对\(荷叶i+1\sim荷叶i+a_i\)有贡献\(\frac1{a_i}\).

遍历每片荷叶计算其贡献复杂度为\(n^3\), 最大走\(n-1\)步, 第\(i\)步最近从第\(i\)片开始.

1
2
3
4
5
6
7
for (int i = 1; i < n; i++) {
        for (int j = i; j < n; j++) {
            for (int k = j+1; k <= j+a[j] && k < n; k++) {
                dp[i][k] += dp[i-1][j]*(1/a[j]);
            }
        }
    }

使用差分前缀和优化成\(n^2\)

1
2
3
4
5
6
7
8
9
10
for (int i = 1; i < n; i++) {
        for (int j = i; j < n; j++) {
            ll temp = mul(dp[i-1][j],Div(1,a[j]));
            dp[i][j+1]      +=  temp);
            dp[i][j+a[j]+1] += -temp);
        }
        for (int j = i; j <= n; j++) {
            dp[i][j] += dp[i][j-1]);
        }
    }

计算过程中经常重复计算\(\frac 1 {a_i}\), 使用快速幂计算逆元也会TLE, 提前记忆化储存优化.

题解

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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll P = 998244353;
const int MAXN = 8005;
int n;
int a[MAXN];
ll inv[MAXN];
ll dp[MAXN][MAXN];//概率=dp[步数][位置]

ll add(ll a, ll b){
    return (a + b) % P;
}
ll sub(ll a, ll b){
    return (a - b + P) % P;
}
ll mul(ll a, ll b){
    return (a * b) % P;
}
ll qpow(ll a, ll n) {
    ll ans = 1;
    while (n) {
        if (n & 1) ans = mul(a, ans);
        a = mul(a,a);
        n >>= 1;
    }
    return ans;
}
ll Div(ll a, ll b){
    return mul(a, inv[b]);
}

void solve() {
    cin>>n;
    for (int i = 1; i < n; i++) {
        cin>>a[i];
        inv[a[i]] = qpow(a[i],P-2);
    }
    ll ans = 0;
    dp[0][1] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = i; j < n; j++) {
            ll temp = mul(dp[i-1][j],Div(1,a[j]));
            dp[i][j+1]      = add(dp[i][j+1]     ,  temp);
            dp[i][j+a[j]+1] = add(dp[i][j+a[j]+1], -temp);
        }
        for (int j = i; j <= n; j++) {
            dp[i][j] = add(dp[i][j], dp[i][j-1]);
        }
        ans = add(ans, mul(dp[i][n],dp[i][n]));
    }
    cout<<ans<<"\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}