题解：UVA701 The Archeologists' Dilemma

AFO_Lzx · 2024-10-16 21:40:08 · 题解

题目传送门

\texttt{Description}

给定一个整数 n，输出一个最小的正整数 x 使得 2^x 以 n 作为开头，且有 \vert n \vert < 2^{x-1} 的限制。

\texttt{Solution}

暴力好题，直接枚举就行，时间复杂度很低，当然我们也可以继续用二分答案优化，不过没有太大的必要。

如果没有满足要求的整数，直接输出 no power of 2 这句话就行。

我们可以用下面的检查函数来检查 2^e 是否合法。

bool f(int x, int n) {
    string s1 = to_string(x);
    string s2 = to_string(n);

    int pos = 0;
    if (s1.size() / 2 + s1.size() % 2 <= s2.size()) return 0;
    for (auto c : s2) if (s1[pos++] != c) return 0;
    return 1;
}

然后我们就直接循环枚举，由于 63 是最大答案的范围，再大就会数据溢出，所以我们如果找到 63 还没有答案，那么就是没有答案，按照题目要求输出。

另外附上难度建议：红题或者橙题。

本题有多组数据，不过不用输入数据组数。

\texttt{Code}

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n;
bool f(int x, int n) {
    string s1 = to_string(x);
    string s2 = to_string(n);

    int pos = 0;
    if (s1.size() / 2 + s1.size() % 2 <= s2.size()) return 0; // 判断长度
    for (auto c : s2) if (s1[pos++] != c) return 0; // 判断前缀
    return 1; // 符合条件
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    while (cin >> n) {
        int ans = 1;
        while (ans <= 63 && f((1 << ans), n) == 0) ans++;
        // 1 << ans 就是 2 ^ ans

        if (ans == 64) { // 没有答案
            cout << "no power of 2\n";
            continue;
        }

        cout << ans << "\n";
    }

    return 0;
}