UVa 1569 - Multiple

Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4351

自己想不出這題,網路上題解也不多,後來研究了這篇的code才知道怎麼寫。

解法

想個暴利的解法,把題目給定的M個數字排序後,用這些數字去組合,BFS搜索下去(必須用BFS去搜索才會優先找到較小的數字),搜索的過程一邊模N就能判斷最後是不是N的倍數(搜索完成)。
不過這樣的作法複雜度是指數級別的,而且沒辦法判斷是不是找不到答案(需輸出0)。

接著我們可以發現一件事,假設某兩個狀態模N後是一樣的,則由他們到答案的路徑也是一樣的,所以他們之間較晚搜索到的數字可以直接忽略,因此狀態只剩下N種,紀錄一下哪個模數出現過即可。

狀態只剩下N種,在這幾種狀態中做BFS,複雜度O(N)。

AC code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> x;
bool u[5010];
string solve()
{
if(n==0) return "0";
memset(u,0,sizeof u);
queue<pair<string,int>> q; //first: value, second: remainder
q.push({"",0});
while(q.size())
{
pair<string,int> now=q.front(); q.pop();
for(int i:x)
{
if(i==0&&now.first=="") continue;
string s=now.first+char(i+'0');
int r=(now.second*10+i)%n;
if(r==0) return s;
if(!u[r])
{
u[r]=1;
q.push({s,r});
}
}
}
return "0";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int m;
while(cin>>n>>m)
{
x.resize(m);
for(int i=0;i<m;i++)
cin>>x[i];
sort(x.begin(), x.end());
cout<<solve()<<'\n';
}
}