讲讲这题的几种做法：

暴力匹配法

rt，暴力匹配，即把字符串存起来一位一位判相等

时间复杂度$ O(n^2·m) $

再看看数据范围

$n\le10^5,m\le10^3$

当场爆炸。当然有暴力分

代码（20pts）：

#include <bits/stdc++.h>

using namespace std;

char c[100001][1001];

bool pd(int x, int y)

{

	int l1 = strlen(c[x]), l2 = strlen(c[y]);

	if(l1 != l2) return 0;

	for(int i = 0; i < l1; i++)

	{

		if(c[x][i] != c[y][i]) return 0;

	}

	return 1;

}

int main()

{

	int n;

	cin >> n;

	int ans = n;

	for(int i = 1; i <= n; i++)

	{

		cin >> c[i];

		for(int j = 1; j < i; j++)

		{

			if(pd(i, j)) ans--;

		}

	}

	cout << ans;

	return 0;

}

好漂亮呀

不要问我为什么WA了，我也没想调

string法

比较正常的方法

思路就是把所有串存下来，用string自带的运算符（大于等于小于）进行字典序排序

然后按照字典序判断是否重复即可

时间复杂度嘛

$O(n·logn)$的，可以卡过

代码（100pts）：

#include <bits/stdc++.h>

using namespace std;

string s[10001];

int main()

{

	int n;

	cin >> n;

	for(int i = 1; i <= n; i++)

	{

		cin >> s[i];

	}

	sort(s + 1, s + n + 1);//因为string自带大于和小于所以不用cmp

	int ans = n;

	for(int i = 1; i < n; i++)

	{

		if(s[i] == s[i + 1]) ans--;

     		//若两个字符串相同则他们的字典序一定是相邻的

	}

	cout << ans;

	return 0;

}

C++STL法

我们当然可以用万能的STL做啦~

先来思考：我们判断一个数字是否重复是什么方法呢？

当然是bool used[1001] 啦

而这题要求判断的是字符串怎么办

把数组下标弄成string类型呗

请出主角：map

简单来讲，我们在定义数组时，只能确定数组中数的类型（比如char、bool、int、long long等等），而下标类型是固定的，即整数型

然而map可以确定这两个类型，也就是说，我们甚至可以把字符串作为下标，数字作为基本类型，来一个“反数组”(别问我反数组是啥，字面意思)

（那是不是要写成$a_{interesting} = 3$了）

那么结合上上上上上上上句话，这题就可做啦！

时间复杂度不明反正能过就是了

代码（100pts）：

#include <bits/stdc++.h>

using namespace std;

map < string , bool > m;//定义一个以string类型为下标的bool数组

string s;

int main()

{

	int n;

	cin >> n;

	int ans = n;

	for(int i = 1; i <= n; i++)

	{

		cin >> s;

		if(m[s]) ans--;

		else m[s] = 1;

	}

	cout << ans;

	return 0;

}

比暴力短

HASH法

不要问为什么是最后，你见过哪个游戏让你一开始就打BOSS的？

这个和C++STL法有异曲同工之妙说反了吧

既然字符串当不了下标，我们就把字符串转成数字嘛。

具体请看那个有几百个赞的dalao的题解吧（orz@_皎月半洒花%%%%%%）

代码（单hash，100pts）：

#include <bits/stdc++.h>

#define ull unsigned long long

using namespace std;

ull base = 131;

ull a[100001];

char c[10001];

ull hashe(char s[])

{

	int l = strlen(s);

	ull ans = 0;

	for(int i = 0; i < l; i++)

	{

		ans = (ans * base + (ull)(s[i])) % 200408020617;

	}

	return ans;

}

int main()

{

	int n;

	cin >> n;

	for(int i = 1; i <= n; i++)

	{

		cin >> c;

		a[i] = hashe(c);

	}

	sort(a + 1, a + n + 1);

	ull ans = 1;

	for(int i = 1; i < n; i++)

	{

		if(a[i] != a[i + 1]) ans++;

	}

	cout << ans;

	return 0;

}

注：模数只写阳历生日太短会被卡？那就把女朋友的阴历生日加在后面鸭

巴特西

题解 Luogu P3370

暴力匹配法

string法

C++STL法

HASH法

最新文章

热门文章