题解 CF44A 【Indian Summer】

## 前言 雾( 为什么要把它们看成两个字符串？ 不就多了个空格吗？ 这题目其实可以把一行当成一个字符串，反正空格又不会变化。 ## 分析 这题目其实 map 可以过，如果不知道 map 那么请自行百度。 STL大法就是好！ ## Code ```cpp #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 ```cpp #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 [洛谷的](https://www.luogu.com.cn/blog/dgt/solution-cf44a) ，[自己的](http://cstdios.cf/uncategorized/solution-cf44a/) ，记得来玩哦！ **谢谢观赏！**