a number puzzle(dfs+hash).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int n,m;
int x,k;
int card[11],ans;
bool mark[11];
int hash[110][110];

void dfs(int v,int d)
{
	if(d == n )//&& (v+x)%k == 0)
	{
		for (int j=1;j<100;j++) {
			if(hash[v%j][j]==0) {
				hash[v%j][j] = v;
			}
		}
	}
	for (int i=0;i<n;i++) {
		if(mark[i])	continue;
		if(card[i]==0 && v==0 ) {
			continue;
		}
		else {
			mark[i] = true;
			dfs(10*v + card[i], d+1);
			mark[i] = false;
		}
	}
}

int main()
{
	while (scanf("%d %d",&n,&m)==2) {
		for (int i=0;i<n;i++) {
			scanf("%d",card+i);
		}
		sort(card,card+n);
		memset(hash,0,sizeof(hash));
		memset(mark,0,sizeof(mark));
		dfs(0,0);
		while(m--)
		{
			scanf("%d %d",&x,&k);
			x %= k;
			int t = hash[0][k]+k - x;//要防止t=-1，所以+k
			if(hash[t%k][k] == 0) {
				printf("None\n");
			}
			else {
				printf("%d\n",hash[t%k][k]);
			}
		}
	}
}