TIANKENG’s restaurant(Ⅱ) hdu 4886 思维暴力_i - tiankeng’s restaurant(Ⅱ)-程序员宅基地

技术标签: 思维  

TIANKENG’s restaurant(Ⅱ)

Time Limit: 16000/8000 MS (Java/Others)    Memory Limit: 130107/65536 K (Java/Others)
Total Submission(s): 717    Accepted Submission(s): 257


Problem Description
After improving the marketing strategy, TIANKENG has made a fortune and he is going to step into the status of TuHao. Nevertheless, TIANKENG wants his restaurant to go international, so he decides to name his restaurant in English. For the lack of English skills, TIANKENG turns to CC, an English expert, to help him think of a property name. CC is a algorithm lover other than English, so he gives a long string S to TIANKENG. The string S only contains eight kinds of letters-------‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’. TIANKENG wants his restaurant’s name to be out of ordinary, so the restaurant’s name is a string T which should satisfy the following conditions: The string T should be as short as possible, if there are more than one strings which have the same shortest length, you should choose the string which has the minimum lexicographic order. Could you help TIANKENG get the name as soon as possible?

Meanwhile, T is different from all the substrings of S. Could you help TIANKENG get the name as soon as possible?
 

Input
The first line input file contains an integer T(T<=50) indicating the number of case.
In each test case:
Input a string S. the length of S is not large than 1000000.
 

Output
For each test case:
Output the string t satisfying the condition.(T also only contains eight kinds of letters-------‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’.)
 

Sample Input
  
  
   
3 ABCDEFGH AAABAACADAEAFAGAH ACAC
 

Sample Output
  
  
   
AA BB B

看了数据这么长,以为肯定是某个数据结构。。。。

其实并不是。。。。

题意:给一个串,求不是这个串的子串的字典序最小的那个字符串

其实结果最大长度不会超过7,可以想一下长度小于等于7的字符串就已经有8^7种了(只有A~H八种字符),如果一个串的子串这些都包括了,那这个串必然特别长,会超过1000000(估计法。。),所以就只需要暴力一下串就可以了,map复杂度会高一写,可以使用O1的hash,把字符串当做一个八进制数

为了区别A和AA,不同长度的可以分别考虑

#include<bits/stdc++.h>
using namespace std;
int book[5000005];
int main()
{
    ios::sync_with_stdio(0);
    int T,i,n,j,k;
    cin>>T;
    string s;
    while(T--)
    {
        cin>>s;
        string ans;
        int flog=0;
        for(i=0;i<6;i++)
        {
            memset(book,0,sizeof(book));
            for(j=0;j+i<s.size();j++)
            {
                int now=0;
                for(k=j;k<=j+i;k++)
                {
                    now=now*8+s[k]-'A';
                }
                book[now]=1;
            }
            int up=(int)pow(8,i)*8;
            int len=0;
            for(j=0;j<up;j++)
            {
                if(book[j]==0)
                {
                    while(j)
                    {
                        ans=(char)('A'+j%8)+ans;
                        len++;
                        j/=8;
                    }
                    for(;len<=i;len++)
                        ans='A'+ans;
                    cout<<ans<<endl;
                    flog=1;
                    break;
                }
            }
            if(flog)
                break;
        }
    }
    return 0;
}




版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/jerans/article/details/73008539

智能推荐

查看ES版本号(Elasticsearch)-程序员宅基地

文章浏览阅读2.1k次。记录下说明:Elasticsearch 是一个分布式、高扩展、高实时的搜索与数据分析引擎。它能很方便的使大量数据具有搜索、分析和探索的能力。充分利用Elasticsearch的水平伸缩性,能使数据在生产环境变得更有价值。Elasticsearch 的实现原理主要分为以下几个步骤,首先用户将数据提交到Elasticsearch 数据库中,再通过分词控制器去将对应的语句分词,将其权重和分词结果一并存入数据,当用户搜索数据时候,再根据权重将结果排名,打分,再将返回结果呈现给用户。Elasticsearch是._es版本号

C语言中遇见Conflicting types for ‘ ‘类型说明什么(大学生)_conflicting types for 'p-程序员宅基地

文章浏览阅读4.8k次,点赞5次,收藏4次。实例我学校的编程课用的是这本教材The.C.Programming.Language.2Nd.Ed。Prentice.Hall.Brian.W.Kernighan.and.Dennis.M.Ritchie.增删改补是这本书的精华所在,谭浩强先生的书更偏向数学逻辑。The.C.Programming.Language.这本书它采用的是C89规则由于函数库中含有子函数的名称,写实验报告时将给的子函数套用主函数后,会出现Conflicting types for ’ '类型的错误这个时候我们_conflicting types for 'p

CSAPP实验-DadaLab_csapp 所有实验-程序员宅基地

