题解【洛谷 P1246 编码】

题目

编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码:把一些有规律的单词编成数宇。

字母表中共有 (26) 个字母 ({ t a,b,cdots,z}),这些特殊的单词长度不超过 (6) 且字母按升序排列。把所有这样的单词放在一起,按字典顺序排列,一个单词的编码就对应着它在字典中的位置。

例如:

( t a o 1) ; ( t b o 2) ; ( t z o 26) ; ( t ab o 27) ; ( t ac o28)

你的任务就是对于所给的单词,求出它的编码。

题解

看了题解发现没有和我一样做法的。

考虑枚举组合,方法就是 P1157 的方法。

我们令 (1) 状态表示不填,故每个单词最多有一个不填的,隔 (2) 枚举即可。

using namespace std;
const int N=25;
int n,r,a[N],cc;
string A;
void C(int nn,int nm) // 枚举组合
{
	if (nm==r)
	{
		string tmp;
		for (int i=1;i<=r;i++)
			if (a[i]!=1) tmp.push_back(a[i]+'a'-2); // 1 代表空了,所以要 -2
		if (tmp==A){printf("%d",cc+1); exit(0);} // 如果枚举到了
		++cc; return ; // 否则计数器 +1
	}
	for (int i=nn+1;i<=n-(r-nm-1);i++) a[nm+1]=i,C(i,nm+1),a[nm+1]=0;
}
int main()
{
	cin>>A; n=27;
	for (r=2;r<=6;r+=2) memset(a,0,sizeof a),C(0,0); // 隔 2 枚举
	puts("0");
	return 0;
}
原文地址:https://www.cnblogs.com/CDOI-24374/p/13939443.html