题解 P4503 【[CTSC2014]企鹅QQ】

· · 题解

题意

给定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