首页 > 其他分享 >[Codeforces Round 987 (Div. 2)](https://codeforces.com/contest/2031)解题报告

[Codeforces Round 987 (Div. 2)](https://codeforces.com/contest/2031)解题报告

时间:2024-11-16 12:07:26浏览次数:1  
标签:子树 contest dfrac Codeforces 27 即可 2031 quad n2

Codeforces Round 987 (Div. 2)

太好了是阳间场,我们有救了

感觉脑子生锈了qwq,F题做不出来


A

分析知如果有 \(i<j\) 且 \(a_i>a_j\) 的情况出现则 \(i\) 和 \(j\) 一定至少改一个。

所以答案即为 \(n-cnt\),\(cnt\)为众数个数。


B

发现一个数离自己原本的位置距离不会超过 \(1\),有意义的交换顶多一次。

于是做一轮满足题目限制的冒泡,最后判断是否还原即可。


C

这玩意居然浪费我 5min,吐血

偶数简单,\(1\quad 1 \quad 2 \quad 2 \quad 3\quad 3 \cdots\) 即可

奇数的话一定有一个数字出现 \(3\) 次以上。不妨记其前三次出现在 \(i,j,k\)。

\(j-i,k-j,k-i\) 均为完全平方数。即有 \(a^2+b^2=c^2\)

最小整数解为 \((3,4,5)\),所以 \(k-i\ge 25\),\(n\ge 27\)

为 $n=27 $ 构造一组解,\(>27\) 则后面偶数填满,\(<27\) 判无解即可。

就这个解居然硬控我 5min,想复杂了。

\(a_1=a_{10}=a_{26} = 1,a_{11}=a_{27}=2\),其余为偶数段。

总结:别想太多。。。


D

一开始想歪了,后面好在调整过来了。

一开始想的是单调栈,后面复杂度一分析不对。。。

所以还是辨析相似的知识点,这点很重要。

考虑到建图其实是一个无向图(两个跳法肯定对称的),于是使用并查集即可。

发现若 \(i<j\) 且 \(a_i>a_j\) 且 \(i,j\) 不相邻,则 \(\forall k\in (i,j)\) 有 \(i,k\) 满足条件或 \(j,k\) 满足条件,所以可以用链表维护相邻关系,用一个队列维护当前可以与后面合并的连通块,每次拉出来合并即可。

如果一个连通块最大值大于后一个的最小值即可合并。

最后答案为每个点所处连通块中的最大值。


E

子树之间是相互独立的,问题是把一个节点的各个子树分配到一棵二叉树里。

肯定尽量把相同大小的子树并列最优。由此得到算法:

记 \(f_u\) 为 \(u\) 及其子树搞定的需要最小深度,则:

\(f_u = 0\),当 \(u\) 为叶子

\(f_u=f_v+1\),当 \(v\) 为 \(u\) 的唯一子树

否则 \(f_u\) 为 \(u\) 的所有子树 \(f_v\) 构成可重集合 \(S\),\(S\) 依次挑出最小的 \(x,y\) 合并得到 \(z=\max(x,y)+1\),\(S\) 删去 \(x,y\) 加入 \(z\),直至剩下一个值即为 \(f_u\)。


F

构造提问以获取信息,这种题目太久没做,有点生疏了。。

考虑随便删掉两个数字,问 \(n-2\) 个,容易在 \(O(1)\) 次问出一个 \(<\dfrac n2\),一个 \(>\dfrac n2+1\) 的数对(判定即返回值为\((\dfrac n2,\dfrac n2+1)\))

记为 \((x,y)\)

然后就不会了,真是怀疑考场上的精神状态。。。

只要把剩余的两两分一组询问 \((x,y,i,j)\),则\((i,j)\) 中存在 \(\dfrac n2\) \(\iff\) 返回值存在 \(\dfrac n2\),另一边 \(\dfrac n2+1\) 同理。

最后 \(C_4^2\) 次询问找出答案即可。

只需问 \(\dfrac n2 +O(1)\) 次。


标签:子树,contest,dfrac,Codeforces,27,即可,2031,quad,n2
From: https://www.cnblogs.com/zsj6315/p/18549244

相关文章

  • CF2031
    A题意给一个单调不增序列,每次操作可以单点修,问把序列变为单调不减序列需要的最小操作次数。分析注意到事实上我们需要修改的数字非常多。考虑一个中间点\(x\),我们将所有小于\(x\)的数提升至\(x\),所有大于\(x\)的数减少至\(x\)。模拟这个过程是\(O(n^2)\)的,但我们发现......
  • Codeforces Round 987 (Div. 2)
    CodeforcesRound987(Div.2)总结A常见的套路,将一个序列变为不下降序列所需要改变的值的最小数量,考虑最大能保留多少个,显然是求最长上升子序列,而这题给出的\(a\)序列保证不上升,所以只需要考虑相同长度的一段。#include<iostream>#include<cstdio>#include<cstring>#......
  • Codeforces Round 983 (div 2)
    A.CircuitAlicehasjustcraftedacircuitwith\(n\)lightsand\(2n\)switches.Eachcomponent(alightoraswitch)hastwostates:onoroff.Thelightsandswitchesarearrangedinawaythat:Eachlightisconnectedtoexactlytwoswitches.Ea......
  • CF2031D 题解
    原题链接最后悔的一集,感觉D\(<\)everything。考虑由确定的点推出其他点的答案,发现最高点的答案是确定的,设其位置为\(x\)。然后根据题目定义,发现可以分成\([1,x-1],[x,n]\)两个区间,\([x,n]\)答案均为\(h_x\)。对于\([1,x-1]\)区间,我们找到第一个\(>[x,n]\)区间最小......
  • Solution - Codeforces 2031F Penchick and Even Medians
    飞快秒掉了,没报名痛失首杀,痛苦。简略题解:考虑先随机二元下标\((x_0,y_0)\)满足删去\((x_0,y_0)\)后查询的中位数还是\(\frac{n}{2},\frac{n}{2}+1\),那么这就说明\(p_{x_0},p_{y_0}\)一定在中位数的两边。那么还剩下的\(n-2\)个下标两两配对成\(\frac{n-2}{......
  • 2024.11.15 Codeforces Round 987(Div. 2)
    Solved:5/6Rank:74比赛链接A.PenchickandModernMonument给定一个不增序列,修改最少的数字使其不降。全都修改为出现次数最多的数即可。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;voidsolve(){intn;cin>>n;vector<int>a(n);......
  • The 2024 ICPC Asia Nanjing Regional Contest
    Preface因为最近大家都有考试啥的,实在太久没训练了,只好在成都到郑州的火车上VP了一场顶着喧闹的车厢以及电脑只能放在腿上打的巨大Debuff,成功打出7题巨大罚时不过可惜的是4h后就没出题了,剩下的C,F瞪了半天是一个不会,甚至赛后看C的题解也搞不明白,只能说计数苦手是这......
  • Toyota Programming Contest 2024#11(AtCoder Beginner Contest 379)题解总结
    AtCoderBeginnerContest379Rated:\(770\)A-Cyclic简单模拟。B-Strawberries字符串模拟,substr函数秒了C-Repeating中等模拟。思路:判断是否合法很简单,重点在计算花费。假设我们是\(0\)号点有\(N\)个棋子,然后移动到每个点上,显然花费为\(\frac{N(N+1)}{......
  • AtCoder Beginner Contest 379
    省流版A.模拟即可B.贪心,有\(k\)个就吃,模拟即可C.维护已经有棋子的格子,有多个棋子往右推,代价等差数列求和,模拟即可D.注意到植物高度=当前天-种植天,维护植物的种植天然后二分找对应高度的植物即可E.考虑最终答案每一个数位的值,然后处理进位即可F.单调栈处理建筑\(r\)......
  • Solution - Codeforces 1725K Kingdom of Criticism
    首先考虑转化一下操作\(3\)。令\(m=\lfloor\frac{l+r}{2}\rfloor\),操作\(3\)就相当于是在\([l,m]\)内的数变为\(l-1\),在\((m,r]\)内的数变为\(r+1\)。于是现在对于操作\(3\)其实就是将一个区间内的数都转为同一个值。其实对于这类将大量信息整合为一体的......