自动搬运

查看原文

来自洛谷，原作者为

	rui_er 九万里风鹏正举

搬运于2025-08-24 22:00:39，当前版本为作者最后更新于2022-02-04 17:50:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

评价：分段打表练习题。

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

第一眼看这题，感觉像是数学题，但是手玩了一会又感觉符合题意的钟点不多（远没有 $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 <bits/stdc++.h>
#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<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> 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 <bits/stdc++.h>
#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<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> 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;
}