P2580 于是他错误的点名开始了

Seanq · 2018-08-19 19:49:10 · 题解

P2580 于是他错误的点名开始了
此题十分卡hush......
3种解法（4）：

1.hush(本蒟蒻只有60分，看来不够欧~)
顺带讲一下
字符串哈希快速入门
输入一个字符串
他的哈希方法：

sum=(sum*a+(int)x[i])%b+c//a、b、c均为自定义参数  

it's so easy!
哈希函数：

int hush(string x)
{
    int sum=0;
    for(int i=0;i<x.size();i++)
        sum=(sum*123+(int)x[i])%mod;
    return sum;
}

60分代码：

#include<iostream>
#include<map>
#include<cstdio>
#include<cstring>
using namespace std;
#define mod 10190207
int n,m;
bool used[mod]={0};
bool g[mod]={0};
int hush(string x)
{
    int sum=0;
    for(int i=0;i<x.size();i++)
        sum=(sum*123+(int)x[i])%mod+233;
    return sum;
}
int main()
{
    freopen("wrong.in","r",stdin);
    freopen("wrong.out","w",stdout);
    memset(g,0,sizeof(g));
    memset(used,0,sizeof(used));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        string x;
        cin >> x;
        int a=hush(x);
        used[a]=1;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        string x;
        cin >> x;
        int a=hush(x);
        if(used[a]==0) printf("WRONG\n");
        else
        {
            if(g[a]==1)
                printf("REPEAT\n");
            else
            {
                g[a]=1;
                printf("OK\n");
            }
        }
    }
    return 0;
} 

2.STL map
显而易见，这道题用map秒过
AC map 代码：

#include<iostream>
#include<map>
#include<cstdio>
#include<cstring>
using namespace std;
#define mod 10190207
int n,m;
bool used[mod]={0};
bool g[mod]={0};
map<string,bool> s;
map<string,bool> u;
int hush(string x)
{
    int sum=0;
    for(int i=0;i<x.size();i++)
        sum=(sum*123+(int)x[i])%mod;
    return sum;
}
int main()
{
//  freopen("wrong.in","r",stdin);
//  freopen("wrong.out","w",stdout);
    memset(g,0,sizeof(g));
    memset(used,0,sizeof(used));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        string x;
        cin >> x;
//      /*int a=hush(x);
//      used[a]=1;*/
        s[x]=1;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        string x;
        cin >> x;
//      /*int a=hush(x);
//      if(used[a]==0) printf("WRONG\n");
//      else
//      {
//          if(g[a]==1)
//              printf("REPEAT\n");
//          else
//          {
//              g[a]=1;
//              printf("OK\n");
//          }
//      }*/
        if(s[x]==0) printf("WRONG\n");
        else
        {
            if(u[x]==0)
            {
                u[x]=1;
                printf("OK\n");
            }
            else
            {
                printf("REPEAT\n");
            }
        }
    }
    return 0;
} 

方法3：显而易见，这题可以用平衡树
（ε=ε=ε=┏(゜ロ゜;)┛）

方法4（又名正解）：Trie 字典树
字典树入门
字典树是一棵多叉树
每一层的节点是一个字符
加入元素时递归操作
类似线段树构建，来一个点插入一个点
有时字典树还是十分好用的
AC Trie 字典树 代码

#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
int n,m;
string s;
int t[N][50];
int vir_t[N][50];
int cnt=1;
int vir_cnt=1;
void build(string v,int sum)
{
    for(int i=0;v[i];i++)
    {
        int x=v[i]-'a';
        if(!t[sum][x]) t[sum][x]=++cnt;
        sum=t[sum][x];
    }
}
void vir_build(string v,int sum)
{
    for(int i=0;v[i];i++)
    {
        int x=v[i]-'a';
        if(!vir_t[sum][x]) vir_t[sum][x]=++vir_cnt;
        sum=vir_t[sum][x];
    }
}
bool serch(string v,int sum)
{
    for(int i=0;v[i];i++)
    {
        int x=v[i]-'a';
        if(!t[sum][x]) return false;
        sum=t[sum][x];
    }
    return true;
}
bool vir_serch(string v,int sum)
{
    for(int i=0;v[i];i++)
    {
        int x=v[i]-'a';
        if(!vir_t[sum][x]) return false;
        sum=vir_t[sum][x];
    }
    return true;
}
int main()
{
    int num=1;
    int sum=1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin >> s;
        build(s,sum);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        cin >> s;
        if(!serch(s,sum)) printf("WRONG\n");
        else
        {
            if(!vir_serch(s,num)) 
            {
                vir_build(s,num);
                printf("OK\n");
            }
            else
            {
                printf("REPEAT\n");
            }
        }
    }
    return 0;
}