题解：[USACO25 Open Bronze]It s Mooin Time III

发表于 分类于 ， ， 本文字数： 1k 阅读时长 ≈ 4 分钟
\[USACO25 Open Bronze\]It s Mooin Time III 的题解

分析

首先, j 一定要靠近 i 和 k 的中点, 这个值才会更大. 考虑枚举 i 和 j 分别对应的字符 c1 和 c2, 找到 l 后第一个 c1 作为 i, r 前第一个 c2 作为 k, 然后在中间找到合适的 j 使得 j 对应字符为 c2.

于是我们有两种预处理方案:

  1. 用 vector 存储每一个字符在字符串中出现的下标. 通过二分确定 i 和 k, 然后 j 可能在 mid 做左边也可能在 mid 右边, 二分找到这两个可能的 j 找出最大贡献维护答案. 显然 mid 左右的 j (若二者均有) 在 vector 中是连续的. 这中方法的时间复杂度为 $O(QK^2 \times 4\log_2{N})$, 其中 $K=26$. 模拟赛想到了这种解法, 能过洛谷, COGS 一半分, USACO 过不了后两个点. 由于 j 是连续的, 可以优化成 $O(QK^2 \times 3\log_2{N})$, 加上关同步流和 endl 改为 \n 后, COGS 也成了过不了后两个点.
  2. 预处理 pre[i][j] 表示在 i 前的第一个字符 j 的下标, nxt[i][j] 表示在 i 后的第一个字符 j 的下标. 然后可以省一个二分. 这种做法我没写, 但是理论上能完全通过此题. 时间复杂度为 $O(QK^2)$.

现在是 yzy 大佬提出的最快解法. 采取 2. 的预处理方式. 直观的感受一下, 如果 j 和 k 都是定的, i 一定比 i+1 更优 (在合法的情况下). 因此, 我们尽量让 i 更靠近 l, 最好就是 l. 什么情况下 i 不能是 l? 若我么已经确定答案就是 (i,j,k), 也就是 j 的字符又恰好和 l 一样, 那么我们的 i 一定是 l 后字符第一个与之不同的下标. 所以我们先找到这个最近不同的下标 p, 然后枚举 k 的字符, 找到 k 的下标. 如果这个 k 的字符与 l 的字符不同, 那么 i=l, 否则 i=p. 然后算出 mid, 还是两个 j, 取最大值贡献答案即可.

参考代码

二分做法

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int>ve[27];
long long solve(int j,int l,int r,int i,int k){
    if(j>r||j<l) return -1;
    if(j==k) return -1;
    if(!(i<j&&j<k)) return -1;
    return (long long)(j-i)*(k-j);
}
int main(){
//    freopen("Time.in","r",stdin);
//    freopen("Time.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    s=" "+s;
    for(int i=1;i<=n;i++){
        ve[s[i]-'a'].push_back(i);
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        long long ans=-1;
        for(int c1=0;c1<26;c1++){
            auto i=lower_bound(ve[c1].begin(),ve[c1].end(),l);
            if(i==ve[c1].end()) continue;
            int pi=*i;
            if(pi>r-2) continue;
            for(int c2=0;c2<26;c2++){
                if(c1==c2||ve[c2].size()<2) continue;
                auto k=upper_bound(ve[c2].begin(),ve[c2].end(),r);
                if(k==ve[c2].begin()) continue;
                k--;
                int pk=*k;
                if(pk<=pi+1) continue;
                
                int mid=(pi+pk)/2;
                auto j1=lower_bound(ve[c2].begin(),ve[c2].end(),mid);
                //auto j2=upper_bound(ve[c2].begin(),ve[c2].end(),mid);
                if(j1!=ve[c2].end()) ans=max(ans,solve(*j1,l,r,pi,pk));
                if(j1!=ve[c2].begin()){
                    j1--;
                    ans=max(ans,solve(*j1,l,r,pi,pk));
                }
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

快解法

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
#include<iostream>
using namespace std;
const int N=1e5+5;
int pre[N][26],nxt[N][26];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    string s;
    cin>>n>>q>>s;
    s=" "+s;
    for(int i=1;i<=n;i++){
        for(int j=0;j<26;j++){
            pre[i][j]=pre[i-1][j];
        }
        pre[i][s[i]-'a']=i;
    }
    for(int i=n;i>=1;i--){
        for(int j=0;j<26;j++){
            nxt[i][j]=nxt[i+1][j];
        }
        nxt[i][s[i]-'a']=i;
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        int cl=s[l]-'a',pl=N;
        for(int i=0;i<26;i++){
            if(nxt[l][i]&&nxt[l][i]<=r&&i!=cl) pl=min(pl,nxt[l][i]);
        }
        long long ans=-1;
        for(int i=0;i<26;i++){
            int nl=l;
            if(i==cl) nl=pl;
            
            int nr=pre[r][i];
            if(nr-nl+1<3) continue;
            int mid=(nl+nr)/2;
            if(nxt[mid][i]<nr) ans=max(ans,(long long)(nxt[mid][i]-nl)*(nr-nxt[mid][i]));
            if(pre[mid][i]>nl) ans=max(ans,(long long)(pre[mid][i]-nl)*(nr-pre[mid][i]));
        }
        cout<<ans<<'\n';
    }
    return 0;
}