拨钟问题新解

作者 : 开心源码 本文共2770个字,预计阅读时间需要7分钟 发布时间: 2022-05-13 共263人阅读

题目形容
Time limit: 10000 ms
Memory limit: 256 MB
Standard I/O
表店里有9个时钟,钟表被编号为A到I。时钟只有一个时针,在初始时,每个时钟可能指向整3点、6点、9点或者12点。你被给予九种“操作”,每种操作可以将某些时钟的时间前进3小时(顺时针旋转),操作编号0到8,每种操作影响的时钟列表:

0: A B C
1: A B D E
2: A D G
3: B C E F
4: B D E F H
5: C F I
6: D E G H
7: E F H I
8: G H I
给你一个对9个时钟当前指针位置的形容,请给出一个操作数最少的操作序列,使得按照这个序列操作后,每个时钟的指针都指向12点。

输入形容
输入有若干行(不给出具体数目),每行包含以一个空格分开的9个整数,每个整数取值可能为3、6、9、12,依次标识时钟A到I的初始指针位置。不会每个指针都指向12点。
在本“完整版”,你将被一次测试一律可能的输入:4的9次方减1共262143组,而仍只有10s的时间限制。 这些输入对应的最少操作序列仍旧都是唯一的(这是一个有趣的线性代数问题)。

输出形容
输出包括若干行,对应每个输入,输出最小操作序列;输入保证对应的最小操作序列是 “唯一” 的:假如将序列中的每个操作按编号升序输出的话。
在可能的情况下,行末多余的空格也会导致你 wrong answer!

逆向思维 假如可以从初始状态顺时针旋转到全12点,那么从全12点,用同样的操作序列,让其逆时针转动,就会回到初始状态,并且这个操作序列也是(唯一)最少操作的。
你需要做的可能是一个与A题相反的对称操作:将加变成减,将负数“同余”(不肯定是取模)回到肯定的范围。
而后,你需要做一次“全面”的初始计算:从全12点的状态出发,枚举计算到所有其余262143个时钟状态的最少(逆时针)操作序列。将这些答案存到表或者数组里,而后再解决 262143 个讯问。

样例输入
9 9 12 6 6 6 6 3 6
3 3 12 9 12 9 12 9 6
样例输出
2 4 7 8
1 1 1 3 4 4 4 5 5 5 6 6 6 7 7 8

通常情况下我们使用九重循环的方法暴力求解.但是这里我们有如此海量的数据,直接九重循环定然超时.

为此,我们需要削减循环次数.

从最后一步考虑.我们此时还剩下几个钟,只要要一次操作就可还原为12点.因为拨钟的顺序不影响结果(比方你先拨AB,再拨AC与先AC后AB是一样的),所以最后剩余的钟我们是可以任意定义的.

观察我们的所有操作.可以发现,只有操作1同时对ABC进行操作,故我们将最后的三个钟设定为ABC.于是我们得到如下思路:

通过op1-op8八个操作,使得最后只剩下ABC未还原,且ABC状态相同.由于只有状态相同的情况才可以通过op0一步到位.

现在我们只要要考虑6个钟了.与ABC相同,我们可以将这六个钟再度划分为DEF与GHI.因为只有op8是对GHI同时操作的.我们需要:
通过op1-op7七个操作,使得最后只剩下GHI未还原,且状态相同.

因为op8与op0互不干扰,所以上述条件应当同时成立.总而言之:

通过op1-op7七个操作,使得DEF一律复位,而ABC与GHI分别处于某个相同状态.

于是我们的循环变为7重,总共减少了15\cdot4^7次运算.

代码如下:

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<string.h>int main(void) {    int Alarm[9] = { 0 };    while (scanf("%d%d%d%d%d%d%d%d%d", &Alarm[0], &Alarm[1],        &Alarm[2], &Alarm[3], &Alarm[4], &Alarm[5], &Alarm[6], &Alarm[7], &Alarm[8])==9) {        int i;        for (i = 0; i < 9; i++) {            Alarm[i] = (Alarm[i] / 3) % 4;        }        int OpNum[10];        int Answer[10];        Answer[9] = 50;        for (OpNum[1] = 0; OpNum[1] < 4; OpNum[1]++) {            for (OpNum[2] = 0; OpNum[2] < 4; OpNum[2]++) {                for (OpNum[3] = 0; OpNum[3] < 4; OpNum[3]++) {                    for (OpNum[4] = 0; OpNum[4] < 4; OpNum[4]++) {                        for (OpNum[5] = 0; OpNum[5] < 4; OpNum[5]++) {                            for (OpNum[6] = 0; OpNum[6] < 4; OpNum[6]++) {                                for (OpNum[7] = 0; OpNum[7] < 4; OpNum[7]++) {                                    if ((OpNum[1] + OpNum[2] + OpNum[4] + OpNum[6] + Alarm[3]) % 4 == 0 &&                                        (OpNum[1] + OpNum[3] + OpNum[4] + OpNum[6] + OpNum[7] + Alarm[4]) % 4 == 0 &&                                        (OpNum[3] + OpNum[4] + OpNum[5] + OpNum[7] + Alarm[5]) % 4 == 0) {                                        int A0= ( OpNum[1] + OpNum[2] + Alarm[0]) % 4;                                        int A1 = (OpNum[1] + OpNum[3] + OpNum[4] + Alarm[1]) % 4;                                        int A2 = ( OpNum[3] + OpNum[5] + Alarm[2]) % 4;                                        if (A0==A1  && A1==A2) {                                            int A6 = (OpNum[2] + OpNum[6] + Alarm[6]) % 4;                                            int A7 = (OpNum[4] + OpNum[6] + OpNum[7] +  Alarm[7]) % 4;                                            int A8 = (OpNum[5] + OpNum[7]+ Alarm[8]) % 4;                                            if (A6==A7&&A7==A8 ) {                                                OpNum[0] = (4 - A0) % 4;                                                OpNum[8] = (4 - A8) % 4;                                                OpNum[9] = OpNum[0] + OpNum[1] + OpNum[2] + OpNum[3] + OpNum[4] + OpNum[5] + OpNum[6] + OpNum[7] + OpNum[8];                                                if (OpNum[9] < Answer[9]) {                                                    memcpy(Answer, OpNum, 10 * sizeof(int));                                                }                                            }                                        }                                    }                                }                            }                        }                    }                }            }        }        for (i = 0; i < 8; i++) {            for (int j = 0; j < Answer[i]; j++) {                    printf("%d ", i);            }        }        if (Answer[8] != 0) {            for (int j = 0; j < Answer[8] - 1; j++) {                printf("8 ");            }            printf("8\n");        }        else {            putchar('\n');        }    }    return 0;}

在codia平台上测试,6853ms通过.比起九重循环快了将近一倍.

这里快了近一倍还有一个因素,在于if判断语句上面.我们并不需要计算出所有情况再判断,边算边判断会节省大量时间.

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 拨钟问题新解

发表回复