那个论坛正在“整治低俗内容”，不开放，所以直接把文本贴来了。


   一、题意简述： 
      二五语言的单词是由A..Y这25个字母组成的，每个单词可以写成一个5*5的矩阵。一个有效单词是每行每列都按升序排列的矩阵表。例如, 单词 ADJPTBEKQUCGLRVFINSWHMOXY 被表示成: 
                       A	D	J	P	T 
                       B	E	K	Q	U 
                       C	G	L	R	V 
                       F	I	N	S	W 
                       H	M	O	X	Y. 
将所有有效单词按升序排列并编号，请写一个程序对任意单词确定其编号，并可以给出任意编号所对应的单词。（单词数小于2^31) 
   二、试题分析： 
       这种在按某种规则构成的字母顺序表中查找指定单词的题目，我们以前也见过，比如binary code(poi0008)。此类题目一般单词数量巨大，想要枚举出每个单词几乎是不可能的。一般的思路是对给定单词的每一位进行分析（从前往后），设当前位置是i，则确定所有前i-1位与给定单词相同，第i位按所给规则顺序比当前单词小的单词数，并将其类加到单词编号变量sum中(初始sum置1），最后给定单词的编号就是sum。比如确定123是自然数中第几个：sum=1;i=1,sum=sum+99=100;i=2,sum=sum+20=120;i=3,sum=sum+3(0,1,2)=123.所以123是自然数中第123个。对于第二个问题，我们可以从第一位开始，由A到Y枚举每个合法的字符q，并确定由此可确定的单词数c,如果c<sum,则dec(sum,c),否则当前位置的字符就是q，转到下一位。这样我们的思路已经明了，解决问题的关键就集中在如何确定一个有部分字母确定的单词的个数了。 
       以往很多这一类型的题目都可以事先用递推的方法确定关键问题的答案，但是这道题有些问题，一个有效单词一定要满足每行，每列都按升序排列的性质。假如我们想按单词的位置（1..25)递推的话，很难保证不出现重复计算和计算不合法状态，必须另辟蹊径。让我们换个角度去思考问题，假如我们按照字母顺序逐一地把25个字母填进去，会有什么效果？我们可以发现’A’一定在第一位，‘Y’一定在最后一位。而填其它的字母时，不妨设填到第i行，第j列，字母为a,一定有(I,j-1),(i-1,j)不为空。如果(I,j-1)为空，假设最后填入字母b，根据字母顺序:b>a,而有效单词每行必按升序排列，此单词不是有效单词；同理，如果(i-1,j)为空，不满足每列必按升序排列的要求。这样，不论在填第几个字母，都有每行的字母是连续的，并且每行的字母总数非减排列，即num1>=num2>=num3>=num4>=num5（numi为第i行的字母总数）。可以用{num1,num2,num3,num4,num5}表示一个状态，对于一个状态，sum=sigma(numi)表示总共填入的字母数，至于这sum个字母是怎么填的没有关系，所能填出的总单词数是一样的，这就具备了重复子结构的性质，可以用动态规划来解决。因为一个状态并不代表字母的具体填放位置，而且状态间的转移是根据当前待填字母可填位置决定的，所以想通过递推一次计算出来不好处理，最好是用记忆化搜索来做。 
三、具体实现： 
1．确定一个有部分字母确定的单词的个数 
  状态的存贮，一个状态{num1,num2,num3,num4,num5}满足0<=numi<=5,所以可以开一个数组f:array[ 0..6^5-1 ] of longint;把一个状态映射到f的第[ sigma(numi*6^(5-i)) ]位。 
  状态间的转移，当前状态：{state[ i ]}(i=1,2,3,4,5),待填字母q. 
      这里state[ 0 ]5. 
      f{state}0 
      if q的位置已确定(i,j)  then 
          if (state[ i ]+1=j) and (state[ i-1 ]>state[ i ]) then 
