USACO Picture

这一题可以说是Section 5.5中最简单的一题了。不过一开始被某人的题解吓了一跳（他是用线段树过的），所以一直不敢下手。

这题的关键在于如何确定一条边是否是周长的一部分。有一种很巧妙的办法。
我们用level[a][b]表示在某个位置上面有几个矩形，那么容易知道，当level[a][b]由0变成某个数值时， 点(a,b)一定在图像的外缘；同理，当level[a][b]由某个正数变成0时，点(a,b)也一定在图像外缘。

问题来了，上面定义的level是二维数组，然而题目的坐标范围是[-10000,10000]，显然是不可行的。进一步观察可以发现，横线和竖线的统计可以分开进行，level可以降低到一维。下面以横线为例。

建立一个struct，其中包含横线的端点（两个横坐标）、高度（一个纵坐标）以及这个横线在所在矩形的位置（用一个Bool表示，在上方为1,下方为0）。

然后，对横线按照高度从高到低排序，如果高度相同，在所在矩形上方的点排在前面（否则在会产生边界误判，导致结果增大）。

接着，初始化level全为0,从高到低开始扫描，如果是在矩形上面的边，那么让这条边两端点值之间的level都+1,如果+1后level==1,说明原来的地方没有被覆盖，而现在被覆盖了，因此tot++；类似的，当遇到在下面的边，端点内的level--，若level==0,则tot++。

对于纵线也可以采用同样的处理方法。

简单分析可知，这个算法的复杂度是O(N),在极端情况下， 两个solve一共会进行400M次操作，不过USACO并没有这么变态的测试数据。最大的数据仅耗时～0.1s，并不比用线段树处理的差。

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

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MAXN 10005
05
06 typedef struct
07 {
08    int b,e,s;
09    int start;
10 }Line;
11
12 Line lx[MAXN],ly[MAXN];
13 int N;
14 int stat[30000];
15 int *level;
16 long tot = 0;
17
18 int cmp(const void *a,const void *b)
19 {
20    Line *m,*n;
21    m = (Line *)a;
22    n = (Line *)b;
23    if(m->s < n->s)    return 1;
24    if(m->s == n->s)
25    {
26        if(m->start)    return -1;
27        return 1;
28    }
29    return -1;
30 }
31
32 void init()
33 {
34    scanf("%d\n",&N);
35    int i;
36    int x1,y1,x2,y2;
37    for(i = 0;i < N;i ++)     //此处写的比较乱
38    {
39        scanf("%d%d%d%d\n",&x1,&y1,&x2,&y2);
40        lx[i].b = lx[i + N].b = x1;
41        lx[i].e = lx[i + N].e = x2;
42        lx[i].s = y1;
43        lx[i + N].s = y2;
44        ly[i].b = ly[i + N].b = y1;
45        ly[i].e = ly[i + N].e = y2;
46        ly[i].s = x1;
47        ly[i + N].s = x2;
48        ly[i].start = lx[i].start = 0;
49        ly[i + N].start = lx[i + N].start = 1;
50    }
51    qsort(lx,N * 2,sizeof(Line),cmp);
52    qsort(ly,N * 2,sizeof(Line),cmp);
53 }
54
55 void solve(Line *p)
56 {
57    int i,j;
58    memset(stat,0,sizeof(stat));
59    level = stat + 15000;
60    for(i = 0;i < 2 * N;i ++)
61    {
62        if(p[i].start)
63            for(j = p[i].b;j < p[i].e;j ++)
64            {
65                level[j] ++;
66                if(level[j] == 1)    tot ++;
67            }
68        else
69            for(j = p[i].b;j < p[i].e;j ++)
70            {
71                level[j] --;
72                if(level[j] == 0)    tot ++;
73            }
74    }
75 }
76
77 int main()
78 {
79    freopen("picture.in","r",stdin);
80    freopen("picture.out","w",stdout);
81    init();
82    solve(lx);
83    solve(ly);
84    printf("%ld\n",tot);
85    return 0;
86 }

缓冲输出

最近在读C Traps and Pitfalls，上面有提到一个叫做“缓冲输出”的概念，意思就是先把要输出的数据保存在一块内存中，当这块内存填满的时候再把数据全部输出。与直接输出相比，缓冲输出有较高的效率。

说来正巧，在提交Hidden Password那题的代码时，我一时懒惰注释掉debug语句，本以为没有太大关系，结果竟然超时了。注释掉debug语句后却飞速通过。

出于好奇，本人增加了一个数组buffer[BUFSIZ],并且在程序开始加入setbuf(stderr,buffer).结果，程序运行速度和没有debug语句时没有太大差别。

看来，缓冲输出会带来性能的提升，尤其是在需要大量输出数据时。

不过需要注意的是，一般情况下stderr是不缓冲的，这是为了避免程序意外终止时错误信息还留在缓冲区中没有打印出来。

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;
}

USACO Hidden Password

对于循环，通用的方法是把字符串复制一遍接在原串的后面，比如：
abcde --> abcdeabcde

