[CF1442D] Sum
由于序列单增，所以最后至多有一个数组不被选满。
证明简单，假设有两个数组 \(x\)，\(y\) 分别选到第 \(i\) 和 \(j\) 项并没有选满。
如果 \(x_{i+1}\leq y_{j+1}\)，那么有 \(x_{i}\leq y_{j+1}\)，将 \(x_{i}\) 替换为 \(y_{j+1}\) 显然不劣。
然后只需要知道去掉每个位置后的背包，枚举当前位置选多少个就行了。
套路地进行分治，即将 \([l,mid]\) 丢进背包后递归 \((mid,r]\)，另一边同理。
这样递归到叶子就是去掉当前位置的背包了，在叶子统计答案即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3005,INF=0x3f3f3f3f3f3f3f3f;
vector<int> v[N];
int n,k,ans=-INF,t[N],dp[N],sum[N];
void solve(int l,int r){int mid=(l+r)>>1,now=0;if(l==r){for(int i=1;i<=min(k,t[l]);i++)ans=max(ans,(now+=v[l][i])+dp[k-i]);return ans=max(ans,dp[k]),void();}vector<int> tmp(dp,dp+k+1);for(int i=l;i<=mid;i++)for(int j=k;j>=t[i];j--)dp[j]=max(dp[j],dp[j-t[i]]+sum[i]);solve(mid+1,r),copy(tmp.begin(),tmp.end(),dp);for(int i=mid+1;i<=r;i++)for(int j=k;j>=t[i];j--)dp[j]=max(dp[j],dp[j-t[i]]+sum[i]);solve(l,mid),copy(tmp.begin(),tmp.end(),dp);
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin>>n>>k,fill(dp+1,dp+k+1,-INF);for(int i=1;i<=n;i++){cin>>t[i],v[i].resize(t[i]+1,0);for(int j=1;j<=t[i];j++)cin>>v[i][j],sum[i]+=v[i][j];}solve(1,n),cout<<ans<<"\n";
}
[Luogu P13552] 鱼类考古学
先观察数据范围，\(10^6\) 还是位运算题目，大致得出复杂度在 \(O(n\log V)\) 左右。
但是拆位后，如果先加后按位与，答案会受进位影响，那有没有办法先与后加呢？
惊奇地发现 \((a\&b)+c\geq c \geq (a+b)\&c\)，所以遇到 \((a+b)\&c\) 的情况一定能进行替换。
那题目就被简化为：将 \(n\) 个数划分为 \(k\) 个不交集合，使得各集合按位与后的求和最大。
于是我们就可以进行拆位，每次让当前位的答案最大就可以了，设有 \(cnt\) 个数当前位为 \(1\)。
当 \(cnt<k\) 时，显然应当让当前位为 \(1\) 的全部独立划分为一个集合。
所以可以直接让答案加上这些数，并把这些数删去，变成集合和 \(k\) 都更小的子问题。
当 \(cnt\geq k\) 时，如果当前位全为 \(1\)，那不管怎么划分这一位答案都相同，直接加上就行了。
否则，我们一定要将这一位的所有 \(0\) 并在一起才最优，这一位就只能贡献 \(k-1\) 个 \(1\)。
然后用 vector 模拟实现上述过程即可。
注意在 \(cnt\geq k\) 的时候要将当前位的 \(1\) 抹去，否则会在后续 \(cnt<k\) 时重复统计贡献。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
long long t,n,k,ans;
void solve(){cin>>n>>k,ans=0;vector<int> v(n,0);for(auto &x:v) cin>>x;for(int i=29;i>=0;i--){vector<int> tmp(0,0);int cnt=0,now=(1<<30)-1;for(auto x:v) cnt+=(x>>i&1);if(cnt<k){for(auto x:v){if(x>>i&1) ans+=x,k--;else tmp.push_back(x);}v=tmp;}else{for(auto x:v){if(!(x>>i&1)) now&=x;else tmp.push_back(x^(1<<i));}v=tmp,ans+=(1<<i)*(k-1);if(now==(1<<30)-1) ans+=(1<<i);else v.push_back(now);}}return cout<<ans<<"\n",void();
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin>>t;while(t--) solve();
}