首页 > 其他分享 >CF Round 982(Div 2)

CF Round 982(Div 2)

时间:2024-11-07 20:19:21浏览次数:1  
标签:frac 982 CF 中位数 leq 即可 如果 Div 配对

游记

还是VP
口胡了ABCD的做法,然后C假了
打代码其实挺难的

题解

A

反复观看样例可知,如果两个开关状态不一样灯泡开,否则灯泡关
如果要灯泡开着的尽可能少,那么相同状态的配对尽可能多
此时就是\(0\)和\(0\)配对,\(1\)和\(1\)配对,
如果有落单的\(0\)必定有落单的\(1\),最多凑\(1\)对
没有就是\(0\)
反之要灯泡开得多,那么\(0\)和\(1\)的配对尽可能多
此时答案就是min(cnt[0],cnt[1])
其中cnt[i]就是满足\(a_j=i\)的\(j\)的个数

B

如果从数组中删掉\(k\),那么数组就会变成两半
这两半中,左半边不管怎么分,各部分中位数必然小于\(k\)
因为最大数都小于\(k\)了中位数肯定小于最大数小于\(k\)
同理右半边不管怎么分,各部分中位数必然大于\(k\)
那如果各部分中位数组成的数组,这个中位数如果是\(k\)的话
其实只需要两边划分出相同的段数即可
如果左右两边都是偶数个元素,那就各分成两个奇数的段
此时\(k\)为奇数
否则两边都不用动,就一整段,此时\(k\)为偶数
唯一需要考虑的就是一半边为空的情况
此时只有另一半边也为空才行
也就是无解判断:
\(k=1\)或\(k=n\),且\(n\not=1\)时无解
如果\(n=1\)那就得特判出去,很简单

C

对于能否构成三角形来说,
如果两个小边加起来大于最大的边,那必然可以构成三角形
所以如果钦定\(a_i\)为最大值
首先大于\(a_i\)的要被赋成\(a_i\)
然后如果\(\exists j,k,a_j\leq \frac{a_i}{2},a_k\leq \frac{a_i}{2}\)
那么显然\(a_j+a_k\leq a_i\)就寄了
所以至多存在唯一的\(j,a_j\leq \frac{a_i}{2}\)
然后就是对\(a\)排个序先,
枚举每个\(a_i\),找到值域在\([\frac{a_i}{2},a_i]\)的最大下标区间
两个下标lower_bound()/upper_bound()一下即可
不在这个区间范围的都要改成\(a_i\)
取改的次数的最小值即可,这个显然可以\(O(1)\)算出来
枚举\(a_i\)二分的复杂度\(O(n\log n)\)
排序时间复杂度\(O(n\log n)\)
总时间复杂度\(O(n\log n)\)
写法在下取整和二分的时候挺麻烦的,有些细节要注意

D

首先,如果\(i\geq j\),必然有\(p_i\geq p_j\)
其次,这棵树切开\(0\)以后必然是若干条链
这样的话首先考虑同一层的节点\(i\)和\(j\)
记\(c_i\)为切掉\(0\)以后的链顶编号
如果\(c_i+1<c_j\),并且\(i,j\)同层
那么中间空着的这么几条链必然不可能连上任何大于\(j\)的节点
否则\(k>j,p_k<p_j\)显然会寄
也就是说,可用的链顶\(c_i\)这个集合的元素只出不进
那么就直接找链顶有多少即可
显然由于BFS序的关系,\(c_i\in [1,l-1],p_l=1\)
也就是说我们直接找到\(l\)即可求出\(c\)
然后对于每个\(i\),如果确定了\(i\)对应的链顶\(c_i\)
直接问\(c_i+1\)和\(i+1\)的关系
如果\(c_i+1\not=c_{i+1}\)直接把\(c_i+1\)扔出去
如果找到了对应的\(c_i\)维护\(c_i\)这条链底下编号最大的元素更新即可
注意如果只剩下了\(l-1\)那就不用问了

标签:frac,982,CF,中位数,leq,即可,如果,Div,配对
From: https://www.cnblogs.com/2K22/p/18533783

