首页 > 其他分享 >CF1234F 题解

CF1234F 题解

时间:2023-12-29 12:44:24浏览次数:29  
标签:CF1234F 题解 texttt small 20 dp

blog。小清新题,下文 \(V=20\) 即值域。


反转操作,本质就是选两个不相交连续段拼起来。

显然合法的最终串长度一定 \(\le V\)。将这些合法串预处理出来,那么每个串都对应一个「字母集合」。

随便 DP 一下,求出所有集合中,的最大的合法「字母集合」大小。\(dp_{\small U}\) 就是只选一个连续段的答案(\(U=\small\{\texttt{a},\cdots,\texttt{t}\}\))。

那么选两个连续段就是 \(\max\limits_{s\subseteq U}dp_s+dp_{\small U\normalsize-s}\)。输出即可。

code,时间复杂度 \(O(2^VV)\),其中 \(V=20\)。

标签:CF1234F,题解,texttt,small,20,dp
From: https://www.cnblogs.com/liangbowen/p/17934640.html

相关文章

  • CF1917F Construct Tree 题解
    题目链接:https://codeforces.com/contest/1917/problem/F题意有\(n\)条长度\(l_i\)的边,问它们是否能组成一棵\(n+1\)个节点的树,使得树的直径长度为\(d\)。\(n,d\le2000\)。题解首先当然要存在一个边集\(D\),使得\(\sum\limits_{i\inD}l_i=d\),这可以使用背包......
  • 在不使用内置函数和中间变量的情况交换数字LeetCode力扣题解面试题16.01
    #异或法#Kotlin```KotlinclassSolution{  funswapNumbers(numbers:IntArray):IntArray{    numbers[0]=numbers[0]xornumbers[1]    numbers[1]=numbers[1]xornumbers[0]    numbers[0]=numbers[0]xor......
  • AT_joisc2015_h 题解
    传送门题意:给定长为\(n\)的字符串\(s\),你可以选择一个区间,将区间内的字符从小到大排序,求可以得到的最长回文子串长度,字符集大小为\(n\)。很有意思的题目。首先容易做到\(O(n^3)\)。考虑怎么优化。我们先考察排序的区间和回文区间的关系。如果两个区间无交,那么显然排序......
  • CF1835C Twin Clusters 题解
    题目链接点击打开链接题目解法很牛逼的构造题好像随也可以过长度为\(2^{k+1}\)的序列的不同区间有\(2^{2k+1}\)个,值域是\(4^k\),所以一定有解将\(a\)做一遍前缀和,那么问题转化成了找\(s_{r1}\opluss_{l1-1}=s_{r2}\opluss_{l2-1}\)先讲一讲具体做法:按照前\(k\)......
  • ICPC2021Kunming G Glass Bead Game 题解
    QuestionICPC2021KunmingGGlassBeadGame有\(n\)个玻璃珠,\(B_1,B_2,\cdots,B_n\)每一步你可以选择一个\(B_i\)移道第一个位置上,花费的代价为操作前\(B_i\)前面的玻璃珠的个数。已知每一步选择玻璃珠\(B_i\)的概率\(p_i\),问当\(m\rightarrow\infty\)时,在第\(......
  • ICPC2021Kunming G Find the Maximum 题解
    QuestionFindtheMaximum给出一个树,每个点有一个权值\(b_n\),求一条树上路径\(V\),要求\(\frac{\sum_{u\inV(-x^2+b_ux)}}{|V|}\)最大,其中\(x\)是自己选择的一个树Solution先转化一下\(\frac{\sum_{u\inV(-x^2+b_ux)}}{|V|}\),得到\[\frac{\sum_{u\inV(-x^2+b_......
  • vue前端node内存溢出问题解决
    前端项目运行时,如果经常运行慢,崩溃停止服务,报如下错误:FATALERROR:CALL_AND_RETRY_LASTAllocationfailed-JavaScriptheapoutofmemory(JavaScript堆内存不足) 原因:因为在Node中,通过JavaScript使用内存时只能使用部分内存(64位系统:1.4GB,32位系统:0.7GB),这个时候,如......
  • openssh升级对应问题解决方案
    问题1:./openssl:errorwhileloadingsharedlibraries:libssl.so.1.1:cannotopensharedobjectfile:Nosuchfileordirectory解决方案:cp/usr/local/openssl1.1.1/lib/libssl.so.1.1/lib64/cp/home/tydl/openssl-1.1.1u/libcrypto.so.1.1/lib64/ 问题2:/etc/ssh/s......
  • 「题解」Codeforces 1427G One Billion Shades of Grey
    感谢127的指导/ll\(|h_u-h_v|=\max(0,h_u-h_v)+\max(0,h_v-h_u)\),那么可以把它看成这样的问题:\[\min\{\sum_{(u,v)}\max(0,h_u-h_v+w_{u,v})c_{u,v}\}\]对偶一下,问题就变为:如果两个格子相邻就互相连容量为\(c_{u,v}=1\),费用为\(w_{u,v}=0\)的边,跑最大费用循环流。为了限......
  • 「题解」P9747 「KDOI-06-S」签到题
    一个区间合法的充要条件是存在\(x\)满足其为区间按位或,并且《\(x\)左侧所有数或起来》《\(x\)右侧所有数或起来》二者有其一为\(x\)。扫描线扫右端点,不同的按位或将左端点分为\(\logA\)个区间,对于每个区间\([l,r]\)先在区间按位或\(v\)在序列中存在位置的vector中......