自动搬运

查看原文

来自洛谷，原作者为

	serverkiller Carpe Diem

搬运于2025-08-24 22:00:49，当前版本为作者最后更新于2020-02-25 08:37:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给定$n$个字符串 问两个字符串只差一个字符的字符串对的数量

solution

没错 我又来卡空间了.在Mr_zherui的题解中 使用了两个数组来储存前后的hash值之和 但是我们其实可以利用前缀和来优化成一个数组qwq

基于上述的 我写了下面这份代码 利用的是进制hash 具体的看注释吧 最主要是在求相等的时候排序可以将复杂度从$O(n^2)$降为$O(nlog_2n+n)$就比较满意了

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n,l,s;
ll ha[30005][205],t[30005],Hina[205];//记得开longlong蛤
const int p = 2333;

int main()
{
	scanf("%d%d%d",&n,&l,&s);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= l; j++)
		{
			char c;
			cin >> c;//注意cin输入的时候是过滤换行符的 而scanf是读入换行符的 被这里卡着了
			ha[i][j] = ha[i][j - 1] * p + c;
		}
	}
	Hina[0] = 1;
	for (int i = 1; i <= l; i++)
	{
		Hina[i] = Hina[i - 1] * p;
	}//这里预处理出每一位的数量
	int ans = 0;
	for (int i = 1; i <= l; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			t[j] = ha[j][l] - (ha[j][i] - ha[j][i - 1] * p) * Hina[l - i] - ha[j][i - 1] * (Hina[l - i + 1] - Hina[l - i]);
                        //去掉给第j个字符串第i位后的hash值 是整个的hash值 减掉这个位置的hash*Hina[l - i] 再减掉前面的数的hash*(Hina[l - i + 1]-Hina[l - i]) 
         		//其实可以去个括号就比较简洁了 但是我懒（
		}
		sort(t + 1,t + n + 1);//这里就是那个排序的地方啦
		int tmp = 1;
		for (int j = 1; j < n; j++)
		{
			if (t[j] != t[j + 1]) tmp = 1;
			else 
			{
				ans += tmp;
				tmp++;
			}
		}
	}
	printf("%d\n",ans);//输出答案qwq
	//system("pause");
	return 0;
}

写完这个代码没完 我们注意到$char$占$1$个字节 而$longlong$占了$8$个字节 所以我们可以保存$char$而不去保存每个位置的前缀和

因为这里进制hash去掉某一位的时候可以单单将那一位变成0而不需要将前面的数位后移 因此有了这个代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n,l,s;
ll ha[30005],t[30005],Hina[205];
char c[300005][205];
const int p = 2333;

int main()
{
	scanf("%d%d%d",&n,&l,&s);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= l; j++)
		{
			cin >> c[i][j];
			ha[i] = ha[i] * p + c[i][j];
		}
	}
	Hina[0] = 1;
	for (int i = 1; i <= l; i++)
	{
		Hina[i] = Hina[i - 1] * p;
	}
	int ans = 0;
	for (int i = 1; i <= l; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			t[j] = ha[j] - c[j][i] * Hina[l - i];
		}
		sort(t + 1,t + n + 1);
		int tmp = 1;
		for (int j = 1; j < n; j++)
		{
			if (t[j] != t[j + 1]) tmp = 1;
			else 
			{
				ans += tmp;
				tmp++;
			}
		}
	}
	printf("%d\n",ans);
	//system("pause");
	return 0;
}

这份代码的评测记录如下:

卡内存完毕x