题解 CF44A 【Indian Summer】

前言

雾( 为什么要把它们看成两个字符串？

不就多了个空格吗？

这题目其实可以把一行当成一个字符串，反正空格又不会变化。

分析

这题目其实 map 可以过，如果不知道 map 那么请自行百度。

STL大法就是好！

Code

#include <iostream>
#include <cstdio>
#include <map> 
//注意要加上头文件 #include <map> ！
using namespace std;
map <string,bool> s;
// map 定义为：下标是字符串，里面存的是布尔类型的值。
int n,ans;
string s1;
//其它的变量不多说。
int main() {
	scanf("%d",&n);
   //读入 n 。
	getline(cin,s1);
   //至关重要，如果说你前面读入了一个n，那么有个换行符还没有读入。
	for (int i=1; i<=n; i++) {
		getline(cin,s1);
        //真正开始读入字符串。
		if (!s[s1]) {//如果没有遇到过。
			s[s1]=1;//那么标记为真，并且答案+1。
			ans++;
		}
	}
	printf("%d\n",ans);
   //输出答案
	return 0;
}

分析2

以为这样子就结束了吗？没有，其实还有另一种做法： hash (哈希)！

hash 就是将一个字符串改为一串数字的神奇方法，重点是：它的速度可能比 map 还要快！

Code

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const long long Mod=100000007;
int n,ans;
string s1;
bool s[Mod+10];
// Mod 限制长度取模，s为 hash 表
int Hash()
{
	long long ans0=1,len=s1.size();//ans表示算出来的 hash 值，注意要开 long long 因为计算过程中，有可能会爆 int 。
	for (int i=0;i<len;i++)
	{
		ans0=(ans0*2+(s1[i]+'F')*233)%Mod;
     // hash 搅拌机开始，如果不理解 hash 的请自行百度。
	}
	return ans0%Mod;//最后取个模。
}
int main() {
	scanf("%d",&n);
	getline(cin,s1);
	for (int i=1; i<=n; i++) {
		getline(cin,s1);
		if (!s[Hash()]) {
			s[Hash()]=1;
			ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
   //上面的主程序也不多说。
}

写在后面的话

我这篇题解如果有错误，那么请在评论区里留言，我将会很感谢反映的人。

最后，宣传一下我的两个 blog 洛谷的 ，自己的，记得来玩哦！

谢谢观赏！