大致题意:
见: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;
}
分享到:
相关推荐
最小表示法,也被称为Morris-Pratt算法或者KMP预处理,是计算机科学中解决字符串匹配问题的一种高效方法。这个方法由C.A.R. Hoare在1968年首次提出,后来由Morris和Pratt进行了改进,主要用于优化Boyer-Moore算法和...
最小表示法是一种在字符串处理和算法竞赛中不太常见但非常经典的思想,主要用于解决字符串的循环同构问题。在本文中,我们将深入探讨最小表示法及其在解决特定问题上的应用。 循环同构指的是两个字符串可以通过有限...
本文档是一份PPT学习教案,旨在指导学习者通过最小表示法来应对字符串循环同构问题。 循环同构,顾名思义,是指在对字符串执行循环移位操作后能够得到另一个字符串的情况。例如,字符串"s1 = 'a b c d'"经过一次...
最小表示法 ioi2003 周源
2. 字符串比较:熟悉strcmp()函数的用法,用于比较两个字符串是否相等或按字典顺序排列。 3. 字符串连接:strcat()和strncat()函数用于连接两个字符串,理解它们的区别和使用场景,以及注意防止溢出。 4. 字符串...
本文实例讲述了javascript实现的字符串与十六进制表示字符串相互转换方法。分享给大家供大家参考。具体如下: 之所以写这个,是因为发现SQL注入和XSS中经常利用十六进制表示的字符串,比如 SELECT CONCAT(0x68656c6...
- 转义字符`\`用于表示特殊含义,例如`\n`表示换行,`\t`表示制表符,`\\`表示反斜杠,`\'`表示单引号,`\"`表示双引号。 3. **下标与索引**: - 字符串中的每个字符都有一个唯一的索引,从0开始。例如,字符串`...
此外,理解字符串在不同编程语言中的表示方式也很重要,例如在C/C++中,字符串是以`\0`结尾的字符数组,而在Python中,字符串是不可变的。 最后,完成函数后,务必用各种测试用例来验证其正确性。这包括但不限于...
在LabVIEW中,数据主要通过数据类型表示,字符串可以以单个字符串或字符串数组的形式存在。字符串数组允许我们存储多个独立的字符串,每个字符串都有自己的索引。拆分后的子字符串通常会存储在一个字符串数组中。 ...
最小表示法的目的是找到一个字符串的最小循环串,这个循环串可以代表整个字符串的特性。为了找到这个循环串,我们需要比较字符串的不同排列组合,选择出最小的那一个。这需要借助于一些高效的数据结构和算法技巧,...
- `IntToHex`函数可以将整数转换为16进制字符串,如`IntToHex(number, length)`,其中`length`是期望的16进制字符串长度,不足部分用零填充。 3. **16进制字符串转字节数组**: - 这通常涉及字符串的分割和逐个...
2. **十六进制转字符串**:相反的过程需要先使用“十六进制到整数”函数将十六进制字符串转换为十进制,再用“整数到字符串”函数将十进制数值转化为字符串。需要注意的是,这里的“整数到字符串”可能会产生一个以...
在IT领域,字符串是编程中常见且重要的数据类型,用于表示和处理文本信息。VB(Visual Basic)是一种经典的、基于事件驱动的编程语言,由微软公司开发,它提供了丰富的库函数和工具,使得生成各种字符串操作变得简单...
2. **数据解析**:接收到的数据可能以字符串形式返回,比如"0x1A",或者直接作为整数类型。如果为字符串,需要进行预处理,去除前缀"0x",然后将剩余的16进制字符转换成对应的十进制数值。你可以使用`QByteArray::...
在西门子PLC编程中,字符串通常表示为“STRING”类型,它由一系列字符组成,可以包含数字、字母和其他字符。而实数则表示为“REAL”类型,用于存储浮点数值。在处理来自传感器、人机界面(HMI)或其他系统的输入时,...
在Delphi编程环境中,处理中文和英文混合的字符串截取是一项常见的任务,特别是在涉及到文本处理、数据解析或者用户界面展示时。由于Unicode编码的存在,中文字符通常占据两个字节,而英文字符则占据一个字节,这就...
2. **字符串函数**:LabVIEW提供了丰富的字符串函数库,包括“连接”(Concatenate)、“分割”(Split)、“查找”(Find)、“替换”(Replace)等,用于对字符串进行各种操作。对于格式化写入,我们需要关注...
字符串是由Unicode字符组成的序列,每个字符在计算机内部通常用16位(2个字节)来表示,可以是英文、数字、标点符号,甚至是中文等多语言字符。十六进制是一种逢16进1的方式,用于表示二进制数,它使用0-9和A-F这16...
本问题涉及的挑战是利用SCL编写一个函数块,该函数块能处理字符串并找到一个最小的子串,这个子串能包含另一个字符串的所有字符。我们将探讨如何实现这个功能,并了解与SCL、算法和字符解析相关的知识。 首先,我们...