首页 > 其他分享 >CF2001 题解

CF2001 题解

时间:2024-11-06 19:08:21浏览次数:1  
标签:le 题解 sum 位置 构造 CF2001 pop 操作

A

给定循环数组,每次操作时,设当前大小为 m。
选择 $i\in [0,m)$,若满足 $a_i\le a_{i+1\bmod m}$,则可删除 $a_i,a_{i+1 \bmod m}$ 中的任意一个。
求最小的操作次数,使得数组中所有元素都相等。
$n\le 100$

操作非常强,除了两个相邻位置相等的情况,可以删除任意元素。
然而所有位置都相等正好是我们需要的答案,所以答案既是 n 减去众数的数量,卡到了上界。
代码

B

对于一个排列 p,你要访问它的每个位置。
具体来说,你要一次访问 $1,2\cdots n$。
现在有两种方式,方式一起点在 1 位置,只能往右走,方式 2 起点在 n 位置,只能往左走。
当无法通过移动走到下一个位置时,就要回到起点。
给你 $n$,构造一个排列,使得两种方式回到起点的次数相等,或输出无解。
$n\le 10^5$

有人想 dilworth 想假了我不说是谁。

容易计算出两种方式回到起点的次数,发现是方式一是对所有 \(pos_{x+1}<pos_{x}\) 的 x 计数,方式二同理。
容易发现两种方式加起来的次数是 \(n-1\),故偶数时无解。
那么奇数时是好构造的,只需两侧对称排列即可,形如 \(1,3,5\cdots 6,4,2\) 即可。
代码

C

交互题。
有一棵树,已知树的大小,你要在不超过 $15n$ 次询问内得到树的结构。
每次可以询问两个点,得到它们的中点,若路径长度为奇数则返回靠近第一个点的那个点。
$n\le 1000$

容易想到分治的做法。
考虑到不断询问一个点到根的路径即可。
对于之前已确定的点打上标记,若询问到打标记的点就跳过,这样就能保证复杂度了。

这个做法在链上时最劣,可以卡到 \(\mathcal O(n\log n)\)。
代码

D

给定原序列,要求选出一个极长的,元素至多出现一次的子序列。
最小化该子序列所有奇数位置乘上 -1 后的字典序。
$n\le 10^5$

提供两种想法:
每次贪心选择最答案中的第一个位置。
只需考虑不能让当前未选元素无法选择,即选择元素的位置必须不大于所有剩余元素的最后一个位置。
区间最值即可,再加一个能维护删除和全局最值得的结构。

每次考虑当前位置是否能放到答案中。
可以用栈做到线性,只需弹栈并维护每个元素的最后位置,正确性是显然的。
注意考虑可能可以一次弹两个元素。

有很多设计的方法,本质上在于最优子结构的性质太强了。

E Easy Version

有一个大根堆,但是是满二叉树,给定树高 $n$。
一次 pop 操作形如:从根节点开始,每次选择两个儿子中权值较大的那个进行交换(若两个儿子权值相等则这次 pop 操作不确定),直到到达叶子。
一个堆是确定的,当且仅当对其进行一次 pop 操作,该操作确定。
一个堆是可构造的,当且仅当它可以通过如下方式构造出:
所有位置初始都是 0,任选恰好 k 个点进行根链加一。
不难证明通过该过程构造出的堆满足大根堆的性质。
给定 $n,k$ 和质数模数 $p$,对于可构造和确定的堆进行计数。
$n\le 500,k\le 500,10^8\le p\le 10^9$

很复杂的定义,但是注意到构造过程的影响。
容易发现一个点的权值由其子树内的操作次数决定。
于是可以考虑进行子树内操作步数分配的 dp:
定义 \(f_{i,j}\) 表示在高为 \(i\) 的堆中进行 \(j\) 次操作的合法堆个数。
转移考虑枚举左右儿子的操作步数分配:
由于小的那个儿子不用管,所以可以任意分配,方案数形如一个插板,故设 \(sz(i)=2^{i}-1\)。
\(f_{i,j}=2\sum\limits_{k=1}^{j}f_{i-1,k}\sum\limits_{p=0}^{\min(k-1,j-k)}\binom{sz(i-1)+p-1}{sz(i-1)-1}\)。
这样转移是 \(\mathcal O(nk^{3})\) 的,考虑优化。
右面这个组合数看起来很好合并,考虑组合意义有如下式子:
\(\sum\limits_{i=0}^{m}\binom{n+i}{n}=\binom{n+m+1}{n+1}\)。
(只需考虑枚举分配方案的最后一个位置是什么)。
故直接优化可做到 \(\mathcal O(nk^{2})\)。
组合数的计算用 lucas,或者用 \(\binom{n}{m}=\frac{n}{n-m}\binom{n-1}{m}\) 递推即可。
代码

E Hard Version

