Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //UVA129KryptonFactor
- #include<cstdio>
- #include<cstdlib>
- #include<cstdlib>
- #include<cstring>
- const int MAXN = 80 + 5;
- int cnt = 0;
- int a[MAXN];
- int n, L;
- int dfs(int cur) {
- if(cnt++ == n) {
- for(int i = 0; i < cur; i++) {
- if(i && i % 4 == 0 && i % 64 != 0) printf(" ");
- if(i && i % 64 == 0) printf("\n");
- printf("%c", 'A' + a[i]);
- }
- printf("\n");
- printf("%d\n", cur);
- return false;
- }
- else {
- for(int i = 0; i < L; i++) {
- bool ok = 1;
- a[cur] = i;
- // printf("cur = %d, a[cur] = %c\n", cur, 'A' + i);
- for(int j = 1; 2 * j <= cur + 1; j++) {
- bool equal = 1;
- for(int k = 0; k < j; k++) if(a[cur - k] != a[cur - k - j]) {///加入一个字符,就判断以这个字符为末尾的j长度的串和在此之前的
- //j长度的串是否相等,本题回溯法核心!!
- // printf("a[%d] = %c, a[%d] = %c\n", cur - k, 'A' + a[cur - k], cur - k - j, 'A' + a[cur - k - j]);
- equal = false; break;
- }
- if(equal) {
- ok = 0; break;//只要出现一种不满足的串,则不符合要求
- }
- }
- // printf("ok = %d\n", ok);
- if(ok) if(!dfs(cur + 1)) return false;
- }
- }
- //printf("cnt = %d\n", cnt);
- return true;
- }
- int main() {
- while(scanf("%d%d", &n, &L) == 2 && n) {
- memset(a, 0, sizeof(a));
- cnt = 0;
- dfs(0);
- }
- return 0;
- }
- /*
- 7 3
- 30 3
- 0 0
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement