CFR591

CFR591 div1

CF1240A Save the Nature

code,当然也能写成线性

CF1240B Sequence Sorting

code

CF1240C Paint the Tree

code

感觉前三题没啥特别想说的,题意、题解可以看Dup4当然代码还是推荐我的


CF1240D Stack Exterminable Arrays

题意:$n \le 3e5$,求多少子串满足是广义的括号序(形如$[5, 1, 2, 2, 1, 4, 4, 5]$)

请先思考后再展开

做法一(赛时想法、官方题解做法):

从后往前维护以每个位置为左端点的合法子串个数,则$dp_i=dp_{第一个j使得(i,j-1)合法}+1$

如果维护nxt表示上面的j,则当$a_i \ne a_{i+1}$时,i的最近合法右端点不可能在$nxt_{i+1}$中,否则当时能有更短的合法子串

1
2
3
4
5
6
if(a[i]!=a[i+1])
{
int j=i+1;while(nxt[j]!=j and nxt[j]<=n and a[i]!=a[nxt[j]]) j=nxt[j];
if(nxt[j]<=n and a[i]==a[nxt[j]]) nxt[i]=nxt[j]+1; else nxt[i]=i;
} else nxt[i]=i+2;
if(nxt[i]!=i) dp[i]=dp[nxt[i]]+1; else dp[i]=0;ans+=dp[i];

当时眼花以为每次只会在某个祖先下面新建叶子所以复杂度是对的,冷静分析才发现有个偏移

那要优化这个跳的过程,相当于要在i+1的祖先中找第一个和ai相等的;注意到每次只询问i+1的话,每个人的祖先都不可能再被直接询问到,因此可以直接在父亲的map给swap到自己身上并修改(当然你写可持久化也没毛病),$O(nlogn)$,code

做法二:人均10min切这题的原因

结论:$[l,r]合法 \leftrightarrow Stack([1,l-1])=Stack([1,r])$,必要性显然,充分性想不到怎么证,不过感受起来好像也在情理之中

写个hash或Trie判断,$O(nlogn)$,主要是猜完结论就没了+不容易写错

做法三:分治,左边的后缀跟右边的前缀,栈形态一定是相同的

总结:这玩意性质挺优美的,原因之一是每个数的角色是不确定的

CF1240E Wooden Raft

没啥思维含量,就是不太好写

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