题意
有n个东西，每个东西有价值，随便选选出的权值和第k小是多少，并输出方案（权值和相同按照选的集合的字典序排列）。
题解
第一问：求第k小方案的价值
考虑贪心，将价值从小到大排序，用二元组(sum,i)描述前i个数中，选出若干数和为sum，其中必选第i个数。利用小根堆不断取出堆顶，并把(sum+a[i+1],i+1)和(sum+a[i+1]-a[i],i+1)加入堆中，保证不重不漏，时间复杂度O(klogn)
第二问：求ans价值下的第cnt个方案
设上一问已经求出：价值为ans，字典序第cnt小的方案。
从前向后取数, 每次尽量取靠前的数, 从而保证字典序最小, 取数可以用线段树维护区间最小值因为取得集合排名一定小于等于k, 所以最多选出k次, 复杂的O(klogn)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,k;
typedef long long ll;
const int maxn=1e6+10;
int a[maxn],b[maxn];
struct node{
ll sum;
int i;
bool operator<(const node &x)const{
return sum>x.sum;
}//优先队列重载运算符，使队列内元素按sum由小到大
};
priority_queue<node> q;
int cnt;
ll ans;
int tree[maxn<<2];
void pushup(int root){
tree[root]=min(tree[root<<1],tree[root<<1|1]);
}
void build(int root,int l,int r){
if(l==r){
tree[root]=a[l];
return;
}
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
pushup(root);
}
int query(int root,int l,int r,int x,ll k){//为保证字典序,查找x右边第一个比k小的元素
if(x<=l){
if(tree[root]>k){
return 0;//区间最小值都小于k,一定不合法
}
if(l==r){
return l;//找到了返回标号
}
}
//以下类似于二分
int mid=(l+r)>>1;
if(x<=mid){
int w=query(root<<1,l,mid,x,k);
if(w){
return w;
}
}
return query(root<<1|1,mid+1,r,x,k);
}
int top,st[maxn];
void dfs(ll res,int pre){
if(!res){//统计答案
cnt--;
if(!cnt){
for(int i=1;i<=top;i++){
printf("%d ",st[i]);
}
exit(0);
}
return;
}
for(int i=pre+1;i<=n;i++){
i=query(1,1,n,i,res);//查找i右边第一个比res小的元素
if(!i){
return;
}
st[++top]=i;//记录答案
dfs(res-a[i],i);
top--;
}
}
int main(){
scanf("%d%d",&n,&k);
k--;
if(k==0){
printf("0");
return 0;
}
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);
q.push({b[1],1});//元素由小的更新大的,每次弹出最小,k次之后一定可以找到答案
while(k--){
node u=q.top();
q.pop();
if(u.sum==ans){
cnt++;
}
else{
ans=u.sum;
cnt=1;
}
if(u.i==n){
continue;
}
q.push({u.sum+b[u.i+1],u.i+1});
q.push({u.sum+b[u.i+1]-b[u.i],u.i+1});
}
build(1,1,n);
printf("%lld\n",ans);
dfs(ans,0);
return 0;
}
题意
有两个人玩游戏，一共m个石子分成n堆，给出每堆石子数量，每轮当前人可以选择一堆石子并扔掉其中任意个最后无法扔的人获胜，A先手B后手，但是B可以在游戏开始之前扔掉一些堆的石子，堆数必须是d的倍数，问有多少种扔的方式使B必胜。
题解
首先根据 Nim 博弈的结论，各堆石子异或和为 0 则后手必胜，否则先手必胜，那么就是统计多少种取法使异或和为 0。
异或的一个性质：对于任何整数A，必然有A^A=0，因此我们可以记录原来n堆石子的异或和s，将题目转化为为了取k×d堆石子，问有多少种方法让取到的石子堆中每堆石子的异或和为s。
dp转移方程：dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k^a[i]]
表示前i堆石子，取出模d余j堆石子，取出的石子异或和为k。
发现空间会炸，于是考虑像背包一样倒序转移，滚掉第一维。发现这样 dp 的时间复杂度为 O(nd×max(ai))，也会炸。
优化（本题核心）：
因为对于任意一个正整数A，它和比它自己小的数字异或起来的结果不会超过A×2。也就是一个数异或上一些比它小的数后，二进制下的位数不变。设x表示二进制下与A位数相同的最大的数，则x≤2A。那么我们把ai从小到大排序，每次只枚举ai到对应的x，复杂度就降到了O(md)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,d;
const int maxn=5e5+10;
const int maxm=1e7+10;
const int mod=1e9+7;
int a[maxn];
int f[maxm];
int dp[15][maxm];
int main(){
scanf("%d%d",&n,&d);
int s=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
s^=a[i];
}
sort(a+1,a+n+1);
int x=1;
dp[0][0]=1;
for(int i=1;i<=n;i++){
while(x<=a[i]){
x<<=1;
}
for(int j=0;j<x;j++){
f[j]=(dp[d-1][j^a[i]]+dp[0][j])%mod;//特判取出d的倍数堆石子的情况
}
for(int j=d-1;j>0;j--){
for(int k=0;k<x;k++){
dp[j][k]=(dp[j][k]+dp[j-1][k^a[i]])%mod;//dp转移
}
}
for(int j=0;j<x;j++){
dp[0][j]=f[j];
}
}
if(n%d==0){
dp[0][s]--;
}
if(dp[0][s]<0){
dp[0][s]+=mod;
}
printf("%d",dp[0][s]);
return 0;
}