文章目录
HDU 4763 Theme Section
题意：
题解：
代码：
POJ 3630 Phone List
题意：
n个号码，如果有一个号码是其他号码的前缀，则输出NO，否则输出YES
题解：
根据字典序排序，然后判断相邻的两个字典序是否有前缀
代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
char s[30];
string w[100005];
int main()
{
int T,n;
bool F=0;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
F=0;
//memset(w,0，sizeof(w));
for(int i=0;i<n;i++)cin>>w[i];
sort(w,w+n);
for(int i=1;i<n;i++)
{
if(w[i].length()>w[i-1].length())
{
int j;
for(j=0;j<w[i-1].size();j++)
if(w[i][j]!=w[i-1][j])break;
if(j==w[i-1].size())
F=1;
}
}
if(F) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
静态数组写字典树做法：
#include <cstdlib>
#include <cstdio>
#include <cstring>
typedef struct node //节点的结构体
{
bool end;//结束的标志
int a[10];
}node;
node phonelist[100000];
int x;
int flag;
void Init()
{
flag=1;//标志
x=0; //初始位置；
for(int i=0;i<100000;i++)
{
phonelist[i].end=false;
for(int j=0;j<10;j++)
phonelist[i].a[j]=-1;
}
}
int build(char *s) //建立字典树
{
int k,now=0,tag=0;// 初始位置
int len=strlen(s);
for(int i=0;i<len;i++)
{
k=s[i]-'0';
if(phonelist[now].a[k]==-1)
{
tag=1;//说明进入一个新的位置
phonelist[now].a[k]=++x; //给数组赋值
now=x;//下一个位置
}
else
{
now=phonelist[now].a[k];
if(phonelist[now].end)
return 0; //单词的结束标志
}
}
phonelist[now].end=true; //标记结束的节点
if(!tag) return 0;
return 1;
}
int main()
{
//freopen("1.txt","r",stdin);
int n,m;
char s[12];
scanf("%d",&n);
while(n--)
{
Init();
scanf("%d",&m);
for(int i=0;i<m;i++)
{
scanf("%s",s);
if(flag)
flag=build(s);
}
if(flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
HDU 3746 Cyclic Nacklace
题意：
一个字符串，在串后面补全几个字符，可以使他的全部字符最少循环2次以上，求最少补几个字符？
题解：
kmp算法的next数组
next数组的含义为, T[0…i-1]中的最大公共真前缀/后缀, 对于0-indexed求出的next数组实际上为1-M
next[M]为T中的最大公共真前缀/后缀, 这样M-next[M]应该就是循环节的长度len(仔细思考)
如果next[M]为0说明没有循环节, M%len==0说明循环节完全重复包含
首先这里用到一个kmp算法的最长相等前后缀算法next[]
然后很重要的一点:补全后字符串循环体L为strlen(s)-next[n]
这里有三种可能性:
1,字符串里已经有两次以上循环,而且都已补全这种就不用补全了,判断方式: 相等前后缀肯定不为零,且总长n%L==0
2,字符串里已经有两次以上循环,后续循环未补全这种要把单次循环的补全,由于已经有两次以上的循环,那么前后缀肯定要比单次循环要长(懒得证明)那么 前后缀%单次循环 就是循环剩下来的: 比如 ababa 前后缀是aba 单次循环是 ab 剩下来的就是a那么我们要补全的就是 单词循环-剩下来的: b ababa + b = ababab
3, 字符串里没有两次以上循环这种要补全两次由于没有两次以上的循环,那么前后缀肯定要比单次循环要短(同上)那么我们就输出 单词循环-前后缀: l-next[n]这种可以和第二种合并
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX=1e5+13;
char w[MAX];
int cnt[MAX];
int F;
void JZY(int len )
{
F=-1;
cnt[0]=-1;
for(int i=0;i<len;)
{
if(F==-1||w[i]==w[F]) cnt[++i]=++F;
else F=cnt[F];
}
}
int main()
{
int T;
int m;
scanf("%d",&T);
while(T--)
{
scanf("%s",w);
int len=strlen(w);
JZY(len);
m=len-cnt[len];
if((m!=len)&&(len%m==0)) printf("0\n");
else printf("%d\n",m-cnt[len]%m);
}
}
HDU 2087 剪花布条
题意：
一个目标串，一个模板串，问目标串最多可以剪除几个模板串?
题解：
可以用kmp来做，也可以用hash来做
代码：
hash代码：
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<string>
#include<cstdio>
using namespace std;
#define maxn 1001
string a;
string b;
const int B = 100000007;
typedef unsigned long long ull;
ull _hash(int al, int bl)
{
if (al < bl)return 0;
ull t = 1, ah = 0, bh = 0, cnt = 0;
for (int i = 0; i < bl; i++)t *= B;
for (int i = 0; i < bl; i++)ah = ah*B + a[i];
for (int i = 0; i < bl; i++)bh = bh*B + b[i];
for (int i = 0; i + bl<=al; i++)
{
//cout << a << "\n" << b << endl;
//cout << ah << "\t" << bh << endl;
if (ah == bh)
{
cnt++;
ah = ah - a[i + bl - 1] + '$';
//这是关键一步，更改字母之后hash值发生变化，所以变化量为'$'-a[i+bl-1]
a[i + bl-1] = '$';//更改已匹配的最后一个字母
}
if (i+bl<al)
ah = ah*B - a[i] * t + a[i + bl];
}
return cnt;
}
int main()
{
while (cin>>a&&a!="#")
{
cin >> b;
int al = a.length();
int bl = b.length();
ull res = _hash(al, bl);
cout << res << endl;
}
}
kmp代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxx=1e6+10;
int Next[maxx];
char s[maxx],p[maxx];
int len1,len2;
void getnext()
{
int i=0,j=-1;
Next[0]=-1;
while(i<len1)
{
if(j==-1||p[i]==p[j])
{
++i;
++j;
if(p[i]==p[j])
Next[i]=Next[j];
else
Next[i]=j;
}
else
j=Next[j];
}
}
void getkmp()
{
int num=0,i=0,j=0;
while(i<len2)
{
if(j==-1|s[i]==p[j])
{
++i;++j;
}
else
j=Next[j];
if(j==len1)
{
++num;
j=0;
}
}
printf("%d\n",num);
}
int main()
{
while(scanf("%s",s),s[0]!='#')
{
scanf("%s",p);
len1=strlen(p);
len2=strlen(s);
getnext();
getkmp();
}
return 0;
}
HDU 1251 统计难题
题意：
统计出以某个字符串为前缀的单词数量
题解：
模板题，map也可以做
代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int N=1e6+1;
const int mod=1e9+7;
const double pi=acos(-1);
const double eps=1e-8;
char s[12];
int trie[N][26],sum[N],tot,root;
void sert()
{
root=0;
for(int i=0;s[i]!='\0';i++)
{
int id=s[i]-'a';
if(!trie[root][id]) trie[root][id]=++tot;
sum[trie[root][id]]++;
root=trie[root][id];
}
}
int finf()
{
root=0;
int id;
for(int i=0;s[i]!='\0';i++)
{
id=s[i]-'a';
if(!trie[root][id]) return 0;
root=trie[root][id];
}
return sum[root];
}
int main()
{
while(gets(s))
{
if(s[0]=='\0') break;
sert();
}
while(gets(s))
{
printf("%d\n",finf());
}
}
HDU 2072 单词数
题意：
统计不同单词的数量
题解：
可以用map来做
不过练习字典树
代码：
#include<iostream>
#include<sstream>
using namespace std;
struct node{
int flag;
struct node *next[26];
node()
{
for(int i=0;i<26;i++)
{
this->next[i]=NULL;
}
this->flag=0;
}
};
node *root;
int ans;
void Insert(string str)
{
node *p=root;
for(int i=0;i<str.size();i++)
{
if(p->next[str[i]-'a']==NULL)
p->next[str[i]-'a']=new node();
p=p->next[str[i]-'a'];
}
p->flag++;
if(p->flag==1)
ans++;
}
int main()
{
string str,str1;
while(getline(cin,str))
{
root=new node();
ans=0;
if(str=="#")
break;
istringstream ss(str);
while(ss>>str1)
{
Insert(str1);
}
cout<<ans<<endl;
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<set>
#include<set>
#include <sstream>
using namespace std;
int main()
{
string a;
while(getline(cin,a)&& a != "#")
{
istringstream stream(a);
string w;
set<string> map;
while(stream >>w) map.insert(w);
printf("%d\n",map.size());
}
}
POJ 2513 Colored Sticks
题意：
给你一堆木棍。每根棍子的每个端点都用某种颜色着色。有没有可能把棍子在一条直线上对齐，使接触的端点的颜色是相同的颜色？
题解：
欧拉通路+并查集+字典树
判断欧拉通路是否存在的方法
有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。
无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。
代码：
#include <cstdio>
#include <cstring>
int const MAX = 500005;
int fa[MAX], d[MAX], cnt;
struct Trie
{
int sz, t[MAX][15];
int jud[MAX];
Trie()
{
sz = 1;
memset(t[0], -1, sizeof(t));
jud[0] = 0;
}
void clear()
{
sz = 1;
memset(t[0], -1, sizeof(t));
jud[0] = 0;
}
int idx(char c)
{
return c - 'a';
}
void insert(char* s, int v)
{
int u = 0, len = strlen(s);
for(int i = 0; i < len; i++)
{
int c = idx(s[i]);
if(t[u][c] == -1)
{
memset(t[sz], -1, sizeof(t[sz]));
jud[sz] = 0;
t[u][c] = sz++;
}
u = t[u][c];
}
jud[u] = v;
}
int search(char* s)
{
int u = 0, len = strlen(s);
for(int i = 0; i < len; i++)
{
int c = idx(s[i]);
if(t[u][c] == -1)
return -1;
u = t[u][c];
}
if(jud[u])
return jud[u];
return -1;
}
}t;
void Init()
{
for(int i = 0; i < MAX; i++)
fa[i] = i;
}
int Find(int x)
{
return x == fa[x] ? x : fa[x] = Find(fa[x]);
}
void Union(int a, int b)
{
int r1 = Find(a);
int r2 = Find(b);
if(r1 != r2)
fa[r1] = r2;
}
bool eluer()
{
int sum = 0, t = -1;
for(int i = 1; i < cnt; i++)
if(d[i] % 2)
sum++;
if(sum != 0 && sum != 2)
return false;
for(int i = 1; i < cnt; i++)
{
if(t == -1)
t = Find(i);
else if(Find(i) != Find(t))
return false;
}
return true;
}
int main()
{
char s1[20],s2[20];
cnt = 1;
Init();
t.clear();
while(scanf("%s %s", s1, s2) != EOF)
{
if(t.search(s1) == -1)
t.insert(s1, cnt++);
int u = t.search(s1);
if(t.search(s2) == -1)
t.insert(s2, cnt++);
int v = t.search(s2);
Union(u, v);
d[u]++;
d[v]++;
}
if(eluer())
printf("Possible\n");
else
printf("Impossible\n");
}
京公网安备 11010502036488号