热门标签 | 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


推荐阅读
  • NOIP2000的单词接龙问题与常见的成语接龙游戏有异曲同工之妙。题目要求在给定的一组单词中,从指定的起始字母开始,构建最长的“单词链”。每个单词在链中最多可出现两次。本文将详细解析该题目的解法,并分享学习过程中的心得体会。 ... [详细]
  • 洛谷 P4035 [JSOI2008] 球形空间生成器(高斯消元法 / 模拟退火算法)
    本文介绍了洛谷 P4035 [JSOI2008] 球形空间生成器问题的解决方案,主要使用了高斯消元法和模拟退火算法。通过这两种方法,可以高效地求解多维空间中的球心位置。文章提供了详细的算法模板和实现代码,适用于 ACM 竞赛和其他相关应用场景。数据范围限制在 10 以内,确保了算法的高效性和准确性。 ... [详细]
  • 解题心得:UVA1339(逻辑分析与字符串处理+排序算法)
    解题心得:UVA1339(逻辑分析与字符串处理+排序算法) ... [详细]
  • 本文深入探讨了佩尔方程 \( x^2 - dy^2 = 1 \) 的递推关系式。通过构造特定的矩阵并利用矩阵快速幂的方法,可以高效地计算出该方程的第 k 组解。此外,文章还详细分析了递推关系式的数学背景及其在数论中的应用,为相关研究提供了坚实的理论基础。 ... [详细]
  • 本文深入解析了Java面向对象编程的核心概念及其应用,重点探讨了面向对象的三大特性:封装、继承和多态。封装确保了数据的安全性和代码的可维护性;继承支持代码的重用和扩展;多态则增强了程序的灵活性和可扩展性。通过具体示例,文章详细阐述了这些特性在实际开发中的应用和优势。 ... [详细]
  • Objective-C 中的委托模式详解与应用 ... [详细]
  • 如何利用Java 5 Executor框架高效构建和管理线程池
    Java 5 引入了 Executor 框架,为开发人员提供了一种高效管理和构建线程池的方法。该框架通过将任务提交与任务执行分离,简化了多线程编程的复杂性。利用 Executor 框架,开发人员可以更灵活地控制线程的创建、分配和管理,从而提高服务器端应用的性能和响应能力。此外,该框架还提供了多种线程池实现,如固定线程池、缓存线程池和单线程池,以适应不同的应用场景和需求。 ... [详细]
  • 在Java编程中,`AbstractClassTest.java` 文件详细解析了抽象类的使用方法。该文件通过导入 `java.util.*` 包中的 `Date` 和 `GregorianCalendar` 类,展示了如何在主方法 `main` 中实例化和操作抽象类。此外,还介绍了抽象类的基本概念及其在实际开发中的应用场景,帮助开发者更好地理解和运用抽象类的特性。 ... [详细]
  • 在当前的软件开发领域,Lua 作为一种轻量级脚本语言,在 .NET 生态系统中的应用逐渐受到关注。本文探讨了 Lua 在 .NET 环境下的集成方法及其面临的挑战,包括性能优化、互操作性和生态支持等方面。尽管存在一定的技术障碍,但通过不断的学习和实践,开发者能够克服这些困难,拓展 Lua 在 .NET 中的应用场景。 ... [详细]
  • 本文详细介绍了在CodeUp平台中实现大数进制转换的技术方法。具体而言,该问题要求将一个最多包含30位数字的十进制非负整数转换为二进制表示。输入数据包含多行,每行包含一个不超过30位的十进制非负整数。通过高效的算法设计,确保了大数转换的准确性和性能。 ... [详细]
  • 本文介绍了如何利用ObjectMapper实现JSON与JavaBean之间的高效转换。ObjectMapper是Jackson库的核心组件,能够便捷地将Java对象序列化为JSON格式,并支持从JSON、XML以及文件等多种数据源反序列化为Java对象。此外,还探讨了在实际应用中如何优化转换性能,以提升系统整体效率。 ... [详细]
  • 在 Linux 环境下,多线程编程是实现高效并发处理的重要技术。本文通过具体的实战案例,详细分析了多线程编程的关键技术和常见问题。文章首先介绍了多线程的基本概念和创建方法,然后通过实例代码展示了如何使用 pthreads 库进行线程同步和通信。此外,还探讨了多线程程序中的性能优化技巧和调试方法,为开发者提供了宝贵的实践经验。 ... [详细]
  • 在Linux系统中,通过使用`read`和`write`函数可以实现文件的高效复制操作。`open`函数用于打开或创建文件,其返回值为文件描述符,成功时返回一个有效的文件描述符,失败时返回-1。`path`参数指定了要操作的文件路径,而`oflag`参数则定义了文件的打开模式和属性。此外,为了确保数据的完整性和一致性,还需要合理处理文件读取和写入过程中的错误和异常情况。 ... [详细]
  • 数字图书馆近期展出了一批精选的Linux经典著作,这些书籍虽然部分较为陈旧,但依然具有重要的参考价值。如需转载相关内容,请务必注明来源:小文论坛(http://www.xiaowenbbs.com)。 ... [详细]
  • Java中不同类型的常量池(字符串常量池、Class常量池和运行时常量池)的对比与关联分析
    在研究Java虚拟机的过程中,笔者发现存在多种类型的常量池,包括字符串常量池、Class常量池和运行时常量池。通过查阅CSDN、博客园等相关资料,对这些常量池的特性、用途及其相互关系进行了详细探讨。本文将深入分析这三种常量池的差异与联系,帮助读者更好地理解Java虚拟机的内部机制。 ... [详细]
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社区 版权所有