[USACO1.2]命名那个数字 Name That Number （DFS&暴力）

题意：给一编号按特定规则转化的字符串，问是否能在给定字典中查找到并按字典序输出。

思路1：DFS 编号对应的每个字符串，用vis[]标记字典中的进行比较。时间复杂度不确定：最大可大O(2^12)会炸。必须开O2||O3优化才能过

思路2：对字典的字符串转化为数字与编号比较。由于字典中的字符串只有4617个，所以时间复杂度O(4617*12)，暴力美学的典范，PS：这个题标签为毛是DFS。

代码1：DFS

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
int n,l,f=0;
string b;
map<string,int>vis;
set<string>st;
vector<char>v[10];
int d[15];
void dfs(string a,int len){
	if(len==l){
	/* printf("a="); cout<<"-"<<a<<"-"<<endl; */	
		if(vis[a]){
			st.insert(a);
			return;
		}
		else return;
	}
		for(auto c:v[d[len+1]])
		{
			string tmp=a+c;
			dfs(tmp,len+1);
		}
}
int main(){
	ios::sync_with_stdio(false);
	int cnt=0,num=2;
	for(char i='A';i<='O';i++)
		{
			cnt++;
			v[num].push_back(i);
			if(cnt==3) num++,cnt=0;
		}
	v[7].push_back('P'),v[7].push_back('R'),v[7].push_back('S');
	v[8].push_back('T'),v[8].push_back('U'),v[8].push_back('V');
	v[9].push_back('W'),v[9].push_back('X'),v[9].push_back('Y');
	cin>>b;
	int k=1;
	 l=b.size();
	for(int i=0;i<l;i++) d[k++]=b[i]-'0';
	for(int i=1;i<=4617;i++)
	{
		string x;
		cin>>x;
		vis[x]=1;
	}
	/*for(auto i:vis) cout<<i.first<<" "<<i.second<<endl; */
	dfs("",0);
	if(st.size())
		for(auto i:st) cout<<i<<endl;
	else cout<<"NONE"<<endl;
	return 0;
}

思路2：巧妙暴力转化

#include<bits/stdc++.h>
using namespace std;
string str="2223334445556667 77888999";//字母转化为数字 
vector<string>v(4617);
string a;
int main(){
	cin>>a;
	for(auto &i:v)
		cin>>i;
	int l=a.size(),f,jg=0;
	for(int i=0;i<4617;i++)
	{
		f=1;
		if(l!=v[i].size()) continue;
		for(int j=0;j<l;j++)
			if(str[v[i][j]-'A']!=a[j])
			{
				f=0;
				break;
			}
		if(f) cout<<v[i]<<endl,jg=1;
	}
	if(!jg) puts("NONE");
	return 0;
}