题解 P1246 【编码】
Alex_Wei
·
·
题解
---
~~用组合数解这道题目实在是再简单不过了。~~
#### 前置芝士：组合数
$C_{n}^{m}$：在 $n$ 个数中选出 $m$ 个数的方案总数。**（不计顺序）**
计算公式是
$$C_{n}^{m}=\frac{\prod_{n-m+1}^{n}}{m!}$$
或者
$$C_{n}^{m}=\frac{n!}{m!(n-m)!}$$
通常的，$C_{n}^{0}=1$。
例如$\ \ C_{4}^{2}=\frac{3*4}{2*1}=6$。
即从 $4$ 个数中选取 $2$ 个有 $6$ 种取法：
$\{1,2\}\ \{1,3\}\ \{1,4\}\ \{2,3\}\ \{2,4\}\ \{3,4\}$。
计算代码如下：
```cpp
int c(int m,int n)
{
if(m==0)return 1;
int mut=1;
for(int i=n;i>n-m;i--)mut*=i;
for(int i=m;i>1;i--)mut/=i;
return mut;
}
```
---
那么组合数与这题到底有什么关系呢？
拿 ```cgx``` 举例，设 $ans$ 为比 ```cgx``` 小的单词个数，初值为 $0$。
$\large1.$ 首先，```cgx``` 肯定比只有一个字母的单词大，$ans+26,\quad ans=26$。
$\large2.$ 其次，```cgx``` 肯定比只有两个字母的单词大。
只有两个字母的单词个数该怎么算呢？就是在 $26$ 个字母中选 $2$ 个。
$ans+C_{26}^{2},C_{26}^{2}=\frac{26*25}{2*1}=325,\quad ans=26+325=351$。
$\large3.$ 只有三个字母
$3.1.$ 第一位：它比以字母 ```a-b``` 为第一位的大（ ```cgx``` 第一位为 ```c```，所以要比 ```c``` 小）
- 以 ```a``` 为第一位，且有三位的单词个数：$C_{25}^{2}=\frac{25*24}{2*1}=300$。
从**比 ```a``` 大的剩下 $25$ 个字母**中选 $2$ 个字母：
$ans+300,\quad ans=351+300=651$。
- 以 ```b``` 为第一位，且有三位的个数：$C_{24}^{2}=\frac{24*23}{2*1}=276$。
从**比 $b$ 大的剩下 $24$ 个字母**中选 $2$ 个字母：$ans+276,\quad ans=651+276=927$。
$3.2$ 第二位（**即第一位已经确定为 $c$**）：它比以字母 ```d-f``` 为第二位的单词大 （第一位为 ```c``` ，所以要比 ```c``` 大，第二位为 ```g```，所以要比 ```g``` 小）
- 第二位为 ```d``` 的个数：$C_{22}^{1}=\frac{22}{1}=22$。
从比 ```d``` 大的剩下 $22$ 个字母中选 $1$ 个字母：$ans+22,\quad ans=927+22=949$。
- 第二位为 ```e``` 的个数：$C^{1}_{21}=21,ans+21,\quad ans=949+21=970$。
- 第二位为 ```f``` 的个数：$C^{1}_{20}=20,ans+20,\quad ans=970+20=990$。
$3.3$ 第三位（一，二位已经确定）：它比以字母 ```h-w``` 为第三位的大，共有 $16$ 个。
$$\sum_{n=8}^{23}C^{0}_{n}=\sum_{n=8}^{23}1=16*1=16$$
$ans+16,\quad ans=990+16=1006
因为比 cgx 小的单词共有 1006 个，所以 cgx 是第 1007 个。
先判断该单词是否存在，再一位一位地去考虑共有多少比给出单词小的单词，如果用的是字符串，则还需要考虑一下边界问题。
#include<bits/stdc++.h>
using namespace std;
string s;
int ans,n;
int c(int m,int n)//组合数计算
{
if(m==0)return 1;
int mut=1;
for(int i=n;i>n-m;i--)mut*=i;
for(int i=m;i>1;i--)mut/=i;
return mut;
}
int main()
{
cin>>s,n=s.size();
for(int i=1;i<n;i++)
if(s[i]<=s[i-1])cout<<0,exit(0);//判断是否存在
for(int i=1;i<n;i++)ans+=c(i,26);//计算出位数比它小的单词数
for(int i=0;i<n;i++)//枚举每一位
for(char j=(i==0?'a':s[i-1]+1);j<s[i];j++)//注意考虑边界
ans+=c(n-i-1,'z'-j);//因为字符串下标从0开始，所以是n-i-1而不是n-i
cout<<++ans;//别忘了最后把自己加上
return 0;
}