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;
}
上一篇:JQuery EasyUI window 用法


下一篇:第一个程序HelloWorld及常见问题解决和练习