社区讨论
实在找不出错了了
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 条回复,欢迎继续交流。
正在加载回复...