抱着侥幸心态去参加了学校的ACM校赛。

十一个题。AC了 四道题。难题基本没做出来。

可以做出来的D题被 负数和 空 卡了。就是卡数据了。一直不停的RE和WA。浪费大把时间。

F题二进制用斐波那契数列排列，结果我搞错排列，WA了几次就没去看了，时间太紧。

H题的八数码问题 本来用打算用哈希表判重，可是一直卡在这写不对。

I题比赛完了跑去问大神，大神说是网络流问题，连题意都理解错的我真是悲剧。

K题是线段树问题，比赛完了才想到，比赛时一直当作优先队列问题在做，于是WA是必然的。

我贴出H题的题意和I题的题意，忘有大神能给于我解答，谢谢。


H：

Problem H: Can you get it？

Time Limit: 5 Sec Memory Limit: 512 MB

Description
      Jingkai Wang always ponder over things alone. So, his gay friend Jie Yang, ask him to play a interesting game which called Jiugong Arrangement. This game is very easy, the rules as follow. Gving you the begin status and the end status, you just need to find what is the minimum steps the begin status change to the end status. Surely, you can move 


Input
      The first line of input contains only one integer T ( 1 < = T < = 100 ) indicates the test cases, the following T cases.

       Each test has six lines, the previous three lines indicate the begin status and the next three lines indicate the end status.  

Output

 The output only contains one number, indicate the minimum steps from the begin status to the end status. If there is impossible to change the begin status to end status, please output -1.


Sample Input
2
123
456
78.

123
.46
758

135
246
78.

467
581
23.

Sample Output
3
22

I题 ：

Problem I: Love Toys

Time Limit: 2 Sec  Memory Limit: 512 MB

Description
     As the Math King in our ACM team, Tailong Wu want to give his girl-friend a surprise in her birthday. He plans to buy n toys to his girl-friend. The n toys can be made in m toy factories, and each toy factory may spend different


 time making toys. Each toy only can be made completely in one factory. The production 

order of these toys can be random. Before the factory finishes one toy , it can’t make 

others. Now, his girl-friend’s birthday is coming, he wants to get the n toys as soon as possible.




Input
The input contains multiple test cases;

The first line of each test case contains two integers n ( 1 < = n < = 50 ), 

m ( 1 < = m < = 50 ), the following n lines, each line contains m integers Ci,j 

indicate the time which the ith spend Ci,j making the toy j.


Output
The output only contains one float time indicate the minimum average time he can buy 

the n toys. The result should be rounded to six decimal places.


Sample Input
3 4
100 100 100 1
99 99 99 1
98 98 98 1

3 4
1 100 100 100
99 1 99 99 
98 98 1 98

3 4
1 100 100 100
1 99 99 99
98 1 98 98

Sample Output
2.000000
1.000000
1.333333

H： BFS算法

I是贪心算法吧

知道是BFS。我卡在判重了。学长说的什么方法没听明白，只是到哈希表可以。
求哈希表的写法。正确的说是本题哈希表判重的写法。

for (s = 0, i = 0;i < 10;i += 1) {
  s *= 10;
  s += isdigit(str[i]) ? str[i] - '0' : 0;
}
flag[s] = 1;

开始也这样想过（数最大也就10e9），但是还是没过。

如果是空间不够，就用 char 甚至 位运算

如果不是，那就是你算法的问题

试试直接用链式。只要有不同就停止比较。
比如
只要比对到和终止状态有不同就停止。
感觉有点像是字典树了。

突发奇想是不是可以开一个九维数组。
a[1][2][3][0][4][6][7][5][8] 表示终止状态。
判重问题也解决了。
可是每次初始化就麻烦了。

查了一下，要用一个叫康托展开的东东

写了才知道，真心麻烦

#define _CRT_SECURE_NO_WARNINGS

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

#define  M     3
#define  N     (M*M)
#define  SIZE  362880  //M!

typedef enum
{
    LEFT, RIGHT, UP, DOWN
}Towards;

typedef struct
{
    int  up, down, left, right;
}MatrixStatus;

typedef struct S
{
    int index, distance;
    struct S *next;
}QueueNode, *QueuePtr;

typedef struct
{
    QueuePtr front, rear;
}Queue, *LinkQueue;

void InitQueue(LinkQueue Q)
{
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QueueNode));
    Q->front->next = NULL;
}

void DestroyQueue(LinkQueue Q)
{
    while (Q->front)
    {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
}

int  QueueEmpty(Queue Q)
{
    return Q.front == Q.rear;
}

void EnQueue(LinkQueue Q, int index, int distance)
{
    QueuePtr p  = (QueuePtr)malloc(sizeof(QueueNode));
    p->index    = index;
    p->distance = distance;
    p->next     = NULL;
    Q->rear->next = p;
    Q->rear       = p;
}

void DeQueue(LinkQueue Q, int *index, int *distance)
{
    QueuePtr p = Q->front->next;
    *index     = p->index;
    *distance  = p->distance;
    Q->front->next = p->next;
    if (Q->rear == p) Q->rear = Q->front;
    free(p);
}

static int fac[]  = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320 };

