CodeForces 1313D Happy New Year

I am here On 1313E It's very difficult to mention this topic in. It's because I'm rude.. I read the wrong question before..

Luogu title page portal & CodeForces title page portal

There are \ (m \) children with the number of \ (1\sim m \). There are \ (n \) incantations. Article \ (I \) allows all children numbered in \ ([l_i,r_i] \) to get \ (1 \) sugar. Each incantation can be applied or not. Ask to maximize the number of children who get an odd number of sugars. Output this quantity. Ensure that if all spells are cast, each child does not receive more than \ (s \) sugar.

\(n\in \left[1,10^5\right],m\in\left[1,10^9\right],s\in[1,8]\).

"Make sure that if all spells are applied, the amount of sugar each child gets does not exceed \ (s \)" this sentence is extremely important. It tells us that each child is in the range of no more than \ (s \) spells, that is, only no more than \ (s \) spells are effective for him / her. This enlightens us to enumerate all \ (x \) spells that are effective for each child, and \ (2^x \) situations that are not effective for each child, so as to suppress DP.

Before DP, the scope of this \ (m \) was to be discretized at first sight. We press \ (\ forall I \ i n [1, n], l_i-1, r_i \) this \ (2n \) number into the 1-indexed sequence \ (nums \) of sort and unique. After sort and unique, \ (\ forall i\in[1,|nums \] \), the future number \ (I \) represents the previous interval \ ((nums{I-1}, nums_i] \), specifically, \ (nums_ = 0 \). In this way, it can ensure that each child in the future represents the same spell range of each number in the previous range, because the endpoint of the spell range represents the boundary of the same spell range. But there's another problem: it's possible that the numbers in a previous suffix are not included in the interval represented by any future numbers. Simply add a number \ (m \) to \ (nums \). Time complexity \ (\ mathrm O(n\log_2n) \).

Next, consider DP. First, preprocess the 0-indexed sequence array \ (in \), \ (in \) represents the sequence composed of the spell interval number of each child in the previous interval represented by the next number \ (I \) (the sequence generated by each child in the interval is the same), and the sequence is arbitrary. I n this way, \ (\ forall i\in[1,n],\forall j\in[1,|nums|] \), if \ (\ forall K \ in (nums {J-1}, nums_j], K \ in [l_i, r_i] \), then the spell \ (I \) has a new number for the future number \ (J \). Obviously, the time complexity of preprocessing this array is \ (\ mathrm O(ns) \).

Set \ (DP {I, j} \) to indicate that considering the future number \ (I \), for bitmask\(j \) to meet \ (x\in j \) when and only when the spell \ (in {I, X} \), the first \ (nums \\\\\\\\\. Obviously the boundary is \ (DP {0,0} = 0 \), and the target is \ (\ Max \ limits_i \ {DP {| nums|, I} \} \} \). When transferring, \ ({I} \} \} \) and \ ({I-1} \} \} \) may not have an empty intersection. At this time, the spells in those intersections cannot be schizophrenic, that is, \ (\ forall x \ in \ {I} \} \ cap \ {in \ {I-1} \} \} \), and the state of the spells \ (x \) in \ (j \) and the transferred bitmask\(k \) must be the same.

Then the equation of state transition is:

\[dp_{i,j}=\max\limits_{cantrs(i,j,k)}\{dp_{i-1,k}+|j|\bmod2\times(nums_i-nums_{i-1})\}\]

Where \ (cantrs(i,j,k) \) indicates that \ (DP {I, J} \) is transferred to \ (DP {I-1, K} \) to meet the above restrictions.

In this way, if the state number \ (\ mathrm O(2^sn) \), the object \ (\ mathrm O(2^s) \), and \ (cantrs \) judgment \ (\ mathrm O(s) \) are transferred directly according to the equation, the time complexity is \ (\ mathrm O(4^sns) \), which is too large. Obviously, we can only accept \ (\ mathrm O(2^sn) \) at most.

Note that for \ (2 \) states \ (J {1, J} \), \ (\ forall x \ in \ {in {I} \} \ cap \ {in {I-1} \} \), if the states of the spells \ (x \) are the same in \ (J {1, J}, DP {I, J} \) are the same. HRM o (1) \) calculates the DP value. But the complexity has not changed.

To change the complexity, the most important thing is to remove \ (cantrs \) judgment. Note that \ (\ forall k \), \ (DP {I-1, k} \) can and can only move to \ (1 \) states, so if we can find the hit rate \ (100 \% \) and do not need to judge the way to find the legal transfer object, we can guarantee the complexity of \ (\ mathrm O(2^sn) \). This is very simple. You only need to split each \ (k \) into \ (\ in and \) and \ (\ notin and \) which are \ (2 \) parts. For each type, fix the \ (\ in and \) parts directly and enumerate the \ (\ notin and \) parts. However, the implementation is not so smooth, because the \ (2 \) part may not be continuous in \ (k \) respectively, and it can not be directly combined with bit operation \ (\ mathrm O(1)), so we can preprocess, number each state of \ (2 \) part, record its state in \ (k \), and finally get \ (k \) by combining the state of \ (2 \) part in \ (k \). For each class, now all legal transfer objects have been found, that is, for all bitmask\(j \), \ (\ Max \ limits {cantrs (I, J, k)} \ {DP {I-1, k} \} \) in this class, you can \ (\ mathrm O(1) \) get the value of each \ (DP {I, J} \} \) just by finding the hit rate \ (100 \% \) and finding all the states in this class without judgment.

