模拟赛题讲解[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);
}