热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

开发笔记:P4051[JSOI2007]字符加密解题报告

篇首语:本文由编程笔记#小编为大家整理,主要介绍了P4051[JSOI2007]字符加密解题报告相关的知识,希望对你有一定的参考价值。

篇首语:本文由编程笔记#小编为大家整理,主要介绍了P4051 [JSOI2007]字符加密 解题报告相关的知识,希望对你有一定的参考价值。



P4051 [JSOI2007]字符加密

题目描述

喜欢钻研问题的JS 同学,最近又迷上了对加密方法的思考。一天,他突然想出了一种他认为是终极的加密办法:把需要加密的信息排成一圈,显然,它们有很多种不同的读法。

例如JSOI07,可以读作: JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序: 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 读出最后一列字符:I0O7SJ,就是加密后的字符串(其实这个加密手段实在很容易破解,鉴于这是突然想出来的,那就^^)。 但是,如果想加密的字符串实在太长,你能写一个程序完成这个任务吗?


输入输出格式


输入格式:

输入文件包含一行,欲加密的字符串。注意字符串的内容不一定是字母、数字,也可以是符号等。


输出格式:

输出一行,为加密后的字符串。


说明

对于(40\%)的数据字符串的长度不超过(10000)

对于(100\%)的数据字符串的长度不超过(100000)



果然人傻就没救了..

我居然想直接把串按倍增拿出来排序,然后成功写不出来,码力太渣了...

然后先倍长直接后缀排序就可以了。

这样做是对的,因为要么在前面n就比出来,要么到最后都比不出来。



Code:

#include
#include
#include
const int N=2e5+10;
char s[N];
int sa[N],Rank[N],tax[N],sec[N],n,m;
void Qsort()
{
for(int i=1;i<=m;i++) tax[i]=0;
for(int i=1;i<=n;i++) ++tax[Rank[i]];
for(int i=2;i<=m;i++) tax[i]+=tax[i-1];
for(int i=n;i;i--) sa[tax[Rank[sec[i]]]--]=sec[i];
}
bool cmp(int x,int y,int l){return sec[x]==sec[y]&&sec[x+l]==sec[y+l];}
void SuffixSort()
{
scanf("%s",s+1);n=strlen(s+1);
for(int i=1;i<=n;i++) Rank[i]=Rank[i+n]=s[i+n]=s[i],sec[i]=i,sec[i+n]=i+n;
m=128,n<<=1;Qsort();
for(int p=0,w=1;p {
p=0;for(int i=n-w+1;i<=n;i++) sec[++p]=i;
for(int i=1;i<=n;i++) if(sa[i]>w) sec[++p]=sa[i]-w;
Qsort();std::swap(Rank,sec);
Rank[sa[1]]=p=1;
for(int i=2;i<=n;i++) Rank[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
}
}
int main()
{
SuffixSort();
for(int i=1;i<=n;i++)
if(sa[i]<=n>>1)
printf("%c",s[sa[i]+(n>>1)-1]);
return 0;
}


2018.12.15


推荐阅读
  • Hadoop MapReduce 实战案例:手机流量使用统计分析
    本文通过一个具体的Hadoop MapReduce案例,详细介绍了如何利用MapReduce框架来统计和分析手机用户的流量使用情况,包括上行和下行流量的计算以及总流量的汇总。 ... [详细]
  • 本文介绍了如何使用Java编程语言实现凯撒密码的加密与解密功能。凯撒密码是一种替换式密码,通过将字母表中的每个字母向前或向后移动固定数量的位置来实现加密。 ... [详细]
  • java datarow_DataSet  DataTable DataRow 深入浅出
    本篇文章适合有一定的基础的人去查看,最好学习过一定net编程基础在来查看此文章。1.概念DataSet是ADO.NET的中心概念。可以把DataSet当成内存中的数据 ... [详细]
  • 本文由公众号【数智物语】(ID: decision_engine)发布,关注获取更多干货。文章探讨了从数据收集到清洗、建模及可视化的全过程,介绍了41款实用工具,旨在帮助数据科学家和分析师提升工作效率。 ... [详细]
  • 页面预渲染适用于主要包含静态内容的页面。对于依赖大量API调用的动态页面,建议采用SSR(服务器端渲染),如Nuxt等框架。更多优化策略可参见:https://github.com/HaoChuan9421/vue-cli3-optimization ... [详细]
  • 如何高效学习鸿蒙操作系统:开发者指南
    本文探讨了开发者如何更有效地学习鸿蒙操作系统,提供了来自行业专家的建议,包括系统化学习方法、职业规划建议以及具体的开发技巧。 ... [详细]
  • 本文详细介绍了在MyBatis框架中如何通过#和$两种方式来传递SQL查询参数。使用#方式可以提高执行效率,而使用$则有助于在复杂SQL语句中更好地查看日志。此外,文章还探讨了不同场景下的参数传递方法,包括实体对象、基本数据类型以及混合参数的使用。 ... [详细]
  • 本文详细探讨了编程中的命名空间与作用域概念,包括其定义、类型以及在不同上下文中的应用。 ... [详细]
  • 初探Hadoop:第一章概览
    本文深入探讨了《Hadoop》第一章的内容,重点介绍了Hadoop的基本概念及其如何解决大数据处理中的关键挑战。 ... [详细]
  • 个人博客:打开链接依赖倒置原则定义依赖倒置原则(DependenceInversionPrinciple,DIP)定义如下:Highlevelmo ... [详细]
  • 本文详细探讨了在Windows 98环境下安装Apache 1.3.9、JServ、GNUJSP 1.0、JDK 1.2.2及JSDK 2.0后遇到的中文显示问题,并提供了多种有效的解决方案。 ... [详细]
  • 本文介绍了一个来自AIZU ONLINE JUDGE平台的问题,即清洁机器人2.0。该问题来源于某次编程竞赛,涉及复杂的算法逻辑与实现技巧。 ... [详细]
  • egg实现登录鉴权(七):权限管理
    权限管理包含三部分:访问页面的权限,操作功能的权限和获取数据权限。页面权限:登录用户所属角色的可访问页面的权限功能权限:登录用户所属角色的可访问页面的操作权限数据权限:登录用户所属 ... [详细]
  • MVC模式下的电子取证技术初探
    本文探讨了在MVC(模型-视图-控制器)架构下进行电子取证的技术方法,通过实际案例分析,提供了详细的取证步骤和技术要点。 ... [详细]
  • Docker安全策略与管理
    本文探讨了Docker的安全挑战、核心安全特性及其管理策略,旨在帮助读者深入理解Docker安全机制,并提供实用的安全管理建议。 ... [详细]
author-avatar
beauty360尜囡囡
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有