太好了是阳间场,我们有救了
感觉脑子生锈了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