首页 > 其他分享 >【做题记录】Codeforces Round 915 (Div. 2)/CF1905A-F

【做题记录】Codeforces Round 915 (Div. 2)/CF1905A-F

时间:2024-08-13 14:54:36浏览次数:11  
标签:lfloor right frac Codeforces rfloor CF1905A 915 节点 left

@

目录

A. Constructive Problems(800)

注意到,对于 \(n\times n\)的矩阵,只需要把对角线全染黑即可。
推广到 \(n\times m\) 的矩阵,不妨令 \(m>n\),那么我们染 \(n\) 个格子把左边 \(n\times n\)的矩阵全染黑,而后对于剩下的矩阵随便找一行全染黑即可,所以:\(ans=\max(n,m)\)

B. Begginer's Zelda(1100)

考虑每次合并一对叶子节点,只剩一个时和根节点合并,这样次数最小。

随便口糊一下证明:因为每一个叶子结点都要合并,那肯定是跟其他叶子结点合并最优。

C. Largest Subsequence(1400)

考虑最终情况,即将典序最大的子序列变成 从小到大 的再插回原序列中,即可判断是否有解和次数。

Tips:
找典序最大的子序列 可以从后往前,没找到一个比自己大的就直接替换,可以证明是对的。

D. Cyclic MEX(2000)

考虑模拟每一次操作。

先求出前缀 mex,则每把一个数 \(a_i\) 扔到后面,则前缀 mex 中 \(<a[i]\) 的不变,\(>a[i]\) 的变为 \(a[i]\),由于前缀 mex 单调不减,考虑用单调队列维护即可。

注意需要维护权值跟出现次数两个东西。

E. One-X(2400)

正难则反,考虑计算每一个节点作为 lca 被计算了多少次。

设节点 \(x\) 所对应的区间为 \([l,r]\),区间长度\(len_x=r-l+1\),那么 \(x\) 的左儿子对应区间为 \([l,\left \lfloor \frac{l+r}{2} \right \rfloor ]\),长度为 $\left \lfloor \frac{l+r}{2} \right \rfloor -l+1=\left \lfloor \frac{r-l+2}{2} \right \rfloor =\left \lfloor \frac{len_x+1}{2} \right \rfloor $,用 \(L\)表示,同理, \(x\) 右儿子所对应区间长度为 $\left \lfloor \frac{len_x}{2} \right \rfloor $,用 \(R\) 表示。

若 \(x\) 节点作为 lca 有贡献,那么它的左右子树内都至少选一个点,多的不限,所以合法方案数为 \((2^L-1)\times (2^R-1)\) (除了全不选其他都和法)

又发现对于不同的点 \(x\),若它们对应区间长度相同,那么合法方案数都一样,根据乘法分配律可以将它们节点的值合起来。

于是正解来了:

考虑直接记忆化搜索。

令 \(f[x]\) 表示对应区间长度为 \(x\) 的节点值之和,\(g[x]\) 为长度为 \(x\) 的区间个数。
得出转移公式:
若 \(x\ne 1\),那么:

