bitset,动态规划

小红组比赛题目大意每组数据各选一个相加后与目标值MAXSUM相减的绝对值最小思路让所有不超过目标值的s分别与下组的每个数据相加把不超过目标值的s用bitset标记为1在遍历S中遇到可访问的就让这个可访问的s与下一组的每个数据相加直到每组数据都遍历过此时从0-MAXSUM的s有被标记过的dp取Abs中的最小值bitset函数/*dp5005dp;bitset5005 tmp;dp.set(x); // 第x位 1dp.reset(x); // 第x位 0dp.flip(x); // 第x位取反dp[x] // 获取第x位的值0或1dp.count() // 统计一共有多少个1*/#includebits/stdc.h using namespace std; #define int long long #define endl \n void solve() { int n, m; cin n m; vectorvectorintgroup(n); // 读取n组数据每组m个数字 for(int i0;in;i) { for(int j0;jm;j) { int x; cin x; group[i].push_back(x); } } int target; cin target; const int MAXSUM 5000; bitset5005 dp; dp.set(0); for(auto a:group){ bitset5005tmp; //遍历已经存在的总和s /*for(int s0;sMAXSUM;s){ //s存在 if(dp[s]){ //在s的基础上加新一组的每个值 for(auto num:a){ //在不超过目标的情况下加入新的总和 if(snumMAXSUM){ //把这个总和标记为可访问 tmp.set(snum); } } } }*/ for(int num : g) { tmp | dp num; } //在本组数据处理过后把可访问的S赋给dp, //让下一组的每组数据和可访问的s分别相加 dptmp; } int ansINT_MAX; //在所有可访问的s中取得abs中的最小值 for(int s0;sMAXSUM;s){ if(dp[s]){ ansmin(ans,abs(s-target)); } } coutansendl; } signed main() { ios::sync_with_stdio(0);cin.tie(0); solve(); return 0; }简单瞎搞题题目大意n个【l,r】中每个中取出一个数s数的平方问用多少个不同的s思路 用bitsetMAX_SUM 1 dp;下标标记s是否存在在没有取值的时候s0,dp.set(0)下标为0的位置存在之后用存在的s加上每组的【l,r】间的每个数的平方用bitsetMAX_SUM 1 tmp;存这组【l,r】内的新s,把dptmp;(动态规划)dp与s的关系下标0 1 2 3 4 5 6 7 8 ... dp 0 0 0 1 0 0 0 0 0 ...​ dp 4​ 下标0 1 2 3 4 5 6 7 8 …​ val0 0 0 0 0 0 0 1 0 …第 1 轮 i0处理 [1,2]tmp 初始全 0x1v1tmp | dp 1dp1 → 下标 011 置 1tmp{1}x2v4tmp | dp 4dp4 → 下标 044 置 1tmp{1,4}dp tmp✅当前可行平方和(\boldsymbol{{1,4}})第 2 轮 i1处理 [2,3]v4,9tmp 初始全 0x2v4dp 9旧可行 {1,4} → 145448 → {5,8}tmp {5,8}x3v9dp 9旧可行 {1,4} → 19104913 → {10,13}→ tmp{5,8,10,13}dp tmp✅当前可行平方和(\boldsymbol{{5,8,10,13}})#includebits/stdc.h using namespace std; #define int long long #define endl \n const int MAX_SUM 100 * 100 * 100; // 1000000 void solve() { int n; cin n; vectorpairint,int seg(n); for(int i0;in;i) { int l,r; cin l r; seg[i] {l,r}; } vectorbool dp(MAX_SUM 1, false); dp[0] true; for(auto p : seg) { int L p.first, R p.second; vectorbool tmp(MAX_SUM 1, false); for(int s0;sMAX_SUM;s) { if(dp[s]) { for(int x L; x R; x) { int val x * x; if(s val MAX_SUM) tmp[s val] true; } } } dp.swap(tmp); } int ans 0; for(int s0;sMAX_SUM;s) if(dp[s]) ans; cout ans endl; } signed main(){ ios::sync_with_stdio(0);cin.tie(0); solve(); return 0; } #includebits/stdc.h using namespace std; #define int long long #define endl \n const int MAX_SUM 1000000; void solve() { int n; cin n; bitsetMAX_SUM 1 dp; dp.set(0); for(int i0;in;i) { int l,r; cin l r; bitsetMAX_SUM 1 tmp; for(int xl;xr;x) { int v x*x; // | 合并进 tmp自动去重。 // 旧方案全部 v 得到的新可行集合 tmp | dp v; } dp tmp; } cout dp.count() endl; } signed main(){ ios::sync_with_stdio(0);cin.tie(0); solve(); return 0; }