蓝桥杯第一场强者挑战赛（C）SOSdp

本文主要是介绍蓝桥杯第一场强者挑战赛（C）SOSdp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

之前在cf上面接触过SOSdp（子集dp），这里就碰到了。

      

思路： 异或运算即非进位加法运算，因此如果需要进位的话，那么就无法满足题意，因此条件弱化为不需要进位，也就是不存在同一位上面都是1。也就是说，对于而言，中为1的地方，其他数不能为1，也就是说其对答案的贡献为的子集的个数。

        

#include <iostream>
using namespace std;
// SOS dp
int dp[(1 << 21)];
#define int long long
const int N = 21;
signed main()
{int n;cin >> n;int a[n];for(int i = 0 ; i <n ; i ++){cin >> a[i];dp[a[i]]++;}    int ans = 0;for(int i = 0;i < N; ++i) {for(int mask = 0; mask < (1 << N); mask++){if(mask & (1 << i))dp[mask] += dp[mask^(1 << i)];}}for(int i = 0 ; i < n ; i ++){ans += dp[(1 << N) - 1 - a[i]];}cout << ans;return 0;
}

这篇关于蓝桥杯第一场强者挑战赛（C）SOSdp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---