湖南师范大学第四届大学生计算机程序设计竞赛 记录下水果的三题。。。

昨晚12点闲着打开oj近期的比赛，发现了湖师大的校赛（？），四级刚考完，好久没刷题的赶脚，于是今天起来就准备刷了，想拉zyf来开黑那家伙竟然睡得像懒猪一样睡了一早上。。。

算了，我一个人水一水就好了。。。

开赛后题目满眼的中文，良心哪。。给我的第一感觉就是很水，因为里面有几个很熟悉的名词，最长公共子序列、汉诺塔什么的。。。

由于前段时间刚学过LCS，于是就先看C题最长公共子序列了，题目也没怎么看，看过样例后就觉得是很水的，手敲了一遍当作练手，调过后提交上去，超时了。。。然后才发现，那题没什么人做，大家都在刷D题。。。

看来C还是有点难度的，至少不是一眼题。。。于是返回看题目，原来是给定的二个序列没有重复的元素，如果数据大点，原来那个n*n的算法肯定超时了。。。

然后YY了一会C发现头脑迟钝想不出来，发了会呆转战D题。。。

D题是超级大水题，于是水掉了。。。（由于重定向没去掉，WA了一次。。）（代码找不到了T T）

然后C题还是没思路，看很多人过了的E题，同水题，画图题，本来以为能用bfs做，于是写出来发现没旋转对，于是重新写，水果了。。。

代码：

#include <cstdio>
#include <cstring>

int snack[12][12];
int fill, n, d[4][2] = {0,1, 1,0, 0,-1, -1,0};
int main() {
    freopen("in", "r", stdin);
    while (scanf("%d", &n) != EOF) {
        memset(snack, 0, sizeof(snack));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                snack[i][j] = -1;
        int x = 1, y = 1, a = 0;
        fill = 1;
        while (fill != n * n + 1) {
            snack[x][y] = fill++;
            if (snack[x + d[a][0]][y + d[a][1]] != -1)
                a = (a + 1) % 4;
            x += d[a][0];
            y += d[a][1];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                printf("%3d", snack[i][j]);
            printf("\n");
        }
    }
    return 0;
}

C题还是没思路，看A题，是英文。。。发现是变形的最短路，感觉和以前的一类最小生成树很像，最近在练最小生成树，本来还挺高兴可以练手下，发现变形太厉害，最短路也不是很熟，于是不会了。。。

回头发呆，继续YY C题，题目说不会重复，总是想到n*n以上复杂度的算法。。。

网上找LCS的优化，发现都是n*n，记起LIS的话就有n*logn的算法优化，于是YY出一个方法，把LCS转化为LIS然后用优化算法就行了。。。

接下来的问题就是YY转化的办法了。。。

思路为：记录第一组各个数字的位置，读取第二组，把第一组出现的相同数字的位置放入序列，没出现就不放。。。然后就转成LIS题目了。。。用上吉大的模版然后就A了。

证明就另开一篇吧。。。

湖师大的oj不能看提交的代码，我本地又覆盖掉了。。。T T

于是重敲了一遍：

#include <cstdio>
#include <cstring>
const int maxn = 100001;
int f[maxn], d[maxn];
//LIS模版。。。
int bsearch(const int *f, int size, const int &a) { 
    int  l=0, r=size-1; 
    while( l <= r ){ 
        int  mid = (l+r)/2; 
  if( a > f[mid-1] && a <= f[mid] ) return mid;
        else if( a < f[mid] ) r = mid-1; 
        else l = mid+1; 
    } 
} 
int LIS(const int *a, const int &n){ 
 int  i, j, size = 1; 
 f[0] = a[0]; d[0] = 1; 
 for( i=1; i < n; ++i ){ 
     if( a[i] <= f[0] ) j = 0;
 else if( a[i] > f[size-1] ) j = size++;
  else j = bsearch(f, size, a[i]); 
  f[j] = a[i]; d[i] = j+1; 
 } 
 return size; 
} 

int main() {
//    freopen("in", "r", stdin);
    int rec[maxn], lis[maxn], n, tmp;
    while (scanf("%d", &n) && n) {
        int cnt = 0;
        memset(rec, -1, sizeof(rec));
        for (int i = 1; i <= n; i++) {
            scanf("%d", &tmp);
            rec[tmp] = i;         //存放位置
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &tmp);
            if (rec[tmp] != -1)
                lis[cnt++] = rec[tmp];   //生成LIS
        }
        printf("%d\n", LIS(lis, cnt));
    }
    return 0;
}

然后作为这题看了下B题，因为很多人A了，感觉得用并查集做，做了一半，肚子饿了，叫餐还叫不过来，于是不做了。。。感觉有更好的方法，而且还不知道会不会超时。。。坐等大神了。。

看其他几题，没几个人A，看了下题目，都改得很奇怪。。。于是就到此了，吃饭休息了。。。

这次比赛感觉还好，YY出了一题感觉真棒，坐等大神牛逼算法了。。。