首页 > 其他分享 >CF1270 Good Bye 2019

CF1270 Good Bye 2019

时间:2024-11-06 20:19:25浏览次数:1  
标签:cnt Good 组别 sqrt le link 对角线 CF1270 Bye

Dashboard

玩构造玩的,服了。

A

拥有最大牌的必胜。link

B

若相邻的差 \(\ge 2\) 则有解,否则根据变化连续性一定无解。link

C

加两个数,第一个数为之前所有数的异或和。加进来之后异或为 0。第二个数为加完第一个数之后的和。link

D

考虑 \(k=n-1\) 时,分别询问除去每个数之后的第 \(m\) 大。若除去的数原排名 \(\le m\) 则回答的是原排名 \(m+1\) 的数,否则是第 \(m\) 的数。所以答案就是回答的值更大的回答个数。

对于原问题,只需对前 \(k+1\) 个数做上述过程。link

E

按所有点 \(x,y\) 两维坐标奇偶性分为四组。考虑两两组别之间点距离的平方除以 \(4\) 的余数,差为 \((0,0)\) 则余 \(0\),\((0,1),(1,0)\) 余 \(1\),\((1,1)\) 余 \(2\)。则同一种距离的所有边连接的组别有三种情况:1. 四个点分别连自环;2. 连正方形四条边;3. 连两条对角线。当两条对角线的组别都非空时直接一条对角线为一组。否则若一条对角线的两个组别都非空则两个组别分别为一组。再否则只剩一组,则横纵坐标除以 \(2\) 递归求解。link

F

倍数相关,考虑根分。记 \(s_i\) 为前缀和,条件可以表示为 \(r-l=k(s_r-s_l)\)。

当 \(k\le \sqrt n\),枚举 \(k\) 之后按照 \(ks_r-r=ks_l-l\) 的条件计数。

当 \(k>\sqrt n\) 时 \((s_r-s_l)<\sqrt n\),枚举 \(s_r-s_l\),然后对一个右端点就有一段符合要求的左端点,算一下有多少左端点满足区间长度是 \(s_r-s_l\) 的 \(>\sqrt n\) 倍可以了。

link

G

一个想法是在无限数轴上对每个 \(a_i\) 每个点 \(x\) 都连边 \(x\rightarrow x+a_i\),然后一种 \(a_i\) 只能走一次,如果有环就找到答案了。

然后想办法注意到 \(i-a_i\in [1,n]\)。所以只需要拉出来 \(1\sim n\),然后 \(i\) 连向 \(i-a_i\),构成基环内向树。把环找出来就行了。link

H

这就很好玩了。

想办法注意到联通块一定是连续区间。证明很简单,对于顺序对 \(i,j\),\(\forall i<k<j\),\(k\) 要么能和 \(i\) 连边要么能和 \(j\) 连边。

那么拆贡献到每个 \(i,i+1\) 是否联通。若要它们不联通,就必须没有任何一条 \([1,i]\rightarrow [i+1,n]\) 的边,也就是 \(\min[1,i]>\max[i+1,n]\)。形象化下来的答案就是从左上到右下的块数。

怎么维护这个块数:把每一块的贡献算在最大值头上。不妨添加一个 \(a_0=+\infty,a_{n+1}=-\infty\)。设最大值为 \(w\),将 \(\le w\) 的点看作 \(0\),\(>w\) 的看作 \(1\),如果 \(w\) 要成为一个块的代表元,就需要整个序列形如 \(\cdots 111000\cdots\)。

对每个权值维护其 \(01\) 序列的相邻两个位置 \(01\) 不同的位置数目 \(cnt_w\)。因为两边有无穷大和无穷小,所以 \(cnt_w\ge 1\),而符合要求的 \(cnt_w=1\),为最小值,那答案就是最小值个数。

对于一对 \(a_i,a_{i+1}\),贡献是让 \([\min(a_i,a_{i+1}),\max(a_i,a_{i+1})-1]\) 区间的 \(cnt_w\) 加 \(1\)。

用线段树维护即可。link

标签:cnt,Good,组别,sqrt,le,link,对角线,CF1270,Bye
From: https://www.cnblogs.com/HildaHu/p/18530961

