https://blog.csdn.net/qq_38891827/article/details/80532462
https://www.cnblogs.com/nyist-TC-LYQ/p/7208054.html
https://www.wandouip.com/t5i148586/
模板
//对于字符串比较多的要统计个数的，map被卡的情况下，直接用字典树
//很多题都是要用到节点下标来表示某个字符串
const int maxn =2e6+5;//如果是64MB可以开到2e6+5，尽量开大
int tree[maxn][30];//tree[i][j]表示节点i的第j个儿子的节点编号
bool flagg[maxn];//表示以该节点结尾是一个单词
int tot;//总节点数
void insert_(char *str)
{
int len=strlen(str);
int root=0;
for(int i=0;i<len;i++)
{
int id=str[i]-'0';
if(!tree[root][id]) tree[root][id]=++tot;
root=tree[root][id];
}
flagg[root]=true;
}
bool find_(char *str)//查询操作，按具体要求改动
{
int len=strlen(str);
int root=0;
for(int i=0;i<len;i++)
{
int id=str[i]-'0';
if(!tree[root][id]) return false;
root=tree[root][id];
}
return true;
}
void init()//最后清空，节省时间
{
for(int i=0;i<=tot;i++)
{
flagg[i]=false;
for(int j=0;j<10;j++)
tree[i][j]=0;
}
tot=0;//RE有可能是这里的问题
}
POJ 1251 统计难题
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=2e6+5;
int tree[maxn][30];
bool flagg[maxn];
int sum[maxn];
int tot;
void insert_(char *str){
int len=strlen(str);
int root=0;
for(int i=0;i<len;i++){
int id=str[i]-'a';
if(!tree[root][id])
tree[root][id]=++tot;
sum[tree[root][id]]++;
root=tree[root][id];
}
flagg[root]=true;
}
int find_(char *str){
int len=strlen(str);
int root=0;
for(int i=0;i<len;i++){
int id=str[i]-'a';
if(!tree[root][id])
return false;
root=tree[root][id];
}
return sum[root];
}
char ss[maxn];
int main()
{
// freopen("data.txt","r",stdin);
while(gets(ss)){
if(ss[0]=='\0')
break;
insert_(ss);
}
while(scanf("%s",ss)!=EOF){
printf("%d\n",find_(ss));
}
return 0;
}
Light OJ 1224 - DNA Prefix
这题要注意数组开的大小
id是利用map映射，ACGT每个字符映射一个数字
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int maxn=2e6+5;
int tree[maxn][5];
map<char,int> m;//字符映射
int sum[maxn];
int tot,t,j,ans;
void insert_(char *str){
int len=strlen(str);
int root=0;
for(int i=0;i<len;i++){
int id=m[str[i]];
if(!tree[root][id])
tree[root][id]=++tot;
sum[tree[root][id]]++;
ans=max(ans,sum[tree[root][id]]*(i+1));
root=tree[root][id];
}
}
/*
int find_(char *str){
int len=strlen(str);
int root=0;
for(int i=0;i<len;i++){
int id=str[i]-'a';
if(!tree[root][id])
return false;
root=tree[root][id];
}
return sum[root];
}*/
char ss[55];
int main()
{
ans=0;
m['A']=0;
m['C']=1;
m['G']=2;
m['T']=3;
// freopen("data.txt","r",stdin);
int n;
cin>>t;
for(j=1;j<=t;j++){
memset(sum,0,sizeof(sum));
ans=0;
cin>>n;
while(n--){
scanf("%s",ss);
insert_(ss);
}
//这里需要初始化
for(int i=0;i<=tot;i++){
sum[i]=0;
for(int j=0;j<4;j++)
tree[i][j]=0;
}
tot=0;
printf("Case %d: %d\n",j,ans);
}
return 0;
}
poj 2513 Colored Sticks
这一题是字典树+并查集+欧拉通路
用并查集确定一条路是否能够连通，但并查集是针对数字的，所以通过字典树将不同颜色生成一个id，在进行并查集。
char s1[maxn],s2[maxn]；这里放全局变量比较好吧~
当时做这道题的时候我们只想着结论，却没有想到它的必要条件（必须是一条通路）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int maxn=2e6+5;
int tree[maxn][55];
int sum[maxn];
int tot,t,j,ans;
int vis[maxn],sz,odd[maxn];//sz记录颜色
int par[maxn],rank[maxn];
void init(){
for(int i=0;i<maxn;i++){
par[i]=i;
}
}
char s1[maxn],s2[maxn];//这里的问题导致不能运行
int find(int x){return par[x]==x?x:par[x]=find(par[x]);}
void unite(int x,int y){
x=find(x);
y=find(y);
if(x==y)
return;
else{
if(rank[x]<rank[y])
par[x]=y;
else{
par[y]=x;
if(rank[x]==rank[y])
rank[x]++;
}
}
}
int insert_(char *str){
int len=strlen(str);
int root=0;
for(int i=0;i<len;i++){
int id=str[i]-'a';
if(!tree[root][id])
tree[root][id]=++tot;
root=tree[root][id];
}
if(!vis[root]){
vis[root]=++sz;
}
return vis[root];
}
int main()
{
ans=0;
init();
freopen("data.txt","r",stdin);
while(cin>>s1>>s2){
int id1=insert_(s1);
int id2=insert_(s2);
odd[id1]++;
odd[id2]++;
unite(id1,id2);
}
bool flag=true;
int here=find(1);//至少有一个数据是他的子节点，用来判断是否为空数据
int sum=0;
for(int i=1;i<=sz;i++){
if(odd[i]%2)
sum++;
if(find(i)!=here){
flag=false;
break;
}
}
if(flag&&(sum==2||sum==0))
printf("Possible");
else
printf("Impossible");
return 0;
}
POJ 2001 Shortest Prefixes
这道题的思路很特别，它insert_ 和find函数用的形参是int，如果有一个字符只出现了一次，就说明这个字符串和其他字符串不同点就在这，将其输出就可以结束。我刚开始使用string s[]开了一个数组，但是在judge的时候compile error~இ௰இ
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int maxn=2e6+5;
int tree[maxn][55];
int sum[maxn];
int tot,t,j,ans;
char s[10000][10000];
void insert_(int l){
int len=strlen(s[l]);
int root=0;
for(int i=0;i<len;i++){
int id=s[l][i]-'a';
if(!tree[root][id])
tree[root][id]=++tot;
sum[tree[root][id]]++;
root=tree[root][id];
}
}
void find(int l){
int len=strlen(s[l]);
int root=0;
for(int i=0;i<len;i++){
int id=s[l][i]-'a';
root=tree[root][id];
putchar(s[l][i]);
if(sum[root]==1)
break;
}
putchar('\n');
}
int main()
{
int k=0;
freopen("data","r",stdin);
while(~scanf("%s",s[k++])){
insert_(k-1);
}
for(int i=0;i<k;i++){
cout<<s[i]<<' ';
find(i);
}
return 0;
}
POJ 2072 单词数
这道题难就难在输入，要学学用STL输入,这题建议用string不用char数组
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <sstream>
using namespace std;
const int maxn=2e6+5;
int tree[maxn][55];
int sum[maxn];
int tot,t,j,ans;
bool flag[maxn];
void insert_(string str){
int len=str.size();
int root=0;
for(int i=0;i<len;i++){
int id=str[i]-'a';
if(!tree[root][id]){
tree[root][id]=++tot;
sum[tree[root][id]]++;
}
root=tree[root][id];
}
flag[root]=true;
}
bool find(string str){
int len=str.size();
int root=0;
for(int i=0;i<len;i++){
int id=str[i]-'a';
if(!tree[root][id])
return true;
root=tree[root][id];
}
if(flag[root])
return false;
else return true;
}
string s1,s2;
int main(){
// freopen("data","r",stdin);
while(getline(cin,s1)&&s1!="#"){
int sum=0;
stringstream ss(s1);//创建ss流
while(ss>>s2){//向流中写入数据
if(find(s2)){
insert_(s2);
sum++;
}
}
cout<<sum<<endl;
for(int i=0;i<=tot;i++){
flag[i]=false;
for(int j=0;j<33;j++)
tree[i][j]=0;
}
tot=0;
}
return 0;
}
网友评论