Magic Square 解题报告

本题是BFS的经典题目，因为只有8个数字，每个都在1～8之间，因此可以使用一个32bit整型描述状态，使用bitwise改变状态。

需要注意散列函数，要使用unsigned long，或者给返回值加上labs()，否则散列值（在某些机器上）可能是负数，造成数组越界。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#define SEED 10007

struct element
{
    unsigned long s;
    char op;
    long prev;
}queue[41000] = {};

struct HNode
{
    unsigned long s;
    struct HNode *next;
}*hashtable[SEED] = {};

long head,tail;
long target = 0;

void enqueue(struct element a)
{
    queue[tail ++] = a;
}

struct element dequeue()
{
    return queue[head ++];
}

void getarget()
{
    int i;
    long t;
    for(i = 7;i >= 0;i --)
    {
        scanf("%ld",&t);
        target |= t << (i * 4);
    }
}

unsigned long h(unsigned long s)
{
    return (s % (unsigned long)SEED);
}

long transA(long s)
{
    long t;
    t = ((s & 0xF) << 28) | ((s & 0xF0) << 20) | ((s & 0xF00) << 12) | ((s & 0xF000) << 4);
    t |= ((s & 0xF0000) >> 4) | ((s & 0xF00000) >> 12) | ((s & 0xF000000) >> 20) | ((s & 0xF0000000) >> 28);
    return t;
}

long transB(long s)
{
    long t;
    t = ((s & 0xFFF00000) >> 4) + ((s & 0xFFF) << 4) + ((s & 0xF0000) << 12) + ((s & 0xF000) >> 12);
    return t;
}

long transC(long s)
{
    long t;
    t = s & 0xF00FF00F;
    t |= (s & 0xF0) << 20 | (s & 0xF00) >> 4 | (s & 0xF00000) >> 12 | (s & 0xF000000) >> 4;
    return t;
}

void pt(struct element p)
{
    char str[70];
    int i;
    for(i = 0;i < 60 && p.op != 0;p = queue[p.prev],i ++)
    {
        str[i] = p.op;
    }
    printf("%d\n",i);
    for(i --;i >= 0;i --)
    {
        printf("%c",str[i]);
    }
    printf("\n");
}

int find(long s)
{
    struct HNode *p;
    for(p = hashtable[h(s)];p != NULL;p = p->next)
        if(p->s == s)   return 1;
    return 0;
}

void insert(long s)
{
    struct HNode *p;
    p = malloc(sizeof(struct HNode));
    p->s = s;
    p->next = hashtable[h(s)];
    //fprintf(stderr,"%ld\n",h(s));
    hashtable[h(s)] = p;
}

int main()
{
    freopen("msquare.out","w",stdout);
    freopen("msquare.in","r",stdin);
    struct element now,next;
    long tmp;
    head = tail = 0;
    getarget();
    now.s = 0x12345678;
    now.prev = 0;
    now.op = 0;
    insert(0x12345678);
    enqueue(now);
    while(head < tail)
    {
        now = dequeue();
        if(now.s == target) break;
        tmp = transA(now.s);
        if(!find(tmp))
        {
            insert(tmp);
            next.s = tmp;
            next.prev = head - 1;
            next.op = 'A';
            enqueue(next);
        }
        tmp = transB(now.s);
        if(!find(tmp))
        {
            insert(tmp);
            next.s = tmp;
            next.prev = head - 1;
            next.op = 'B';
            enqueue(next);
        }
        tmp = transC(now.s);
        if(!find(tmp))
        {
            insert(tmp);
            next.s = tmp;
            next.prev = head - 1;
            next.op = 'C';
            enqueue(next);
        }
    }
    pt(now);
    return 0;
}

此外，USACO的题解给出了一种更适用与本题的方法，即把每个状态与一个数字相对应，只要用8！个数字就可以描述所有状态。并且从目标向初始状态搜索，输出结果时就没有必要反过来了。

NOIP 2008 双栈排序

起初想用贪心做，不过贪心算法不能判定要把数字放在哪一个栈里面。

