首页 > 代码库 > uva 11732 "strcmp()" Anyone?
uva 11732 "strcmp()" Anyone?
https://vjudge.net/problem/UVA-11732
题意：
给出许多字符串，他们两两按下面的函数比较
输出比较次数
s[i]==t[i] , 和 s[i]==‘\0‘ 各算一次比较
法一：
每两个字符串，要么全部匹配，要么中间停止匹配
如果全部匹配，比较次数为 2*len+2（‘\0’两次匹配）
如果中间停止匹配，比较次数为 2*相同前缀长度+1 （1次失败匹配后退出）
所以
1、对于第i个字符串，先加上i-1，即假设全部 中间停止匹配
这样最后再加上全部匹配数
2、匹配一个就+sum*2
#include<cstdio>#include<cstring>#define N 1001using namespace std;char s[N];int sum[N*4001],len,trie[N*4001][63],tot;long long ans;int mark[N*4001];int get(int i){ if(s[i]>=‘0‘&&s[i]<=‘9‘) return s[i]-‘0‘; if(s[i]>=‘a‘&&s[i]<=‘z‘) return s[i]-‘a‘+10; if(s[i]>=‘A‘&&s[i]<=‘Z‘) return s[i]-‘A‘+36;}void insert(int cnt){ int root=0,id; ans+=cnt; for(int i=0;i<len;i++) { id=get(i); if(!trie[root][id]) { trie[root][id]=++tot; memset(trie[tot],0,sizeof(trie[tot])); sum[tot]=mark[tot]=0; } root=trie[root][id]; ans+=sum[root]<<1; sum[root]++; } ans+=mark[root]; mark[root]++;}int main(){ int n,t=0; while(scanf("%d",&n)!=EOF) { if(!n) return 0; memset(trie[0],0,sizeof(trie[0])); ans=0;tot=0; for(int i=1;i<=n;i++) { scanf("%s",s); len=strlen(s); insert(i-1); } printf("Case %d: %lld\n",++t,ans); }}
法二：
用cnt记录现在还剩下几个是匹配的
那么每次
1、ans+=cnt-sum 匹配失败
2、ans+=sum*2 匹配成功
3、cnt=sum
注意：为了好处理，所以字符串的结束符也算上了
那么这就要循环到len，另外特殊给‘\0’赋一个id
#include<cstdio>#include<cstring>#define N 1001using namespace std;char s[N];int sum[N*4001],len,trie[N*4001][63],tot;long long ans;int get(int i){ if(s[i]>=‘0‘&&s[i]<=‘9‘) return s[i]-‘0‘; if(s[i]>=‘a‘&&s[i]<=‘z‘) return s[i]-‘a‘+10; if(s[i]>=‘A‘&&s[i]<=‘Z‘) return s[i]-‘A‘+36; return 62;}void insert(int cnt){ int root=0,id; for(int i=0;i<=len;i++) { id=get(i); if(!trie[root][id]) { trie[root][id]=++tot; memset(trie[tot],0,sizeof(trie[tot])); sum[tot]=0; } root=trie[root][id]; ans+=cnt-sum[root]; ans+=sum[root]<<1; cnt=sum[root]; sum[root]++; }}int main(){ int n,t=0; while(scanf("%d",&n)!=EOF) { if(!n) return 0; memset(trie[0],0,sizeof(trie[0])); ans=0;tot=0; for(int i=1;i<=n;i++) { scanf("%s",s); len=strlen(s); insert(i-1); } printf("Case %d: %lld\n",++t,ans); }}
uva 11732 "strcmp()" Anyone?
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。