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

#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';
	}
}