注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

URAL 1882 Old Nokia  

2012-04-02 21:27:16|  分类: 字符串 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       ural regional school contest里最难的一道题,online constest只有几个人过了,训练赛的时候我们看了下题目然后就果断放弃了。后来我仔细想了一下,YY出来了一个结论:在找一个电话号码的时候,删除操作最多只能连续用一次,多用是没有意义的。多画几个图就清楚了。有了这个结论后这题就好办了,把所有的电话号码用trie树存储,然后对于每一个电话号码都在trie树上找一遍,找的过程中每到一个新的节点就枚举一下删除操作和向下向上操作,更新最优解,复杂度为O(电话号码总长度)。最后0.078ms AC,rank 5。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#define N 100009
using namespace std;
struct trie{
int l,r,next[26];
bool flag;
}data[N];

int tp;
string s[N];
int ans[N];
int get(char c){
c-='a';
if(c<18) return c%3+1;
if(c==18||c==25) return 4;
return (c-19)%3+1;
}
void insert(string::iterator it,int id)
{
int p=0;
for(;*it;it++){
if(data[p].next[*it-'a']==0) data[p].next[*it-'a']=++tp;
p=data[p].next[*it-'a'];
if(data[p].l)
data[p].l=min(data[p].l,id),data[p].r=max(data[p].r,id);
else
data[p].l=data[p].r=id;
}
data[p].flag=true;
}
int abc(int a){
return a>0?a:-a;
}
int find(string::iterator it,int id)
{
int p=0,pp,t=0,ret=1000000000;
for(;*it;it++){
ret=min(ret,t+min(id-data[p].l,data[p].r-id+1));
for(int i=0;i<26;i++)
if(pp=data[p].next[i])
ret=min(ret,t+1+get(i+'a')+min(abc(id-data[pp].l),data[p].r-data[pp].l+id));
p=data[p].next[*it-'a'];
t+=get(*it);
}
ret=min(ret,t);
return ret;
}
int main()
{
int n;
scanf("%d",&n);
data[0].l=1,data[0].r=n;
for(int i=1;i<=n;i++){
cin>>s[i];
insert(s[i].begin(),i);
}
for(int i=1;i<=n;i++)
ans[i]=find(s[i].begin(),i);
printf("%d",ans[1]);
for(int i=2;i<=n;i++) printf(" %d",ans[i]);
puts("");
return 0;
}


  评论这张
 
阅读(114)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017