跳至正文

[未完成]USACO 1.4.1 Prime Cryptarithm

  • OI路程

  这是这一次做USACO目前唯一一个没做完的题目!第六种情况实在是不知道怎么写,我觉得最好还是不写最好,所以就没去写了。我也尝试了一下自己试着写写,结果写了最后一种情况竟然还不如不写的分数高!但是自己实在是不知道为什么,以前的代码这三行(最后一种情况)也是抄的,不是理解的,所以现在也就忘了……
  我的思路就是暴搜,用srch0将所用的矩形换位置,srch1将所有的矩阵的长宽交换,然后用count进行判断,代码十分易读(以前别人写的,不过因为确实有特色,所以已经变成了自己的东西了。)
  总结一下错误:

  1、把return忘记了,会进入死循环。
  2、递归调用时应该是srch(0)而不是n + 1。
  3、在记录答案时竟然没有判断。
  4、在一种情况的时候把y写成了x。
  注意:本程序还没AC,但是要他AC只需要最后的两个if,因为我不理解缘由,所以没写第六种情况(代码中注释好了!)
/
LANG: C
ID: yylogoo2
PROG: packrec
/
#include <math.h>
#include <stdio.h>
#include <string.h>
struct box{
        int x, y;
}box[4];
int place[4];
int ans = 2501;
int take[2501];

void check(int x, int y)
{
        if(x y < ans){
                ans = x
y;
                memset(take, 0sizeof(take));
        }
        /
        Mistack 3:
          没经过任何判断就直接把x, y作为答案了,那么就错了!! 
        即刚刚忘记敲入if了。 
        
/
        if(x y == ans){
                take[x] = 1;
                take[y] = 1;
        }
}

int max(int a, int b)
{
        return a > b ? a : b;
}

void count(int x1, int y1, int x2, int y2,
                int x3, int y3, int x4, int y4)
{
        int x, y;

        x = x1 + x2 + x3 + x4;
        y = max(max(y1, y2), max(y3, y4));
        check(x, y);

        x = max(x1, x2 + x3 + x4);
        y = y1 + max(y2, max(y3, y4));
        check(x, y);

        x = max(x1, x2 + x3) + x4;
        y = max(y4, y1 + max(y2, y3));
        check(x, y);

        x = x1 + max(x2, x3) + x4;
        /

        Mistack 4:
          下面把y写成了x
        /
        y = max(y2 + y3, max(y1, y4));
        check(x, y);

        / 最后一种情况 /
}

void output(void)
{
        int i, limit;
        printf("%d\n", ans);
        limit = sqrt(ans);
        for(i = 1; i <= limit; i++){
                if(take[i]){
                        printf("%d %d\n", i, ans / i);
                }
        }
}

void change(struct box a)
{
        a->x ^= a->y;
        a->y ^= a->x;
        a->x ^= a->y;
}

void srch1(int now)
{
        if(now == 4){
                count(  box[place[0]].x, box[place[0]].y,
                        box[place[1]].x, box[place[1]].y,
                        box[place[2]].x, box[place[2]].y,
                        box[place[3]].x, box[place[3]].y);
                return;
        }
        srch1(now + 1);
        change(&box[place[now]]);
        srch1(now + 1);
        change(&box[place[now]]);
}

int used[4];

void srch0(int now)
{
        int i;
        if(now == 4){
                /
                Mistack 2:
                  是调用srch1(0)而不是srch(now + 1)
                
/
                srch1(0);
                /
                Mistack 1:
                  把函数返回掉了…那样会死循环的..
                
/
                return;
        }
        for(i = 0; i < 4; i++){
                if(!used[i]){
                        used[i] = 1;
                        place[now] = i;
                        srch0(now + 1);
                        used[i] = 0;
                }
        }
}

int main(void)
{
        int i;
        freopen("packrec.in""r"stdin);
        freopen("packrec.out""w"stdout);
        for(i = 0; i < 4; i++){
                scanf("%d%d", &box[i].x, &box[i].y);
        }
        srch0(0);
        output();
        return 0;
}

发表评论

您的电子邮箱地址不会被公开。