社区讨论

实在找不出错了了

P3067[USACO12OPEN] Balanced Cow Subsets G参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lvdzn2uu
此快照首次捕获于
2024/04/24 23:47
2 年前
此快照最后确认于
2024/04/24 23:49
2 年前
查看原帖
CPP
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ma make_pair
#define int long long
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define fup(x, l, r) for (int x = (l), eNd = (r); x <= eNd; ++ x )
#define fdw(x, r, l) for (int x = (r), eNd = (l); x >= eNd; -- x )
typedef long long ll;
typedef unsigned long long LL;
typedef pair<int, int> PII;

struct fastread {
    template <typename T>
    fastread& operator >>(T& x) {
        x = 0; bool flg = false; char c = getchar();
        while (c < '0' || c > '9') flg |= (c == '-'), c = getchar();
        while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
        if (flg) x = -x; return *this;
    }
    template <typename T>
    fastread& operator >>(vector<T>& x) {
        for (auto it = x.begin(); it != x.end(); ++ it ) (*this) >> *it;
        return *this;
    }
}fin;

struct fastwrite {
    template <typename T>
    fastwrite& operator <<(T x) {
        if (x < 0) x = -x, putchar('-');
        static int buf[35]; int top = 0;
        do buf[top ++ ] = x % 10, x /= 10; while (x);
        while (top) putchar(buf[ -- top] + '0');
        return *this;
    }
    fastwrite& operator <<(char x) {
        putchar(x); return *this;
    }
    template <typename T>
    fastwrite& operator <<(vector<T> x) {
        for (auto it = x.begin(); it != x.end(); ++ it ) (*this) << *it, putchar(' ');
        putchar('\n');
        return *this;
    }
}fout;

const int N = 2e5 + 10;
const int mod = 998244353;

int n, a[23];
vector < int > g[N];
int mid;
int ans[N];
int id;
map< int, int  > mp;
void dfs1(int x, int sum, int now)
{
    if(x > (n >> 1))  
    {
        if(!mp.count(sum))
        {
            mp[sum] = ++id;
            //fout << mp[sum] << ' ';
        }
        g[mp[sum]].eb(now);
        //fout << g[mp[sum]][now] << ' ';
        return ;
    }  
    dfs1(x + 1, sum, now | (1 << (x - 1)));
    dfs1(x + 1, sum + a[x], now | (1 << (x - 1)));
    dfs1(x + 1, sum - a[x], now | (1 << (x - 1)));
}
void dfs2(int x, int sum, int i)
{
    if(x > n)
    {
        if(mp.count(sum))
        {
            int w = mp[sum];
            for (auto e : g[w])
            {
                //fout << e << ' ';
                ans[(e | i)] = 1;
            }
        }
        return ;
    }
    dfs2(x + 1, sum, i | (1 << (x - 1)));
    dfs2(x + 1, sum + a[x], i | (1 << (x - 1)));
    dfs2(x + 1, sum - a[x], i | (1 << (x - 1)));
}

signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fin >> n;
    fup(i, 1, n)    fin >> a[i];
    mid = n >> 1;
    dfs1(1, 0, 0);
    dfs2(mid + 1, 0, 0);
    int res = 0;
    fup(i, 1, (1 << n)) res += ans[i];
    fout << res << '\n';
    return 0;
}



回复

0 条回复,欢迎继续交流。

正在加载回复...