菜鸡求调,全WA
  • 板块P1537 弹珠
  • 楼主神仙酱
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/7/2 21:36
  • 上次更新2024/7/3 08:54:58
查看原帖
菜鸡求调,全WA
22716
神仙酱楼主2024/7/2 21:36
#include <bits/stdc++.h>

using namespace std;
const int N = 6e4 + 10;
bitset<N> f;
bool check(const vector<int>& a) {
    int sum = 0;
    for (int i = 0; i < a.size(); ++i) {
        sum += a[i] * (i + 1);
    }
    if (sum & 1)
        return false;
    sum /= 2;
    f.reset();
    f[0] = true;
    for (int i = 0; i < a.size(); ++i) {
        for (int j = sum; j > i; --j) {
            if (f[j]) continue;
            for (int k = 1; k <= a[i] && j - k * (i + 1) >= 0; ++k) {
                if (f[j - k * (i + 1)]) {
                    f[j] = true;
                    break;
                }
            }
        }
        if (f[sum])
            return true;
    }
    return false;
}
signed main() {
#ifndef ONLINE_JUDGE
    freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
#else
    cin.tie(0)->sync_with_stdio(0);
#endif

    for (int k = 1;; ++k) {
        vector<int> a;
        copy_n(istream_iterator<int>(cin), 6, back_inserter(a));
        if (all_of(a.begin(), a.end(), [](const int v) { return v == 0; }))
            break;
        cout << "Collection #" << k << "\n";
        cout << (check(a) ? "Can" : "Can't") << " be divided.\n\n";
    }
}

2024/7/2 21:36
加载中...