题解：P12024 [USACO25OPEN] It's Mooin' Time III B

· · 题解

这是我第一次 AK 铜组！！！

首先根据长方形与正方形的启迪，可以想到在确定了 i,k 后 j = \lfloor \frac{i+k}{2} \rfloor 左右肯定是最优的，那么 j 和 k 肯定是一个越小越好，一个越大越好，所以预处理三个数组，一个表示一个字母 x 在 i 之前最晚出现的下标，另一个表示一个字母 x 在 i 之后最早出现的下标，最后一个表示字母 x 出现的所有下标排序后的结果，那么枚举 i,k 分别为什么字母，然后二分出左右端点，再来一个二分找出 \frac{i+k}{2} 的近似位置（就是第一个大于等于 \frac{i+k}{2} 的数的下标）。

本题还有坑点，就是这个位置不一定最优，设它为 j'，那么还得看 j'-1 是否更优。同时，如果 j' 不存在，显然直接拿右端点最优。

赛时代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
char a[N];
int s1[N][30];
int s2[N][30];
int e[30][N];
int num[30]; 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,_;
    cin >> n >> _ >> a+1;
    for(int i = 1;i<=n;i++)
    {
        for(int j = 0;j<=25;j++)
        {
            s1[i][j] = s1[i-1][j];
        }
        s1[i][a[i]-'a'] = i;
    }
    for(int i = n;i;i--)
    {
        for(int j = 0;j<=25;j++)
        {
            s2[i][j] = s2[i+1][j];
        }
        s2[i][a[i]-'a'] = i;
    }
    for(int i = 1;i<=n;i++)
    {
        e[a[i]-'a'][++num[a[i]-'a']] = i;
    }
    while(_--)
    {
        int x,y;
        cin >> x >> y;
        long long maxx = -1;
        for(int i = 0;i<=25;i++)
        {
            for(int k = 0;k<=25;k++)
            {
                if(i!=k&&s2[x][i]<=y&&s1[y][k]>=x&&s2[x][i]<s1[y][k]&&s2[x][i]&&s1[y][k])
                {
                    int l = 1,r = num[k],sum1 = 0;
                    while(l<=r) 
                    {
                        int mid = l+r>>1;
                        if(e[k][mid]<=s2[x][i])
                        {
                            sum1 = mid;
                            l = mid+1;
                        }
                        else
                        {
                            r = mid-1;
                        }
                    }
                    l = 1,r = num[k];
                    int sum2 = 0;
                    while(l<=r) 
                    {
                        int mid = l+r>>1;
                        if(e[k][mid]<=s1[y][k]-1)
                        {
                            sum2 = mid;
                            l = mid+1;
                        }
                        else
                        {
                            r = mid-1;
                        }
                    }
                    int j1 = 0;
                    l = sum1+1,r = sum2;
                    while(l<=r)
                    {
                        int mid = l+r>>1;
                        if(e[k][mid]>=(s2[x][i]+s1[y][k])/2)
                        {
                            j1 = mid;
                            r = mid-1;
                        }
                        else
                        {
                            l = mid+1;
                        }
                    }
                    if(j1 == 0)
                    {
                        int j = e[k][sum2];
                        maxx = max(maxx,(long long)(j-s2[x][i])*(long long)(s1[y][k]-j));
                        continue;
                    }
                    for(int o = max(sum1+1,j1-1);o<=j1;o++)
                    {
                        int j = e[k][o];
                        maxx = max(maxx,(long long)(j-s2[x][i])*(long long)(s1[y][k]-j));
                    }
                }
            }
        }
        cout << maxx << '\n';
    }
    return 0;
}

跑的挺慢的。

稍微优化了一下：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
char a[N];
int s1[N][30];
int s2[N][30];
int e[30][N];
int num[30];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,_;
    cin >> n >> _ >> a+1;
    for(int i = 1;i<=n;++i)
    {
        for(int j = 0;j<=25;++j)
        {
            s1[i][j] = s1[i-1][j];
        }
        s1[i][a[i]-'a'] = i;
    }
    for(int i = n;i;i--)
    {
        for(int j = 0;j<=25;++j)
        {
            s2[i][j] = s2[i+1][j];
        }
        s2[i][a[i]-'a'] = i;
    }
    for(int i = 1;i<=n;++i)
    {
        e[a[i]-'a'][++num[a[i]-'a']] = i;
    }
    while(_--)
    {
        int x,y;
        cin >> x >> y;
        long long maxx = -1;
        for(int i = 0;i<=25;++i)
        {
            for(int k = 0;k<=25;++k)
            {
                if(i!=k&&s2[x][i]<=y&&s1[y][k]>=x&&s2[x][i]<s1[y][k]&&s2[x][i]&&s1[y][k])
                {
                    int sum1 = upper_bound(e[k]+1,e[k]+num[k]+1,s2[x][i])-e[k],sum2 = lower_bound(e[k]+1,e[k]+num[k]+1,s1[y][k])-e[k]-1;
                    if(sum1>num[k])
                    {
                        continue;
                    }
                    int j1 = lower_bound(e[k]+sum1,e[k]+sum2+1,s2[x][i]+s1[y][k]>>1)-e[k];
                    if(j1>sum2)
                    {
                        int j = e[k][sum2];
                        maxx = max(maxx,1ll*(j-s2[x][i])*(s1[y][k]-j));
                        continue;
                    }
                    int j = e[k][max(sum1,j1-1)];
                    maxx = max(maxx,1ll*(j-s2[x][i])*(s1[y][k]-j));
                    if(j!=j1)
                    {
                        j = e[k][j1];
                        maxx = max(maxx,1ll*(j-s2[x][i])*(s1[y][k]-j));
                    }
                }
            }
        }
        cout << maxx << '\n';
    }
    return 0;
}

跑得更快了。

原来手写二分不如 upper_bound 和 lower_bound。