相关文章

  • Features of three electronic component platforms: Findchips, JLCPCB, and ICgoodF
    Thecharacteristicsofthreeelectroniccomponentplatforms:Findchips,JLCPCB,andICgoodFindareasfollows:Findchips:Powerfulsearchanddataintegrationfunction.Itcanaggregatedatafrommajordistributors.Userscansearchforinformationonse......
  • 亿配芯城(ICGOODFIND)教你外贸(海外)推广电子元器件芯片的专用词语
    在电子元器件行业,海外推广是企业拓展市场、提升竞争力的重要手段。而在海外推广过程中,恰当运用专用词语能够准确传达产品信息、吸引客户关注,提升推广效果。本文将详细介绍亿配芯城(ICGOODFIND)电子元器件海外推广中的专用词语。一、产品描述类专用词语IntegratedCircuit(集成电......
  • 文件同步文件备份软件 Goodsync 序列号
    GoodSync是一种简单和可靠的文件备份和文件同步软件。它会自动分析、同步,并备份您的电子邮件、珍贵的家庭照片、联系人,、MP3歌曲,财务文件和其他重要文件本地-之间的台式机,笔记本电脑,服务器,外部驱动器,以及WindowsMobile设备,以及通过FTP远程,网友的WebDAV等等。该版本已内置序......
  • 亿配芯城:电子元器件芯片大全 “ICgoodFind” 的寓意
    在当今科技飞速发展的时代,电子元器件就如同构建现代科技大厦的基石一般重要。而亿配芯城(ICgoodFind),无疑是这座大厦中一颗极为耀眼的明星。亿配芯城始终致力于为客户提供最为优质、全面的电子元器件产品和服务。我们的产品线极为广泛,涵盖了集成电路、分立器件、无源元件等众多......
  • 20AB-day3 Good Subsegments
    20AB-day3GoodSubsegments题意给你一个长度为\(n\)的序列\(a\),问有多少个子区间,满足\(\sum_{i=l}^r2^{a_i}=2^x\),其中\(x\)为非负整数。原题解第一个想法:若\(2^{a_l}+2^{a_{l+1}}+\cdots+2^{a_r}=2^x\),则\(x\le\max(a_l,a_{l+1},\cdots,a_r)+\logn\)。第二......
  • 题解:CF724E Goods transportation
    可以在cnblog中阅读。题意有\(n\)座城市,第\(i\)座城市生产了\(p_i\)件货物,最多可以出售\(s_i\)件货物,编号小的城市可以向编号大的城市运输至多\(c\)件货物,问最多能出售多少货物。\(n\le10^4\)。分析乍一看是一个网络流问题,可以这样建图,令\(S\)为源点\(T\)......
  • 题解:SP7973 ACPC10E - Sometimes, a penalty is good!
    比较简单的一道数学题。思路:计算小组赛的比赛总数。longlongstage1=G*T*(T-1)/2;每组有\(T\)个队伍,每个队伍都需要与其他\(T-1\)个队伍比赛,共有\(T\cdot(T-1)\)场比赛。共有\(G\)组,因此小组赛总比赛数为\(\frac{G\cdotT\cdot(T-1)}{2}\)。计算进入......
  • CF1214G Feeling Good 题解
    题目链接点击打开链接题目解法我真菜啊,感觉每一步都不难,但一步都没想到/yun考虑两行\(x,y\)什么时候可以构造出合法的矩形?即\(x\)中需要有\(y\)对应位置为\(0\)的\(1\),\(y\)中需要有\(x\)对应位置为\(0\)的\(1\)归纳一下,\(x\)不是\(y\)的子集且\(y\)不......
  • jspGoodstuff社区购物网站8pf7x--程序+源码+数据库+调试部署+开发环境
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表用户,商品分类,商品信息技术要求:开发语言:JSP前端使用:HTML5,CSS,JSP动态网页技术后端使用SpringBoot,Spring技术主数据库使用MySQL开题报告内容一、项目背......
  • 数据同步备份软件 GoodSync 12.7.5.5 绿色版 运维神器
    下载地址:https://pan.quark.cn/s/c039278a61b0介绍GoodSync,数据同步备份软件,文件实时同步及网盘管理工具!它是一款独特同步算法的文件同步和备份软件,能实现多台电脑、电脑与云端网盘、电脑和远程FTP服务器、电脑与U盘之间的数据和文件同步转换。软件特点实时数据传输自动、计......