题解洛谷 P4483【[BJWC2018]神奇的钟点】

评价：分段打表练习题。

这题第一篇题解，随机跳题跳到这题就来写了。。

第一眼看这题，感觉像是数学题，但是手玩了一会又感觉符合题意的钟点不多（远没有 \(2\times 10^9\) 那么吓人），还没啥规律，于是想先枚举一遍可能的答案，看看有多少个，尝试把表打出来。于是就写了个 \(\mathcal{O}(24^360^3)\) 的暴力，根据 WC2022 讲题人的理论这是 \(\mathcal{O}(1)\)。

经过 59.34s 的等待，我们发现答案总共只有 \(127034\) 个，于是我们进行打表，得到了一张 2482KB 的大表，改一改尝试提交，发现代码过长交不上去。

直接跑要跑 1min，打表还打不下，于是我们退而求其次，每隔 \(K\) 个答案分一段把答案打出来，这样打出 \(\frac{127034}{K}\) 个答案，然后段中间的查询暴力去做。首先我们尝试了 \(K=5000\)，结果 TLE 成了 70/80 分，调整 \(K=3000\) 就过了。

AC 之后查百度，没查到这题的解法，不知道分段打表是不是正解，反正我只会这一种。

UPD：查到了一篇这题的博客，发现正解也是分段打表做的。

打表代码：

//By: Luogu@rui_er(122461)
#include 
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;

template void chkmin(T& x, T y) {if(x > y) x = y;}
template void chkmax(T& x, T y) {if(x < y) x = y;}

int main() {
    freopen("P4483-biaosmall.txt", "w", stdout);
    printf("int ans[44][6]={{0}");
    int tot = 0;
    rep(h1, 0, 23) {
        rep(m1, 1, 59) {
            rep(h2, 0, 23) {
                if(h1 + h2 > 23) break;
                rep(m2, 1, 59) {
                    rep(h3, 0, 23) {
                        if(h1 + h2 + h3 > 23) break;
                        rep(m3, 1, 59) {
                            int H = h1 + h2 + h3;
                            int M = m1 + m2 + m3;
                            H += M / 60;
                            M %= 60;
                            if(H > 23) break;
                            if(!M) continue;
                            int p1 = h1 * m2 * m3 + m1 * h2 * m3 + m1 * m2 * h3;
                            int q1 = m1 * m2 * m3;
                            int p2 = H;
                            int q2 = M;
                            int g1 = __gcd(p1, q1);
                            p1 /= g1; q1 /= g1;
                            int g2 = __gcd(p2, q2);
                            p2 /= g2; q2 /= g2;
                            if(p1 == p2 && q1 == q2) {
                                ++tot;
                                if(tot % 3000 == 1) printf(",{%d,%d,%d,%d,%d,%d}", h1, m1, h2, m2, h3, m3);
                            }
                        }
                    }
                }
            }
        }
    }
    printf("};");
    return 0;
}

最终代码：

//By: Luogu@rui_er(122461)
#include 
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 127034, K = 3000;
int ans[44][6]={ /* 打表的结果，篇幅考虑就不放了*/  };

int n;
template void chkmin(T& x, T y) {if(x > y) x = y;}
template void chkmax(T& x, T y) {if(x < y) x = y;}
struct Time {
    int h, m;
    Time(int a=0, int b=0) : h(a), m(b) {}
    ~Time() {}
    Time nxt() {
        Time tmp = *this;
        ++tmp.m;
        if(tmp.m == 60) {
            ++tmp.h;
            tmp.m = 1;
        }
        return tmp;
    }
    bool last() {
        return h == 23 && m == 59;
    }
};

int main() {
    scanf("%d", &n);
    if(n > N) return puts("-1")&0;
    int k = (n - 1) / K + 1;
    Time A = Time(ans[k][0], ans[k][1]);
    Time B = Time(ans[k][2], ans[k][3]);
    Time C = Time(ans[k][4], ans[k][5]);
    rep(T, K*(k-1)+2, n) {
        while(true) {
            if(!C.last()) C = C.nxt();
            else if(!B.last()) B = B.nxt(), C = Time(0, 1);
            else A = A.nxt(), B = C = Time(0, 1);
            int H = A.h + B.h + C.h;
            int M = A.m + B.m + C.m;
            H += M / 60;
            M %= 60;
            if(0 <= H && H <= 23 && 1 <= M && M <= 59) {
                int p1 = A.h * B.m * C.m + A.m * B.h * C.m + A.m * B.m * C.h;
                int q1 = A.m * B.m * C.m;
                int p2 = H;
                int q2 = M;
                int g1 = __gcd(p1, q1);
                p1 /= g1; q1 /= g1;
                int g2 = __gcd(p2, q2);
                p2 /= g2; q2 /= g2;
                if(p1 == p2 && q1 == q2) break;
            }
        }
    }
    printf("%02d:%02d %02d:%02d %02d:%02d\n", A.h, A.m, B.h, B.m, C.h, C.m);
    return 0;
}