【洛谷P4503】【CTSC2014】企鹅QQ

- 一月 14, 2020

【洛谷P4503】【CTSC2014】企鹅QQ

题目背景

PenguinQQ 是中国最大、最具影响力的 SNS（Social Networking Services）网站，以实名制为基础，为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验，满足用户对社交、资讯、娱乐、交易等多方面的需求。

题目描述

小Q 是 PenguinQQ 网站的管理员，他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析，小Q 发现同一个人注册的账户名称总是很相似的，例如 Penguin1，Penguin2，Penguin3 ……于是 小Q 决定先对这种相似的情形进行统计。

小Q 定义，若两个账户名称是相似的，当且仅当这两个字符串等长且恰好只有一位不同。例如 “Penguin1” 和 “Penguin2” 是相似的，但 “Penguin1” 和 “2Penguin” 不是相似的。而 小Q 想知道，在给定的 n 个账户名称中，有多少对是相似的。

为了简化你的工作，小Q 给你的 N 个字符串长度均等于 L ，且只包含大小写字母、数字、下划线以及 ‘@’ 共64种字符，而且不存在两个相同的账户名称。

输入格式

第一行包含三个正整数 N ，L ，S 。其中 N 表示账户名称数量，L 表示账户名称长度，S 用来表示字符集规模大小，它的值只可能为 2 或 64。

若 S 等于 2，账户名称中只包含字符 ‘0’ 和 ‘1’ 共2种字符；

若 S 等于 64，账户名称中可能包含大小写字母、数字、下划线以及 ‘@’ 共64种字符。

随后 N 行，每行一个长度为 L 的字符串，用来描述一个账户名称。数据保证 N个字符串是两两不同的。

输出格式

仅一行一个正整数，表示共有多少对相似的账户名称。

输入输出样例

输入 #1

4 3 64
Fax
fax
max
mac

输出 #1

说明/提示

4对相似的字符串分别为：Fax 与 fax，Fax 与 max，fax 与 max，max 与 mac。

测试点编号	N	L	S
1	50	10	64
2	500	100	64
3	3000	100	2
4	3000	100	64
5	30000	50	2
6	30000	50	64
7	30000	200	2
8	30000	200	64
9	30000	200	2
10	30000	200	64

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#include "bits/stdc++.h"

#define mem(x) memset((x), 0, sizeof((x)))
#define il __attribute__((always_inline))

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#if __cplusplus > 201403L
#define r
#else
#define r register
#endif

#define c const

namespace _c
{
c double pi = acos(-1.0);
namespace min
{
c int i8 = -128;
c int i16 = -32768;
c int i = -2147483647 - 1;
c ll l = -9223372036854775807LL - 1;
} // namespace min

namespace max
{
c int i8 = 127;
c int i16 = 32767;
c int i = 2147483647;
c ll l = 9223372036854775807LL;
} // namespace max
} // namespace _c

namespace _f
{
template <typename T>
inline c T gcd(T m, T n)
{
    while (n != 0)
    {
        T t = m % n;
        m = n;
        n = t;
    }
    return m;
}

template <typename T>
inline c T abs(c T &a)
{
    return a > 0 ? a : -a;
}

template <typename T>
inline T pow(T a, T b)
{
    T res = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            res = res * a;
        }
        a = a * a;
        b >>= 1;
    }
    return res;
}

template <typename T>
inline T pow(T a, T b, c T &m)
{
    a %= m;
    T res = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            res = res * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    return res % m;
}
} // namespace _f

namespace io
{
template <typename T>
inline T read()
{
    r T res = 0, neg = 1;
    char g = getchar();
    for (; !isdigit(g); g = getchar())
    {
        if (g == '-')
        {
            neg = -1;
        }
    }
    for (; isdigit(g); g = getchar())
    {
        res = res * 10 + g - '0';
    }
    return res * neg;
}
template <typename T>
inline void read(T &t)
{
    t = read<T>();
}
template <typename T>
inline void readln(c T first, c T last)
{
    for (r T it = first; it != last; it++)
    {
        read(*it);
    }
}

template <typename T>
inline void _write(T x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
    {
        _write(x / 10);
    }
    putchar(x % 10 + '0');
}
template <typename T>
inline void write(c T &x, c char &sep = ' ')
{
    _write(x);
    putchar(sep);
}
template <typename T>
inline void writeln(c T &x)
{
    write(x, '\n');
}
template <typename T>
inline void writeln(c T first, c T last, c char &sep = ' ', c char &ends = '\n')
{
    for (r T it = first; it != last; it++)
    {
        write(*it, sep);
    }
    putchar(ends);
}

#if __cplusplus >= 201103L
template <typename T, typename... Args>
void read(T &x, Args &... args)
{
    read(x);
    read(args...);
}
#endif
} // namespace io
#undef c
#undef r

const int N = 30000 + 5;
const int L = 200 + 5;

const int MOD_1 = 149;
const int MOD_2 = 137;
const int MOD_3 = 233;
const int MOD_4 = 213;

int n, l, s;
int ans = 0;
char str[L];

ull t[N], bf[N][L], bh[N][L];

inline void proc(int x)
{
    for (register int i = 1; i <= l; i++)
    {
        bf[x][i] = bf[x][i - 1] * MOD_1 + str[i];
    }
    for (register int i = l; i >= 1; i--)
    {
        bh[x][i] = bh[x][i + 1] * MOD_2 + str[i];
    }
}

int main()
{
    io::read(n, l, s);

    for (register int i = 1; i <= n; i++)
    {
        scanf("%s", str + 1);
        proc(i);
    }

    for (register int i = 1, j, now = 1; i <= l; i++, now = 1)
    {
        for (j = 1; j <= n; j++)
        {
            t[j] = bf[j][i - 1] * MOD_3 + bh[j][i + 1] * MOD_4;
        }
        sort(t + 1, t + n + 1);

        for (j = 2; j <= n; j++)
        {
            if (t[j] == t[j - 1])
            {
                ans += now;
                now++;
            }
            else
            {
                now = 1;
            }
        }
    }

    io::writeln(ans);
}

NULL2020年1月14日 19:22
GitHub: programthink/books
回复删除
回复

添加评论

搜索此博客

好文收藏夹