相关文章

  • CF Round 984 C. Anya and 1100(模拟)
    传送门https://codeforces.com/contest/2036/problem/C解题思路先扫一遍字符串,判断有几个1100子串。然后,对于每一次操作,可以算出对答案的影响,减去更改会减少的子串,再加上更改后会增加的子串。代码#include<bits/stdc++.h>usingnamespacestd;chars[200001];intq......
  • 雷达目标检测cfar小白版本
     一编2024.11.7日 目前只是简单概念后续持续更**参考单元**和**保护单元**的概念###1.什么是保护单元?**保护单元**是指在检测过程中,紧邻目标检测单元的几个位置(也称距离单元)。这些单元的作用是**防止目标信号影响噪声估计**。例如,如果我们想在位置\(i\)检测......
  • Codeforces Round 982 (Div. 2)(A~C)
    对dp还不是特别熟练只做到了C(还是太菜了),开始前刚好各种事情来了,vp晚了10多分钟开才始做题,喜提排名(不是)3000+,后面有时间就尽量把dp补掉A.RectangleArrangement你需要在一个无限的方格网格上涂色,所有格子最初都是白色的。为了完成这项任务,你有\(n\)个印章。每个印章是一个......
  • 【题解】CF1944
    CF1944A简要题意给定完全图删k条边使得从一号点开始的可达点最少Solution注意到最多需要删n-1条边就可以使得任意一个其他点都到达不了又注意到只要删的边少于n-1就可以从一号点走出去,主要走出去就可以走到任何点所以这题答案只有两种如果k≤n-1答案为n否则答案为1......
  • SpringBoot图片创作分享平台的设计与实现7l7cf 文末可获取,系统界面在最后面。
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表系统内容:用户,图片橱窗开题报告内容一、选题理由随着互联网技术的飞速发展和社交媒体的普及,图片已成为人们日常交流和分享的重要载体。然而,当前市场上的图片分......
  • CF 口胡笔记 2200Ct辑
    ¿如何搞笑高效做题?只需要口胡CF题就行啦!(从前天起口胡CF按照洛谷通过人数排序的题单这期我们来口胡CF2200Part1吧~CF617EXORandFavoriteNumber给定一个长度为\(n\)的序列\(a\),然后再给一个数字\(k\),再给出\(m\)组询问,每组询问给出一个区间,求这个区间......
  • CF1270 Good Bye 2019
    Dashboard玩构造玩的,服了。A拥有最大牌的必胜。linkB若相邻的差\(\ge2\)则有解,否则根据变化连续性一定无解。linkC加两个数,第一个数为之前所有数的异或和。加进来之后异或为0。第二个数为加完第一个数之后的和。linkD考虑\(k=n-1\)时,分别询问除去每个数之后的第\(......
  • CF 1438 题解
    CF1438题解ASpecificTastesofAndre考虑一种非常简单的构造:\(a_i=1\).不难发现满足条件.BValeriiAgainstEveryone结论:符合条件当且仅当有两个一样的元素.证明:充分性显然,下证必要性.若不存在两个一样的元素,则由于无法进位,故没有办法得到两个区间和在相......
  • Educational Codeforces Round 161 (Rated for Div. 2) - VP记录
    Preface先被A题硬控\(20\)分钟,有点不爽。又看到E题AC的人比D题多而去嗑E题去了,结果D题反而是我更能做的。将问题排序:根据你所需付出的努力,将能够最快解决的问题排在前面。(答题的次序为:以前做过的,容易的,不熟悉的,难的)——李博杰《骗分导论》\(\rmP_{114}\)所以......
  • CF963-Div2-E. Xor-Grid Problem
    CF963-Div2-E.Xor-GridProblem题意给定一个\(n\timesm\)的矩阵\(a\),有两种操作:选择一行,把每个数变成所在列所有数的异或之和。选择一列,把每个数变成所在行所有数的异或之和。求进行任意次操作后整个矩阵最小的美丽值。思路第一个发现:同一数异或两次相当于没有异......