题解：UVA701 The Archeologists' Dilemma

AK_lwh_888 · 2024-10-11 21:35:33 · 题解

我开始看一眼这道题，这不得用暴力吗？于是我用暴力做了出来。

做的时候有两个重要的点。

check

check 的大致功能如下：可以判断后一个数是否是前一个数的前缀。我们首先要把数字转字符串，得用到一个函数 to_string() 函数，功能说了，就是将数字转换成为字符串。转换后我们还不可以直接判断前缀，因为题目说了一句话：

且 N 的位数小于 2^e 的一半。

所以我们还要加上一个判断：

int w=0;
if(s.size()%2==1)w=1;
if(s.size()/2+w<=s1.size())return false;

做完这个后就可以判断后一个数是否前一个数的前缀了，代码如下：

for(int i=0;i<s1.size();++i){
    if(s[i]!=s1[i])return false;
}
return true;

这样一个 check 函数就好了。

bool check(int x,int n){
    string s=to_string(x);
    string s1=to_string(n);
    int w=0;
    if(s.size()%2==1)w=1;
    if(s.size()/2+w<=s1.size())return false;
    for(int i=0;i<s1.size();++i){
        if(s[i]!=s1[i])return false;
    }
    return true;
}

pow

这个函数的功能是用来计算 2^e 的，这个就很简单了，我们只要将 sum 数值设为 1，循环 e 次，每次 sum*=2; 就可以了，最后 return sum; 一个 pow 就做好了。

代码如下：

int pow_my(int m){
    int sum=1;
    for(int i=1;i<=m;++i){
        sum*=2;
    }
    return sum;
}

知道这些后就已经可以写完了。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long 
bool check(int x,int n){
    string s=to_string(x);
    string s1=to_string(n);
    int w=0;
    if(s.size()%2==1)w=1;
    if(s.size()/2+w<=s1.size())return false;
    for(int i=0;i<s1.size();++i){
        if(s[i]!=s1[i])return false;
    }
    return true;
}
int pow_my(int m){
    int sum=1;
    for(int i=1;i<=m;++i){
        sum*=2;
    }
    return sum;
}
signed main(){
    int n;
    while(cin>>n){
        int i;
        for(i=1;!check(pow_my(i),n);++i){

        }
        cout<<i<<"\n";
    }
    return 0;
}