SSL 2669_选数_模拟+搜索

发布于 2017-08-08  857 次阅读


题目描述

给出n个数a[i],现在可以在其中任意选出若干个数,问有多少种选择方案,使得这几个数可以分成两个和相等的集合。


思路

将这个序列分为两份进行处理,对于每一个数我们可以在其前面加上系数[-1,0,1],来表示它是放在左集合/右集合或是不选

首先可以通过搜索得出所有的状态,然后我们就可以用指针在两段里面分别进行查找,如果相加等于0,那么就是一个符合的方案

然后显然会有重复的情况,我们可以用一个十进制数来表示每一个状态,然后相加时也用左边的进行左移然后加上右边的进行判重即可


#include 
#include 
using namespace std;
int a[21], n, ll = 0, rr = 0, totl, totr;
struct arr
{
    int x, w;
}l[70000];
arr r[70000];
bool fl[20000000];
int cmp(arr a, arr b)
{
    return a.x < b.x;
}
int dfs(int dep, int end, int tot, int o, int m)
{
    if (dep > end) 
    {
        if (o == 1) 
        {
            if (m == 0) return 0;
            l[++ll].x = tot;
            l[ll].w = m;
            return 0;
        }
        else
        {
            if (m == 0) return 0;
            r[++rr].x = tot;
            r[rr].w = m;
            return 0;
        }
        return 0;
    }
    dfs(dep + 1, end, tot + a[dep], o, m * 2 + 1);
    dfs(dep + 1, end, tot - a[dep], o, m * 2 + 1);
    dfs(dep + 1, end, tot, o, m * 2);
}
int main()
{
//    freopen("number.in", "r", stdin);
//    freopen("number.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
        
    dfs(1, n / 2, 0, 1, 0);
    dfs(n / 2 + 1, n, 0, 2, 0);
    int ans = 0;
    sort(l + 1, l + ll + 1, cmp);
    sort(r + 1, r + rr + 1, cmp);
    int j = rr;
    for (int i = 1; i <= ll; i++)
    {
        while (l[i].x + r[j].x > 0 && j > 0) j--;
        int k = 0;
        int jj = j;
        while (l[i].x + r[j].x == 0 && j > 0)
        {
            if (!fl[(l[i].w << (n / 2 + 1)) + r[j].w])
                fl[(l[i].w << (n / 2 + 1)) + r[j].w] = 1;
            else k++;
            j--;
        }
        ans += (jj - j) - k;
        j = jj;
    }
    for (int i = 1; i <= ll; i++)
        if (l[i].x == 0 && !fl[l[i].w << (n / 2 + 1)])
        {
            ans++;
            fl[l[i].w << (n / 2 + 1)] = 1;
        }
    for (int i = 1; i <= rr; i++)
        if (r[i].x == 0 && !fl[r[i].w])
        {
            ans++;
            fl[r[i].w] = 1;
        }
    printf("%d\n", ans);
}

 

]]>