HDU - 4886 (hash + 폭력 매 거)

제목: 메 인 꼬치 s ('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' 만 포함) 를 주 고 하나의 꼬치 ans ('A', 'B', 'C', 'D', 'E', 'F', 'H' 만 포함) 를 찾 아야 합 니 다. ans 만족 조건: s 모든 하위 꼬치 에 나타 나 지 않 았 습 니 다. 그 다음 에 길이 가 가장 짧 고 마지막 으로 사전 순서 가 가장 작 습 니 다.
사고방식: ans 의 길이 가 가장 긴 것 은 7 로 추정 할 수 있다. 왜냐하면 메 인 문자열 s 에 모든 8 개의 문자 가 존재 하 는 배열 의 길 이 는 8 ^ 7 이 어야 하기 때문에 제목 이 정 한 길 이 를 초과 했다.모든 길이 의 하위 문자열 을 열거 한 다음 문자열 하 쉬 를 진수 로 만 듭 니 다. 8 진법 일 수도 있 고 9 진법 일 수도 있 지만 둘 은 다 를 수 있 습 니 다.
8 진법 은 AABCAD 가 001203 (기수 8) 에 대응 하고 int 범 위 를 폭발 시 키 지 않 는 다 는 것 이 분명 하 다.매 거 진 길이 1 - 7 의 모든 하위 문자열 은 8 진법 으로 해시 표 에 존재 합 니 다. 매 거 진 전에 해시 표를 비 워 야 합 니 다. 그리고 어 릴 때 부터 해시 표를 옮 겨 다 니 며 첫 번 째 사용 하지 않 은 아래 표 시 를 문자열 로 출력 하면 됩 니 다. 0 은 A 를 표시 할 수도 있 고 AAA 를 표시 할 수도 있 기 때문에 자릿수 (하위 문자열 길이) 가 부족 할 때 선도 0 을 통 해 'A' 를 추가 합 니 다.
9 진 AABCAD 는 112314 (기수 9) 에 대응 하고 int 가 터 지지 않 기 때문에 모든 9 진 에 0 이 존재 하 는 수 는 합 법 적 이지 않 으 며 문자열 로 변환 하 는 과정 에서 어느 때 남 은 수가 9 를 제거 할 수 있다 는 것 을 발견 하면 9 진 이 0 으로 바 뀌 는 것 이 비합법적 이다.첫 번 째 합 법 적 인 아래 표 시 를 찾 아 문자열 로 변환 하면 ans 입 니 다.
Code(base 8):

#include 
using namespace std;
const int maxn = 1e6+5;
char s[maxn], ans[10];
int hs[maxn*3], wei[10];
int main()
{
	int t, len, k, cnt;
	wei[0] = 1;
	for(int i = 1; i <= 7; ++i) wei[i] = wei[i-1]*8;
	scanf("%d", &t);
	for(int _ = 1; _ <= t; ++_)
	{
		scanf("%s", &s);
		len = strlen(s);
		for(int i = 1; i <= 7; ++i)
		{
			memset(hs, 0, sizeof hs);
			for(int j = 0; j < len; ++j)
			{
				if(j+i > len) break;
				k = 0;
				for(int l = 0; l < i; ++l)
				{
					k = k*8 + (s[j+l]-'A');
				}
				++hs[k];
			}
			cnt = 0;
			for(int j = 0; j < wei[i]; ++j)
			if(!hs[j])
			{
				for(int l = i-1; l >= 0; --l)
				{
					printf("%c", j/wei[l] + 'A');
					j %= wei[l];
				}
				puts(""); cnt = -1;
				break;
			}
			if(cnt == -1) break;
		}
	}
	return 0;
}

Code(base 9):

#include 
using namespace std;
const int maxn = 1e6+5;
char s[maxn], ans[10];
int vis[maxn*6], wei[10];
int main()
{
	wei[0] = 1;
	for(int i = 1; i <= 7; ++i) wei[i] = wei[i-1]*9;
	int t, len, cnt, tmp;
	scanf("%d", &t);
	for(int _ = 1; _ <= t; ++_)
	{
		scanf("%s", &s);
		len = strlen(s);
		memset(vis, 0, sizeof vis);
		for(int i = 1; i <= 7; ++i)
		{
			if(i > len) break; tmp = 0;
			for(int j = 0; j < i; ++j)
				tmp = tmp*9 + (s[j]-'A'+1);
			vis[tmp] = 1;
			for(int j = i; j < len; ++j)
			{
				tmp = tmp%wei[i-1];
				tmp = tmp*9 + (s[j]-'A'+1);
				vis[tmp] = 1;
			}
		}
		for(int j = 1, k; j < maxn*6; ++j)
		if(!vis[j])
		{
			tmp = j, cnt = 0;
			while(tmp && tmp%9)
			{
				ans[cnt++] = 'A'+tmp%9-1;
				tmp /= 9;
			}
			if(!tmp)
			{
				ans[cnt] = '\0';
				break;
			}
		}
		reverse(ans, ans+cnt);
		printf("%s
", ans);
	}
	return 0;
}

계속 파 이 팅 ~