本题的关键在于利用栈的性质建图，用来确定每个数所放的栈。
依据栈FILO的特点，栈里面的数必须是递减的，否则就有数字出不来了，

NOIP 2009 最优贸易

容易知道，商人的旅行路线一定是这样的：
1--->A--->B--->N
他在A点买入，在B点卖出，因此，容易想到下面的算法：

1、先BFS标记可以由1到达的点；
2、然后BFS标记可以到N的点；
3、对于第一步标记可达的点BFS，计算如果在这个点购买，并且可以到达终点，可以获得的最大差价（需要用到第二步的结果）；
4、输出第三步中结果的最大值即可。

不过，这种算法的效率不是很高，仅仅通过了50%的数据。因此，还需要对问题做进一步分析。
题目仅仅要我们求出商人的最大收益，并没有问A，B两点的位置，有又因为A可以到达B，所以在A->B的路径中（包括AB）一定存在一个或者几个点，满足条件：
1-->X-->N
X靠近1一侧可以低价买入，靠近N一侧可以高价卖出，我们只要把每个点两侧的最低最高价格求出来就可以了。
要实现这一点，只需要把上面BFS稍稍修改即可，即在每次扩展节点的时候比较价格，详见代码88～96行，62～70行。

代码：

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

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 #define MXN (100000+10)
006 #define QL 10000000
007
008 typedef struct node
009 {
010     int v;
011     struct node *next;
012 }node;
013
014 long queue[QL];
015 long head,tail;
016 int price[MXN];
017 int c1[MXN] = {};
018 int cn[MXN] = {};
019 long N,M;
020 node *first[MXN];
021 node *reverse[MXN];
022
023 void enqueue(long a)
024 {
025     queue[tail] = a;
026     tail = (tail + 1) % QL;
027 }
028
029 int get_min(int a,int b)
030 {
031     if(a < b)    return a;
032     return b;
033 }
034
035 int get_max(int a,int b)
036 {
037     if(a > b)    return a;
038     return b;
039 }
040
041 long dequeue()
042 {
043     long r;
044     r = queue[head];
045     head = (head + 1) % QL;
046     return r;
047 }
048
049 void bfs1()
050 {
051     node *p;
052     long i;
053     head = tail = 0;
054     c1[1] = price[1];
055     enqueue(1);
056     while(head < tail)
057     {
058         i = dequeue();
059         for(p = first[i];p != NULL;p = p->next)
060         {
061             if(c1[i] < c1[p->v])
062             {
063                 c1[p->v] = c1[i];
064                 enqueue(p->v);
065             }
066             else if(c1[p->v] == 0)
067             {
068                 c1[p->v] = get_min(price[p->v],c1[i]);
069                 enqueue(p->v);
070             }
071         }
072     }
073 }
074
075 void bfs2()
076 {
077     node *p;
078     long i;
079     head = tail = 0;
080     cn[N] = price[N];
081     enqueue(N);
082     while(head < tail)
083     {
084         i = dequeue();
085         for(p = reverse[i];p != NULL;p = p->next)
086         {
087             if(cn[p->v] == 0)
088             {
089                 cn[p->v] = get_max(price[p->v],cn[i]);
090                 enqueue(p->v);
091             }
092             else if(cn[i] > cn[p->v])
093             {
094                 cn[p->v] = cn[i];
095                 enqueue(p->v);
096             }
097         }
098     }
099 }   
100
101 void addedge(long b,long e)
102 {
103     node *p;
104     p = malloc(sizeof(node));
105     p->v = e;
106     p->next = first[b];
107     first[b] = p;
108     //reverse adjlink,for BFS2
109     p = malloc(sizeof(node));
110     p->v = b;
111     p->next = reverse[e];
112     reverse[e] = p;
113 }
114
115 int main()
116 {
117     scanf("%ld%ld",&N,&M);
118     long i,j,k;
119     int max;
120     for(i = 1;i <= N;i ++)
121         scanf("%d",&price[i]);
122     while(M --)
123     {
124         scanf("%ld%ld%ld",&i,&j,&k);
125         if(k == 1)
126             addedge(i,j);
127         else if(k == 2)
128         {
129             addedge(i,j);
130             addedge(j,i);
131         }
132     }
133     bfs1();
134     bfs2();
135     for(i = 1,max = 0;i <= N;i ++)
136     {
137         if(cn[i] - c1[i] > max)
138             max = cn[i] - c1[i];
139     }
140     printf("%d\n",max);
141     return 0;
142 }

