CFR542

CFR542 div1

过A是rk45,看C的时候看看错题以为是子序列,过C的时候忘了,剩10min的时候写完B发现看错题,以为看错两次题崩盘上天有点难受就直接跑路了,最后是rk116(估计是$2150->2200$)

结果第二天发现把那份代码的输出翻转过来就过了

back题感想:这可能是我见过最水的一场div1了,但看错两次题的选手大概没资格这么说

CF1129A Toy Train

请先思考后再展开

不知道A1的做法,看完题的第一想法就是到i后,需要走$(cnt_i-1)*n+\min\ |b_j-a_j|$步,枚举起点后直接计算每个的max就是$O(n^2)$,code

CF1129B Wrong Answer

请先思考后再展开

一直以为这伪代码写的是最大子段和,将错就错按这个讲,我想到的构造方案:

构造题肯定要尽量结构简单,$[一个x>0],[a个数,和为y<0]$,当然$x+y>0$

则要满足$x=(a+1)(x+y)-K,K=a(x+y)+y,不妨令y=-(a-K\%a),则条件就是\lfloor \frac{K}{a} \rfloor+1-y=x$

这样$x+y$一定是正数,然后因为$y \le a$,直接用-1和0组成就行

但我们似乎还没保证不会在中间某处达到最大,即$\forall 0<i<y,(x-i)(i+1) \le (x-y)(a+1)$(只需要分析$y=a$这种最坏情况),只需令$x \ge a+y+1,即a^2 \le K$,那这就是我们做法的额外条件了,发现K取最大x依然在合法范围内,则不会出现-1

回到伪代码,发现其实写的是每个位置往左最大后缀+当前的数,然后乘上对应长度,而我的方案翻转一下就是对的了(准确的说如果是最大子段和方向是无所谓的,仅此而已),code


其实直接一堆0,然后一个y一个x就行了,枚举y,$x=\frac{K-2e3y}{2e3-1}$,在$[0,2e3-1]$中一定有可行的y

CF1129C Morse Code

请先思考后再展开

感觉没啥思维含量,子序列的话就是直接dp,子串的话就是直接在sam的dag上dp

常数写丑了t了一发,code

当然我这样完全没利用题目的特殊性,想利用的话把所有子串丢trie就完了吧,反正复杂度差不多,而且sam直接复制就好了(我花了挺多时间写了个子序列dp所以花了挺久)

emm发现了更sb的方法,直接根据子串是否出现过判断是否带来贡献,然后dp出分割方案表示贡献

所以我的做法的优越性在于,没有这个增量构建的性质,也能单次$O(len)$,虽然也没啥技术含量就是了

CF1129D Isolation

请先思考后再展开

套路:枚举右端点,每种数左边第一次出现是1,第二次是-1,否则是0,那么合法的转移点就是后缀和不超过k的位置

看起来就很数据结构,但当时完全没感觉分块能胜任,想到这个就很容易了:对每个块维护每种后缀和的dp和前缀和,修改一个块就直接重构,$O(n \sqrt n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n,K,m,a[N],dp[N],cnt[N],sum[320][N],okay[320],tg[320];vc<int> pos[N];
void cls(int id){fo(i,id*m,min(n+1,(id+1)*m-1)) sum[id][cnt[i]]=0,cnt[i]+=tg[id];tg[id]=0;}
void rebuild(int id){okay[id]=0;fo(i,id*m,min(n+1,(id+1)*m-1)){add(sum[id][cnt[i]],dp[i]);if(cnt[i]<=K) add(okay[id],dp[i]);}}
void ad(int pos,int c)
{
int id=pos/m;
fo(i,0,id-1)
{
int tc=c;
while(tc>0) {if(tg[i]<=K) add(okay[i],MOD-sum[i][K-tg[i]]);tg[i]++,tc--;}
while(tc<0) {tg[i]--,tc++;if(tg[i]<=K) add(okay[i],sum[i][min(K-tg[i],N-1)]);}
}
cls(id);fo(i,id*m,pos) cnt[i]+=c;rebuild(id);
}
void main()
{
n=qread(),K=qread(),m=sqrt(n+1);fo(i,1,n) a[i]=qread();dp[1]=1,rebuild(1/m);
fo(i,1,n)
{
ad(i,1);if(sz(pos[a[i]])>1) ad(pos[a[i]][sz(pos[a[i]])-2],1);
if(sz(pos[a[i]])) ad(pos[a[i]][sz(pos[a[i]])-1],-2);pos[a[i]].PB(i);
cls((i+1)/m);fo(bk,0,(n+1)/m) add(dp[i+1],okay[bk]);rebuild((i+1)/m);
}write(dp[n+1]);

CF1129E Legendary Tree

题意补充:即不存在一棵不同构的树,使得也满足目前为止的条件(样例看起来是这个意思?

请先思考后再展开

发现通过询问${rt},{1,2,..n},x$可以得到以rt为根时x的子树大小,询问${rt},{y},x$可以判断y是否在x子树中

按子树大小排个序后,父亲就是左边中,满足是x祖先中最右边的,但这样没法询问

换过来,从右往左删除子树内的点,这样父亲会比祖先先删除点。具体而言,在还没知道父亲的人中,二分出第一个子树内的点,这样每个点确定父亲的询问次数花费都是log,总询问次数=$O(nlogn)$

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