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

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

【大部分转载】hdu4333题解  

2016-08-12 16:29:41|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本文转载自liangpeiqi0《扩展KMP详解_暨_hdu4333题解》

//lpq

【题目大意】

给定一个数字<=10^100000,一次将该数的第一位放到放到最后一位,求所有组成的不同的数比原数小的个数,相等的个数,大的个数。

【解题思路】

如果每次将该数的第一位放到放到最后一位,然后再比较,时间复杂度为O(|数字|^2)

做完会发现有很多无谓的比较,这里就要引用到扩展KMP。比如一个数字12121。一开始我们可以将这个数字扩展成两倍,即12121。定义next_[i]为以i为开头的后缀与原串的最长公共前缀,即S[0..next_[i]-1] = S[i..i+next_[i]-1]。特别地,next_[0]=len。而我们只需要比较S[next_[i]]S[i+next_[i]],就能知道现在这个数比原数大还是小,或是相等了。

现在的问题就是这个next_数组怎么求了。思想有点像Manacher

(http://liangpeiqi0.blog.163.com/blog/static/24671503920167885258656/)

S  :aaaabaaaa

ans :932104?

已知:S[0..3]=S[5..8] (ans[5]=4可得) S[1..3]=S[0..2] (ans[1]=3可得)

S[0..3]=S[5..8] -> S[1..3]=S[6..8]

S[6..8]=S[1..3]=S[0..2]

因此ans[6]至少为3,检查ans[6]能否更大

S[9]!=S[3],因此ans[6]就是3

/*==========yhf===============*/

这道题还要注意一个地方,求所有组成的不同的数。其实也是很简单,有两种方法,一是求出S的循环节用总数去除,还有就是算到第一个与S相等的数就break,因为再算下去一定会重复。

/*==========yhf===============*/

AC代码】

# include <iostream>
# include <cstdio>
# include <string>
# include <cstring>
# include <algorithm>
# include <cstdlib>
 
using namespace std;
char st[200020];
int next_[200020],t;
 
int main()
{
      scanf("%d",&t);
      for (int g=1; g<=t; g++)
      {
            int s1=0,s2=0,s3=0;
            scanf("%s",&st);
            int len=strlen(st);
            for (int i=0; i<len; i++) st[i+len]=st[i];
 
            int k=1;
            next_[0]=len*2-1; next_[1]=0;
            while (st[next_[1]]==st[next_[1]+1]) next_[1]++;
            for (int i=0; i<len; i++)
            {
                  if (i>1)
                  {
                        int p=k+next_[k];
                        if (next_[i-k]+i<p) next_[i]=next_[i-k];
                        else
                        {
                               next_[i]=max(0,p-i);
                               while (st[next_[i]]==st[next_[i]+i]) next_[i]++;
                               k=i;
                        }
                  }
                  if (next_[i]>=len) s2++;
                  else if (st[next_[i]+i]<st[next_[i]]) s1++;
                  else s3++;
            }
            printf("Case %d: %d %d %d\n",g,s1/s2,s2/s2,s3/s2);
      }
      return 0;
}

 

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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