The final total complexity is \ (\ mathrm o (n \ log ﹣ 2n) + \ mathrm o (n s) + \ mathrm o (2 ^ SN) = \ mathrm o (n (\ log ﹣ 2n + 2 ^ s)) \), which is slightly abnormal, but it doesn't need to be noticed.

Code above:

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define X first
#define Y second
int lowbit(int x){return x&-x;}
int lbt(int x){return __builtin_ctz(x);}
const int N=100000;
int n/*Number of incantation*/,m/*Number of children*/,s/*Maximum number of spells per child*/;
int l[N+1],r[N+1];//Spell interval 
vector<int> nums;//Discretized array 
void discrete(){//Discretization 
    sort(nums.begin(),nums.end());
    nums.resize(unique(nums.begin(),nums.end())-nums.begin());
    for(int i=1;i<=n;i++)
        l[i]=lower_bound(nums.begin(),nums.end(),l[i])-nums.begin(),
        r[i]=lower_bound(nums.begin(),nums.end(),r[i])-nums.begin();
}
vector<int> in[3*N+1];//Array of spell interval number sequence 
vector<int> dp[3*N+1];//DP array 
int main(){
    cin>>n>>m>>s;
    nums.pb(0);nums.pb(m); 
    for(int i=1;i<=n;i++)scanf("%d%d",l+i,r+i),nums.pb(l[i]-1),nums.pb(r[i]);
    discrete();
    for(int i=1;i<=n;i++)for(int j=l[i];j<=r[i];j++)in[j].pb(i);//Preprocessing 
    dp[0].resize(1,0);//boundary 
    for(int i=1;i<nums.size();i++){
//      printf("%d dping\n",i);
//      printf("\tin=",i);for(int j=0;j<in[i].size();j++)cout<<in[i][j]<<" ";puts("");
        dp[i].resize(1<<in[i].size());//Determine the number of dp[i] elements 
        vector<pair<int,int> > _and;//For all the binary sequences of x in {in[i]} cap {in[i-1]}, (x number in[i], X number in[i-1]) 
        for(int j=0;j<in[i].size();j++)for(int k=0;k<in[i-1].size();k++)if(in[i][j]==in[i-1][k])_and.pb(mp(j,k));//Preprocessing and 
//      printf("\t_and=");for(int j=0;j<_and.size();j++)printf("(%d,%d) ",_and[j].X,_and[j].Y);puts("");
        vector<int> nin_and1/*j Not in and*/,nin_and2/*k Not in and*/; 
        for(int j=0,k=0;j<in[i].size();j++)if(k>=_and.size()||(j==_and[k].X?k++,false:true))nin_and1.pb(j);//Pretreatment of NIN ﹣ and1 
        for(int j=0,k=0;j<in[i-1].size();j++)if(k>=_and.size()||(j==_and[k].Y?k++,false:true))nin_and2.pb(j);//Pretreatment of NIN and 2 
//      printf("\tnin_and1=");for(int j=0;j<nin_and1.size();j++)cout<<nin_and1[j]<<" ";puts("");
//      printf("\tnin_and2=");for(int j=0;j<nin_and2.size();j++)cout<<nin_and2[j]<<" ";puts("");
        vector<int> chg1(1<<_and.size(),0),chg2(1<<nin_and1.size(),0),chg3(1<<_and.size(),0),chg4(1<<nin_and2.size(),0);
        for(int j=1;j<chg1.size();j++)chg1[j]=chg1[j^lowbit(j)]|1<<_and[lbt(j)].X;//Preprocessing the state of each state of the part in and in j 
        for(int j=1;j<chg2.size();j++)chg2[j]=chg2[j^lowbit(j)]|1<<nin_and1[lbt(j)];//Preprocessing the state of each state of the part not in and in j
        for(int j=1;j<chg3.size();j++)chg3[j]=chg3[j^lowbit(j)]|1<<_and[lbt(j)].Y;//Preprocessing the state of each state of the part in k in and in j
        for(int j=1;j<chg4.size();j++)chg4[j]=chg4[j^lowbit(j)]|1<<nin_and2[lbt(j)];//Preprocessing the states of each state of the parts in k that are not in and in j
        for(int j=0;j<chg1.size();j++){//Enumeration class 
            int mx=0;//For all bitmask j, max[cantrs(i,j,k)]{dp[i-1][k]} 
            for(int k=0;k<chg4.size();k++)mx=max(mx,dp[i-1][chg3[j]|chg4[k]]);//Calculate mx 
            for(int k=0;k<chg2.size();k++)dp[i][chg1[j]|chg2[k]]=mx+__builtin_parity(chg1[j]|chg2[k])*(nums[i]-nums[i-1]);//Transition each state in this class 
        }
//      for(int j=0;j<dp[i].size();j++)printf("\tdp[%d]=%d\n",j,dp[i][j]);
    }
    cout<<*max_element(dp[nums.size()-1].begin(),dp[nums.size()-1].end());//target 
    return 0;
}

Tags: C++

Posted on Tue, 03 Mar 2020 21:00:21 -0800 by joePHP