专栏文章

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

llinjinkun
P12024题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minjmsgr
此快照首次捕获于
2025/12/02 03:29
3 个月前
此快照最后确认于
2025/12/02 03:29
3 个月前
查看原文
这是我第一次 AK 铜组！！！
首先根据长方形与正方形的启迪，可以想到在确定了 i,ki,k 后 j=⌊i+k2⌋j = \lfloor \frac{i+k}{2} \rfloor 左右肯定是最优的，那么 jj 和 kk 肯定是一个越小越好，一个越大越好，所以预处理三个数组，一个表示一个字母 xx 在 ii 之前最晚出现的下标，另一个表示一个字母 xx 在 ii 之后最早出现的下标，最后一个表示字母 xx 出现的所有下标排序后的结果，那么枚举 i,ki,k 分别为什么字母，然后二分出左右端点，再来一个二分找出 i+k2\frac{i+k}{2} 的近似位置（就是第一个大于等于 i+k2\frac{i+k}{2} 的数的下标）。
本题还有坑点，就是这个位置不一定最优，设它为 j′j'，那么还得看 j′−1j'-1 是否更优。同时，如果 j′j' 不存在，显然直接拿右端点最优。
赛时代码：
CPP
#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;
}
跑的挺慢的。
稍微优化了一下：
CPP
#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。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...