归约做成了没有

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

一次归约算不算做成，验三件事：答案对、没写新算法（can_split 的源码里没有 for）、两者同时成立。输出如 过/过/过。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 有些情况根本不用跑一个解法三个问题 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

#include <numeric>

bool subset_sum(const vector<int>& arr, int target) {   // 老朋友：能不能挑出子集，和正好是 target
    if (target < 0) return false;
    vector<bool> reach(target + 1, false);
    reach[0] = true;
    for (int x : arr) {
        for (int r = target; r >= x; r--) {
            if (reach[r - x]) reach[r] = true;
        }
    }
    return reach[target];
}

const vector<int> NO = {17, 24, 15, 13, 23};
const vector<int> YES = {10, 20, 15, 5};
const vector<int> ODD = {17, 24, 15, 13, 23, 3};

bool can_split(const vector<int>& arr) {
    int s = accumulate(arr.begin(), arr.end(), 0);
    if (s % 2 == 1) return false;
    return subset_sum(arr, s / 2);
}

int main() {
    bool c1 = (can_split(NO) == false && can_split(YES) == true);   // 答案对
    string SRC = "int s = accumulate(arr.begin(), arr.end(), 0); if (s % 2 == 1) return false; return subset_sum(arr, s / 2);";
    // TODO: c2——SRC 里找不到 "for"（用 SRC.find("for") == string::npos 判）
    bool c2 = false;
    // TODO: c3——前两条同时成立
    bool c3 = false;
    cout << (c1 ? "过" : "不过") << "/" << (c2 ? "过" : "不过") << "/" << (c3 ? "过" : "不过") << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

归约做成了没有

更多题目

全部评论