Home > Old Blog Posts > USACO 1.2.3 Name That Number

USACO 1.2.3 Name That Number


这道题没什么好说的,按题目意思去做就行了。

代码:

/*
ID: dementr1
PROG: namenum
LANG: C++
*/
#include<iostream>
#include<string>
#include<fstream>
using namespace std;
string word[5000],longer[100];
ifstream finword(“dict.txt”);
ifstream fin(“namenum.in”);
ofstream fout(“namenum.out”);
const char letter[10][3]={{},{},{‘A’,’B’,’C’},{‘D’,’E’,’F’},{‘G’,’H’,’I’},{‘J’,’K’,’L’},
{‘M’,’N’,’O’},{‘P’,’R’,’S’},{‘T’,’U’,’V’},{‘W’,’X’,’Y’}};
int START[26],END[26];
int N,N2,L,num;
string ans[10000];
int str[20];
void init()
{
memset(str,0,sizeof(str));
int i,c=1;
N=N2=0;
char now=’B’;
while(!finword.eof())
{
finword>>word[N++];
if(word[N-1].length()==12) longer[N2++]=word[N-1];
if(word[N-1][0]==now)
{
START[c]=N-1;
END[c-1]=N;
now++;
c++;
}
}
string tmp;
START[0]=0;
END[25]=N;
fin>>tmp;
L=tmp.length();
for(i=0;i<L;i++)
str[i]=tmp[i]-‘0’;
}
int search(string s)
{
int start=START[s[0]-‘A’],end=END[s[0]-‘A’],mid;
int count=0;
if(L==12)
{
start=0;
end=N2;
do
{
mid=(int)(start+end)/2;
if(longer[mid]==s)
return mid;
else if(longer[mid]<s)
{
start=mid;
continue;
}
else
{
end=mid;
continue;
}
}while(start<end-1);
}
else
{
do
{
mid=(int)(start+end)/2;
if(word[mid]==s)
return mid;
else if(word[mid]<s)
{
start=mid;
continue;
}
else
{
end=mid;
continue;
}
}  while(start<end-1);
}
if(N!=12&&word[start]==s) return start;
if(N==12&&longer[start]==s) return start;
return -1;
}
void dfs(int n, string s)
{
if(n==L-1)
{
int tmp=search(s);
if(tmp!=-1)
{
if(L==12) ans[num++]=longer[tmp];
else
ans[num++]=word[tmp];
}
}
else
{
dfs(n+1,s+letter[str[n+1]][0]);
dfs(n+1,s+letter[str[n+1]][1]);
dfs(n+1,s+letter[str[n+1]][2]);
}
}
int main()
{
init();
int i;
string a,b,c;
a+=letter[str[0]][0];
b+=letter[str[0]][1];
c+=letter[str[0]][2];
dfs(0,a);
dfs(0,b);
dfs(0,c);
if(num==0) fout<<“NONE”<<endl;
else
for(i=0;i<num;i++) fout<<ans[i]<<endl;
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: