`
暴风雪
  • 浏览: 388940 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[字符串最小表示法]hdoj 4162:Shape Number(解法2)

阅读更多

大致题意:

    见:http://bbezxcy.iteye.com/blog/1439384

 

大致思路:
    最小表示法果然快啊!!从7000多ms优化到900ms,膜拜Orz。

 

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax =800000;

char sss[nMax];
int  num[nMax];

int minexp(int *s,int x) {
  int i=0,j=1,k=0,t;
   while(i<x&&j<x&&k<x) {
     t=s[ (i+k)%x ]-s[ (j+k)%x ];
      if(t==0) k++;
      else {
        if(t>0)  i+=k+1;
        else     j+=k+1;
        if(i==j) j++;
        k=0;
      }
   }
  return i<j?i:j;
}

int main(){
    int i,j,len,a,b,n;
    while(scanf("%s",sss)!=EOF){
        len=strlen(sss);
        for(i=0;i<len-1;i++){
            if(sss[i]<=sss[i+1]){
                num[i]=sss[i+1]-sss[i];
            }
            else{
                num[i]=8-(sss[i]-sss[i+1]);
            }
        }
        if(sss[len-1]<=sss[0]){
            num[len-1]=sss[0]-sss[len-1];
        }
        else{
            num[len-1]=8-(sss[len-1]-sss[0]);
        }
        n=len;
        int pos1=minexp(num,n);
        for(i=pos1;i<len;i++){
            printf("%d",num[i]);
        }
        for(i=0;i<pos1;i++){
            printf("%d",num[i]);
        }printf("\n");
    }
    return 0;
}
0
0
分享到:
评论

相关推荐

    最小表示法

    最小表示法,也被称为Morris-Pratt算法或者KMP预处理,是计算机科学中解决字符串匹配问题的一种高效方法。这个方法由C.A.R. Hoare在1968年首次提出,后来由Morris和Pratt进行了改进,主要用于优化Boyer-Moore算法和...

    算法文档无代码浅析“最小表示法”思想在字符串循环同构问题中的应用

    标题中提到的“最小表示法”是一种解决字符串问题的算法思想,特别是在处理字符串循环同构问题时非常有用。在深入了解之前,我们首先要明白几个基本概念。 字符串循环同构是指一个字符串可以被看作是另一个字符串的...

    最小表示法,周源ppt

    最小表示法是一种在字符串处理和算法竞赛中不太常见但非常经典的思想,主要用于解决字符串的循环同构问题。在本文中,我们将深入探讨最小表示法及其在解决特定问题上的应用。 循环同构指的是两个字符串可以通过有限...

    查找字符串中最小字符串-C语言代码

    在C语言中,查找字符串中最小字符串的问题是一个基础但有趣的编程练习。这个问题通常涉及比较字符串长度,找到字符串数组中长度最短的那一个。这里,我们将会深入探讨如何使用C语言来解决这个问题,并通过实际代码...

    最小表示法 ioi2003 周源

    最小表示法 ioi2003 周源

    详解C++ string常用截取字符串方法

    在C++编程中,`std::string`是一个非常重要的数据类型,用于表示和操作字符串。本文将详细解析两种常用的C++ `std::string`截取字符串的方法:`find`和`find_last_of`,以及如何结合使用它们来满足各种字符串处理...

    javascript实现的字符串与十六进制表示字符串相互转换方法

    本文实例讲述了javascript实现的字符串与十六进制表示字符串相互转换方法。分享给大家供大家参考。具体如下: 之所以写这个,是因为发现SQL注入和XSS中经常利用十六进制表示的字符串,比如 SELECT CONCAT(0x68656c6...

    Delphi字符串16进制互相转换

    - `IntToHex`函数可以将整数转换为16进制字符串,如`IntToHex(number, length)`,其中`length`是期望的16进制字符串长度,不足部分用零填充。 3. **16进制字符串转字节数组**: - 这通常涉及字符串的分割和逐个...

    随机生成32位字符串

    在IT领域,字符串是编程中常见且重要的数据类型,用于表示和处理文本信息。VB(Visual Basic)是一种经典的、基于事件驱动的编程语言,由微软公司开发,它提供了丰富的库函数和工具,使得生成各种字符串操作变得简单...

    易语言十六进制与字符串转换

    2. **十六进制转字符串**:相反的过程需要先使用“十六进制到整数”函数将十六进制字符串转换为十进制,再用“整数到字符串”函数将十进制数值转化为字符串。需要注意的是,这里的“整数到字符串”可能会产生一个以...

    C# 字符串转十六进制串,16进制反向转回原字符串

    字符串是由Unicode字符组成的序列,每个字符在计算机内部通常用16位(2个字节)来表示,可以是英文、数字、标点符号,甚至是中文等多语言字符。十六进制是一种逢16进1的方式,用于表示二进制数,它使用0-9和A-F这16...

    正则表达式随机生成字符串工具

    2. 长度设置:用户可以指定生成字符串的最小和最大长度。 3. 模板选择:提供预设的常见模板,如邮箱地址、电话号码等,方便快速生成。 4. 重复次数:决定生成多少个符合规则的字符串。 5. 输出格式:可能支持多种...

    Objective-C中字符串操作总结

    - `compare:`:用于比较两个字符串的顺序,返回三种可能的值:1表示第一个字符串大于第二个,0表示相等,-1表示小于。 - `caseInsensitiveCompare:`:忽略大小写进行字符串比较。 3. **大小写转换**: - `...

    截取用,分割的字符串中的第n个字符串 SQL

    根据给定的信息,本文将详细解释如何在SQL中实现截取用特定字符分割的字符串中的第n个子字符串。此需求通常应用于数据处理与分析场景中,尤其在处理半结构化或非结构化的文本数据时非常有用。 ### 核心知识点解析 ...

    编辑距离问题 对于给定的字符串A和字符串B,编程计算其编辑距离d(A,B)。

    编辑距离指的是通过一系列预定义的操作(如插入、删除或替换字符)将一个字符串转换为另一个字符串所需的最小操作次数。这个问题在自然语言处理、生物信息学以及文本比对等领域有着广泛的应用。 #### 二、编辑距离...

    03 C#与C++dll互相传递字符串.rar

    C++的字符串通常使用`char*`或`std::string`表示。为了与C#兼容,我们通常选择`const char*`作为字符串类型,因为它更接近C的内存管理方式。在C++ DLL中,函数声明如下: ```cpp extern "C" __declspec(dllexport...

    带通配符的字符串匹配算法

    2. **匹配过程**:逐个比较两个字符串的字符,如果匹配成功,则移动两个指针到下一个位置;如果不匹配,根据通配符规则进行调整。 3. **结束条件**:当模式字符串的所有字符都与待匹配字符串对应时,匹配成功;如果...

    C语言二进制字符串与十六进制字符串相互转化

    本文将深入探讨如何在C语言环境中实现二进制字符串与十六进制字符串之间的转换,并结合MFC(Microsoft Foundation Classes)框架创建一个小工具来辅助这些操作。 首先,让我们理解二进制和十六进制的基本概念。二...

    c语言写的根据字符串排序的算法

    在C中,字符串是由字符数组表示的,通常以空字符'\0'作为结束标志。处理字符串时,我们经常使用标准库函数,如`strlen()`来计算字符串的长度,`strcpy()`和`strcat()`用于复制和连接字符串,以及`strcmp()`进行字符...

    关于java按字节截取带有汉字的字符串的解法

    在Java编程语言中,处理带有汉字的字符串时,由于汉字占据多个字节,按照字节进行截取可能会导致汉字被不完整地分割,从而产生乱码。为了解决这个问题,我们需要理解Unicode编码以及如何在Java中正确处理多字节字符...

Global site tag (gtag.js) - Google Analytics