国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

[BZOJ2687]簡單題（dp+bitset優化）

2019-11-11 02:16:50
字體：大 中 小
來源：轉載
供稿：網友

題目描述

傳送門

題解

剛開始想的有問題，因為很多子集和可能為同一個數 f(i)表示和為i的子集一共有多少個，那么每加進一個數x，f(i+x)+=f(i) 這樣的話時間是O((∑ai)2)的，考慮怎么優化 很顯然最終的答案只與f的奇偶有關，那么讓f(i)表示和為i的子集的個數%2的值 轉移就變成了f(i+x)^=f(i) 可以把整個f看成一個二進制數，這樣就是左移一下然后做異或 直接搞成二進制數太大了，用bitset搞一下就行了

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<bitset>using namespace std;#define N 2000005int n,x,sum,ans;bitset <N> f;int main(){ scanf("%d",&n); f[0]=1; for (int i=1;i<=n;++i) { scanf("%d",&x); sum+=x; f^=f<<x; } for (int i=1;i<=sum;++i) if (f[i]) ans^=i;

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板： 恩施市| 漳浦县| 临海市| 佳木斯市| 万安县| 特克斯县| 隆尧县| 濉溪县| 安顺市| 宣化县| 城市| 克拉玛依市| 鹤峰县| 永修县| 中阳县| 东港市| 平遥县| 白银市| 富川| 信阳市| 兴宁市| 来宾市| 漠河县| 曲靖市| 香河县| 厦门市| 沧源| 原平市| 鹿邑县| 保康县| 洱源县| 积石山| 金昌市| 周至县| 库尔勒市| 西吉县| 利川市| 五寨县| 神农架林区| 普陀区| 宜城市|