加载中…POJ 1780欧拉回路建模 最小字典序
(2011-08-05 18:57:44)
标签：
poj1780欧拉回路最小字典序it |
分类： 图论 |
题目描述：
给你一个数字n，表示密码由n位数字构成，让你构造一个字典序最小的串，让这10^n种密码都是这个串的子串，同时每种密码在这个串中近出现一次。
解题报告：
比如n=6，对于密码123456，则在12345和23456之间建立一条边（前者到后者的有向边），这条边就代表123456这个密码。边上的值是6.
每个点的边按边值排序，然后按照欧拉回路搜索的方法搜索即可:正常一笔画，没有走错路的话，就是正常的BFS，每步贪心，肯定正确。否则，走错路的部分一定是要放在最后的（画一画图就明白了），直接入栈，压根和字典序没有关系。
代码如下：（题目用递归搜索会爆栈）
int to,
next; char val;
e[cnt].to = to; e[cnt].val = val; e[cnt].next =
v[from];
v[from]
= cnt++;
int
base = 1;
for(int
i = 1; i < n; i++) base *= 10;
memset(v, -1, sizeof(v)); cnt = 0;
int
base2 = base * 10;
for(int
i = base2; i >= 0; i--)
{
int fir = i / 10, sec = i %
base, tar = i % 10;
insert(fir, sec, tar +
'0');
}
int top
= 0;
sta[0][0] = 0; sta[0][1] = -1; sta[0][2] =
v[0];
top++;
while(top)
{
int id = sta[top - 1][0], val
= sta[top - 1][1], i = sta[top - 1][2];
while(i != -1
&& e[i].to == -1) i =
e[i].next;
if (i != -1)
{
int to = e[i].to;
e[i].to = -1;
sta[top - 1][2] = e[i].next;
sta[top][0] = to; sta[top][1] = e[i].val;
sta[top][2] = v[to];
top++;
}else
{
if (val >= 0)
ans[now].push_back(val);
top--;
}
}
for(int
i = 1; i <= 6; i++)
{
now = i;
judge(i); eul();
for(int j = 1; j
< i; j++) ans[i].push_back('0');
}
int nn;
while(scanf("%d", &nn)
&& nn)
{
for(int i = ans[nn].size() -
1; i >= 0; i--)
putchar(ans[nn][i]);
putchar('\n');
}
代码如下：（题目用递归搜索会爆栈）
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
int n;
vector<char> ans[7];
struct edge
{
}e[10000000];
int v[1000000], cnt;
void insert(int from, int to, char val)
{
}
int sta[2000000][3];
void judge(int n)
{
}
int now;
void eul()
{
}
int main()
{
return 0;
}
喜欢
0
赠金笔