\[\left\{\begin{aligned} f[ls] &= 2f[x] \\ f[rs] &=2f[x]+g[x] \\ g[ls] &=g[x] \\ g[rs] &=g[x] \end{aligned}\right.\]

其中 \(ls,rs\) 为 \(x\) 的左右儿子。

为什么呢?
回到建树过程:

void buuild(int x,int l,int r){
//
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
}

就是这两行,懂?

于是我们就可以欢乐记忆化暴搜了。

对了,忘记证明时间复杂度了,关键是 线段树上长度不同的区间个数是 \(\log n\) 级的,这就能保证时间复杂度了。

F. Field Should Not Be Empty(2600)

这里用 \(a\) 代替题目中的 \(p\)。

观察到一个数是好的,当且仅当 \(a[i]=i,\max_{j=1}^ia[j]=a[i]\)

瞪眼法可知,我们只会换逆序对,除非没有(所以要特判),因为这样原来是好的还是好的,原来不好的有可能变为好的,可证明是最优的。

那我们考虑对于一个不好的点,记录那些操作能把它编号,最终我们取最大的即可。

考虑分类讨论:

  • \(a[i]=i\),则能把 \(a[i]\) 从不好变为好 当且仅当只有一个 \(j<i\),使得 \(a[j]>a[i]\),则调换一下 \(a[j]\) 和\(i\) 后面那个小于 \(a[i]\) 的即可。

  • \(a[i]>i\) 此时只有可能把 \(i\) 和 \(a[i]\) 位置调换才有可能,判断一下即可。(这里不详说,留给读者仔细思考)

  • \(a[i]<i\) 同上

提交记录

A
B
C
D
E
F

标签:lfloor,right,frac,Codeforces,rfloor,CF1905A,915,节点,left
From: https://www.cnblogs.com/conti123/p/18342167

相关文章

  • Codeforces Round 903 (Div. 3) F. Minimum Maximum Distance
    https://codeforces.com/contest/1881/problem/F不难发现一件事情,我们这里最后的答案所在的点是1和3号点。我们有没有发现一个性质:就是这两个点都是红点间的路径上的,而且最后的答案就是最长的红点间的距离的长度除以二上取整。那么,我们怎么找到最长的红点间的距离呢?很显......
  • Codeforces Round 964 (Div. 4)
    CodeforcesRound964(Div.4)标题CodeForces1999A.A+BAgain?时限1second空限256megabytes题目描述给定一个两位数的正整数\(n\),求其数字之和。输入第一行包含一个整数\(t\)(\(1\leqt\leq90\))——测试用例的数量。每个测试用例的唯一一行包含一个两位数的正......
  • Codeforces Round 963 (Div. 2)
    Preface有懒狗上周日的比赛拖到这周日才写博客,我不说是谁这场比赛的时候因为C数组没开两倍卡了1h最后写对拍才看出来,直接心态爆炸导致D没写完掉大分A.QuestionMarks签到#include<cstdio>#include<iostream>#include<utility>#include<vector>#include<cstring>......
  • Codeforces Round 965 (Div. 2) 题解
    个人难度顺序:A<D<B<C<E。A.FindKDistinctPointswithFixedCenter如果\(k\)是偶数,构造\((x_c+i,yc+i)\),其中\(-\frac{k}{2}\lei\le\frac{k}{2}\)。对于\(k\)是奇数,先加一个点\((xc,yc)\),然后就变成偶数的情况了。B.MinimizeEqualSumSubarr......
  • Codeforces Round 965 (Div. 2) 补题记录(A,B,D,E1)
    speedforcesagain~A<E1<<B<D<<CA若\(k\equiv1(\bmod2)\),则构造\((x,y)\),\((x-1,y)\),\((x+1,y)\),\((x-2,y)\),\((x+2,y)\),\(\ldots\)。否则构造\((x-1,y)\),\((x+1,y)\),\((x-2,y)\),\((x+2,y)\),\(\ldots\)。#pra......
  • Codeforces Round 964 (Div. 4)
    这场的题不错,就是一直在inqueue......
  • Codeforces 165E Compatible Numbers 题解
    思路高维前缀和高维前缀和把数的二进制看成一个集合,二进制的每一位为\(1\)为全集\(V\)。根据题目描述,若两数\(a,b\)相容,则\(a\operatorname{and}b=0\),容易发现,\(b\in\complement_{V}a\),所以我们只需要用高维前缀和处理出\(\complement_{V}a\)的一个元素即可。......
  • Codeforces Round 964 (Div. 4)
    知识点1.对于两个数字,一个乘n,一个除以n,可以理解为n进制下的这个数乘10和除10。比如E题用这个知识点就可以很快的解决问题。题解A.A+BAgain?#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;voidsolve(){ strings; cin>>s; cout<<s[0]-'0'+s[1]-......
  • Codeforces Round 964 (Div. 4)
    CodeforcesRound964(Div.4)A送分B大意:两个人两张牌随机翻求a翻出来的牌比b大的可能#include<cstdio>#include<cmath>#include<algorithm>#include<iostream>#include<cstring>#include<vector>#defineepemplace_backusingnamespace......
  • Codeforces Round 964 (Div. 4) D. Slavic's Exam
    题目链接:https://codeforces.com/contest/1999/problem/D题目描述Slavic的考试非常难,需要您的帮助才能通过。以下是他正在努力解决的问题:存在一个字符串s,它由小写英文字母和可能零个或多个“?”组成。Slavic被要求将每个“?”更改为小写英文字母,使得字符串t成为字符串s的......