[HDU-6883] Coin Game(2020HDU多校第十场T7)

[HDU-6883] Coin Game(2020HDU多校第十场T7)

题目给出的模型看起来比较奇怪，但是简单推理后，发现可以转化为一个简单的01背包问题

对于题目给定的权值(a_i,b_i)，分为(a_i,a_i+b_i)两个物品，发现可以得到这个机器的所有合法贡献情况

也就是说，有两种大小分别为(1,2)的物品，要做01背包

这个刚刚在WC2020考过。。。

设两类转化后的权值分别为(a_i,b_i)，则转移过程可以简单描述为

1.将两类权值分别从大到小排序

2.将dp值转化为在两个序列中分别选取一段前缀和

3.转移时枚举下一次决策的选取是那种物品，选取最优一个，记录指针转移即可

主要复杂度可能还在于排序，Trick:有一点卡内存

但是实测桶排和直接sort好像差距不大。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)

const int N=5e6+10,INF=1e9;

int n,m;
int a[N],b[N];
ull k1,k2;
int Shift(){
    ull k3=k1,k4=k2;
    k1=k4;
    k3^=k3<<23;
    k2=k3^k4^(k3>>17)^(k4>>26);
    return (k2+k4)%10000000+1;
}
int A[N*3],B[N*3]; // 记录在两个序列中的指针
ll dp[3]; // dp数组滚动了一下

int main(){
    while(~scanf("%d%d%llu%llu",&n,&m,&k1,&k2)) {
        rep(i,1,n) a[i]=Shift(),b[i]=Shift()+a[i];
        sort(a+1,a+n+1,greater<int>()),sort(b+1,b+n+1,greater<int>());

        A[0]=B[0]=1;
        rep(i,0,2) dp[i]=0;
        ll ans=0;
        int cur=0;
        rep(i,0,m) {
            if(i+1<=m && A[i]<=n) {
                int nxt=(cur+1)%3;
                if(dp[cur]+a[A[i]]>dp[nxt]) dp[nxt]=dp[cur]+a[A[i]],A[i+1]=A[i]+1,B[i+1]=B[i];
            }
            if(i+2<=m && B[i]<=n) {
                int nxt=(cur+2)%3;
                if(dp[cur]+b[B[i]]>dp[nxt]) dp[nxt]=dp[cur]+b[B[i]],A[i+2]=A[i],B[i+2]=B[i]+1;
            }
            ans^=dp[cur];
            cur=(cur+1)%3;
        }
        printf("%lld
",ans);
    }
}