赞
踩
利用字符串公共前缀建树
输入:
3
asd
asdf
asdff
as
asdf
asdff
sd
输出:
3
2
1
0
#include <bits/stdc++.h> using namespace std; const int maxn=1e6+10; int sum[maxn]={0}; int trie[maxn][26]; char s[15]; int pos=1; void add() //插入 { int c=0;//c=1; for(int i=0;s[i];i++) { int x=s[i]-'a'; if(trie[c][x]==0) //没出现过就增加一个结点 trie[c][x]=pos++; c=trie[c][x]; //下一个结点//若初始c=1:c=trie[c][x]+1 sum[c]++; //更新前缀出现次数 } } void query() //查找 { int c=0;//c=1; for(int i=0;s[i];i++) { int x=s[i]-'a'; if(trie[c][x]==0) { //找不到说明没出现过 printf("0\n"); return; } c=trie[c][x]; //下一个结点//若初始c=1:c=trie[c][x]+1 } printf("%d\n",sum[c]); } int main() { int n; cin>>n; while(n--&&cin>>s) add(); while(cin>>s) query(); return 0; }
在一个 Minecraft 村庄中,村长有这一本小写字母构成的名册(字符串的表), 每个名字旁边都记录着这位村民的声望值,而且有的村民还和别人同名。 随着时间的推移,因为没有村民死亡,这个名册变得十分大。 现在需要您来帮忙维护这个名册,支持下列 4 种操作:
输入描述:
第一行为一个整数 0 ≤ N ≤ 105,表示接下来有 N 个操作;接下来 N 行,每行输入一个操作,行首为一个整数 1 ≤ oi ≤ 4,表示这一行的操作的种类,那么这一行的操作和格式为:1. 插入人名,这一行的格式为 1 si ai,其中 |ai| ≤ 1032. 前缀修改声望,这一行的格式为 2 pi di,其中 |di| ≤ 1033. 查询名字的声望和,这一行的格式为 3 sj4. 查询前缀的声望和,这一行的格式为 4 pj输入保证插入人名的字符串的长度和小于或等于 105,总的字符串的长度和小于或等于 106。
输出描述:
对于每一次询问操作,在一行里面输出答案。
输入:
20
1 a -10
1 abcba -9
1 abcbacd 5
4 a
2 a 9
3 aadaa
3 abcbacd
4 a
3 a
2 a 10
3 a
2 a -2
2 d -8
1 ab -2
2 ab -7
1 aadaa -3
4 a
3 abcba
4 a
4 c
输出:
-14
0
14
13
-1
9
11
1
11
0
思路:
sum[]存储当前前缀声望总和
cot[]存储当前前缀个数
per[]={num,val}结构体存储当前姓名的村民个数num和声望总和
需要懒惰值来向下处理声望的改变量。
过样例50%:
#include<bits/stdc++.h> #include<time.h> #include<cctype> #include<iostream> #include<ostream> #include<cstdio> #include<algorithm> #include<iomanip> #include<cstring> #include<string> #include<cmath> #include<stack> #include<queue> #include<vector> #include<set> #include<map> using namespace std; #define maxn 10000000 typedef long long ll; const int inf=0x3f3f3f3f;//1061109567 const int INF=0x7fffffff;//2147483647 const int SUP=0x80000000;//-2147483648 #define loop(a,b,i) for(int i=a;i<b;i++) #define loopx(a,b,i) for(int i=a;i<=b;i++) #define lson (p<<1) #define rson ((p<<1)|1) #define mid ((l+r)>>1) #define MAX 1000005 char s[MAX]; char p[MAX]; ll trie[MAX][27]={0}; ll sum[MAX]={0};//某一前缀和的人的声望总和 ll cot[MAX]={0};//某一前缀和人数 ll lazy[MAX]={0};//懒惰值 struct node { ll num;//当前名字村民的个数 ll val;//当前名字声望总和 }per[MAX]; ll pos=1; void down(int c)//更新懒惰值 { for(int i=0;i<26;i++) { int x=trie[c][i]; if(x!=0) { sum[x]+=cot[x]*lazy[c];//前缀声望总和更新 // cout<<"lazy "<<lazy[c]<<endl; // cout<<"sum "<<sum[x]<<endl; if(per[x].num!=0)//如果字典里有这个名字 { per[x].val+=per[x].num*lazy[c];//更新这个名字的声望总和 } lazy[x]+=lazy[c]; } } lazy[c]=0; } void add(int a)//添加 { int c=0; for(int i=0;s[i];i++) { int x=s[i]-'a'; if(trie[c][x]==0) trie[c][x]=pos++; c=trie[c][x]; sum[c]+=a; cot[c]++; down(c); } per[c].num++;per[c].val+=a; } void change(int d)//改变 { int c=0; for(int i=0;p[i];i++) { int x=p[i]-'a'; if(trie[c][x]==0)return; c=trie[c][x]; down(c); } for(int i=1;i<=c;i++)//包括c节点之前的前缀更新 sum[i]+=d*cot[c];//更新d的个数时c节点前缀的个数 lazy[c]+=d; if(per[c].num!=0)per[c].val+=(per[c].num*d); } void inqs()//查询人名 { int c=0; for(int i=0;s[i];i++) { int x=s[i]-'a'; if(trie[c][x]==0) { cout<<0<<endl; return; } c=trie[c][x]; down(c); } cout<<per[c].val<<endl; } void inqp()//查询前缀 { int c=0; for(int i=0;p[i];i++) { int x=p[i]-'a'; if(trie[c][x]==0) { cout<<0<<endl; return; } c=trie[c][x]; down(c); } cout<<sum[c]<<endl; } int main() { int n,m,a,d; cin>>n; memset(per,0,sizeof(per)); while(n--) { // for(int i=1;sum[i]!=0;i++) // cout<<"sum "<<sum[i]; // cout<<endl; cin>>m; switch(m) { case 1: cin>>s>>a; add(a); break; case 2: cin>>p>>d; change(d); break; case 3: cin>>s; inqs(); break; case 4: cin>>p; inqp(); } } return 0; }
Vasya有几本电话簿,他记录了他的朋友的电话号码。他的每个朋友可以有一个或几个电话号码。 Vasya决定组织有关朋友电话号码的信息。您将获得n个字符串 - 来自Vasya电话簿的所有条目。每个条目都以朋友的名字开头。然后跟随当前条目中的电话号码数量,然后是电话号码本身。有可能几部相同的电话被记录在同一记录中。 Vasya还认为,如果电话号码a是电话号码b的后缀(即,电话号码b以a结尾),并且两个电话号码都由Vasya写成同一个人的电话号码,不记录a。 任务是输出有关Vasya朋友电话号码的组织信息。**两个不同的人可能有相同的号码。**如果一个人有两个数字x和y,并且x是y的后缀(即y以x结尾),那么您不应该输出数字x。如果Vasya电话簿中的朋友的号码以相同的格式记录多次,则有必要将其记录一次。 阅读样例以更好地理解输出的语句和格式。
输入描述:
第一行包含整数n(1<=n<=20) 表示Vasya电话簿中的条目数。 下面的n行后面是描述声明中描述的格式的记录。 Vasya的朋友的名字是非空字符串,其长度不超过10,只包含小写英文字母。 一个条目中的电话号码不少于1不超过10。电话号码只包含数字。如果您将电话号码表示为字符串,则其长度将在1到10的范围内。电话号码可以包含前导零。
输出描述:
输出出有关Vasya朋友电话号码的订购信息。 首先输出m表示在Vasya电话簿中找到的朋友的数量。 下列m行必须包含以下格式的条目“姓名 电话号码的个数 电话号码”。电话号码应该用空格隔开。每个记录必须包含当前朋友的所有电话号码。 条目可以以任意顺序显示,一个记录的电话号码也可以以任意顺序打印。
所有后台样例:
链接:点击任一个accepted代码编号
1.stl就是容器互套。set,map,vector。
2.字典树:
1)根据题目要求:判断是否重复,是否是其他电话后缀,可以建两个树,一个正序,一个逆序。
2)另外有两个判断函数,分别判断正序是否重复,逆序是否有后缀。
3)可以用两个数组分别记录 (建树过程记录):正序电话在树中根节点,如果有这个电话就记录1;逆序电话是否重复经过该节点,重复经过置0,第一次经过置1。 p.s.逆序这样记录意义是如果有重复经过代表之前有这个电话,之后判别时只用遍历到根节点再看该节点记录值是否为0,如果为0代表是正序电话后缀。
4)注意:输入过程中是可以进行正序查重的,但是不可以进行后缀查询。因为如果先录入后缀比如0,再录入10,要去掉前面的0较麻烦。所以等所有树建好,整体判别。
具体解释看代码注释
#include<bits/stdc++.h> using namespace std; const int N=30; bool check(string s,string t) { for(int i=0;i<s.size();i++) { if(s[s.size()-1-i]!=t[t.size()-1-i]) return false; } return true; } bool cmp(string s,string t) { return s.size()<t.size(); } int main() { int n; cin>>n; map<string,set<string> >s; string a,b; set<string>q; int x; for(int i=0;i<n;i++) { cin>>a>>x; q.insert(a); for(int j=0;j<x;j++) { cin>>b; s[a].insert(b); } // printf("%d\n",s["]) } map<string,set<string> >::iterator it1; set<string>::iterator it2; vector<string>v; set<string>p; for(it1=s.begin();it1!=s.end();it1++) { v.clear(); p.clear(); for(it2=it1->second.begin();it2!=it1->second.end();it2++) { v.push_back(*it2); } sort(v.begin(),v.end(),cmp); for(int i=0;i<v.size();i++) { bool mark=false; for(int j=i+1;j<v.size();j++) { if(check(v[i],v[j])) mark=true; } if(!mark) p.insert(v[i]); } it1->second=p; } cout<<q.size()<<endl; for(it1=s.begin();it1!=s.end();it1++) { cout<<it1->first<<" "<<it1->second.size(); for(it2=it1->second.begin();it2!=it1->second.end();it2++) { cout<<" "<<*it2; } cout<<endl; } return 0; }
#include<bits/stdc++.h> #include<time.h> #include<cctype> #include<iostream> #include<ostream> #include<cstdio> #include<algorithm> #include<iomanip> #include<cstring> #include<string> #include<cmath> #include<stack> #include<queue> #include<vector> #include<set> #include<map> using namespace std; #define maxn 10000000 typedef long long ll; const int inf=0x3f3f3f3f;//1061109567 const int INF=0x7fffffff;//2147483647 const int SUP=0x80000000;//-2147483648 #define loop(a,b,i) for(int i=a;i<b;i++) #define loopx(a,b,i) for(int i=a;i<=b;i++) #define lson (p<<1) #define rson ((p<<1)|1) #define mid ((l+r)>>1) #define MAX 1005 struct node//朋友信息 { string name; int num=0; string tele; }per[25]; int trie1[25][2005][15]={0};//正字典树 int trie2[25][2005][15]={0};//逆字典树 int record1[25][2005]={0};//记录正字典树是否有改电话 int record2[25][2005]={-1};//记录逆字典树该节点是否被重复经过 //如果是重复经过更新为0,第一次经过更新为1 int pos1=1; int pos2=1; void buildfront(int pot,string tel)//正 { int c=0; for(int i=0;tel[i];i++) { int x=tel[i]-'0'; if(trie1[pot][c][x]==0) trie1[pot][c][x]=pos1++; c=trie1[pot][c][x]; } record1[pot][c]=1;//记录该电话号码存在 } void buildback(int pot,string tel)//逆 { reverse(tel.begin(),tel.end()); int c=0; for(int i=0;tel[i];i++) { int x=tel[i]-'0'; record2[pot][trie2[pot][c][x]]=0;//重复经过置0 if(trie2[pot][c][x]==0) { trie2[pot][c][x]=pos2++; record2[pot][trie2[pot][c][x]]=1;//第一次经过置1 } c=trie2[pot][c][x]; } } int judgefront(int pot,string tel)//正向判断 { int c=0,flag=0; for(int i=0;tel[i];i++) { int x=tel[i]-'0'; if(trie1[pot][c][x]==0) { flag=1;break;//以前没出现过 } c=trie1[pot][c][x]; } if(record1[pot][c]==0)flag=1;//如果以前没出现过 //要再判断一次,因为有可能出现该电话是已有电话的前缀的情况 return flag; } int judgeback(int pot,string tel)//逆向判断 { reverse(tel.begin(),tel.end()); int c=0,flag=1; for(int i=0;tel[i];i++)//遍历到电话逆序底部 { int x=tel[i]-'0'; c=trie2[pot][c][x]; } if(record2[pot][c]==0)flag=0; //如果这个节点重复走过,那么说明该逆向电话是已有逆向电话的前缀 //即该电话是已有电话后缀 return flag; } int main() { int n,num,pot=-1,m=0; string name,tel; cin>>n; for(int i=0;i<n;i++) { cin>>name>>num; for(int j=0;per[j].num!=0;j++)//判断是否之前记录过相同名字 if(per[j].name==name) { pot=j;break; } if(pot==-1)pot=m++;//没有就新记录一个点 per[pot].name=name; per[pot].num+=num; for(int j=0;j<num;j++) { cin>>tel; if(judgefront(pot,tel))//判断是否重复 { per[pot].tele+=" "+tel; buildfront(pot,tel);//正建树 buildback(pot,tel);//逆建树 } else per[pot].num--; } pot=-1; } for(int i=0;i<m;i++)//为下边可以读取最后一个数准备 { per[i].tele+=" "; //cout<<per[i].name<<" "<<per[i].num<<per[i].tele<<endl; } int st,en;//开始点和截止点 for(int i=0;i<m;i++)//进行后缀判别 { st=1; int j=1;//j从1开始,因为0是空格 while(per[i].tele[j]) { if(per[i].tele[j]==' ') { en=j; //cout<<" st en "<<st<<en<<endl; string s=per[i].tele.substr(st,en-st);//提取电话 //cout<<s<<endl; if(!judgeback(i,s))//如果不符合 { per[i].tele.erase(st,en-st+1);//删除 per[i].num--; j-=(en-st+1);//更新步进值 } st=j+1;//让st指向空格的下一位 } j++; } } cout<<m<<endl; for(int i=0;i<m;i++) cout<<per[i].name<<" "<<per[i].num<<per[i].tele<<endl; return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。