文章浏览阅读1k次。简介csapp的datalab配套实验, 要求修改bits.c源文件使所有给定函数满足功能并通过btest的所有测试用例,每个实现函数内均对使用的运算符种类和数量有所限制,可以用dlc程序进行检查。该实验主要为了强化理解整形和浮点型数据的编码形式和位运算相关知识。实验内容bitXor实现异或操作/* * bitXor - x^y using only ~ and & * ..._csapp 所有实验

Tomcat 连接池的配置-程序员宅基地

文章浏览阅读98次。转录笔记:不过遗憾的是,如下几种方法都没有在我的机器上配置成功(Tomcat5.5.17 + WinXPSP2)。正确配置见我自己的评论,Tomcat 的日志中没发现什么错误,看上去都很正常,但是测试程序却老是提示同样的错误:Error occurred:org.apache.tomcat.dbcp.dbcp.SQLNestedException: Cannot create JDBC drive..._tomcat xianchenchi

Java 9 逆天的十大新特性_java最新版本是几-程序员宅基地

文章浏览阅读110次。在介绍java9之前,我们先来看看java成立到现在的所有版本。1990年初,最初被命名为Oak;1995年5月23日,Java语言诞生;1996年1月,第一个JDK-JDK1.0诞生;1996年4月,10个最主要的操作系统供应商申明将在其产品中嵌入Java技术;1996年9月,约8.3万个网页应用了Java技术来制作;1997年2月18日,JDK1.1发布;1997年4月2日,JavaOne会议召开,参与者逾一万人,..._java最新版本是几

python正则匹配常见错误_python正则匹配出错-程序员宅基地

文章浏览阅读478次。for line in f:searchObj = re.search(r’static bl_u8_t__attribute__((section(".my_f180")))f180[17] = (.*)’, line)括号需要用转义字符转换_python正则匹配出错

随便推点

卡片 -蓝桥 -java_卡片蓝桥java-程序员宅基地

文章浏览阅读301次。卡片最大运行时间:1s最大运行内存: 128M题目描述:小蓝有很多数字卡片,每张卡片上都是数字 0 到 9。 小蓝准备用这些卡片来拼一些数,他想从 1 开始拼出正整数,每拼一个, 就保存起来,卡片就不能用来拼其它数了。 小蓝想知道自己能从 1 拼到多少。 例如,当小蓝有 30 张卡片,其中 0 到 9 各 3 张,则小蓝可以拼出 1 到 10, 但是拼 11 时卡片 1 已经只有一张了,不够拼出 11。 现在小蓝手里有 0 到 9 的卡片各 2021 张,共 20210 张,请问小蓝可以从 1 _卡片蓝桥java

支付网关和api网关_将您的钱放在鼠标所在的位置:已审查6个支付网关-程序员宅基地

文章浏览阅读3.9k次。支付网关和api网关So you’re starting your own ecommerce Website? Good for you! But you have many decisions to make. Do you write your own shopping cart or use an existing one? Who should be your merchant acco..._make pay gateway

network namespace与veth pair_如何查看veth归属哪个namespace-程序员宅基地

文章浏览阅读1.2w次。network namespace创建network namespace# ip netns add blue# ip netns listblue 添加网口到namespace先创建veth# ip link add veth0 type veth peer name veth1在当前namespace可以看到veth0和veth1# ip link _如何查看veth归属哪个namespace

LeetCode1-540题汇总,希望对你有点帮助!-程序员宅基地

文章浏览阅读239次。时间很快,公众号发布的LeetCode题目,已经达到520道题了。今天把发布的1-520篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相信很多人都没看过,如果对于算..._leetcode1-540题汇总,希望对你有点帮助!

北邮通信土著--非技术路线备忘录 (摘自北邮人论坛)_hku committee 面试 cs-程序员宅基地

文章浏览阅读3.3k次。作者:5yearszz 谨此文,感谢求职漫漫路帮助过我、与我分享过的兄弟姐妹!共勉~北邮七载,想留下些东西,为母校能继续保持就业传统之优势,尽微薄贡献! 校园 理工科背景申请各类行业非纯技术岗位可行性分析,欢迎拍砖。专业背景或求职意向不符,请绕行。 专业背景:

【人脸识别数据集】MS-Celeb-1M 下载、读取、超细处理步骤及踩坑心得-程序员宅基地

文章浏览阅读3.7k次,点赞19次,收藏29次。直接上数据集种子下载地址。​torrent种子的解压方法见(linux系统):解压种子链接:【Linux操作】常用命令整理。下载完之后大概230G,我只下载了其中对齐人(FaceimageCroppedWithAlignment.tsv)的部分,大概90G,需要提前分配一下空间。​这里提供了干净的数据集列表和重标签后的数据集列表。_ms-celeb-1m