| String’s Puzzle |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB |
| Total submit users: 11, Accepted users: 11 |
| Problem 10783 : No special judgement |
| Problem description |
| Zhu Ming and Small Li find a strange stone tablet, which has some capitals printed on it. Capitals in every string are different with each other, and every capital string is followed by a number. Because of their supernormal intelligence, Zhu Ming and Small Li find the number following the string is numbered in the order of dictionary sequence from little to big (the original number is 0).For example, when the length of capital string is 3, number following the string will be: ABC 0 ABD 1 …… ZYX 15599 To better study this puzzle, please make a program to given a n-length string (1<=n<=26), output the number of the string. |
| Input |
| There are several test cases. Each data is made up of two lines. The first line is number n (1<=n<=26) The second line is a string with its length of n. n=0 means end of the input. |
| Output |
| Output the string number for each group of data tested. |
| Sample Input |
3 ABC 3 ZYX 3 ABD 4 ABCD 0 |
| Sample Output |
0 15599 1 0 |
解题报告：
设字符串为 abcd (a,b,c,d 代表大写字母), 设count(n) 表示比 n 代表的大写字母
小并且尚未使用的字母个数, f(str) 表示字符串 str 代表的数，则 :
f(abcd)= count(a)*(26-1)*(26-2)*(26-3)+count(b)*(26-2)*(26-3)+count(c)*(26-3)+count(d)
即有递归公式： f(abcd) = count(a)*(26-1)*(26-2)*(26-3) + f(bcd)
证明：在第一个位置放上比 a 小的字母，有 count(a) 种放法，第二个位置可以放除 第一个位置
之外的所有大写字母共 26-1 种，同理，第三个位置的放法 26-2, 第四个位置的放法 26-3
所以在第一个位置放比 a 小的字母的方法共有 count(a)*(26-1)*(26-2)*(26-3)。
此后在第一个位置放上 a ，递归求 f(bcd). (f(k) = count(k))
举例：
3
ZYX
第一个位置可放 A,B,C,...,Y 共 25 种，第二个位置 25，第三个位置 24
sum1 = 25*25*24 = 15000;
第二个位置可放 A,B,C,...X 共 24 种，第三个位置，除去两个有 24 种
sum2 = 24*24 = 576
一，二位置放 ZY，第三个位置可放 A,B,C,...,W， 23 种
所以 sum = sum1 + sum2 + 23 = 15000 + 576 + 23 = 15599
要注意放小字母的时候除去使用过的字母，如：
2
BC
比第一个位置小的字母个数为 1， sum1 = 1*25 = 25
在第一个位置放B，比第二个位置小的字母有，A，B，但B已经放置过，所以 sum2 = 1
sum = sum1 + sum2 = 26;
这题另外要注意的是：最大数可以是: sum=25*24*23...*2*1=403291461126605635582865999
显然内部数据类型无法处理，必须用数组，开始我没注意到WA了两次，下面是最开始的代码：
简洁但是数据溢出了。。。。
#include <iostream>
using namespace std;
bool bUsed[26] = {false};
int get(int n, int i, char str[]){
int sum, j;
if(n==i)
return 0;
bUsed[str[i]-'A'] = true;
for(sum=j=0; j<str[i]-'A'; j++){
if(!bUsed[j])
sum++;
}
for(int k=i; k<n-1; k++)
sum *= (26-k-1);
return sum + get(n, i+1, str);
}
int main(){
char str[27];
int n;
for(; cin>>n && n; ){
cin>>str;
memset(bUsed,false,sizeof(bool)*26);
cout<<get(n, 0, str)<<endl;
}
return 0;
}
//// 正确代码，非常难看，全局变量太泛滥了，
//// 写过几次大数乘了，下次再遇到，就写可复用函数了。。
#include <iostream>
using namespace std;
const int MAX = 30;
bool bUsed[26] = {false}; //记录字母的使用情况
char sum[MAX]; // sum 存结果，开始存放的是整数
int gi; // 跟踪 sum 的有效下标
// 求 sum + tmp ，sum 和 tmp 的无效位都是 0 ，这样比较容易处理
void myAdd(int j, char tmp[]){
int move=0, i, s;
for(i = MAX-1; i>=j || move; i--){
s = tmp[i] + sum[i] + move;
sum[i] = s % 10;
move = s / 10;
}
if(i+1<gi)
gi = i+1;
}
// 求 m * tmp ，m 是整数 j 是 tmp 的有效下标
void myMulti(int& j, int m, char tmp[]){
char dig[4],k,local[MAX]={0};
for(k=3; m; k--){ // 将 m 化为数组
dig[k] = m%10;
m = m/10;
}
int ci = MAX-1, n;
for(int i=3,move=0; i>k; i--,ci--){
n = ci;
for(int t=MAX-1,s; t>=j; t--,n--){
s = tmp[t]*dig[i]+move+local[n];
local[n] = s % 10;
move = s / 10;
}
if(move){
local[n] += move;
move = 0;
}
}
if(local[n]==0)
n++;
for(j=n; n < MAX; n++)
tmp[n] = local[n];
}
void get(int n, int i, char str[]){
char tmp[MAX] = {0};
if(n==i)
return ;
bUsed[str[i]-'A'] = true;
for(int k=0; k<str[i]-'A'; k++){
if(!bUsed[k])
tmp[MAX-1]++;
}
int j = MAX-1;
if(tmp[j] > 10){
int s = tmp[j];
tmp[j] = s % 10;
tmp[j-1] = s / 10;
j--;
}
if(tmp[j]){
for(int k=i; k<n-1; k++)
myMulti(j,(26-k-1),tmp);
myAdd(j,tmp);
}
get(n, i+1, str);
}
int main(){
char str[30];
int n;
for(; cin>>n && n; ){
cin>>str;
memset(bUsed,false,sizeof(bool)*26);
memset(sum,0,sizeof(char)*MAX);
gi = MAX-1;
get(n, 0, str);
for( ; gi<MAX; gi++)
cout<<char(sum[gi]+'0');
cout<<endl;
}
return 0;
}
评论