题解 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 洛谷的自己的 ,记得来玩哦!

谢谢观赏!


发表于 2020-02-19 12:24:23 in 题解