nyist 303序号互换(数学推理)

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=303

思路：

开始看错题了，以为最多只有两个字母。

字母转数字的表达式很容易看出来是：(26^(n-1))*(s[0]-64)+(26^(n-2))*(s[1]-64)+……

主要是数字怎么转字母，这应该是个数学问题。可是我想了好久没想出好方法，数学太差了吧。最好只好想个笨点的方法AC掉了。

我的方法：

用 mi[i][j]表示从后面数第i位上是字母j的最小值。

用 ma[i][j]表示从后面数第i位上是字母j的最大值。

（1<=i<10 1<=j<=26 j=1时，即‘A’）

例如： mi[3][4]="DAA"转成数字。 ma[3][4]="DZZ"转成数字。

这样算出来后，数字转字母，就可以从高位递归出字母来。

假设，给的数字是x。

如果mi[i][j]<=x<=ma[i][j],那么可以知道转化后的位数是i,且第i位是(char)(j+64)；

根据前面推出的字母转数字的公式。

x-=(26^(i-1))*j

递归即可求出所有序列。

 #include <iostream>#include <string>using namespace std;long long ma[11][30],mi[11][30];long long pow(int a,int b){long long i=1,x=1;while(i<=b){x*=a; i++;}return x;}long long zimu(string s){long long x=0,n=s.length(),i;for(i=0;i<n;i++){x+=pow(26, n-i-1)*(s[i]-64);}return x;}void init(){int i,j,x,k; string s;for(i=1;i<27;i++)for(j=1;j<10;j++){s=""; s+=char(64+i); k=1;while(k<j) {s+='Z';k++;}ma[j][i]=zimu(s);s=""; s+=char(64+i); k=1;while(k<j) {s+='A'; k++;}mi[j][i]=zimu(s);   //cout<<s<<":"<<mi[j][i]<<" "<<ma[j][i]<<endl;}}void ans(long long x){int i,j;if(x<=26)cout<<(char)(x+64)<<endl;else{for(i=1;i<10;i++)for(j=1;j<27;j++){if(x>=mi[i][j]&&x<=ma[i][j]){cout<<(char)(j+64);ans(x-pow(26,i-1)*j);}}}}int main(int argc, char *argv[]){long long t,i,j,n,x;string s;init();cin>>t;while(t--){cin>>s;if(s[0]>='0'&&s[0]<='9'){for(x=i=0;i<s.length();i++){x=x*10+(s[i]-'0');}ans(x);}else{cout<<zimu(s)<<endl;}}return 0;}