SPOJ-SUBSET Balanced Cow Subsets

嘟嘟嘟spoj

嘟嘟嘟vjudge

嘟嘟嘟luogu

这个数据范围都能想到是折半搜索。

但具体怎么搜呢？

还得扣着方程模型来想：我们把题中的两个相等的集合分别叫做左边和右边，令序列前一半中放到左边的数为\(a\)，右边的数为\(b\)，后一半同理为\(c\)和\(d\)。则我们要找的就是满足\(a + c = b + d\)的选取方案。

然后变形\(a - b = d - c\)。因此我们只要在前一半枚举\(a, b\)，存起来，然后在后一半枚举\(c, d\)，然后查找\(d - c\)是否出现过。

注意不是每一个数都要选，所以枚举的时候有三种情况：1.不选。2.选到左边。3.选到右边。所以复杂度为\(O(3 ^ {\frac{n}{2}})\)。

还有一点就是状态判重，这个用二进制表示就行。

具体实现就是用\(map\)离散化\(a - b\)，然后因为\(a - b\)可能由好多种选取方案得来的，所以开一个\(vector\)记录每一个\(a - b\)对应的状态。统计答案的时候用一个\(bool\)数组判重即可。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

#include<map>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define rg register

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-8;

const int maxn = 22;

const int maxp = 1.2e6 + 5;

inline ll read()

{

  ll ans = 0;

  char ch = getchar(), last = ' ';

  while(!isdigit(ch)) last = ch, ch = getchar();

  while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();

  if(last == '-') ans = -ans;

  return ans;

}

inline void write(ll x)

{

  if(x < 0) x = -x, putchar('-');

  if(x >= 10) write(x / 10);

  putchar(x % 10 + '0');

}

int n, m;

ll a[maxn];

int cnt = 0;

map<int, int> mp;

vector<int> v[maxp];

bool vis[maxp];

void dfs1(int stp, ll tot, int now)

{

  if(stp > m)

    {

      if(mp.find(tot) == mp.end()) mp[tot] = ++cnt;

      v[mp[tot]].push_back(now); return;

    }

  dfs1(stp + 1, tot, now);

  dfs1(stp + 1, tot + a[stp], now + (1 << (stp - 1)));

  dfs1(stp + 1, tot - a[stp], now + (1 << (stp - 1)));

}

void dfs2(int stp, ll tot, int now)

{

  if(stp > n)

    {

      if(mp.find(tot) == mp.end()) return;

      int id = mp[tot];

      for(int i = 0; i < (int)v[id].size(); ++i) vis[v[id][i] | now] = 1;

      return;

    }

  dfs2(stp + 1, tot, now);

  dfs2(stp + 1, tot + a[stp], now + (1 << (stp - 1)));

  dfs2(stp + 1, tot - a[stp], now + (1 << (stp - 1)));

}

int main()

{

  n = read(); m = n >> 1;

  for(int i = 1; i <= n; ++i) a[i] = read();

  dfs1(1, 0, 0); dfs2(m + 1, 0, 0);

  int ans = 0;

  for(int i = 1; i < maxp; ++i) ans += (int)vis[i];

  write(ans), enter;

  return 0;

}

巴特西

SPOJ-SUBSET Balanced Cow Subsets

最新文章

热门文章