CF1313D
Exschawasion
·
·
题解
好题。想通一个点之后就轻松了。
打过定轨音游的都知道所谓的**轨道**。它的本质就是：**任何一个**线段都会在**某个单一的轨道**中固定移动。如下图，$7$ 条线段被放进了 $3$ 个轨道中。
这道题里，每个位置都只会被最多 $8$ 个线段覆盖，也就是说，所有线段一定可以**无重叠**地放置进 $8$ 个轨道。因此只要记录当前位置的所有轨道上是否有线段即可。
现在问题是如何把线段放进轨道里。直接扫描线过去，开一个 `vis` 数组记录轨道是否占用即可。之后，第 $i$ 条线段将拥有一个编号 $id_i$ 表示所在轨道的编号。
转移就很显然了。枚举 $2n$ 个线段的端点，再枚举 $2^8-1=255$ 种状态，直接转移即可。注意判断当前枚举到的端点是左端点还是右端点、状态的 `popcount` 个数是奇数还是偶数。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+5;
struct seg{
int x,id;
int tag;//1=insert,0=delete
bool operator<(const seg&s)const{
if(x!=s.x)return x<s.x;
else return tag<s.tag;
}
};
vector<seg>Q;
int n,m,k;
int f[256+5];
inline int chk(int x){
return __builtin_popcount(x)%2==1;
}
int used[8];
int ID[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
memset(f,-0x3f,sizeof(f));
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
int l,r;cin>>l>>r;
Q.emplace_back((seg){l,i,1});
Q.emplace_back((seg){r+1,i,0});//note: r+1
}
sort(Q.begin(),Q.end()),f[0]=0;
for(auto a:Q){
if(a.tag){
for(int i=0;i<8;i++)if(!used[i]){
used[i]=1,ID[a.id]=i;
break;
}
}
else used[ID[a.id]]=0;
}
for(unsigned i=0;i<Q.size();i++){
seg cur=Q[i];
int id=ID[cur.id];
if(cur.tag){
for(int S=(1<<8)-1;~S;S--){
int v=(i+1<Q.size()?(Q[i+1].x-Q[i].x):0);
if(!chk(S))v=0;
if((S>>id)&1)f[S]=f[S^(1<<id)]+v;
else f[S]=f[S]+v;
}
}
else{
for(int S=0;S<(1<<8);S++){
if(!((S>>id)&1)){
if(chk(S))f[S]=max(f[S],f[S^(1<<id)])+(i+1<Q.size()?(Q[i+1].x-Q[i].x):0);
else f[S]=max(f[S],f[S^(1<<id)]);
}
else{
f[S]=-0x3f3f3f3f;
}
}
}
}
cout<<f[0];
}
```