首页 > 代码库 > HDOJ4886(hash+枚举)

HDOJ4886(hash+枚举)

2024-07-14 11:25:03   223人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4886

思路是队友想出来的，代码我写。

因为只有8个字母，容易证明答案只会在长度为8之内。长于8的因为可以用长度n+8得到，所以不存在。从长度1到8依次枚举所有原串中的子串，并将此串当成8进制存在哈希表中，每次枚举前都将哈希表置空，而后再从小到大遍历哈希表，将第一个没用过的下标换算为字符串输出，当位数不够时注意前导0处加‘A’。

  1 #include<iostream>  2 #include<stdio.h>  3 #include<string.h>  4 using namespace std;  5 int f[10],h[2100005];  6 char s[1000005];  7 int init()  8 {  9     int ans=1; 10     memset(h,0,sizeof(h)); 11     for(int i=0;i<9;i++) 12     { 13         f[i]=ans; 14         ans*=8; 15     } 16 } 17 int eight(char ss[]) 18 { 19     int ans=0,l=strlen(ss)-1; 20     for(int i=strlen(ss)-1;i>=0;i--) 21     { 22         ans+=(ss[i]-‘A‘)*f[l-i]; 23     } 24     return ans; 25 } 26 char *ret(char *s,int n) 27 { 28     int l=0,ll=0; 29     //cout<<n<<endl; 30     char c[10]; 31     while(n) 32     { 33         c[l++]=n%8+‘A‘; 34         n/=8; 35     } 36     s[l]=0; 37     while(l--) 38     { 39         s[ll++]=c[l]; 40     } 41     return s; 42 } 43 int Pow(int x,int l) 44 { 45     int ans=1; 46     while(l--)ans*=8; 47     return ans; 48 } 49 int main() 50 { 51     int t; 52     char c[10]; 53     init(); 54     cin>>t; 55     gets(c); 56     //cout<<Pow(8,2)<<endl; 57     while(t--) 58     { 59         gets(s); 60         init(); 61         int len=strlen(s); 62         int flag=1; 63         for(int i=0;i<7&&i<=len&&flag;i++) 64         { 65             memset(h,0,sizeof(h)); 66             for(int j=0;s[j];j++) 67             { 68                 if(j+i<len) 69                 { 70                     char a[10]; 71                     int l=0; 72                     for(int k=j;k<=i+j;k++) 73                     { 74                         a[l++]=s[k]; 75                     } 76                     a[l]=0; 77                     h[eight(a)]=1; 78                     //cout<<a<<"=="<<eight(a)<<endl; 79                 } 80             } 81             //cout<<h[eight("AD")]<<endl; 82             int e=Pow(8,i+1); 83             for(int q=0;q<e;q++) 84             if(h[q]==0) 85             { 86                 int temp=i+1-strlen(ret(c,q)); 87                 for(int j=0;j<temp;j++) 88                 cout<<‘A‘; 89                 cout<<ret(c,q)<<endl; 90                 flag=0; 91                 break; 92             } 93         } 94  95     } 96     return 0; 97 } 98 /* 99 5100 ABCDEFGHAAABAC101 */
View Code

 


联系
我们