/*

 * 康托展开

 */
int  GetIndex(char *str)
{
    int result = 0;
    for (int i = 0; i < N; i++)
    {
        int count = 0;
        for (int j = i + 1; j < N; j++)
        {
            count += str[i] > str[j];
        }
        result += count * fac[N - i - 1];
    }
    return result;
}

/*

 * 逆康托展开

 */
void UnCantor(char a[N], int x)
{
    int i, j, l, t;
    char h[N + M] = {0};

    for (i = 1; i <= N; i++)
    {
        t  = x / fac[N - i];
        x -= t * fac[N - i];

        for (j = 1, l = 0; l <= t; j++)
            if (!h[j])  l++;

        h[--j]   = 1;
        a[i - 1] = j - 1 + '0';
    }
}

void Swap(char *str, int ip, Towards flag)
{
    char tmp;

    switch (flag)
    {
    case LEFT:
        tmp = str[ip], str[ip] = str[ip - 1], str[ip - 1] = tmp;
        break;
    case RIGHT:
        tmp = str[ip], str[ip] = str[ip + 1], str[ip + 1] = tmp;
        break;
    case UP:
        tmp = str[ip], str[ip] = str[ip - M], str[ip - M] = tmp;
        break;
    case DOWN:
        tmp = str[ip], str[ip] = str[ip + M], str[ip + M] = tmp;
        break;
    }
}

int  FindZero(char *str)
{
    for (int i = 0; i < N; i++)
    {
        if ('0' == str[i])  return i;
    }
    return -1;
}

void InitArray(MatrixStatus *ans)
{
    char str[N];
    for (int i = 0; i < SIZE; i++)
    {
        UnCantor(str, i);
        int ip = FindZero(str);

        //LEFT
        if (ip % M)
        {
            Swap(str, ip, LEFT);
            ans[i].left = GetIndex(str);
            Swap(str, ip, LEFT);
        }
        else  ans[i].left = -1;

        //RIGHT
        if (M - 1 != ip % M)
        {
            Swap(str, ip, RIGHT);
            ans[i].right = GetIndex(str);
            Swap(str, ip, RIGHT);
        }
        else  ans[i].right = -1;

        //UP
        if (M <= ip)
        {
            Swap(str, ip, UP);
            ans[i].up = GetIndex(str);
            Swap(str, ip, UP);
        }
        else  ans[i].up = -1;

        //DOWN
        if (N - M > ip)
        {
            Swap(str, ip, DOWN);
            ans[i].down = GetIndex(str);
            Swap(str, ip, DOWN);
        }
        else  ans[i].down = -1;
    }
}

int  BFS(MatrixStatus *ans, int a, int b)
{
    Queue Q;
    int   tmp = a, index, distance, step = -1;
    char *flag = calloc(SIZE, sizeof(char));

    flag[tmp] = 1;
    InitQueue(&Q);
    EnQueue(&Q, tmp, 0);
    while (!QueueEmpty(Q))
    {
        DeQueue(&Q, &index, &distance);

        tmp = ans[index].left;
        if (-1 != tmp && !flag[tmp])
        {
            if (tmp == b)  break;
            EnQueue(&Q, tmp, distance + 1);
            flag[tmp] = 1;
        }

        tmp = ans[index].right;
        if (-1 != tmp && !flag[tmp])
        {
            if (tmp == b)  break;
            EnQueue(&Q, tmp, distance + 1);
            flag[tmp] = 1;
        }

        tmp = ans[index].up;
        if (-1 != tmp && !flag[tmp])
        {
            if (tmp == b)  break;
            EnQueue(&Q, tmp, distance + 1);
            flag[tmp] = 1;
        }

        tmp = ans[index].down;
        if (-1 != tmp && !flag[tmp])
        {
            if (tmp == b)  break;
            EnQueue(&Q, tmp, distance + 1);
            flag[tmp] = 1;
        }
    }
    if (!QueueEmpty(Q)) step = distance + 1;
    free(flag);  DestroyQueue(&Q);
    return step;
}

int main(int argc, char *argv[])
{
    int  a, b, T;
    char str[N + 1];
    MatrixStatus *ans = calloc(SIZE, sizeof(MatrixStatus));

    InitArray(ans);

    scanf("%d", &T);
    while (T--)
    {
        scanf("%s", str), scanf("%s", str + 3), scanf("%s", str + 6);
        a = GetIndex(str);

        scanf("%s", str), scanf("%s", str + 3), scanf("%s", str + 6);
        b = GetIndex(str);

        printf("%d\n", (a == b) ? 0 : BFS(ans, a, b));
    }
    free(ans);
    return 0;
}

[ 本帖最后由 azzbcc 于 2014-4-29 21:17 编辑 ]