hdu 1251 统计难题

字典树模板题。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;//开大一点,否则RE
char s[N];
int num,cnt[N],ch[N][30];
void build(char s[])
{
    int u=0;
    for(int i=0;i<strlen(s);i++)
    {
        int x=s[i]-'a';
        if(!ch[u][x])ch[u][x]=++num;
        u=ch[u][x];
        cnt[u]++;
    }
}
int query(char s[])
{
    int u=0;
    for(int i=0;i<strlen(s);i++)
    {
        int x=s[i]-'a';
        if(!ch[u][x])return 0;
        u=ch[u][x];
    }
    return cnt[u];
}
int main()
{
    ios::sync_with_stdio(false);
    while(gets(s)&&s[0]!='
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;//开大一点,否则RE
char s[N];
int num,cnt[N],ch[N][30];
void build(char s[])
{
int u=0;
for(int i=0;i<strlen(s);i++)
{
int x=s[i]-'a';
if(!ch[u][x])ch[u][x]=++num;
u=ch[u][x];
cnt[u]++;
}
}
int query(char s[])
{
int u=0;
for(int i=0;i<strlen(s);i++)
{
int x=s[i]-'a';
if(!ch[u][x])return 0;
u=ch[u][x];
}
return cnt[u];
}
int main()
{
ios::sync_with_stdio(false);
while(gets(s)&&s[0]!='\0')//用gets处理空行,如果是空行,gets会自动把'\n'转化为'\0'
build(s);
while(gets(s)&&s[0]!='\0')printf("%d\n",query(s));
//虽然是处理到文件末尾,但是不能写成while(cin>>s),否则会WA(不知道为什么...)    
return 0;
}
')//用gets处理空行,如果是空行,gets会自动把'\n'转化为'
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;//开大一点,否则RE
char s[N];
int num,cnt[N],ch[N][30];
void build(char s[])
{
int u=0;
for(int i=0;i<strlen(s);i++)
{
int x=s[i]-'a';
if(!ch[u][x])ch[u][x]=++num;
u=ch[u][x];
cnt[u]++;
}
}
int query(char s[])
{
int u=0;
for(int i=0;i<strlen(s);i++)
{
int x=s[i]-'a';
if(!ch[u][x])return 0;
u=ch[u][x];
}
return cnt[u];
}
int main()
{
ios::sync_with_stdio(false);
while(gets(s)&&s[0]!='\0')//用gets处理空行,如果是空行,gets会自动把'\n'转化为'\0'
build(s);
while(gets(s)&&s[0]!='\0')printf("%d\n",query(s));
//虽然是处理到文件末尾,但是不能写成while(cin>>s),否则会WA(不知道为什么...)    
return 0;
}
' build(s); while(gets(s)&&s[0]!='
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;//开大一点,否则RE
char s[N];
int num,cnt[N],ch[N][30];
void build(char s[])
{
int u=0;
for(int i=0;i<strlen(s);i++)
{
int x=s[i]-'a';
if(!ch[u][x])ch[u][x]=++num;
u=ch[u][x];
cnt[u]++;
}
}
int query(char s[])
{
int u=0;
for(int i=0;i<strlen(s);i++)
{
int x=s[i]-'a';
if(!ch[u][x])return 0;
u=ch[u][x];
}
return cnt[u];
}
int main()
{
ios::sync_with_stdio(false);
while(gets(s)&&s[0]!='\0')//用gets处理空行,如果是空行,gets会自动把'\n'转化为'\0'
build(s);
while(gets(s)&&s[0]!='\0')printf("%d\n",query(s));
//虽然是处理到文件末尾,但是不能写成while(cin>>s),否则会WA(不知道为什么...)    
return 0;
}
')printf("%d\n",query(s)); //虽然是处理到文件末尾,但是不能写成while(cin>>s),否则会WA(不知道为什么...) return 0; }

hdu 1671 Phone List

给你n个字符串,如果存在一个字符串是其他某个字符串的前缀,则输出NO,否则输出YES。

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=1e5+10;
string a[N];
int t,n,num,cnt[M],ch[M][10];
bool cmp(string s1,string s2)
{return s1<s2;}
int build(string s)
{
    int u=0;
    for(int i=0;i<s.length();i++)
    {
        int x=s[i]-'0';
        if(cnt[u])return 1;
        if(!ch[u][x])ch[u][x]=++num;
        u=ch[u][x];
    }
    cnt[u]++;
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+n+1,cmp);
        memset(ch,0,sizeof(ch));
        memset(cnt,0,sizeof(cnt));
        num=0;
        int flag=0;
        for(int i=1;i<=n;i++)
        {
            int tmp=build(a[i]);
            if(tmp==1){printf("NO\n");flag=1;break;}
        }
        if(flag==0)printf("YES\n");
    }
    return 0;
}

hdu 2072 单词数

分割单词,再构造字典树即可。
注意特判 全是空格 的情况。

要注意一下输入字符串的格式。

跳过空格输入可以用 gets(a) 或者 scanf("%[^\n]",a)

while(scanf("%[^\n]",a))无法while循环,因为第一次遇到 \n 程序就停止了。

可以写 while(scanf("%[^\n]%*c",a)), 与 while(gets(a)) 等效。
%*c表示跳过一个字符,也就是把 \n 吸收掉。

也可以写 while(scanf("%[^\n]",a)),内循环加一句 getchar() 来吸收 \n 字符。

(所以说为什么不直接写gets(a)?)

关于while(scanf("%[^\n]%*c",a))输入,具体的原理可以看看这篇文章:https://blog.csdn.net/weixin_43469047/article/details/83753526

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char a[N],s[N];
int num,tot,ans,cnt[N],ch[N][30];
void build(char s[])
{
    int u=0;
    for(int i=1;i<=tot;i++)
    {
        int x=s[i]-'a';
        if(!ch[u][x])ch[u][x]=++num;
        u=ch[u][x];
    }
    cnt[u]++;
    if(cnt[u]==1)ans++;
}
int main()
{
    ios::sync_with_stdio(false);
    while(gets(a)&&a[0]!='#')//注意用gets(a),不要用scanf(" %[^\n]",a),否则会错
    {
        memset(s,0,sizeof(s));
        memset(ch,0,sizeof(ch));
        memset(cnt,0,sizeof(cnt));
        tot=0;num=0;ans=0;
        for(int i=0;i<strlen(a);i++)
        {
            if(a[i]!=' ')
            {
                s[++tot]=a[i];
                if(a[i+1]==' '||a[i+1]=='
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char a[N],s[N];
int num,tot,ans,cnt[N],ch[N][30];
void build(char s[])
{
int u=0;
for(int i=1;i<=tot;i++)
{
int x=s[i]-'a';
if(!ch[u][x])ch[u][x]=++num;
u=ch[u][x];
}
cnt[u]++;
if(cnt[u]==1)ans++;
}
int main()
{
ios::sync_with_stdio(false);
while(gets(a)&&a[0]!='#')//注意用gets(a),不要用scanf(" %[^\n]",a),否则会错
{
memset(s,0,sizeof(s));
memset(ch,0,sizeof(ch));
memset(cnt,0,sizeof(cnt));
tot=0;num=0;ans=0;
for(int i=0;i<strlen(a);i++)
{
if(a[i]!=' ')
{
s[++tot]=a[i];
if(a[i+1]==' '||a[i+1]=='\0')
{
build(s);
memset(s,0,sizeof(s));
tot=0;
}
}
}
printf("%d\n",ans);
}
return 0;
}
') { build(s); memset(s,0,sizeof(s)); tot=0; } } } printf("%d\n",ans); } return 0; }