UVa

Luogu

分析

$\text{meet in the middle}$ 。

枚举 $4$ 个数 $a_1,a_2,a_3,a_4$ ,设 $w=a_1+2a_2+3a_3+4a_4$ 。

对于每一种 $w$ 开一个 vector ,记下所有权值为 $w$ 的四元组。

对于当前的 $w$ ,到对应的 vector 中遍历所有四元组,如果两个四元组没有交就说明这八个数可以放在算式里。

设 $cnt_S$ 表示八元组 $S$ 有多少种方法放在算式里。这个在上面那句话时处理出来。

然后只需要枚举所有八元组 $S$ ,设另外八个数组成的八元组为 $T$ ,那么把 $cnt_S\times cnt_T$ 加到答案里去。

这样子会多算一遍,所以最后还要除以二。

代码中四元组、八元组可以用状压实现。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int a[20],b[5];
int cnt[65536];
vector<int> vec[65536];

int main() {
    int _=0;
    while (a[1]=read()) {
        for (re int i=0;i<65536;++i) cnt[i]=0,vec[i].clear();
        for (re int i=2;i<=16;++i) a[i]=read();
        sort(a+1,a+17);
        for (re int S=0;S<65536;++S) {
            if (__builtin_popcount(S)!=4) continue;
            for (re int i=1,t=0;i<=16;++i)
                if (S&(1<<(i-1))) b[++t]=a[i];
            do {
                int w=b[1]+b[2]*2+b[3]*3+b[4]*4;
                for (re int i:vec[w])
                    if ((S&i)==0) ++cnt[i|S];
                vec[w].push_back(S);
            } while (next_permutation(b+1,b+5));
        }
        int ans=0;
        for (re int S=0;S<65536;++S) ans+=cnt[S]*cnt[S^65535];
        printf("Case %d: %d\n",++_,ans>>1);
    }
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 46 PM