首页 > 代码库 > HDU 4850 Wow! Such String! 【欧拉回路】【一顿乱构造】
HDU 4850 Wow! Such String! 【欧拉回路】【一顿乱构造】
link: http://acm.hdu.edu.cn/showproblem.php?pid=4850
题解：
每个长度为3的字符串当一个节点，每个节点连出26条边，代表给长度为3的字符串吼添加‘a‘~‘z‘
那我们每条边经过一次，就能构造出长度为26^4 + 3的字符串！
我们从"aaa"表示的节点出发，注意到每个点出度为26，入度也为26。
所以，非"aaa"的节点，能进去就能离开。(因为这些点是：先入再出)
"aaa"表示的节点，进入26次后就再也出不去了。（"aaa"：先出再入）
所以啊，我们尽可能的不回"aaa"节点。三顾家门而不入(( ≧?≦))
#include <iostream>
using namespace std;
const int NICO = 26*26*26*26+3;
int used[26][26][26][26];
int a[500000];
void init()
{
a[1] = a[2] = a[3] = 0;
for(int i=4;i<=NICO;i++)
{
for(int j=25;j>=0;j--)
{
if(used[a[i-3]][a[i-2]][a[i-1]][j] == 0)
{
used[a[i-3]][a[i-2]][a[i-1]][j] = 1;
a[i] = j;
break;
}
}
}
}
int n;
int main()
{
init();
while(~scanf("%d", &n))
{
if(n > NICO)
{
printf("Impossible\n");
} else {
for(int i=1;i<=n;i++)
{
printf("%c", a[i] + ‘a‘);
}
printf("\n");
}
}
}
训练赛的时候，智障の队友写的DFS各种爆栈, MLE，(｀?ω′? )v。
然后智障の队友突然觉醒了，优化一波后AC了。【好吧，虽然我更智障】
但还是觉得贪心构造更加赏心悦目！
HDU 4850 Wow! Such String! 【欧拉回路】【一顿乱构造】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。