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<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>
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"<<endl;
// 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<M;++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<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>
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"<<endl;
// 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<M;++i)
{
cin>>c;
hav[c]=1;// 標志為1的數字不能夠使用
}
printf("Case %d: ",++ca);
bfs();
}
return 0;
}
