打卡信奥刷题（3230）用C++实现信奥题 P8431 「WHOI-2」彗星蜜月

rogeliu

301人浏览 · 2026-05-08 12:30:07

rogeliu · 2026-05-08 12:30:07 发布

P8431 「WHOI-2」彗星蜜月

题目背景

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

看完这首 mv 的前奏之后你应该知道 $f$ 是什么鬼了（误）。

题目描述

定义 $f (x)$ 是 $x$ 的各位数码翻转以后形成的数。

例如：

$f (12323) = 32321$
$f (114514) = 415411$
$f (250) = 52$

给定一个 $n$ 。求最大的 $k$ ，使得对于所有处于 $[1, k]$ 区间中的正整数 $m$ ，有 $f(m)≤nf(m)\leq n$ 。

输入格式

本题多测

第一行一个正整数 $T$ 表示测试点数目。

接下来每个测试点一个正整数 $n$ 。

输出格式

$T$ 行，对应每个测试点的答案。

输入输出样例 #1

输入 #1

输出 #1

11
298
100001

输入输出样例 #2

输入 #2

2
99999
99998

输出 #2

100000
99998

说明/提示

对于测试样例 $1$ ：
$f (1) = 1, f (2) = 2, f (3) = 3, f (4) = 4, f (5) = 5, f (6) = 6, f (7) = 7, f (8) = 8, f (9) = 9, f (10) = 1, f (11) = 11, f (12) = 21$ 。所以 $k$ 最大为 $11$ 。

本题采用捆绑测试

$subtask1(10pts):1≤T,n≤103\text{subtask1(10pts)}:1\leq T,n\leq10^3$ 。
$subtask2(30pts):1≤n≤106\text{subtask2(30pts)}:1\leq n\leq10^6$ 。
$subtask3(40pts):1≤n≤109\text{subtask3(40pts)}:1\leq n\leq10^9$ 。
$subtask4(20pts):\text{subtask4(20pts)}:$ 无特殊限制。

对于 $100%100\%$ 的数据， $1≤T≤105,1≤n≤10181\leq T\leq10^5,1\leq n\leq10^{18}$ 。

提示：unsigned long long 可以储存 $0$ 到 $18,446,744,073,709,551,615(2^{64}-1)$ 的自然数。

C++实现

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
int LEN(LL n) {
	int cnt = 0;
	while (n) cnt++, n /= 10;
	return cnt;	
}
LL f(LL n) {
	LL ans = 0;
	while (n) ans = ans * 10 + (n % 10), n /= 10;
	return ans;
}
void solve(){
	LL n, minn = 9e18;
	scanf("%lld", &n);
	int len = LEN(n);
	for (int i = 0; i <= len; i++)
	{
		LL p = pow(10, (LL)i); //第 i 位加一。 
		LL ni = n - (n % p) + p; //后面的位全部变成 0。 
		if (ni % 10 == 0) ni++;  // 最后一位变成 1。 
		minn = min(minn, f(ni));
	}
	printf("%lld\n", minn - 1);
}
int main(){
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}