f{state} f{state[ 1 ],…,state[ i ]+1,…state[ 5 ]} 
              else f{state}0 
          else 
            for i1 to 5 do 
              if (state[ i-1 ]>state[ i ]) then 
                f{state}f{state}+f{state[ 1 ],…state[ i ]+1,…state[ 5 ]} ; 
    2．主过程 
       {num：单词编号；ch:string[ 25 ]：所给单词} 
       读入数据 
       if 问题一 then   
         num1 
         for i1 to 25 do 
           {for j’A’ to pred(ch[ i ]) do 
             if 字母j未确定位置 then 
               {确定位置为i； 
                调用1.,得到单词数l; 
                numnum+l； 
                释放} 
            确定ch[ i ]位置为i} 
      else 
         for i1 to 25 do 
          {for j’A’ to ‘Y’ do 
             if j 未确定 then 
               {确定j位置为i； 
                调用1,得到单词数l； 
                if num>l then dec(num,l) 
                        else 跳出} 
           j位置确定为i}； 
       输出结果 
       结束。 
    3．性能分析： 
          时间复杂度：O(CN) 
                      N合法状态数：搜索得252 
                      C 一常数：最多5*25*25 
          空间需求：6^5*4Byte≈31Kb 
四．启发与总结： 
   这一类的题有不少，大部分可以预先算出“关键步骤”，这题不同。如按一般思维方法很难想出，需要我们去挖掘题目的内涵，充分利用一些良好的性质，换个角度思考问题。 
   我在想这个题的过程中发现我可以确定每个位置可能字母的范围，不知道这个会不会对产生一种新的方法有帮助？ 
    
五．程序清单： 
{Author: Lijiganjun 
Date:   05-12-2003 
Theme:  IOI2001 Twofive 
} 
const 
 states=6*6*6*6*6; 
var 
 num:longint; 
 c:char; 
 str:string; 
 lx,ly:array[ 1..25 ] of integer; 
 state:array[ 0..5 ] of longint; 
 f:array[ 0..states-1 ] of longint; 

function calc(l:integer):longint; 
 var i,a,b,c:longint; 
 begin 
   a:=state[ 1 ]; 
   for i:=2 to 5 do a:=a*6+state[ i ]; 
   if f[ a ]<0 then begin 
     b:=0;c:=lx[ l ]; 
     if c<0 then begin 
       for i:=1 to 5 do 
         if state[ i ]<state[ i-1 ] then 
         begin 
           inc(state[ i ]); 
           inc(b,calc(l+1)); 
           dec(state[ i ]); 
         end 
     end else 
       if (state[ c-1 ]>state[ c ]) and (state[ c ]+1=ly[ l ]) then 
       begin 
         inc(state[ c ]); 
         inc(b,calc(l+1)); 
         dec(state[ c ]); 
       end; 
     f[ a ]:=b; 
   end; 
   calc:=f[ a ]; 
 end; 

function numconts:longint; 
 begin 
   fillchar(f,sizeof(f),$ff); 
   fillchar(state,sizeof(state),0); 
   state[ 0 ]:=5; 
   f[ states-1 ]:=1; 
   numconts:=calc(1); 
 end; 

function wordtonum:longint; 
 var i,j,k,ch:integer; 
 begin 
   fillchar(lx,sizeof(lx),$ff); 
   num:=1; 
   for i:=1 to 5 do 
     for j:=1 to 5 do 
       begin 
         ch:=ord(str[ (i-1)*5+j ])-64; 
         for k:=1 to ch-1 do 
           if lx[ k ]<0 then begin 
             lx[ k ]:=i; 
             ly[ k ]:=j; 
             inc(num,numconts); 
             lx[ k ]:=-1; 
           end; 
         lx[ ch ]:=i; 
         ly[ ch ]:=j; 
       end; 
   wordtonum:=num; 
 end; 

procedure numtoword; 
 var i,j,k:integer; 
     out:array[ 1..25 ] of char; 
     l:longint; 
 begin 
   fillchar(lx,sizeof(lx),$ff); 
   for i:=1 to 5 do 
     for j:=1 to 5 do 
       for k:=1 to 25 do 
         if lx[ k ]<0 then begin 
           lx[ k ]:=i; 
           ly[ k ]:=j; 
           l:=numconts; 
           if num>l then dec(num,l) 
           else break; 
           lx[ k ]:=-1; 
         end; 
   for i:=1 to 25 do out[ (lx[ i ]-1)*5+ly[ i ] ]:=chr(64+i); 
   for i:=1 to 25 do write(out[ i ]); 
   writeln; 
 end; 

begin 
 assign(input,'twofive.in'); 
 assign(output,'twofive.out'); 
 reset(input); 
 rewrite(output); 
 readln(c); 
 if c='W' then begin 
   readln(str); 
   writeln(wordtonum); 
 end else begin 
   readln(num); 
   numtoword; 
 end; 
 close(input); 
 close(output); 
end.