计算机算法设计与分析1-2

2-1字典序问题

问题描述：

在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A由26个小写字母组成。该字母表产生的升序字符串中字母从左到右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1次。例如，a,b,ab,bc,xyz等字符串都是升序字符串。现在对字母表中产生的所有长度不超过6的升序字符串，计算它在字典中的编码。

 

a	b	c	…	ab	ac
1	2	3	…	27	28

样例输入：

 2

 a

 b

样例输出：

 1

 2

我的做法是深搜得到所有字符串并保存，因为字符串的排序和题目要求的排序方式不同，所以存放在结构体中，并记录对应数值，然后对字符串排序，最后输入字符串后二分搜索。

答案的做法又是推了数学公式，这操作学不来Σ( ° △ °|||)︴，下面会贴上答案的公式。

#include<bits/stdc++.h>
using namespace std;
char tep[7];
struct node{
	string a;
	int rank;
}N[350000];
int s[7]={0,1,2,3,4,5,6};
int book[27];
int ans=0;
void dfs(int step,int des)
{
	if(step==des)
	{
		N[++ans].a=tep;
		N[ans].rank=ans;
		return ;																																																	
	}
	for(int i=1;i<=26;i++)
	{
		if(book[i]==0 && 96+i>tep[step-1])
		{
				tep[step]=96+i;
				book[i]=1;
				dfs(step+1,des);
				book[i]=0;
		}
	}
	return ;
}

void inti()
{
	for(int i=1;i<=6;i++)
	{
		memset(book,0,sizeof(book)); 
		dfs(0,s[i]);
	}
}
int judge(string &a)
{
	if(a.length()>6)
		return 0;
	for(int i=1;i<a.length();i++)
	{
		if(a[i]<a[i-1])
			return 0;
	}
	return 1;
}
int Find(string &s)
{
	int l=1,r=ans;
	int mid=(l+r)/2;
	while(l<r)
	{
		if(N[mid].a<s)
			l=mid+1;
		else if(N[mid].a>s)
			r=mid-1;
		else if(N[mid].a==s)
			l=r=mid;
		mid=(l+r)/2;
	}
	return N[l].rank;
}
bool cmp(node a,node b)
{
	return a.a<b.a;
}
int main()
{
	inti();
	sort(N+1,N+ans+1,cmp);
	int n;
	string target;
	printf("Please input the number of strings you want to search by\n");
	scanf("%d",&n);
	while(n--)
	{
		cout<<"Please input the string"<<endl;
		cin>>target;
		if(!judge(target))
			printf("Invalid input\n");
		else
			printf("%d\n",Find(target));
	}
	return 0;
}