09/22快手笔试

第一题

没看懂题目意思，但

 cout << 111 << endl；

AC了，请求各位大老爷们没必要再考我们语文了，没Offer已经够难受了！

第二题，动态规划

题的具体内容不记得了，不相邻元素的最大和？

代码：

#include <bits/stdc++.h>
using namespace std;

int func(const vector<int>& v, vector<int>& indexes) {
    int size = v.size();
    vector<int> dp(size);   // dp[i]表示以位置i处元素结尾的元素所能获取的最大值
    vector<vector<int>> dp_index(size, vector<int>());
    dp[0] = v[0];
    dp_index[0].push_back(0);
    if (v[1] > v[0]) {
        dp_index[1].push_back(1);
        dp[1] = v[1];
	}    
    else {
        dp_index[1] = dp_index[0];
        dp[1] = v[0];
	}

    for (int i = 2; i < size; ++i) {
        if (dp[i - 1] < dp[i - 2] + v[i]) {
            dp_index[i] = dp_index[i - 2];
            dp_index[i].push_back(i);
            dp[i] = dp[i - 2] + v[i];
        }
        else {
            dp_index[i] = dp_index[i - 1];
            dp[i] = dp[i - 1];
        }
    }
    indexes = dp_index[size - 1];
    return dp[size - 1];
}

int main () {
    vector<int> v;
    int n;
    while (cin >> n)
    {
        v.push_back(n);
        if (cin.get() == '\n')  break;
    }

    vector<int> index;
    
    int res = func(v, index);

    for_each(index.begin(), index.end(), [](int x) { cout << x << " "; });

    cout << '\n' << res << endl;

    return 0;
}

第三题，分割等和子集；

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


int main() {
    int n;
    cin >> n;
    vector<int> vec(n);
    int sum = 0;
    int biggest_value = 0;
    for (int i = 0; i < n; ++i) {
        cin >> vec[i];
        sum += vec[i];
        biggest_value = max(biggest_value, vec[i]);
    }


    if (sum % 2 || sum / 2 < biggest_value)    cout << 0 << endl;


    else {
        int target = sum / 2;
        vector<vector<bool>> dp(n, vector<bool>(target + 1));   // 已经给定正整数
        dp[0][vec[0]] = true;
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= target; ++j) {
                if (vec[i] <= j) dp[i][j] = dp[i - 1][j] | dp[i - 1][j - vec[i]];
                else dp[i][j] = dp[i - 1][j]; 
            }
        }


        if (dp[n - 1][target])  cout << 1 << endl;
        else cout << 0 << endl;
    }


    return 0;
}
// 64 位输出请用 printf("%lld")