首页 > 代码库 > COGS 788. 昵称
COGS 788. 昵称
788. 昵称
★☆ 输入文件：nickname.in 输出文件：nickname.out 简单对比
时间限制：1 s 内存限制：128 MB
【问题描述】
ZSUQ送信者与腾讯QQ相似。每个用户需要为自己起一个昵称。不同的用户有不同的昵称。一些普通的名字像“Tom”、“Marry”和“Kate”会经常被用到。最近的一次调查中，ZSUQ公司发现有超过5000个独特的昵称正在被使用。
作为一个ZSUQ公司的成员，你需要写一个报告，每一个昵称有多少个用户。你用于一个所有用户昵称的完整清单。注意昵称是不分大小写的。
【输入格式】
文件第一行包括所有整形数据表示测试数据的个数。
在每组测试数据中，第一行有一个整数N（0<n≤100000），下面n行描述n个用户的昵称。每个昵称不超过100个字符。两个测试数据之间有空行。< p="">
【输出格式】
对于每组测试数据，给出一个独特昵称的清单。每一行，后面有一个空格，数字表示有这个昵称的用户个数。名称按字母序，每一行的开头或结尾没有空格。昵称都是小写字母，每两组数据间有空行。
【输入样例】
输入文件名： nickname.in
1
4
carp
inkfish
peipei
carp
输出文件名： nickname.out
carp 2
inkfish 1
peipei 1
trie树模版
屠龙宝刀点击就送
#include <algorithm>#include <cstring>#include <cstdio> using namespace std;struct node { int pos; node * next[30];}*root;struct nicheng{ char nc[205]; int num; bool operator<(nicheng a)const { int l=0;while(nc[l]==a.nc[l]) l++; return nc[l]<a.nc[l]; }}yh[100005];node *create(){ node *rt=new node; rt->pos=0; memset(rt->next,0,sizeof(rt->next)); return rt; }int T;void ins(int po,char *a){ char *q=a; node *p=root; while(*q) { int id=*q-‘a‘+1; if(p->next[id]==NULL) p->next[id]=create(); p=p->next[id]; q++; } p->pos=po;}int search(char *a){ char *q=a; node * p=root; while(*q) { int id=*q-‘a‘+1; if(p->next[id]==NULL) return 0; p=p->next[id]; q++; } return p->pos;}int main(){ freopen("nickname.in","r",stdin); freopen("nickname.out","w",stdout); scanf("%d",&T); for(int n;T--;) { scanf("%d",&n); int tot=0;root=create();memset(yh,0,sizeof(yh)); for(int i=1;i<=n;i++) { scanf("%s",yh[++tot].nc); for(int i=0;i<strlen(yh[tot].nc);i++) if(‘A‘<=yh[tot].nc[i]&&yh[tot].nc[i]<=‘Z‘) yh[tot].nc[i]+=32; int pos=search(yh[tot].nc); if(!pos) { ins(tot,yh[tot].nc); yh[tot].num=1; } else yh[pos].num++,--tot; } sort(yh+1,yh+1+tot); for(int i=1;i<=tot;i++) printf("%s %d\n",yh[i].nc,yh[i].num); } return 0;}
COGS 788. 昵称
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。