20220721 蔚来笔试三道编程题（附题解）

恭喜发现宝藏！微信搜索公众号【TechGuide】回复公司名，关注更多新鲜好文和互联网大厂的笔经面经。
作者@TechGuide【全网同名】
点赞再看，养成习惯，您动动手指对原创作者意义非凡欄

小A和小B创造了一个叫添数博弈的游戏，游戏规则如下:
首先在数池中添加两个整数xy，接下来，两个人轮流开始添数;添数的规则是在数池中任意选择两个数x，y，令m=x-y，若m不在数池中，则将m添加到数池中;若m已经在数池中，则游戏结束。
假设小A先选数，两人轮流操作添数，若有一方不能无法添数时，则该人就输了。

输入的第一行给出测试用例的数量T(1 输出描述:

对于每一个测试样例，输出获胜方的名字

时间限制:C/C++1秒，其他语言2秒
空间限制:C/C++262144K，其他语言524288K

#include 
using namespace std;
int getNum(int x,int y){
    int z = y;
    while(x%y){
        z = x%y;
        x = y;
        y = z;
    }
    return z;
}
// 关注TechGuide 实时题库 闪电速递
int main(){
    int n;
    int x,y;
    for(int i=0;i
        cin>>x>>y;
        int maxNum = max(x,y);
        int minNum=min(x,y);
        if((maxNum/getNum(maxNum,minNum))%2==0){
            cout<<"B"<
            cout<<"A"< 
第二题：作弊能得到的最大得分 
题目描述 
有一个网站叫做NowCoder，他的比赛机制非常有趣。当你参加一场比赛时，会根据你当前的 rating和排名来确定你的rating变化程度(正值代表rating增加，负值代表rating下降，0代表rating不变)。我们不关心他的具体计算函数，我们把一个连续的n场比赛抽象成三个数列
 {an}，{bn}{cn}。如果以你当前的实力参加第场比赛，那么你会得到ai的rating变化程度。如果你在这场比赛中作弊，那么你会得到6的rating变化程度，由于每场比赛难度不同，你在其中作弊的风险也不同。具体来说，如果你在第场比赛作弊，需要承担{cl的作弊风险。为了使得自己不被发现，你的总作弊风险不能超过k。假定你的初始rating为1500，请你找出一种参赛方式，使得结束后rating最高。
 
Note:rating可以出现负数，每场比赛都必须参加。
 
输入描述: 
第一行两个正整数n，k(1 接下来一行n个整数，表示{an}，-109 接下来一行个整数，表示{bn}，-109 接下来一行n个整数，表示{cn1 
输出描述: 
一行一个整数，代表结束后最高的rating值是多少。
 
#include 
#include 
#include 
#include 
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	vector> num;
	int x, y, z;
	vectora(n);
	vectorb(n);
	vectorc(n);
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		ans += a[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> b[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> c[i];
	}
	for (int i = 0; i < n; ++i) {
		num.push_back({ a[i],b[i]-a[i],c[i] });
	}
	// 关注TechGuide 实时题库 闪电速递
	sort(num.begin(), num.end(), [&](tuple& a, tuple& b)
		{
			return get<1>(a) > get<1>(b);
		}
	);
	a.clear();
	a.resize(k+1,0);
	for (int i = 0; i < n; ++i) {
		for (int j = k; j >= get<2>(num[i]); --j) {
			
			a[j] = max(a[j], a[j - get<2>(num[i])]+get<1>(num[i]));
		}
	}
	int res = a[k] +1500+ans;
	cout << res;
	return 0;
}
 
第三题：排列 
题目描述 
给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且拥有小于 k 个逆序对的不同的数组的个数。
 
逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a[i] > a[j]，则其为一个逆序对；否则不是。
 
 
 
参考力扣629，区别是需要累加1~k的数组和，即k次调用下面方法
 
 
代码 
Java版本 
class Solution {
    public int kInversePairs(int n, int k) {
        final int MOD = 1000000007;
        int[][] f = new int[2][k + 1];
        f[0][0] = 1;
        // 关注TechGuide 实时题库 闪电速递
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                int cur = i & 1, prev = cur ^ 1;
                f[cur][j] = (j - 1 >= 0 ? f[cur][j - 1] : 0) - (j - i >= 0 ? f[prev][j - i] : 0) + f[prev][j];
                if (f[cur][j] >= MOD) {
                    f[cur][j] -= MOD;
                } else if (f[cur][j] < 0) {
                    f[cur][j] += MOD;
                }
            }
        }
        return f[n & 1][k];
    }
}
 
CPP版本 
class Solution {
private:
    static constexpr int mod = 1000000007;

public:
	// 关注TechGuide 实时题库 闪电速递
    int kInversePairs(int n, int k) {
        vector> f(2, vector(k + 1));
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                int cur = i & 1, prev = cur ^ 1;
                f[cur][j] = (j - 1 >= 0 ? f[cur][j - 1] : 0) - (j - i >= 0 ? f[prev][j - i] : 0) + f[prev][j];
                if (f[cur][j] >= mod) {
                    f[cur][j] -= mod;
                }
                else if (f[cur][j] < 0) {
                    f[cur][j] += mod;
                }
            }
        }
        return f[n & 1][k];
    }
};