P7855 「EZEC-9」暂颓恒卷 题解
Perfound
·
·
题解
P7855 「EZEC-9」 暂颓恒卷 题解
为防棕名先发个声明：和 wyy332623 的 3 个代码雷同是因为我一天内交的次数满了,就把代码给他交.
思路
这题最重要的一点是要知道 1-3 之间（无 2 或 1）可全部变卷。
方便起见，把每个 1-2（之间无 2 或 1）叫做一个区间。
要求最大值，那就先把所有输入的区间内 1-3（离 2 最近的）的距离（包括 2 个端点）之和记作 res。
那这 1-3（离 2 最近的）之间的3就没用了，数量记作 us3（不包括 2 个端点）。
要移动 3（离 2 最近的）当然要移到那个 2（本区间）边上，区间 i 的移动所加的值记为 add_ i。
但这通过率不到 2% 的 大水题 肯定会有像 1-2（无 1 或 2）之间只有 4 的 比较水的 数据，把它定义为 水区间。
那怎么办呢？
肯定先用 us3 因为它可以进行 人见人爱花见花开的白嫖，把它放到 水区间 的 2 边上。
把 水区间 i 内 4 的个数记为 empty_i。
那 res=res+empty_{headempty}。
那有 ~~更水的~~ 数据连 3 都不够（$us3<tailempty-headempty+1$）就 ~~拆东墙补西墙~~，把区间 i 拆下要减的 1-3 （离 2 最近的）的距离（包括 1 个端点）记为 $wipe_i$（加到 ~~水区间~~ 的 2 边上）
即 $res=res+empty_{headempty}-wipe_{headwipe}
（empty_{headempty}-wipe_{headwipe}<0 时退出）因为这样 res 会倒减且这是最后方案（即 白嫖失败）
排序：
$empty$ 从大到小。
$wipe$ 从小到大。
（$add_{headadd} \geq empty_{headempty}$ 时）先用 $add$。
否则用 $us3$（因为 ~~可以白嫖~~）最后用 $wipe$，即 ~~有代价的白嫖~~（$us3$ 没了所以可以用）。
$add_i$ 用了 $wipe_i$ 就用不了了（反过来也一样）用 set 即可解决这个问题。
为使 $add$ 和 $wipe$ 一一对应，$add_k=0$ 时也应算入。
记得把 $wipe$ 生成的 $empty$ 重新加入。
------------
# 代码
------------
```cpp
#include<bits/stdc++.h>
using namespace std;
int add[2000010],wipe[2000010];
struct ad{
int v,p;
friend bool operator <(ad x,ad y){
return x.v==y.v?x.p>y.p:x.v>y.v;
}
};
struct wp{
int v,p;
friend bool operator <(wp x,wp y){
return x.v==y.v?x.p<y.p:x.v<y.v;
}
};
struct ep{
int v;
friend bool operator <(ep x,ep y){
return x.v>y.v;
}
};
set<ad>s1;set<wp>s2;
multiset<ep>s3;
int empty[2000010],is[2000010];
bool cme(int a,int b){return a>b;}
int hw,he,ha;
int ta=-1,tw=-1,te=-1;
int f,b13,b3,b1,b2;
int res,us3;
void usa(){
auto it=s1.begin();
s2.erase((wp){wipe[(*it).p],(*it).p});
res+=(*it).v,s1.erase(it);
}
void usw(){
auto it=s2.begin();
s1.erase((ad){add[(*it).p],(*it).p});
res+=(*s3.begin()).v-(*it).v;
s3.erase(s3.begin());
s3.insert((ep){is[(*it).p]});
s2.erase(it);
}
int main(){
int k,c,a;
scanf("%d%d",&k,&c);
for(int i=1;i<=k;i++){
scanf("%d",&a);
if(a==1){
if(b13>0)wipe[++tw]=i-b3,is[tw]=i-b2-1;
if(b13<=0&&i!=1)empty[++te]=i+b13-1;
f=min(f+1,2),us3+=(f==2);
if(b13>=0)res+=i-b13;
else res++;
b13=b1=i,f=0;
}else if(a==2){
if(b13!=b1)wipe[++tw]=b13-b1,is[tw]=i-b1-1;
if(f==0&&i!=1)empty[++te]=i-b13-1;
if(f>0)add[++ta]=i-b13-1;b13=-i,b2=i,f=0;
}else if(a==3){
if(b13>0)res+=i-b13,f=min(f+1,2),us3+=(f==2);//去掉二个端点 f 就这样搞
else add[++ta]=i+b13-1,b3=i,res++;b13=i;
}
}
for(int i=0;i<=ta;i++)s1.insert((ad){add[i],i});
for(int i=0;i<=tw;i++)s2.insert((wp){wipe[i],i});
for(int i=0;i<=te;i++)s3.insert((ep){empty[i]});
for(int i=0;i<c;i++){
if(s3.size()){
if(s1.size()){
if((*s1.begin()).v>=(*s3.begin()).v)usa();
else if((us3--)>0)res+=(*s3.begin()).v,s3.erase(s3.begin());
else if(!s2.size())usa();
else if((*s1.begin()).v>=(*s3.begin()).v-(*s2.begin()).v)usa();
else if((*s3.begin()).v-(*s2.begin()).v>0)usw();
else break;
}else if((us3--)>0)res+=(*s3.begin()).v,s3.erase(s3.begin());
else if(!s2.size())break;
else if((*s3.begin()).v-(*s2.begin()).v>0)usw();
else break;
}else if(s1.size())usa();
else break;
}
cout<<res;
return 0;
}
```
------------
# 总结
------------
~~洛谷月赛真是越来越毒瘤了~~
~~都开始传播白嫖主义了~~