USACO Twofive

还记得Section 3.2的Stringsobits那一题吗？这道题可以说是它的加强版了。

与Stringsobits相同的是，这题的数据范围也是比较大的。本人起初用DFS搜索所有可能的序列，运行2分钟后，输出文件超过10000000行。（某博客上说DFS可以过6个点）

先讨论已知序号求字符串吧。与Stringsobits类似，我们可以通过计算以某几个字符开头的串的数目，从而逐个确定字符串中每一位的字符。怎么样才可以计算出某几个字符开头的串的数目呢？

定义数组：
long dp[6][6][6][6][6]——记录每行填充了前几个空时剩下字符的所有合法排列的总数。
int used[25]——标记某个字符是否已经有确定的位置
int maxrow[5],maxcol[5]——分别记录没行、列的最大字符。

显然，dp[5][5][5][5][5] = 1。dp数组中的下标一定是非递增的，比如dp[5][4][3][3][3]是合法的，而dp[1][1][3][3][3]就是无效的。
此外，字符ch可以放在行r，列c的条件是:

• used[ch] == 0;
• 它的上方和左方都已经放置（边界情况除外）；
• ch的值都大于这行和这列的最大值（因为他的上面和左边都是放满的）。

static long calc(int a,int b,int c,int d,int e,int ch)   //ch：等待放置的字符
{
    long *p;
    p = &dp[a][b][c][d][e];
    if(*p > 0)    return *p;
    if(used[ch])   //这个字符已经有确定的位置了，跳过
    {
        *p = calc(a,b,c,d,e,ch + 1);
        return *p;
    }
    if(a < 5 && ch > maxrow[0] && ch > maxcol[a])    *p += calc(a + 1,b,c,d,e,ch + 1);   //放在第一行最后，以递增数值填充，故calc内部无需更新used、maxrow、maxcol。
    if(b < a && ch > maxrow[1] && ch > maxcol[b])    *p += calc(a,b + 1,c,d,e,ch + 1);    //放在第二行最后
    if(c < b && ch > maxrow[2] && ch > maxcol[c])    *p += calc(a,b,c + 1,d,e,ch + 1);
    if(d < c && ch > maxrow[3] && ch > maxcol[d])    *p += calc(a,b,c,d + 1,e,ch + 1);
    if(e < d && ch > maxrow[4] && ch > maxcol[e])    *p += calc(a,b,c,d,e + 1,ch + 1);
    return *p;
}

接下来的构造就很简单了，比如要输出第N小的字符串，先判断第一位（用k表示，初始为0），置used[k] = 1,然后调用calc(1,0,0,0,0,0)，如果返回值小于等于N，那么说明这个位置就是k了，否则N -= 返回值，used[k] = 0,k ++，测试下一个k值。

类似的，已知字符串S求序号N就更简单了，那么只要依次处理每一位就可以了，实现过程请看代码。

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long num;
char str[30];
long dp[6][6][6][6][6];
int used[26];
int maxrow[5],maxcol[5];

static long calc(int a,int b,int c,int d,int e,int ch)
{
   long *p;
   p = &dp[a][b][c][d][e];
   if(*p > 0)    return *p;
   if(used[ch])
   {
       *p = calc(a,b,c,d,e,ch + 1);
       return *p;
   }
 
   if(a < 5 && ch > maxrow[0] && ch > maxcol[a])    *p += calc(a + 1,b,c,d,e,ch + 1);
   if(b < a && ch > maxrow[1] && ch > maxcol[b])    *p += calc(a,b + 1,c,d,e,ch + 1);
   if(c < b && ch > maxrow[2] && ch > maxcol[c])    *p += calc(a,b,c + 1,d,e,ch + 1);
   if(d < c && ch > maxrow[3] && ch > maxcol[d])    *p += calc(a,b,c,d + 1,e,ch + 1);
   if(e < d && ch > maxrow[4] && ch > maxcol[e])    *p += calc(a,b,c,d,e + 1,ch + 1);
 
   return *p;
}


static void dp_init(int ch,int row,int col)
{
   used[ch] = 1;
   maxrow[row] = maxcol[col] = ch;
   memset(dp,0,sizeof(dp));
   dp[5][5][5][5][5] = 1;
}

static void solve_N()
{
   int in[5] = {};  //记录每一行已经占据的位置
   int p,ch;
   long t;
   memset(used,0,sizeof(used));
   for(p = 0;p < 5;p ++)
       maxrow[p] = maxcol[p] = -1;
   for(p = 0;p < 25;p ++)
   {
       in[p / 5] ++;
       for(ch = 0;ch < 25;ch ++)
           if(!used[ch] && ch > maxrow[p / 5] && ch > maxcol[p % 5])
           {
               dp_init(ch,p / 5,p % 5);
               t = calc(in[0],in[1],in[2],in[3],in[4],0);
               if(t < num)    num -= t;   //累减直到找到对应的字符
               else break;
               used[ch] = 0;   //请注意这里，如果是对应的字符会在break处跳出，used依然为1
           }
       str[p] = (char)('A' + ch);
   }
   printf("%s\n",str);
}

static void solve_W()
{
   int p,ch;
   int in[5] = {};
   memset(used,0,sizeof(used));
   for(p = 0;p < 5;p ++)
       maxrow[p] = maxcol[p] = -1;
   for(p = 0;p < 25;p ++)
   {
       in[p / 5] ++;
       for(ch = 0;ch < str[p] - 'A';ch ++)
           if(!used[ch] && ch > maxcol[p % 5] && ch > maxrow[p / 5])
           {
               dp_init(ch,p / 5,p % 5);
               num += calc(in[0],in[1],in[2],in[3],in[4],0);
               used[ch] = 0;
           }
       used[str[p] - 'A'] = 1;   //已经确定了
       maxrow[p / 5] = maxcol[p % 5] = str[p] - 'A';
   }
   num ++;
   printf("%ld\n",num);
}

int main()
{
   freopen("twofive.in","r",stdin);
   freopen("twofive.out","w",stdout);
   char c;
   scanf("%c\n",&c);
   if(c == 'N')
   {
       scanf("%ld",&num);
       solve_N();
   }
   else if(c == 'W')
   {
       scanf("%s",str);
       solve_W();
   }
   fclose(stdout);
   return 0;
}