20191112模拟-qzz

qzz的场

好题：loj2336「JOI 2017 Final」绳

uoj213「UNR #1」争夺圣杯

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

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