CF718E Matvey's Birthday

一、题目

点此看题

二、解法

我自己的想法是把问题转化成 \(8\) 个点 \(n\) 条边的问题（把每个颜色看成一个点），这样看似简单实则难做，因为问题的关键是求最远点对数量，所以计数应产生在点之间而不是在颜色之间（而且这道题并不好把颜色转化到点），但是上面的思考也不是全无作用，它告诉我们答案一定不超过 \(15\)

那么考虑怎么描述两点之间的最短距离，这里我们可以以颜色为中介，首先预处理出 \(f[i][j]\) 表示点 \(i\) 到颜色 \(j\) 的距离，\(g[i][j]\) 表示颜色 \(i\) 到颜色 \(j\) 的距离，这可以从每个颜色为起点 \(\tt bfs\) 解决。然后考虑点对 \((i,j)\) 之间的大致走法，我们可以花 \(|i-j|\) 直接走，或者是枚举一个会走字符边的颜色 \(k\) 计算长度：

优化考虑去掉这个 \(\min\)，因为答案不超过 \(15\) 所以我们暴力计算 \(i-j\leq 15\) 的这些点，其他点的答案一定是 \(\min(f[i][k]+f[j][k]+1)\)，发现重要的是 \(f[j][k]\) 而不是 \(j\)，所以我们给 \(j\) 划分等价类，因为 \(g[s_j][k]\leq f[j][k]\leq g[s_j][k]+1\)，所以可以把 \(j\) 表示成一个颜色和 \(8\) 位二进制数的一个二元组，每一组的距离一定是相同的，那么时间复杂度 \(O(n\cdot 2^8\cdot 8^2)\)

三、总结

一定要注意观察答案的形式来判断思路是否可行。

当某一个东西范围很小的时候，可以考虑划分等价类来优化复杂度。

#include 
#include 
#include 
#include 
using namespace std;
const int M = 100005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,ans,c[M],f[M][8],g[8][8],o[8][256],vis[M],vc[8];
vector v[M];char s[M];queue q;long long cnt;
void upd(int w,int c)
{
	if(w>ans) ans=w,cnt=c;
	else if(w==ans) cnt+=c;
}
signed main()
{
	n=read();scanf("%s",s+1);
	for(int i=1;i<=n;i++)
		c[i]=s[i]-'a',v[c[i]].push_back(i);
	memset(f,0x3f,sizeof f);
	memset(g,0x3f,sizeof g);
	for(int i=0;i<8;i++)
	{
		memset(vis,0,sizeof vis);
		memset(vc,0,sizeof vc); 
		for(int j:v[i])
			f[j][i]=0,vis[j]=1,q.push(j);
		g[i][i]=0;vc[i]=1;
		while(!q.empty())
		{
			int u=q.front();q.pop();
			if(u>1 && !vis[u-1])
				vis[u-1]=1,f[u-1][i]=f[u][i]+1,q.push(u-1);
			if(u>k&1)+1);
				upd(d,o[j][s]);
			}
	}
	printf("%d %lld\n",ans,cnt);
}