hdu 5845 Best Division(trie+dp,好題)

2019-11-08 02:12:05

字體：大中小

來源：轉載

供稿：網友

Best Division

Time Limit: 4000/2000 MS (java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 663 Accepted Submission(s): 199PRoblem DescriptionYou are given an array A, consisting of N integers.You are also given 2 integers K and L.You must divide the whole array A into exactly K nonempty intervals, such that the length of each interval is not greater than L.The cost of an interval [S, E] is the bitwise XOR sum of all elements of A whose indices are in [S, E].The score of a division is simply the maximum cost of K intervals in the division. You are interested in the best division, which minimizes the score of the division. Since this is too simple for you, the problem is reversed.You know the minimum score: the answer for the original problem is not greater than X. Now you want to know, the maximum value of K. InputThere are several test cases.The first line of the input contains an integer T (1<=T<=20), the number of test cases. Then T test cases follow.Each test case starts with 3 integers N, X, L (1<= L<=N<=100000, 0<=X<268435456), which are described above.The next line contains 3 integers A[1], P, Q. All other integers of the array A are generated from these 3 integers in the following rule:For every integer 1<k<=N, A[k] = (A[k-1]*P+Q) mod 268435456.(0 <= A[1], P, Q < 268435456) OutputFor each test case, you should print a single line containing the answer.If the answer does not exist, just print 0. Sample Input

23 1 21 1 13 0 31 1 1 Sample Output21 Author金策工業綜合大學（DPRK） Source2016 Multi-University Training Contest 9  
題意：給你n個數字的序列，問你最多能把序列分成多少份，每份長度不能超過l，且異或和不能超過x。
題解：
可以想到n2的dp[n][m]表示到第n個數字能否分成m段然后二分，但是這題不管是時間還是空間都過不去，而n2的dp僅僅記錄了這個狀態能否到達，有些浪費所以我們可以改成dp[n]=m表示到第n的數組，最多能分成多少段 dp[i]=max(dp[j])+1,并且s[i]XORs[j]<=x 
這里可以用trie樹進行優化。
維護前綴異或和，構造trie，節點保留這個子樹下的最大值，每次插入和刪除都要更新，然后每次去字典樹里查最大值更新即可。注意i-l-1>= 0時要刪除一個前綴sum[i-l-1].
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const int inf=0x3fffffff;const int mod=268435456;const int maxn=1e5+100;int ch[32*maxn][3];int d[maxn],val[32*maxn],num[32*maxn];int sz;int x;ll sum[maxn];void insert(int i,int id,int u){    if(i==-1)    {        val[u]=d[id];        return;    }    ll x=sum[id];    int v=(x>>i)&1;    if(!ch[u][v])    {        ch[u][v]=++sz;        num[sz]=0;        val[sz]=-1;    }    num[ch[u][v]]++;    insert(i-1,id,ch[u][v]);    val[u]=max(val[u],val[ch[u][v]]);}void del(int i,int id,int u){    if(i==-1)    {        if(!num[u]) val[u]=-1;        return;    }    ll x=sum[id];    int v=(x>>i)&1;     //一開始寫成v=x&(1<<i),re了好久,這簡直是個傻逼錯誤。。。    num[ch[u][v]]--;    del(i-1,id,ch[u][v]);    val[u]=val[ch[u][v]];    if(ch[u][v^1]&&num[ch[u][v^1]])    val[u]=max(val[ch[u][v^1]],val[ch[u][v]]);}int query(int i,ll c,int u){    if(i==-1)    {        return val[u];    }    int v=(c>>i)&1,d=(x>>i)&1;    int ans=-1;    if(d==1)    {        if(ch[u][v]&&num[ch[u][v]])            ans=max(ans,val[ch[u][v]]);        if(ch[u][v^1]&&num[ch[u][v^1]])            ans=max(ans,query(i-1,c,ch[u][v^1]));    }    else    {        if(ch[u][v]&&num[ch[u][v]]) ans=max(ans,query(i-1,c,ch[u][v]));    }    return ans;}int main(){    int cas;    scanf("%d",&cas);    while(cas--)    {        memset(d,0,sizeof(d));        memset(val,-1,sizeof(val));        memset(ch,0,sizeof(ch));        memset(num,0,sizeof(num));        sz=0;        int n,l;        ll a,p,q;        scanf("%d%d%d%lld%lld%lld",&n,&x,&l,&a,&p,&q);        sum[1]=a;sum[0]=0;        rep(i,2,n+1)        {            a=(1ll*a*p%mod+q)%mod;            sum[i]=sum[i-1]^a;        }        d[0]=0;        insert(30,0,0);        rep(i,1,n+1)        {            if(i>l&&d[i-l-1]) del(30,i-l-1,0);            if(i==l+1) del(30,0,0);            int p=query(30,sum[i],0);            if(p>=0)            {                d[i]=p+1;                insert(30,i,0);            }        }        printf("%d/n",d[n]);    }    return 0;}
可以想到n2的dp[n][m]表示到第n個數字能否分成m段然后二分，但是這題不管是時間還是空間都過不去，而n2的dp僅僅記錄了這個狀態能否到達