题目要求输出排序最小的字符串的首字母所在位置，可以想到一个朴素的办法。
用minp记录答案，初始化为0，然后
for(i = 1;i < L;i ++)
   if(strncmp(str + i, str + minp, L) < 0)
      minp = i;
容易知道，这是一个O(n^2)的算法，当测试数据是100000个a时，就会超时。

最后不得已上NOCOW看了别人的题解，找到了一个比较简便的方法，可以通过所有测试数据，不过正确性有待证明。这个算法主要建立在安徽周源的论文《浅析“最小表示法”思想在字符串循环同构问题中的应用》上，读者还可以参考HDU-2609.

代码如下

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

01 #include
02 #include
03 #include
04
05 long l;
06 char str[200003];
07
08 void init()
09 {
10    long i;
11    char c;
12    scanf("%ld\n",&l);
13    for(i = 0;i < l;)
14    {
15        c = getchar();
16        if(c <= 'z' && c >= 'a')
17            str[i ++] = c;
18    }
19    strncpy(str + l,str,l);    //转环为链
20 }
21
22 int main()
23 {
24    freopen("hidden.in","r",stdin);
25    freopen("hidden.out","w",stdout);
26    init();
27    long i,j,k,minp;
28    for(i = 0,j = 1,k = 0;i < l && j < l;)    //请参考周源的论文
29    {
30        if(k == l)    break;
31        if(*(str + i + k) == *(str + j + k))
32            {k ++;continue;}
33        if(*(str + i + k) > *(str + j + k))
34        {
35            i += k + 1;
36            k = 0;
37        }
38        else
39        {
40            j += k + 1;
41            k = 0;
42        }
43        if(i == j)    j ++;  //避免i,j相等，发生误判
44    }
45    minp = (i < j)?i:j;
46    printf("%ld\n",minp);
47    return 0;
48 }

为什么说这种算法正确性有待证明？

因为HDU-2609和那篇论文都是正向使用这个算法的，即用最小表示法判断两个环是否相同。

而上面的代码却逆用这个方法：已知两个相同的环，求它们在哪两个位置开始相同。 

==================================================

USACO上面的Analysis介绍了一种不错的DP算法，不过它给出的代码可读性太差了。于是我参考了这一篇博文（链接）。先使用同样的方法处理环。然后定义数组len[],len[i] = k表示以i开头的k个字符组成的串，与其他位置连续k个字符组成的串相比，是最小的。
那么，容易知道，两个相邻的最小串相连依然是最小的，并且长度增加。于是就有了下面的转移方程：

len[i] += len[i + len[i]]   当 len[i + len[i]] > 0
len[i] += 1                      当 s[len[i]]是最小的字符

需要注意的是，当这两个串相连后，前一个串长度是两者之和，所以下次计算的时候就没有必要再算后一个串了，因此可以把它从链表中除去（在下面的代码中使用数组模拟双向链表）。

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 200010

long len[MAXN];
long prev[MAXN],next[MAXN];  //Two-way linking list
long head;
char str[MAXN];
long l,nl;

void init()
{
   scanf("%ld\n",&l);
   long i;
   for(i = 0;i < MAXN;i ++)   //初始化为最大值，方便dp
       str[i] = 'z' + 1;
   for(i = 0;i < l;)
   {
       scanf("%c",str + i);
       str[i + l] = str[i];
       if(str[i] <= 'z' && str[i] >= 'a')    i ++;
   }
   nl = l * 2 + 1;
}

void dp_init()
{
   memset(len,0,sizeof(len));
   long i;
   for(i = 0;i < nl;i ++)   //初始化双向链表
   {
       prev[i] = i - 1;
       next[i] = i + 1;
   }
   next[nl - 1] = -1;
   prev[0] = -1;
   head = 0;
}

void del(long p)    //remove node p from list
{
   if(head == p)    head = next[p];
   if(next[p] != -1)    prev[next[p]] = prev[p];
   if(prev[p] != -1)    next[prev[p]] = next[p];
}

void dp()
{
   long max,i,prevmax;
   int minchar;
   prevmax = -1;
   while(1)
   {
       minchar = 10000;
       for(i = head;i != -1;i = next[i])
           if(str[i + len[i]] < minchar)        minchar = str[i + len[i]];
       max = -1;
       for(i = head;i != -1;i = next[i])
       {
           if(i + len[i] > nl)    continue;
           if(len[i + len[i]] > 0)
           {
               del(i + len[i]);
               len[i] += len[i + len[i]];
           }
           else if(len[i + len[i]] == 0 && str[i + len[i]] == minchar)
               len[i] ++;
           if(len[i] > max)
               max = len[i];
       }
       for(i = head;i != -1;i = next[i])
           if(len[i] < max)    del(i);
       if(max == l)    break;    //max最大只可能是字符串长度
       if(max == prevmax)    //当max不再变更时跳出
           break;
       else    prevmax = max;
   }
   printf("%ld\n",head);
}

int main()
{
   freopen("hidden.in","r",stdin);
   freopen("hidden.out","w",stdout);
   init();
   dp_init();
   dp();
   return 0;
}