【贪心】选择尽量多的不相交区间

参考链接问题跟定n个开区间(a,b)或闭区间[a,b]选择尽量多个区间且这些区间互不相交。贪心策略将每个区间按右端点从小到大排序。遍历所有的区间如果当前区间的左端点和最长区间的右端点相冲突直接放弃否则选取。模版题AC代码#includebits/stdc.husingnamespacestd;constintmaxn1e65;structqj{ints,f;friendbooloperator(qj x,qj y){if(x.fy.f)returnx.sy.s;returnx.fy.f;}}a[maxn];intn,ans,last;intmain(){cinn;for(inti1;in;i)cina[i].sa[i].f;sort(a1,an1);last1,ans1;for(inti2;in;i){if(a[i].sa[last].f){ans;lasti;}}coutans;return0;}进阶题这题题目明确给出了不相交区间我们不难想到模版题。但是这道题需要转一下弯这里的区间是怎么构成的呢拿数据举例422103找权值为2的区间我们不难想到前缀和的思想。开一个数组ss[t]存储a[1]^ a[2] ^ … ^ a[t]的结果。找权值为2的区间[l,r]就是找s[l-1]^s[r]2的lr。why? 因为同一个数异或偶数次结果为0s[r]的计算过程中有s[l-1]的计算再异或一次s[l-1]就抵消了a[1] ^ … ^ a[l-1]的结果。s[l-1] ^ s[r]求到的就是a[l]^ … ^a[r]的结果。那怎么找满足s[l-1]^s[r]k的区间[l,r]呢我们按下标顺序枚举左端点计算每个左端点找到与之匹配的右端点的条件:s[r]s[l-1] ^ k。我们一步步拆解来说1s[r]s[l-1] ^ k是什么要找s[l-1] ^ s[r]k,等号两边同时异或s[l-1]得到的就是s[r]k^s[l-1],我们枚举l,s[l-1]已知k已知就看如果s[r]k ^ s[l-1]说明[l,r]权值为k。2如何使用选择尽可能多不相交的区间a数组下标01234元素值02103s数组下标01234元素值02330我们另开一个数组h初始化h数组元素为-1。当s[l]^ki时h[i]l。这样当找到s[r]i时我们就可以通过数组h找到l区间[l1,r]就是一个满足权值为k的区间。另外我们开个变量last初始化为-1记录上一个满足条件的区间右端点的值。如果当前区间满足条件且左端点比上一个满足条件的区间的右端点要大说明两个区间不相交答案1。举例来说变量i遍历s数组·i0s[i]0,h[0]-1,说明暂时没有匹配到满足的左端点不处理。然后记录h[2]0·i1,s[1]2,h[2]0,匹配到了左端点为h[2]1,然后看一下左端点的值是否大于last是则ans,lasti。然后记录h[0]1;h数组下标01234元素值1-10-1-1·i2,s[i]3,h[3]-1,说明暂时没有匹配到满足的左端点不处理。然后记录h[1]2;·i3,s[i]3,h[3]-1,说明暂时没有匹配到满足的左端点不处理。然后记录h[1]3;h数组h数组下标01234元素值130-1-1·i4,s[i]0,h[0]1,匹配到了左端点为h[0]1,大于lastans,lasti。于是找到了两个不相交的区间。记录h[2]4。h数组h数组下标01234元素值134-1-13在代码实现上要注意a2^20,s数组要开到2e6比较保险。AC代码#includebits/stdc.husingnamespacestd;constintmaxn2e65;intn,k,a[maxn],s[maxn],h[maxn];intmain(){cinnk;for(inti1;in;i){cina[i];s[i]s[i-1]^a[i];}for(inti0;in;i)h[i]-1;h[0^k]1;intlast0,ans0;for(inti1;in;i){if(h[s[i]]!-1h[s[i]]last){ans;lasti;}h[s[i]^k]i1;}coutans;return0;}