秋招日寄|理想笔试【算力平台】通用软件编程题记录

单选题×10；

编程题×2；

编程题1：

你和小明正在玩一个新石子游戏,游戏的规则如下：
有两堆石子,开始时大小分别为α,b,每回合在石子数较多的堆中取走一定倍数(不能为0)的min(a,b),当某方可以把一堆石子取完时便是胜者；

现在你是先手，在两人都采取最优决策的前提下,求出谁是胜者。

输入描述：
第一行个整数t，表示测试样例(1≤t≤10e5)；
接下来行每行两个整数a,b，表示初始时两堆石子的大小(1 ≤a,b ≤ 10e18)；

输出描述：
对于每组测试样例一行输出一个结果，如果是你获胜则输出"you"否则输出"xiaoming"。

示例输入：
3
3 3
3 2
3 1

输出：
you
xiaoming
you

代码：

#include <iostream>
using namespace std;

bool solve(long long a, long long b) {
    if (a < b) swap(a, b);
    if (a % b == 0) return true;
    if (a / b > 1) return true;

    return !solve(b, a % b);
}

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

    while(t--) {
        long long a, b;
        cin >> a >> b;

        if (solve(a, b)) cout << "you" << endl;
        else cout << "xiaoming" << endl;
    }

    return 0;
}

编程题2：

C++题目：你有一个长度为n的a序列，要求你将这个序列分成k个部分。要求：

每一个部分都非空；
部分与部分不能重叠；
每一个部分都是一串连续下标的数；
每一个部分的分数等于这个部分的gcd，整个序列的得分sum为所有部分分数的总和。请你求出最大的序列得分。

输入描述：
第一行包含两个整数，分别是n,k（k≤n≤10e4,1≤k≤50），n表示a序列的大小，k表示这个序列应该要被分成的部分数；
第二行n个整数a，1≤a≤100；

输出描述：
输出一个值sum表示获得的最大得分。

输入：
4 4
1 2 3 4

输出：
10

输入2：
5 3
7 4 5 6 8

输出：
16

代码（一直超时，只通过了60%）：

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

int gcd(int a, int b) {
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    
    for (int i = 0; i < n; i++) cin >> a[i];
    
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, -1e4));
    vector<vector<int>> gcd_cache(n + 1, vector<int>(n + 1, 0));
    
    for (int i = 0; i < n; i++) {
        int current_gcd = a[i];
        for (int j = i; j < n; j++) {
            current_gcd = gcd(current_gcd, a[j]);
            gcd_cache[i][j] = current_gcd;
        }
    }
    
    dp[0][0] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            for (int l = j; l <= i; l++) {
                dp[i][j] = max(dp[i][j], dp[l-1][j-1] + gcd_cache[l-1][i-1]);
            }
        }
    }
    
    cout << dp[n][k] << endl;
    
    return 0;
}