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

[后缀数组]hdoj 4162:Shape Number

阅读更多

大致题意:
   题中的图片可以无视, 给出一串数,经过变化后变为另一个串,变化的方式是num[i]=abs(num[i+1]-num[i]),求变化后串的最小表示。

 

大致思路:
    这里用的是后缀数组,把当前串复制一遍接到这个串后面做的,shi慢shi慢的……Orz。马上去学学最小表示去。

 

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

int  num[nMax];
int sa[nMax], rank[nMax], height[nMax];
int wa[nMax], wb[nMax], wv[nMax], wd[nMax];

int cmp(int *r, int a, int b, int l){
    return r[a] == r[b] && r[a+l] == r[b+l];
}

void da(int *r, int n, int m){          //  倍增算法 r为待匹配数组  n为总长度 m为字符范围
    int i, j, p, *x = wa, *y = wb, *t;
    for(i = 0; i < m; i ++) wd[i] = 0;
    for(i = 0; i < n; i ++) wd[x[i]=r[i]] ++;
    for(i = 1; i < m; i ++) wd[i] += wd[i-1];
    for(i = n-1; i >= 0; i --) sa[-- wd[x[i]]] = i;
    for(j = 1, p = 1; p < n; j *= 2, m = p){
        for(p = 0, i = n-j; i < n; i ++) y[p ++] = i;
        for(i = 0; i < n; i ++) if(sa[i] >= j) y[p ++] = sa[i] - j;
        for(i = 0; i < n; i ++) wv[i] = x[y[i]];
        for(i = 0; i < m; i ++) wd[i] = 0;
        for(i = 0; i < n; i ++) wd[wv[i]] ++;
        for(i = 1; i < m; i ++) wd[i] += wd[i-1];
        for(i = n-1; i >= 0; i --) sa[-- wd[wv[i]]] = y[i];
        for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i ++){
            x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p - 1: p ++;
        }
    }
}

void calHeight(int *r, int n){           //  求height数组。
    int i, j, k = 0;
    for(i = 1; i <= n; i ++) rank[sa[i]] = i;
    for(i = 0; i < n; height[rank[i ++]] = k){
        for(k ? k -- : 0, j = sa[rank[i]-1]; r[i+k] == r[j+k]; k ++);
    }
}

char sss[nMax];

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]);
        }
        for(i=0;i<len;i++){
            num[len+i]=num[i];
        }
        n=len*2;
        num[n]=0;
        da(num,n + 1,30);
        calHeight(num,n);
        int loc,mine=inf;
        for(i=1;i<=len;i++){
            if(rank[i]<mine){
                loc=i;
                mine=rank[i];
            }
        }
        for(i=loc;i<loc+len;i++){
            printf("%d",num[i]);
        }printf("\n");
    }
    return 0;
}
 
0
0
分享到:
评论

相关推荐

    hdoj1005 Number Sequence 代码

    ### hdoj1005 Number Sequence 代码分析与解析 #### 一、问题背景与题目概述 在深入了解代码之前,我们先来了解下题目背景。`hdoj1005 Number Sequence` 是杭州电子科技大学在线评测系统(Online Judge,简称OJ)...

    hdoj1002——大整数相加

    ### hdoj1002——大整数相加 #### 题目背景与目的 本题目来源于杭州电子科技大学的在线评测系统(HDOJ),编号为1002的大整数相加问题。该题目主要考察的是编程者对于大整数处理的基本技巧以及对数组、循环等基础...

    HDOJ题目分类 HDOJ题目分类

    【标题】:“HDOJ题目分类 HDOJ题目分类” HDOJ,全称为Happy DingO Online Judge,是一个在线编程竞赛平台,它为参赛者提供了大量编程题目进行练习和比赛,旨在提升编程技能和算法理解。HDOJ的题目分类是帮助用户...

    HDOJ 80题 Java

    【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...

    hdoj--acm题目,有注释

    "hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...

    hdoj2066最短路

    根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...

    hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000

    【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...

    HDOJ离线版

    《HDOJ离线版:探索编程竞赛的智慧宝库》 HDOJ,全称为“杭州电子科技大学在线评测系统”(Hangzhou Dianzi University Online Judge),是中国早期的编程竞赛平台之一,深受广大编程爱好者和在校学生的喜爱。HDOJ...

    hdoj:杭电OJ题目源码记录 —— a source code of hdoj acm problem archive

    hdoj-problem-archive 杭电OJ题目源码记录 —— a source code of hdoj acm problem archive 简介 此项目为 的 题目以及代码仓库 src 中每一个文件夹代表一个题目 每个文件夹中都有 原题文档介绍.md 原题文档介绍.md...

    HDOJ1002

    ACM ICPC HDOJ1002

    HDOJ1001

    ACM ICPC HDOJ1001

    hdoj1001标程

    hdoj1001标程

    hdoj杭电入门训练题

    ### hdoj杭电入门训练题 #### 概述 杭电在线评测系统(HDOJ)是中国杭州电子科技大学提供的一套在线编程题库平台,主要用于计算机程序设计竞赛(ACM-ICPC)的训练与选拔。对于初学者而言,通过解决HDOJ中的题目可以...

    hdoj 2013 多校训练4标程+解题报告

    【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...

    hdoj1004 解题代码 答案

    hdoj1004,解题代码,答案代码,欢迎下载

    OJ.tar.gz_HDOJ _OJ源码_oj

    【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...

    HDOJ1003

    ACM ICPC HDOJ1003

    hdoj 2013 多校训练2标程+解题报告

    “hdoj 2013 多校训练2标程+解题报告”这个标题指的是2013年举行的一场由hdoj(HDU Online Judge,即杭州电子科技大学在线评测系统)组织的多校联合编程训练活动的第二阶段。其中,“标程”是指官方提供的正确解答...

    hdoj解题代码

    这些文件是针对“hdoj”(HDU Online Judge)在线编程竞赛平台的解题代码,涵盖了题目编号从1000到1050的若干题目。HDU Online Judge是一个用于训练和测试编程技能的系统,用户可以提交代码解决各种算法问题,并获取...

    HDOJ 1008

    ACM ICPC HDOJ1008

Global site tag (gtag.js) - Google Analytics