Best Division

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 663 Accepted Submission(s): 199

Problem Description

You 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.

Input

There 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)

Output

For 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 Output

Author

金策工业综合大学（DPRK）

Source

题意

：

给你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
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define rep(i,a,n) for (int i=a;i
          
           =a;i--)#define pb push_back#define fi first#define se secondtypedef vector
           
             VI;typedef long long ll;typedef pair
            
              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)&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;}

转载地址：https://blog.csdn.net/fouzhe/article/details/55823601 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Codeforces Beta Round #50 C. First Digit Law(概率dp,好题)

下一篇：gym 100820G Racing Gems(二维LIS,好题)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

Best Division

发表评论

最新留言

关于作者

推荐文章