寒假训练赛G_牛客博客

题目链接 https://ac.nowcoder.com/acm/contest/50309/G
思路:对于此类问题，可以归纳为：对于使用天平x次，我们可以在 ${3^x-3 \over 2}$ 个球中找到一个重量不一样的球，并且说出这个球相对于标准球是重了还是轻了。如果仅要求找出问题球，那么 ${3^x-1 \over 2}$ 个球即可，所以这道题可以对于输入的球的总数x和使用天平次数y，求出对于y次使用天平求出最大能辨别球的上限K，假若K>=x，即能实现，否则就不能实现

值得一提的是这道题x和y的范围都是一百万，求一次 $3^{y}$ 远远超出了精度范围因此很自然的想到高精度，没错，我也是这么想的，直接上板子
注意特判n==2的时候，当n等于2时，我们不知道哪一个是标准球，因此无法判断谁重谁轻

//减法
vector<int> sub(vector<int> &A,vector<int> &B){
    vector<int>C;
    int t=0;//t表示借位
    for(int i=0;i<A.size();i++){
        t=A[i]-t;
        if(i<B.size()) t=t-B[i];//判断B有没有这一位
        C.push_back((t+10)%10);//注意这儿(t+10)%10，包含着两种情况，第一种t小于0，第二种t大于0
        if(t<0)//假如借了一位，下次就要减去
            t=1;
        else 
            t=0;
    }
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}
//乘法
vector<int> mul(vector<int> &A, int b){
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ ){
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
//除法
vector<int> div(vector<int> &A,int b){
    vector<int>C;
    int r=0;
    for(int i=A.size()-1;i>=0;i--){
        r=r*10+A[i];
        C.push_back(r/b);
        r=r%b;
    }
    reverse(C.begin(),C.end());
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}

对于这种高精题目，会用java和python的最好，用c/c++写起来真的很蛋疼
好了，有了板子，我们可以来处理输入输出的问题我们的先把数据存进vector里面，最后比较的时候搞一个vector的比较函数即可

//比较函数
bool cmp(vector<int>A,vector<int>B){
    if(A.size()!=B.size())
        return A.size()>B.size();
    for(int i=A.size()-1;i>=0;i--)
        if(A[i]!=B[i])
            return A[i]>B[i];
    return true;
}

最后完整code:

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
#define debug cout<<"--------"<<endl;

vector<int> mul(vector<int> &A, int b){
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ ){
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

vector<int> div(vector<int> &A,int b){
    vector<int>C;
    int r=0;
    for(int i=A.size()-1;i>=0;i--){
        r=r*10+A[i];
        C.push_back(r/b);
        r=r%b;
    }
    reverse(C.begin(),C.end());
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}

vector<int> sub(vector<int> &A,vector<int> &B){
    vector<int>C;
    int t=0;//t表示借位
    for(int i=0;i<A.size();i++){
        t=A[i]-t;
        if(i<B.size()) t=t-B[i];//判断B有没有这一位
        C.push_back((t+10)%10);//注意这儿(t+10)%10，包含着两种情况，第一种t小于0，第二种t大于0
        if(t<0)//假如借了一位，下次就要减去
            t=1;
        else 
            t=0;
    }
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}

bool cmp(vector<int>A,vector<int>B){
    if(A.size()!=B.size())
        return A.size()>B.size();
    for(int i=A.size()-1;i>=0;i--)
        if(A[i]!=B[i])
            return A[i]>B[i];
    return true;
}

int n,m;
int main(){
    while(cin>>n>>m){
        if(n==2){
            puts("No");
            continue;
        }
        vector<int>ans,data,two;
        int x=n;
        while(x){
            data.push_back(x%10);
            x=x/10;
        }
        bool f=false;
        ans.push_back(3);
        two.push_back(3);
        for(int i=1;i<m;i++){
            ans=mul(ans,3);
            auto tmp=sub(ans,two);
            auto res=div(tmp,2);
           if(cmp(res,data)) {
               puts("Yes");
               f=true;
               break;
           }
        }
        if(!f)
        puts("No");
    }
    return 0;
}

----------------------------------------------------华丽的分界线-----------------------------------------------------
事实上这道题并不需要写蛋疼的高精，我们发现最后只需要判断Yes或者No就行，很明显x的最大值才一百万，所以我们算的时候发现大于一百万的时候就已经可以下结论了(悲，赛中没想到，跑去写高精，淦
Code:

  //真短
#include<iostream>
using namespace std;
int main(){
    int x,y;
  while(cin>>x>>y){
  	 if(x==2) {
	  	cout<<"No"<<endl;
	     continue;
  	 }   
  	long long k=3;
  	  int j=1;
  	 for(j=2;j<=15;j++){
	 	k=k*3;
	 	if((k-3)/2>=x) break;
	 }
  	if(j<=y) cout<<"Yes"<<endl;
  	else cout<<"No"<<endl;
  }
  return 0;
}