洛谷 129. UVA Krypton Factor dfs
原题链接
简单
作者:
kxzz
,
2022-06-26 22:43:17
,
所有人可见
,
阅读 130
此题的判断很有意思
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000;
int a[N];
int n,m;
int cnt;
bool flag;
void dfs(int u)
{
if(cnt++ == n)//每递归一层就会产生一个合法的新数
{
for (int i = 0; i < u; i ++)
{
if (i > 0)
{
if (i % 64 == 0) printf("\n");
else if (i % 4 == 0) printf(" ");
}
printf("%c", 'A' + a[i]);
}
printf("\n%d\n", u);
flag = true;//如果找到答案标记一下
return;
}
/*
0 1 2 3 4 2 u = 4
j : 1 2
k : 0 1
j = 1
u - k :4
u - k - j :3
j = 2
u - k :4 3
u - j - k:2 1
*/
for(int i = 0; i < m; i ++)
{
a[u] = i;
bool ok = true;
//由于我们是一个字符一个字符的加,所以我们只需要以结尾新加的字符为起点,枚举和前面是否有重复即可
//例子:对于这个字串abcdef,假设f是新加的那么我们从f开始枚举
//长度为1:f,e 长度为2:fe cd 依次类推
for(int j = 1;j * 2 <= u + 1; j ++)//间隔至少是1
{
bool equal = true;
//检查是否存在相等子串
for(int k = 0; k < j ; k ++)
{
if(a[u - k] != a[u - k - j])
{
equal = false;
break;
}
}
if(equal)
{
ok = false;
break;
}
}
//ok为true则没有相等字串递归到下一层
if(ok)dfs(u + 1);
if(flag)return;//找到答案就不要往后找了直接返回
}
}
int main()
{
while(cin >> n >> m, n || m)
{
cnt = 0;
flag = false;
dfs(0);//当前已经用了几个字母
}
return 0;
}