ABC461 枚举|扫描线|动态前缀和|数论|dfs枚举子集

C贪心N个物品每个都有颜色和价值要求选K个物品至少M种颜色使得价值和最大贪心的想先凑齐M种颜色然后剩下的不受颜色的约束挑价值最大的。凑齐M种颜色的过程可以对于每种颜色选出价值最大的然后对于这些物品颜色是互异的选出价值最大的M个。对于这M个标记为已选然后把未标记的拿出来根据价值排序选出最大的K-M个。voidsolve(){intn,m,k;cinnkm;mapint,intmp;vic(n1),v(n1);rep(i,1,n){cinc[i]v[i];if(v[i]v[mp[c[i]]]){mp[c[i]]i;}}vivis(n1);vi a;for(auto[k,v]:mp){a.push_back(v);}sort(a.begin(),a.end(),[](intx,inty){returnv[x]v[y];});intans0;rep(i,0,m-1){ansv[a[i]];vis[a[i]]1;}// coutans\n;vi b;rep(i,1,n){if(!vis[i]){b.push_back(v[i]);}}ranges::sort(b);k-m;while(k--){ansb.back();b.pop_back();}coutans;}D枚举 扫描线 前缀和 时间戳一个矩阵问多少个子矩阵元素和恰好为Kn,m500那么有一个经典的O(n3)O(n^3)O(n3)做法枚举子矩阵的x维度区间[i,j][i,j][i,j]这是O(n2)O(n^2)O(n2)然后看成一个一维数组里面每个元素都是原数组上j−i1j-i1j−i1个元素的和于是问题转化成问一个一维数组多少个区间元素和等于K这可以map维护前缀和计数。然后发现map被卡常了换成静态数组时间戳时间很富裕。voidsolve(){intn,m,K;cinnmK;vvia(n1,vi(m1));inttot0;rep(i,1,n){rep(j,1,m){charc;cinc;a[i][j]c-0;if(a[i][j])tot;}}intans0;vicnt(tot10),t(tot10);inttime0;autoadd[](inti,intv)-void{if(t[i]time){cnt[i];}else{t[i]time;cnt[i]1;}};autoask[](inti)-int{if(t[i]time){returncnt[i];}else{cnt[i]0;t[i]time;return0;}};rep(i,1,n){vicur(m1);rep(j,i,n){add(0,1);intpre0;rep(k,1,m){cur[k]a[j][k];precur[k];if(preK)ansask(pre-K);add(pre,1);}time;}}coutans;}E思维 数据结构n*n的网格上q1e5次操作每次染黑一行或者染白一列。n1e5问每一步操作后的黑色格子数暴力计算黑色不可行考虑每一次操作对黑色格子的改变量。对于染黑一行如果这是这一行第一次染黑增加n个黑色如果之前已经染黑了这次能染黑的只有在上次染黑到这次之间被染白的位置。于是计算从上次染黑到这次之间染白一列的操作次数。注意多次染白同一列也只计算一次所以实际要求的是上次染黑到现在的不同列染白次数。对于染白一列类似但有不同。如果之前染白过这一列这次能染白的就是上次染白到现在中间染黑的不同行的个数。如果之前没染白过这次能染白的就是从最开始到现在染黑的不同行数。这里需要维护每一行最后一次染黑的时间每一列最后一次染白的时间。这静态数组维护即可。然后还要求一个时间段内染黑的不同行数染白的不同列数。如果不考虑去重前缀和就可以。考虑去重不能让同一行产生多次贡献每次操作一行除了增加这一次的贡献还要取消这一行之前的贡献也就是让一行的贡献始终不超过1想实现这点考虑把前缀和换成树状数组树状数组可以看成一个动态前缀和不仅支持增加还支持删除。横轴是操作的时间每次对于染黑一行假设当前时间t,上一次操作这一行的时间是pre执行add(t,1),add(pre,-1)。查询的用法和前缀和一样直接查区间和。voidsolve(){intn,q;cinnq;viprex(n1),prey(n1);FenwickTreetx(q10),ty(q10);intans0;rep(i,1,q){intop,x;cinopx;if(op1){if(prex[x]0){ansn;}else{ansty.rangeQuery(prex[x]1,i);}if(prex[x])tx.update(prex[x],-1);tx.update(i,1);prex[x]i;}else{if(prey[x]0){ans-tx.query(i);}else{ans-tx.rangeQuery(prey[x]1,i);}if(prey[x])ty.update(prey[x],-1);ty.update(i,1);prey[x]i;}coutans\n;}}F数论 枚举/记忆化搜索对于N1e10一个分拆序列是找到一个不含重复元素的序列乘起来等于N。现在要计算所有分拆序列的元素和。注意这是序列也就是相同元素不同排列视为不同方案。对于1乘上不影响结果企鹅最多出现一次可以单独处理。假设当前一个分拆方案有cnt个数和为sum那么不加入1是一类方案答案是(cnt)!乘sum也就是这些元素的全排列加入1是另一类(cnt1)!×(sum1)也就是加入1之后再全排列。接下来不考虑1只要能求出所有组合方案的(cnt,sum)就可以计算答案了。这会很多吗注意到由于(14)!1e10N1e10的不同质因子个数不会超过14考虑到相同质因子也是O(log⁡N)O(\log N)O(logN)量级的。拆成一个序列等价于把这个质因子集合拆成若干个互不相交的子集这是经典的贝尔数问题B(14)左右的贝尔数不会太大这里实际的肯定会多一点因为14是对于不同质因子来说的一个质因子可能出现多次。但是从另一方面讲也不会那么多因为不能包含相同元素也就是有一些分拆子集会产生相同元素大胆guess一下还是可以通过。尝试做一些剪枝。首先暴力O(n)O(\sqrt n)O(n​)的到所有因子然后dfs枚举这个因子集合的一个子集记录子集大小cnt,元素和sum并且维护当前剩余待拆分的乘积边界是剩余乘积为1那么根据前面的讨论计算加不加入1对答案的贡献。每一层接下来要选的枚举因子必须能整除剩余乘积才行。枚举时一个经典优化是记录当前考虑了前idx个元素只枚举idx往后的每个因子选不选。直接这样还是超时加点剪枝把因子升序排序递归枚举到因子x如果x×xcurx×xcurx×xcur了由于后面都是更大的因子不可能选出一个yx∗ycurx*ycurx∗ycur了而cur还没等于1没到边界还需要一个因子那么这个因子只能是x了后面更大因子不用枚举了。voidsolve(){intn;cinn;vi f;for(inti2;i*in;i){if(n%i0){f.push_back(i);if(i*i!n){f.push_back(n/i);}}}f.push_back(n);intmf.size();ranges::sort(f);vip(m10);p[0]1;rep(i,1,m5){p[i]p[i-1]*i%M2;}intans0;autodfs[](autodfs,inti,intcur,intcnt,intsum)-void{if(cur1){ans(anssum*p[cnt]%M2)%M2;ans(ans(sum1)*p[cnt1]%M2)%M2;return;}rep(j,i,m-1){if(f[j]cur){break;}if(f[j]*f[j]cur){dfs(dfs,j1,1,cnt1,sumcur);break;}if(cur%f[j]0){dfs(dfs,j1,cur/f[j],cnt1,sumf[j]);}}};dfs(dfs,0,n,0,0);coutans;}