跳至正文

USACO 1.4.2 The Clocks

  • OI路程

  这一个题目我还算是自豪吧,代码比以前写的好看一点,仅仅是因为几行代码的原因,但是这几行代码我觉得挺好的!具体是哪几行,看代码的注释,代码中唯一的一个错误就是判断一个数据是否为答案时竟然忘记判断了!!

  代码如下:
/
LANG: C
ID: yylogoo2
PROG: clocks
/
#include <stdio.h>
#include <string.h>
int clocks[9];
char ways[9][6] = {"ABDE""ABC""BCEF""ADG""BDEFH""CFI",
                        "DEGH""GHI""EFHI"};
int used[9];
int ans[9];
int len = 50;

void change(int a)
{
        char str = ways[a];
        while(
str != ‘\0’){
                clocks[str – ‘A’]++;
                if(clocks[
str – ‘A’] == 5){
                        clocks[str – ‘A’] = 1;
                }
                str++;
        }
}

void check(int sum)
{
        int i;
        if(sum > len){
                return;
        }
        /

        Mistack 1:
          刚刚忘记判断下面的for了
        /
        for(i = 0; i < 9; i++){
                if(clocks[i] != 4){
                        return;
                }
        }
        if(sum < len){
                memcpy(ans, used, sizeof(used));
                len = sum;
        }else if(sum == len){
                for(i = 0; i < 9; i++){
                        if(used[i] >= ans[i]){
                                break;
                        }
                }
                if(i != 9){
                        memcpy(ans, used, sizeof(used));
                        len = sum;
                }
        }
}

void srch(int now, int sum)
{
        int i;
        check(sum);
        if(now == 9){
                return;
        }
        /

                对下面我解释一下:
          要知道的是,任何一个移动方法,当同一种移动方式出现四次之后,
        都可以将其无视掉。如:1212212因为其中2出现了4次,那么相当于没有
        2的存在,即:111,又如:21121211,其中有5个1,那么就相当于3个2和
        1个1,又要按照最小顺序排序,即:1222。
          下面巧用了这个性质,就不许要将其复原,因为四次循环之后自然而
        然就已经复原了!
        */
        for(i = 1; i <= 4; i++){
                srch(now + 1, sum + used[now]);
                used[now]++;
                change(now);
        }
        used[now] = 0;
}

int main(void)
{
        int i, j, k = 0;
        freopen("clocks.in""r"stdin);
        freopen("clocks.out""w"stdout);
        for(i = 0; i < 9; i++){
                scanf("%d", &clocks[i]);
                clocks[i] /= 3;
        }
        srch(00);
        for(i = 0; i < 9; i++){
                for(j = 0; j < ans[i]; j++){
                        if(k){
                                printf(" ");
                        }
                        k = 1;
                        printf("%d", i + 1);
                }
        }
        printf("\n");
        return 0;
}

发表回复

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