模拟赛题讲解[13]

来自 yukuai26 2022-08-06 noi.ac #2757

据说是从JOI搬过来的，赛时有位巨佬18min就A了 Orz

题目描述：

橙 —— 作为幽幽子大人的朋友的使者, 非常贪玩, 也喜欢思考有趣 的问题。

她在冥界思考一个有趣的问题, 希望赶到的灵梦能够解答。

一个字符串由 $\tt{a,b,c}$三种字母组成, 它最多能分成多少个 $\tt{abc}$ 和 $\tt{cbc}$ 的子序列呢?

具体的, 一个字符串 $str$ 可以由选择 $3$ 个位置 $i < j < k$ 使得 $s_i,s_j,s_k$ 依次连接组成 $\tt{abc}$ 或 $\tt{cbc}$ ，

这样算分出一个字符串, 接着把 $3$ 个位置上的字母删掉, 剩下的字母重新组成新的字符串并接着提取。

输入格式：

第一行一个正整数 $n$ 表示字符串的长度

接下来一个长度为 $n$ 的字符串, 保证由 $\tt{a,b,c}$ 组成

输出格式：

一行一个数，表示最大能分成的个数

输入1：

6
abcbcc

输出1：

2

输入2：

5
abcbb

输出2：

1

数据范围：

打包测试

对于测试包 $1$，分值 $40$ 分，$n \leq 15$

对于测试包 $2$，分值 $30$ 分，$n \leq 50$

对于测试包 $3$，分值 $20$ 分，$n \leq 3000$

对于测试包 $4$，分值 $10$ 分，$n \leq 10^6$

题解：

Subtask 1 40pts

注意到 $\tt{c}$ 可以作为结尾，也可以作为开头

考虑对于所有的 $\tt{c}$ 暴搜他作为第一个还是第三个

如果是第一个就变成 $\tt{a}$ ，计算即可。

Subtask 2 30pts

考虑从后往前做

设 $f_{i,j,k}$ 表示最后 $i$ 位，有 $j$ 个 $\tt{bc}$ ，$k$ 个 $\tt{c}$ ，最多能有多少 $\tt{abc}$ 或 $\tt{cbc}$ ，转移 $O(1)$。

Subtask 3 20pts

把所有作为 $\tt{abc}$ 和 $\tt{cbc}$ 末尾的 $\tt{c}$ 放在原串的最后面

具体地，如果串里面出现了

$$\tt{a\dots b\dots c \dots c \dots b \dots c \dots}$$

我们强制做如下匹配

$$\tt{\color{red}{a} \,\color{black}{\dots} \, \color{red}{b} \,\color{black}{\dots} \, \color{blue}{c} \,\color{black}{\dots}\, \color{red}{c} \,\color{black}{\dots}\, \color{blue}{b}\, \color{black}{\dots} \, \color{blue}{c}\, \color{black}{\dots}}\,$$

这样的好处在于，对于合法的方案，一定存在一个分界线，满足：

• 分界线左侧的所有 $\tt{c}$ 均可以看作 $\tt{a}$
• 分界线右侧仅由 $\tt{bc}$ 构成，并且与分界线左侧每个 $\tt{a/c}$ 两两配对

考虑枚举这个分界线，时间复杂度 $O(n^2)$

Subtask 4 10pts

注意到如果右侧的 $\tt{bc}$ 不够了，分界线理应往左移

如果左侧的 $\tt{c}$ 过多了，分界线理应往右移

实际上是存在单调性的。考虑二分分界线。

时间复杂度 $O(n \log n)$ ，可以通过此题

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e6+15)

int n;
bool vis[N];
char s[N];
bool check(int mid)
{
    for(int i=1; i<=n; i++) vis[i]=0;
    int cnt_a=0,cnt_b=0,cnt_c=0;
    for(int i=n; i>=1; i--)
    {
        if(s[i]=='c'&&cnt_c<mid) vis[i]=1,++cnt_c;
        else if(s[i]=='b'&&cnt_b<cnt_c) vis[i]=1,++cnt_b;
    }
    if(cnt_b < mid)return 0;
    cnt_a=cnt_b=0;
    for(int i=n; i>=1; i--)
    {
        if(s[i]=='b'){if(vis[i]) ++cnt_b; else continue;}
        else if(!vis[i] && cnt_a < cnt_b) ++cnt_a;
    }
    return cnt_a==mid;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> (s+1);
    int l=0,r=n/3,mid;
    while(l<r)
    {
        mid=(l+r+1) >> 1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout << l << '\n';
    return 0;
}

Extra 更快的解法

时间复杂度 $O(n)$ ，目前q779还不会，因此把老师的题解搬过来了

O(n)
考虑从后往前做，记录bc和c的个数
对于已经有bc时出现c的情况，先匹配成cbc，并记录这个c的位置
对于没有c并且出现b的情况，也记录这个b的位置
这时出现a并且没有bc，我们考虑反悔操作，把前面的cbc拆开变成abc，这时候会多出一个c，根据前面记录的b的位置与c的位置视情况会多出一个c或者bc

老师的代码：

#include<bits/stdc++.h>
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define ll long long
using namespace std;
const int N=1000005;
int n,ans;
char s[N];
int f[N][3];
int g[N][3];
int main(){
	scanf("%d%s",&n,s+1);
	For(i,1,n){
		For(j,0,2) f[i][j]=f[i-1][j];
		if (s[i]=='a'||s[i]=='c') ++f[i][0];
		else if (f[i][0]) --f[i][0],++f[i][1];
	}
	Rep(i,n,1){
		For(j,0,2) g[i][j]=g[i+1][j];
		if (s[i]=='c') ++g[i][0];
		else if (s[i]=='b'){
			if (g[i][0]) --g[i][0],++g[i][1];
		}
		else{
			if (g[i][1]) --g[i][1],++g[i][2];
		}
	}
	For(i,0,n){
		int sum=g[i+1][2],v;
		v=min(f[i][0],g[i+1][1]);
		sum+=v; f[i][0]-=v; g[i+1][1]-=v;
		v=min(f[i][1],g[i+1][0]);
		sum+=v; f[i][1]-=v; g[i+1][0]-=v;
		v=min(f[i][1],g[i+1][1]);
		sum+=v; f[i][1]-=v; g[i+1][1]-=v;
		ans=max(ans,sum);
	}
	printf("%d\n",ans);
}