HDU 4886 TIANKENG’s restaurant(Ⅱ) ( 暴力+hash )
2024-09-06 01:38:15
TIANKENG’s restaurant(Ⅱ)
Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 130107/65536 K (Java/Others)
Total Submission(s): 466 Accepted Submission(s): 153
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.
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’.)
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
因为只有8个字母 。
那么先枚举长度 ( i = 1 ~ 8 )。
O(n)处理出该长度下主串存在的子串。
再枚举排列 ( j = 0 ~ i ! )判存。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <algorithm> using namespace std; typedef long long LL;
typedef pair<int,int> pii;
const int N = ;
const int M = ;
const int inf = 1e9+;
const double eps = 1e-;
bool vis[M];
char str[N];
int a[N],f[N],len; void get_s( int n , int cnt ,char *s) {
for( int i = cnt- ; i >= ; --i ){
s[i] = (n%)+'A';
n/=;
}
s[cnt] = ;
} int check( int n ) {
int tmp = ;
if( len < n ) return -;
for( int i = ; i < f[n] ; ++i ) vis[i] = false ;
for( int i = ; i < n ; ++i )
tmp = tmp * + a[i] ;
vis[tmp] = true ;
for( int i = n ; i < len ; ++i ){
tmp = ( tmp % f[n-] ) * + a[i] ;
vis[tmp] = true ;
}
for( int i = ; i < f[n] ; ++i )if(!vis[i]){
return i ;
}
return - ;
} void Run(){
scanf("%s",str); len = strlen(str);
for( int i = ; i < len ; ++i ) a[i] = str[i]-'A';
for( int i = ; i <= ; ++i ){
int res = check(i) ;
if( res == - ) continue ;
get_s(res,i,str) ;
puts(str);
return ;
}
} int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif // LOCAL
int tot = , m = ; f[] = ;
for( int i = ; i < ; ++i ) m *= ,f[tot++] = m ;
int _ ; scanf("%d",&_);
while( _-- ) Run();
}
最新文章
- FZU5BOYS-Beta版本冲刺计划及安排
- swift 子类继承父类
- Magento产品批量导入方法?
- NServiceBus教程-消息传递与处理
- 13.mariadb-rhce考试解题思路
- 简单dp-poj-2231-Moo Volume
- HDU-4920 Matrix multiplication
- 安装Codeception框架
- Unity3D中切换场景可能导致材质变暗的问题
- 大数据学习(2)HDFS文件管理
- Jenkins 关闭和重启实现方式.
- django 下拉菜单显示为object的解决办法
- centos6.5中rpm包安装mysql5.7(初始化出错如何解决)
- Spring Boot + Jersey发生FileNotFoundException (No such file or directory)
- 将个人博客从GitHub迁移至阿里云服务器过程总结
- H2 Database Engine
- linux svn安装 及 常用命令
- 基于三层架构项目下的Ado【六】
- Fence Repair POJ - 3253 哈夫曼思想 优先队列
- VS2013中如何解决error C4996: &#39;fopen&#39;问题