20191112模拟-qzz

qzz的场

好题:loj2336「JOI 2017 Final」绳

uoj213「UNR #1」争夺圣杯

请先思考后再展开

考虑每个点作为最大值的可行范围,向左ln1向右ln2,讨论一下发现是三段等差数列,二阶差分后就是线性的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll a[N],gol[N],gor[N];pr b[N];
ll f[N];
void main()
{
int n=qread();fo(i,1,n) a[i]=qread(),b[i]=MP(a[i],i),gol[i]=i-1,gor[i]=i+1;sort(b+1,b+n+1);
fo(i,1,n)
{
int pos=b[i].SE,x=gol[pos],y=gor[pos];gor[x]=y;gol[y]=x;
int ln1=pos-x,ln2=y-pos;if(ln1<ln2)swap(ln1,ln2);
f[1]+=a[pos],f[ln2+1]-=a[pos],f[ln1+1]-=a[pos],f[ln1+ln2+1]+=a[pos];
}
fo(i,1,n) f[i]+=f[i-1];fo(i,1,n) f[i]+=f[i-1];
ll ans=0;fo(i,1,n)ans^=f[i]%MOD;write(ans);
}

CF634E Preorder Test

题意:给出一棵n个点的树,求一条不一定简单的路径,要求经过了k个不同的点,最小化经过点的最大点权

请先思考后再展开

明显二分,然后可以把那些满的子树缩上去,跑个类似求直径的换根就行了

code

loj2336「JOI 2017 Final」绳

请先思考后再展开

好高兴能想出这种思维题,虽然因为一些原因并不是在赛中完成的;另外所有部分分的做法都想到了,恰好层层递进

转化一:数字不要中途改,将他们堆成两组后,各自统一颜色来考虑代价

转化二:考虑将所有位置分两组,考虑希望颜色now所在组为1,那么这个01序列一定满足,将连续同值的缩在一起,除了最左边和最右边一段,其他长度都是偶数,这个可以感性理解,再打个表验证也很容易

于是现在无脑枚举now和另一组中最后颜色mx就是$O(m^2n)$的,思考一下这个段长度的奇偶性,枚举第一个块的长度是奇数还是偶数,那么剩下的就能捆绑在一起选择(例如第一个块是奇数,那么位置2和3绑在一起,4和5绑在一起),于是答案的计算就是$n-C_{mx}-sum,sum=选若干组的最小权值$,每个组的权值的话如果存在颜色now就-1,存在颜色mx就+1,那么预先把mx插好,枚举now并和之前的mx插在一起,这样复杂度就是$O(m\sum=mn)$,比赛中止步到这里,然后忙于搞别的事了

感觉这个捆绑还是很妙的,如果只是部分分的话会很可惜,所以想着怎么推广,发现还可以进一步优化!

融入一点贪心,所有有-1的组肯定都选,假设最初权值就是$-C_{now}$,然后两个1的组肯定不选,单个的1如果和-1一组就要增加1的贡献,将式子改写成$n+(-1)*C_{now}+(-C_{mx}+「-1和1组合的损失」)$,枚举now的话找出每个单独now旁边的颜色,更新其作为mx的贡献,暴力找最小的mx就是$O(m^2)$,code

很明显可以优化成$O(n+m)$,每次将那些修改的地方存起来,思考一些小技巧怎么保证复杂度地回撤,可能方法很多,想不到见code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/f89c918e.html
转载请注明出处,谢谢!