[Luogu](https://www.luogu.com.cn/problem/CF2001E2)
有一个大根堆,但是是满二叉树,给定树高 $n$。
一次 pop 操作形如:从根节点开始,每次选择两个儿子中权值较大的那个进行交换(若两个儿子权值相等则这次 pop 操作不确定),直到到达叶子,最后把叶子设为 -1。
一个堆是确定的,当且仅当对其连续进行两次 pop 操作,该操作确定。
一个堆是可构造的,当且仅当它可以通过如下方式构造出:
所有位置初始都是 0,任选恰好 k 个点进行根链加一。
不难证明通过该过程构造出的堆满足大根堆的性质。
给定 $n,k$ 和质数模数 $p$,对于可构造和确定的堆进行计数。
$n\le 100,k\le 500,10^8\le p\le 10^9$
思路解析
正解

考虑到 Easy Version 的做法,想到去进行子树分配式的递推。
由于这部分的转移跟二阶儿子有关,所以记 \(f_{i,j,k},g_{i,j},h_{i,j,k}\) 分别表示树高 \(i\) 层,子树内分配即根节点权值为 \(j\),较大的那个儿子为权值为 \(k\) 的一次确定堆,任意堆,二次确定堆方案数。

\(g\) 的值为组合数,\(f\) 的值只需在 Easy Version 的基础上稍加转移即可。
考虑 \(h\) 的转移,要不然是在同一个子树上操作两次,要不然是各操作一次,故可列出转移式:
\(h_{i,j,k}=2g_{i-1,j-k}\sum\limits_{p=j-k+1}^{k}h_{i-1,k,p}+2\sum\limits_{t} f_{i-1,j-k,t}\sum\limits_{p=0}^{j-k-1} f_{i-1,k,p}\)。
直接前缀优化就可做到 \(\mathcal O(nk^{2})\)。

实现细节

代码

标签:le,题解,sum,位置,构造,CF2001,pop,操作
From: https://www.cnblogs.com/Sugar-Cube/p/18530874

相关文章

  • 暂存的题解
    P4011孤岛营救问题感觉其实我能想出来,但是对难题产生了恐惧,直接看题解了,确实简单,很抱歉浪费了一道题。数据范围很小,搜索bfs,钥匙直接状态压缩,找到答案立即返回,否则就无解。我们要彻底的分析问题,为什么我想不到,以后我要怎么总结,首先看到题之后要先看数据范围,看到数据范围非常小......
  • [USACO22JAN] Minimizing Haybales P 题解
    [USACO22JAN]MinimizingHaybalesP随机化?五分。显然对于任意\(a_i,a_j\),若\(|a_i-a_j|>K\),则这两堆草的先后顺序永远不会改变。所以易得暴力:对于所有这样的\(i,j\),不妨设\(i<j\),则连一条\(i\toj\)的边,答案就是这个图字典序最小的拓扑排序,优先队列即可。voidtoposort(......
  • [USACO21DEC] Tickets P 题解
    [USACO21DEC]TicketsP首先我们思考暴力的\(O(n^2)\)怎么做。显然比起每次以\(i\)为起点跑\(n\)遍最短路,建反图后分别以\(1\)和\(n\)为起点跑两遍最短路是更加经济的方式。然后你可能会以为\(\text{dis}(1,i)+\text{dis}(n,i)\)就是答案了,之后你就会发现连样例都过......
  • 【问题解决】java.lang.SecurityException: JCE cannot authenticate the provider BC
    问题复现历史项目升级JDK(由1.7升级到8),进行加密/解密时出现报错java.lang.SecurityException:JCEcannotauthenticatetheproviderBC。问题原因Wikipa上查到JCE的描述如下:JavaCryptographyExtension(JCE)isanofficiallyreleasedStandardExtensiontotheJavaPl......
  • 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间
    问题复现项目上历史项目为解决漏洞扫描从Tomcat6.0升级到了9.0版本,服务启动的日志显示如下警告,数据源是通过JNDI方式在server.xml中配置的,控制台上狂刷无法找到表空间的错误(没截图)报错:06-Nov-202410:32:03.701警告[main]java.util.ArrayList.forEachName=数据源Proper......
  • CF1909题解
    CF1909A一眼秒之题,我们发现就是四个方向选三个方向,若是存在一个点它的方向恰好在(0,0)点的另外一个方向,则一定不成立枚举4个方向,发现有点在这个方向,显然选除这个点之外的三个方向的方案就不可行点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=105;int......
  • 题解:P7082 [NWRRC2013] Dwarf Tower
    涉及知识点:动态规划。解题思路设\(dp_i\)为得到\(i\)最小的花费。可以得到转移方程:\(dp_{a_i}=\min(dp_{x_i}+dp_{y_i},dp_{a_i})\)。很明显最多迭代\(n\)次,还需要再外面套一个循化即可。但是有些OJ没有洛谷跑得快,所以需要加一点优化。如果当前循环没有更新......
  • 【题解】CF1956
    CF1956A简要题意有\(n\)个人玩一个游戏,把这\(n\)个人分别编号为\(1\)到\(n\)。每一轮,编号为\(a_1,a_2,\ldots,a_k\)(\(a\)序列递增)的人会被踢出这个游戏,剩下的人会补齐空位并重新从\(1\)开始编号。当某一轮没有人被踢出时,游戏结束,剩下没有被踢出的人成为......
  • “SSL 证书验证失败”问题解决方法“urllib.error.URLError: <urlopen error [SSL: CER
    第一部分:问题描述第二部分:解决方法错误的代码:dataset_train=datasets.MNIST('../data/mnist/',train=True,download=True,transform=trans_mnist)dataset_test=datasets.MNIST('../data/mnist/',train=False,download=True,transform=trans......
  • P6667 [清华集训2016] 如何优雅地求和 题解
    一道非常有启发性的题目。思路考虑对于一个给出点值的多项式函数如何处理。我们发现,对于一个\(m\)次多项式\(f(x)\),由于\(\binom{x}{i}\)为\(i\)次多项式,所以说我们必定可以把一个多项式函数写成如下模样:\[F(k)=\sum_{i=0}^m\binom{k}{i}f_i\]可以看出,\(f_i\)实际上......