米哈游笔试2023.4.15

第一题：

思路先转换成3进制，再从低位到高位，利用公式2*3^k=-3^k+3^(k+1)依次将不符合的2转换为-1，然后顺延到高位，刷新，代码有注释。

#include <iostream>
#include <vector>
#include <unistd.h>
#include <fcntl.h>

using namespace std;

long long three[20];//存储3^i打印用

int main(){
    int x;
    cin>>x;

    three[0]=1;
    for(int i=1;i<=20;++i){
        three[i] = three[i-1]*3;
    }

//计算3^i存入three备用
    vector<long long> nums;
    while(x){
        nums.emplace_back(x%3);
        x/=3;
    }

//3进制 & 刷新
    int len = nums.size();
    nums.emplace_back(0);//延长一位
    for(int i=0;i<len;++i){
        //如果超过2或者小于-2继续进位，当前位nums[i]限定到[-2,2]内
        nums[i+1] += nums[i]/3;
        if(nums[i]==-2){
            --nums[i+1];
            nums[i] = 1;
        }else if(nums[i]==2){
            ++nums[i+1];
            nums[i] = -1;
        }
    }

//打印    
    int flag=0;
    for(int i=len;i>=0;--i){
        if(nums[i]>0){
            if(flag==0){
                flag=1;
                cout<<three[i];//第一个不加正号
            }else{
                cout<<"+"<<three[i];
            }
        }else if(nums[i]<0){
            cout<<"-"<<three[i];
        }
    }

    return 0;
}

第二题：

思路：只要确定了an-1项的范围(min,max)，就可以得到种类=max-min-1。

#include <iostream>
#include <vector>
#include <unistd.h>
#include <fcntl.h>

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<long long> bn(n-1);
    vector<long long> bntmp(n,0);//包含末尾0
    for(int i=0;i<n-1;++i){
        cin>>bn[i];
    }
    
    for(int i=n-2;i>=0;--i){
            bntmp[i] = bn[i]-bntmp[i+1];
    }
    int flag=0;
    long long maxn_1=0;
    long long minn_2=INT64_MAX;
    for(int i=n-1;i>=0;--i){
        if(flag==0){
            maxn_1 = max(maxn_1,-bntmp[i]);
        }else{
            minn_2 = min(minn_2,bntmp[i]);
        }
        flag=~flag;
    }
    
    long long res = minn_2-maxn_1-1;
    if(res<=0){
        cout<<0;
    }else{
        cout<<res;
    }
    return 0;
}

第三题：

思路：组合数，具体见草稿例子

#include <iostream>
#include <vector>
#include <unistd.h>
#include <fcntl.h>
#include <unordered_map>

using namespace std;
constexpr int MOD = 1e9+7;

unordered_map<int,int> mp;

long long Cnk(int n,int k){
    long long res=1;
    k=min(k,n-k);
    for(int i=1;i<=k;++i){
        res = res*n/i;
        res = res%MOD;
        --n;
    }
    return res;
}

int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;++i){
        int tmp;
        cin>>tmp;
        ++mp[tmp];
    }
    vector<int> valid;
    for(auto m:mp){
        if(m.second>=k){
            valid.emplace_back(m.second);
        }
    }
    int kind = valid.size();//记录数量>=k的数字种类
    long long res=1;
    for(int i=0;i<kind;++i){
        long long tmp=1;
        for(int kk=k;kk<=valid[i];kk+=k){
            tmp += Cnk(valid[i],kk);
        }
        res *= tmp;
        res %= MOD;
    }
    //删掉全不选的情况
    res-=1;
    cout<<res;
    return 0;
}