hdu4474-Yet Another Multiple Problem - c++编程基础

Yet Another Multiple Problem
模型转换 BFS搜索根据剩余类建图广搜
K -Yet Another Multiple Problem点击打开链接

此题如果处理得不好可能会造成非常多的特殊情况需要特判。一种比较简洁的处理方法是：首先建有向图i->(i*10+j)%n，然后沿着这个图反向从0'广搜0算出每个点到0的最短距离，最后从0开始沿着这个图正向广搜，利用刚才的最短距离表直接递推出答案的每一位。另一种处理方法是直接用string记录答案，不过要注意常数。时间复杂度每组数据O(n)。

题意：

　　给一个N(n<=1e4), M个数字(长度为1),问最小的数x(x%n=0) 不包含这m个数。

思路:

　　直接求,没想出解法.

　　对于一个数 x%n = m, 则 x` = x*10+i , 有 m` = (m*10+i)%n

　　我们可以利用除了M个数字外的数来构造这个 X.

　　因为需要最小的, 则其长度与字典序排列皆最小. 通过BFS进行搜索. 每一个模n的余数之取第一次出现的,

因为之后再出现的. 只可能更长或者更大. 必定不是最优解.

　　搜索节点,保存三个信息: 当前x的最后一位, 当前x%n的余数, 当前节点的父亲节点.

　　结果输出利用记忆父亲节点 ,然后递归输出即可.

[cpp]
// File Name: hdu4474.cpp
// Author: rudolf
// Created Time: 2013年04月26日星期五 14时06分16秒

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
int N,M;
char hav[15];
char vis[10005];

struct node
{
int mod,f;// mod表示对N取余后的值，f表示父亲节点的编号
char digit; // 当前放置的数字为多少

}info,que[10005];

inline bool ok(int x,int &ans)
{
if(que[x].mod==0)
{
ans=x;
return true;
}
return false;
}

void print(int x)
{
if(que[x].f!=-1)
print(que[x].f);
printf("%d",que[x].digit);
}

void bfs()
{
int ans,front=0,tail=0;
bool finish=false;
for(int i=1;i<10;++i)
{
if(!hav[i])
{// 如果这个数码没有被限制
que[tail].mod=i % N;//把所有的包括输入m项例如7、8、9、17、18、19.。。。都排除了~~~~
if(vis[que[tail].mod])
continue;// 判定这个余数是否已经走过

vis[que[tail].mod]=1;
que[tail].digit=i;//存放某一个满足掉的位置的数值
que[tail].f=-1;// -1是一个特殊的标识，表示到了根节点
// 把一个合法的初始化根节点加入到队列中去
if(ok(tail,ans))
{
finish=true;
break;
}
++tail;
}

}
while(!finish&&tail!=front)
{
info=que[front++];// 取出队首元素
for(int i=0;i<10;++i)
{
if(!hav[i])
{
//第二次执行该语句，将队列中的数据不断扩大，最后找到能够MOD n的非输入数据的最小数值 que[tail].mod=(info.mod * 10 + i) % N;
if(vis[que[tail].mod])
continue;
vis[que[tail].mod]=1;
que[tail].digit=i;
que[tail].f=front-1;// 保留上一个状态的编号
if(ok(tail,ans))
{
finish=true;
break;
}
++tail;
}
// tail++;
}
}
if(finish)
{
print(ans);
puts("");
}
else
cout<<"-1"< // puts(" ");
}

int main()
{
int c,ca=0;
while(cin>>N>>M)
{
memset(hav,0,sizeof(hav));
memset(vis,0,sizeof(vis));
for(int i=0;i {
cin>>c;
hav[c]=1;// 标志为1的数字不能够使用

}
printf("Case %d: ",++ca);
bfs();
}
return 0;
}

// File Name: hdu4474.cpp
// Author: rudolf
// Created Time: 2013年04月26日星期五 14时06分16秒

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
int N,M;
char hav[15];
char vis[10005];

struct node
{
int mod,f;// mod表示对N取余后的值，f表示父亲节点的编

hdu4474-Yet Another Multiple Problem (一)