本次机试共4题，不直接将分数计入成绩，仅在面试时用于参考。

A. 平衡三进制II

代码：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> h10Toh3(int x){
    vector<int> res;
    while(x!=0){
        res.push_back(x%3);
        x=x/3;
    }
    return res;
}

int Count3n(int x){
    int count=0;
    while(x!=1){
        count++;
        x=x/3;
    }
    return count;
}

int main(){
    int a,b;
    cin>>a>>b;

    int count= Count3n(b);
    vector<int> res= h10Toh3(a);

    int ci=0;
    for(int i=0;i<res.size();i++){
        int t=res[i];
        res[i]=(t+1+ci)%3;
        ci=(t+1+ci)/3;
    }
    if(ci!=0) res.push_back(ci+1);

    for(int i=0;i<res.size();i++){
        if(res[i]-1==-1) res[i]=2;
        else res[i]=res[i]-1;
    }

    reverse(res.begin(),res.end());
    int pos=0;
    while(res[pos]==0) pos++;
    res.erase(res.begin(),res.begin()+pos);

    for(int i=0;i<res.size()-count;i++) cout<<res[i];
    if(count!=0){
        cout<<".";
        int pos2=res.size()-1;
        while(res[pos2]==0) pos2--;
        for(int i=res.size()-count;i<=pos2;i++)
            cout<<res[i];

    }
}

上述代码只能实现70%的数据，A为负数的部分短时间想不出。

C. 子序列

代码：

类似背包问题，动态规划的思想写的，但是数组开不到题目要求那么大……

#include <iostream>

using namespace std;

const int MAXN=10001;
int a[MAXN];
int dp[MAXN][MAXN];

int main(){
    int n,s,a1,b;
    cin>>n>>s>>a1>>b;
    for(int i=1;i<=n;i++){
        if(i==1) a[i]=a1;
        else a[i]=(a[i-1]*b)%1000000007;
    }

    for(int i=0;i<=n;i++)
        for(int j=0;j<=s;j++){
            if(j==0) dp[i][j]=0;
            else dp[i][j]=-1;
        }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=s;j++){
            if(j-a[i]<=0) dp[i][j]=1;
            else if(dp[i-1][j]!=-1 && dp[i-1][j-a[i]]!=-1)
                dp[i][j]=min(dp[i-1][j],dp[i-1][j-a[i]]+1);
            else if(dp[i-1][j]!=-1 && dp[i-1][j-a[i]]==-1)
                dp[i][j]=dp[i-1][j];
            else if(dp[i-1][j]==-1 && dp[i-1][j-a[i]]!=-1)
                dp[i][j]=dp[i-1][j-a[i]]+1;
        }
    }

    /*for(int i=0;i<=n;i++){
        for(int j=0;j<=s;j++)
            cout<<dp[i][j]<<" ";
        cout<<endl;
    }*/

    cout<<dp[n][s]<<endl;
    
}

不好做，不想写啦TAT