NOIP 2009 靶形数独

本题要取得满分需要一定的剪枝，不过，一般的DFS+适当的数据结构可以获得80分。

代码如下（80分，4个测试点严重超时）：

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

001 #include <stdio.h>
002 #include <stdlib.h>
003 #define MXN 10
004
005 typedef struct point
006 {
007     int i,j;
008 }point;
009
010 int dx[8] = {0,0,1,-1,1,-1,-1,1};
011 int dy[8] = {1,-1,1,-1,0,0,1,-1};
012
013 point empty[MXN * MXN];
014 int find;
015 int ecount;
016 long initmark;
017 int board[MXN][MXN];  //记录数字
018 int belong[MXN][MXN];  //某个位置所在的小区域编号
019 int rank[MXN][MXN];  //权重
020 int col[MXN] = {},row[MXN] = {};  //类似下面的
021 int part[MXN] = {};  //小区域中某个数字是否使用过
022 long max = 0;  //填入的数字可以增加的最大分值
023
024 void markbelong(int i,int j,int b)
025 {
026     int k;
027     belong[i][j] = b;
028     for(k = 0;k < 8;k ++)
029         belong[i + dx[k]][j + dy[k]] = b;
030 }
031
032 void toggle(int i,int j,int v)
033 {
034     row[i] ^= (1 << v);
035     col[j] ^= (1 << v);
036     part[belong[i][j]] ^= (1 << v);
037 }
038
039 void init()
040 {
041     int i,j,t;
042     for(t = 0;t < 5;t ++)
043     {
044         for(i = t;i < 9 - t;i ++)
045             for(j = t;j < 9 - t;j ++)
046                 rank[i][j] = 5 + t + 1;
047     }
048     //初始化belong数组
049     markbelong(1,1,1);
050     markbelong(1,4,2);
051     markbelong(1,7,3);
052     markbelong(4,1,4);
053     markbelong(4,4,5);
054     markbelong(4,7,6);
055     markbelong(7,1,7);
056     markbelong(7,4,8);
057     markbelong(7,7,9);
058
059     ecount = initmark = 0;
060     for(i = 0;i < 9;i ++)
061         for(j = 0;j < 9;j ++)
062         {
063             scanf("%d",&board[i][j]);
064             if(board[i][j] == 0)
065             {
066                 empty[ecount].i = i;
067                 empty[ecount].j = j;
068                 ecount ++;
069             }
070             else
071             {
072                 initmark += rank[i][j] * board[i][j]; //计算已经有数组的格子获得的分值
073                 toggle(i,j,board[i][j]);  //标记使用过
074             }
075         }
076 }
077
078 void dfs(int p,long m)
079 {
080     if(p == ecount)
081     {
082         find = 1;
083         if(m > max) max = m;
084         return;
085     }
086     int k;
087     for(k = 1;k <= 9;k ++)
088     {
089         if((((row[empty[p].i] >> k) & 1) == 0) && (((col[empty[p].j] >> k) & 1) == 0) && (((part[belong[empty[p].i][empty[p].j]] >> k) & 1) == 0))
090         {
091             toggle(empty[p].i,empty[p].j,k);
092             dfs(p + 1,m + rank[empty[p].i][empty[p].j] * k);
093             toggle(empty[p].i,empty[p].j,k);
094         }
095     }
096 }
097
098 int main()
099 {
100     init();
101     find = 0;
102     dfs(0,0);
103     if(find)    printf("%ld\n",max + initmark);
104     else    printf("-1\n");  //注意无解情况
105     return 0;
106 }