HZOJ
写在前面
嗯。。。大概就是无缝衔接吧。
《Winter Sleep》
早春时节折下几枝花
放在你的房门前
当你从漫长的睡眠中醒来时，
到那时应该会开得漂亮吧
星辉夏夜，一杯相伴
放在了你的枕边
这下全都要化没了。
看来你还想一个人休息呢。
没有你的第一个春天如夏日般灼热
无缘无故怎么这么漂亮？
在结束之前，我必须让你看看。
嗯，这个一定要看。
曾倚着我沉睡的
就这样沉睡了啊
做了什么梦？
醒来后我会告诉你。
如同往常的清晨，嗯
折一张薄如蝉翼的秋日
我放进了你的信箱。
在最喜欢的一句话下面画线。
见面时能读给我听吗？
在洁白的冬日气息之中
收录了我的自言自语
一直忍着不发作
偶尔想看个没头脑的
格外冷冽的年末空气
骨缝间渗出寒意
你那颤抖着的干枯的肩膀
一定要抱抱你。
依偎在我怀中浅眠
就这样沉沉睡去
你做了什么梦？
等醒来再告诉你。
如同往常的早晨，嗯
A. 挑战
题意大概是给定一个\(2\times n\) 的矩阵，每次操作可将一个移动一格，多个可合并为1个，求将所有*合并到一个格子的最小操作数。
赛时就是贪心写假了。看到用了近一小时还不一定得分心都凉了。还好及时转战dp拿下了本题。思路大概就是分别求该点左边及下边所有点都转移到该点的最小步数和右边及下边所有点转移到该点的最小步数，最后求两者和的最小值即可。
B. 染色
题意是给定一个只含\(R, B\) 两种元素的序列，求问是否能通过交换某些位置上的元素，使所有前缀中\(R\) 的个数都不小于\(B\)。如果能，求问最小操作次数。
做法格外的简单啊。转化题意就是令\(R\) 为1 \(B\) 为-1，通过操作使得所有位置的前缀和都不小于0。首先求出原序列的前缀和。对于每个交换操作，容易知道一定是将\(B\) 换为\(R\) 的。交换后相较于原序列，前面的位置开始前缀和会增加1，后面的位置开始前缀和不变。所以将\(R\) 从后面换到前面一定更优。进行模拟即可若出现某个位置前缀和小于0，表示最后一个\(R\) 位置的指针所指的位置小于了当前位置，则说明无解。
C. 海
题意是给定一个序列，每次操作可以删去一个最大值只出现一次的区间，求问恰好删去给定大小区间的最小操作次数。
讲讲赛时写法吧。先转化了题意，对于每个点，它能作为最大值贡献的区间即为其往前往后分别扩展到的最远的小于它的值。由于要求操作次数最少，所以操作的区间就该尽可能大。所以我们要求出能覆盖整个序列的所有不重区间。可以用优先队列，如果当前栈顶的长度与其贡献区间剩余的位置数相等，栈顶长度即为不重区间的组成。否则修改栈顶长度重新入栈。然后竟然能过3个样例。到了第四个过不了了。分析发现那种思路错在实际上不一定会取到某些区间，但这些区间取了且作用于其他区间使答案偏大。不知道怎么写就乱搞，先弹出某些区间再求，最后询问就求弹出不同区间的答案中的最小值。然后还是错的。没招了。然后这个假做法获得了惊人的56pts。
其实赛时思路有不完善的地方。对于能贡献的区间我们只考虑整个序列的最大值的即可。因为显然这样每个区间的长度是最大的，最后的操作次数也该是最小的。每个位置代表的区间即为其前驱到后继的开区间。令\(f_i\) 为选\(i\) 个位置最多能删去的区间大小。如果不考虑数据范围，显然可以dp。然而数据不支持，所以考虑用考虑后效性但复杂度正确的方法——反悔贪心。
当\(i=1\) 时，显然\(f_1\) 就是所有区间中最大的那个，令其表示为\(p_1\)。当\(i=2\) 时，\(p_2\)与\(p_1\) 的位置关系有两种可能：\(p_2\) 是\(p_1\) 加上一个不重区间，或者\(p_2\) 是与\(p_1\) 左右部分分别重合的两个相邻的区间。考虑如何反悔贪心。当\(i=1\) 选取某个区间后，如果我们\(p_2\) 会选择它相交的两个区间，则贡献的差值即为与其相交的区间长度和减去该区间长度。如果我们将该区间对应点的权值修改成这个值的话，当再次选到这个点时，贡献和便为选取了两个相交区间而不选该区间。就算我们没有再次选到这个点而选了其他点对答案和区间数也不会产生影响。那就按照这个思路，每次将所选区间对应点的权值更新成贡献差再次插入队列，然后删去相邻区间即可。询问答案就二分一下即可。
然后本题细节巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨多。首先可能会出现的情况是最边上的两个区间讨论漏了。为了避免这种情况我们将第0个点的权值更新为最左边的区间长度，第点数+1个点的权值更新为最右边区间的长度，正常进行反悔贪心即可。但是注意，这两个点只能对答案造成一次贡献，所以使用后要立即将其赋为极小值。还有就是将所有区间选完后，必定会剩下一些长度为1的区间。原因是选区间时无法选到相交区间的端点，所以最后形成的是若干的连续段，且容易知道这若干个连续段是选取同样多个数区间，区间大小最大的情况。所以最后要将差的区间补上，直接\(f_{区间数-1}+1\) 即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10,inf=1044266559;
int n,Q;
int h[maxn],le[maxn],ri[maxn],cnt;
pair<int,int> lsh[maxn];
int cun[maxn],len[maxn],f[maxn];
bool ex[maxn];
priority_queue<pair<int,int>> q;
int main(){freopen("summer.in","r",stdin);freopen("summer.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>Q;for(int i=1;i<=n;i++) cin>>h[i],lsh[i].first=h[i],lsh[i].second=i;lsh[0]={-1,-1};sort(lsh+1,lsh+n+1);for(int i=1;i<=n;i++){if(lsh[i].first!=lsh[i-1].first) ++cnt;h[lsh[i].second]=cnt;}int tot=0;for(int i=1;i<=n;i++)if(h[i]==cnt) cun[++tot]=i;cun[0]=0,cun[tot+1]=n+1;for(int i=1;i<=tot;i++) len[i]=cun[i+1]-cun[i-1]-1,q.push({len[i],i}),le[i]=i-1,ri[i]=i+1;ri[0]=1,le[tot+1]=tot,ri[tot+1]=tot+1;len[0]=cun[1],len[tot+1]=n-cun[tot]+1;int now=1;while(q.size()){pair<int,int> k=q.top();q.pop();if(ex[k.second]) continue;if(k.first<0) break;f[now]=f[now-1]+k.first;++now;if(now==tot+1) break;ex[le[k.second]]=ex[ri[k.second]]=1;k.first=len[le[k.second]]+len[ri[k.second]]-k.first;len[k.second]=k.first;if(le[k.second]==0) len[0]=-1e9;if(ri[k.second]==tot+1) len[tot+1]=-1e9;le[k.second]=le[le[k.second]];ri[k.second]=ri[ri[k.second]];ri[le[k.second]]=le[ri[k.second]]=k.second;q.push(k);}for(int i=now;i<=tot;i++) f[i]=f[i-1]+1;for(int i=1,a;i<=Q;i++){cin>>a;cout<<lower_bound(f+1,f+tot+1,a)-f<<' ';} return 0;
}
D. 星白
暴力写挂了。然后不会笛卡尔树也不会扫描线所以咕了。然后大概就是优秀的暴力83pts吧。