首页 > 其他分享 >【题解】「NOIP2024模拟赛24 T2」子序列们

【题解】「NOIP2024模拟赛24 T2」子序列们

时间:2024-11-08 20:08:53浏览次数:1  
标签:24 题解 元素 T2 序列 删去 dp

【题解】「NOIP2024模拟赛24 T2」子序列们

https://www.becoder.com.cn/contest/5715/problem/2


\(\mathcal{Description}\)

给定一个 0/1 串 \(a\),你需要生成一个长度为 \(n\) 的序列 \(b\),其中 \(b_i\) 为 \(a\) 的一个子序列,且满足:

  1. \(|b_i|=n-i+1\);
  2. \(\forall i\in(1,n]\),\(b_{i}\) 是 \(b_{i-1}\) 的子序列。

求 \(b\) 本质不同的个数。


\(\mathcal{Solution}\)

题目其实就是要我们确定每个元素的删去时间,这个时间是一个排列。

(当然,我们不能直接用 \(n!\) 然后去重,因为去重的时候仍涉及某个部分的方案数,所以不如直接面对本质不同的方案数。

考虑什么时候会出现重复。

当存在两个相同值的元素相邻的时候就选其中一个和其她是完全相同的。

所以我们钦定,出现这种情况的是后必定先取前面的。

怎么刻画这件事情?

Motivation: 上面这种情况有可能在删去某一个元素后新出现,比如 101 中删去 0。

所以,我们考虑的因素应该包含:删去时间、元素值。

设 \(i\) 的删除时间为 \(t_i\)。

于是,我们钦定的要求也就等价于:对于一个 \(i\),\(j\) 是 \(i\) 左边第一个 \(t_j>t_i\) 的元素,那么需要满足 \(a_j\ne a_i\)。


考虑 dp。

时间实际上是和 \(|b_i|\) 息息相关的,我们可以不用在状态里面考虑。

考虑区间 dp。

设:\(f_{i,j}\) 表示将 \([i,j]\) 删除到只剩一个元素时,或者说确定了这个区间内所有元素的 \(t_i\),满足 \(t_{j+1}>t_k,k\in[i,j]\)(将 \(t_{j+1}\) 换成 \(t_{i-1}\) 是等价的。

dp 转移的时候需要满足一些条件?那就在状态里面做手脚。

此时枚举,区间中最后被删去的元素 \(k\),那么她一定不能等于 \(a_{j+1}\),剩下就分成了完全独立的两个子区间。

那么这样就有转移:(规定 \(a_{n+1}\ne 0/1\)

\[f_{i,j}=\sum_{k=i}^j {j-i\choose k-i}f_{i,k-1}f_{k+1,j}[a_{k}\ne a_{j+1}] \]

标签:24,题解,元素,T2,序列,删去,dp
From: https://www.cnblogs.com/CloudWings/p/18535856

相关文章

  • 题解:P11266 【模板】完全体·堆
    也算是对pb_ds库中的优先队列各种操作的科普?一些碎碎念提醒:你可以不看这部分,这部分算是作者探索未知功能的过程平常写优先队列的时候一般用不到对值进行修改或者删除的操作,所以我在看这到题的时候在想怎么才能实现题目中的操作,因为我不知道有什么成员函数可以直接获取具体哪......
  • NOIP2024模拟赛 #17 总结
    省流:T1对\(998244353\)取模,T2对\(mod\)取模,T3求排名,T4对\(10^9+7\)取模。比赛出锅不少。开T1,发现并没有前几天那么简单,对着题目盯了\(1\)h毫无思路,发现没看见所有高塔的高度两两不同这个条件,看到后略有思路,但是还不太行。后来说大样例出锅了,幸好没写。T2很......
  • 启明云端&触觉智能与您相约2024年慕尼黑国际电子元器件博览会,不见不散!
    2024德国慕尼黑国际电子元器件博览会(Electronica2024)是全球规模最大、最具影响力的电子元器件展会之一。此次展会将于2024年11月12-15日在德国·慕尼黑展览中心隆重举行,汇聚来自全球电子行业领军企业和创新者,展示最前沿的技术成果与设计产品,为全球电子行业的发展提供一个交流和合......
  • Hive3.1.2搭建文档包含详细步骤及相关截图以及常见问题解决
    hive-3.1.2分布式搭建文档1、下载,上传,解压,配置环境变量#1、解压(解压到上级目录)tar-zxvfapache-hive-3.1.2-bin.tar.gz-C..#2、重名名mvapache-hive-3.1.2-binhive-3.1.2#3、配置环境变量vim/etc/profile#4、在最后增加配置exportHIVE_HOME=/usr/local/......
  • 2024.0902模拟赛反思总结
    09:00~09:20终于想出来了之前没考虑到的特殊情况,把困扰多时的\(R\)题做出来了,美滋滋。09:20~10:35突然的一场考试,看到\(A\)题先写了一份暴力,测了一下\(10^{12}\)和\(10^{12}-1\),成功炸掉。思考了很久优化,把特殊情况判了一下,没头绪就去做\(B\)题了。10:35~10:50\(B\)......
  • 2024.0906模拟赛反思总结
    08:56~09:10先总体看了一遍题目,\(A\)题没思路,\(B\)题模拟,\(C\)题似乎是个\(dp\),\(D\)题一眼原题,果断选择倒开。\(D\)题因为原题的缘故过于自信,导致没有对拍测大样例,没看数据范围以为是跟以前的题一模一样,导致RE\(30\)分。09:10~09:25接着去写模拟,一开始在想链表模拟......
  • 2024.0905模拟赛反思总结
    08:59~09:50老师今天怎么提前一分钟发题。先总体看了一遍题目。\(A\)题原题分讨,\(B\),\(C\),\(D\)题赛时觉得都是搜索(其实\(C\)题递推,\(D\)题\(dp\))。\(A\)题跟之前做的换了一种写法,开始看错题了,调了很久,后面细节没处理好,挂了\(26\)分。09:50~11:00\(B\)题我写的......
  • 2024.0904模拟赛反思总结
    9:00~9:25老师不发卷是在考验我们的心态吗。9:25~10:00总体看了一眼题目,\(A\)题貌似做过,\(B\)题推公式,\(C\)题简单最短路,\(D\)题构造。\(A\)题一开始我想的全部设为\(0\),算汉明距离从后往前调整\(1\),赛时写挂了,赛后发现两个字符串的汉明距离实时调整的时候写错了。10:......
  • 2024.0903模拟赛反思总结
    09:00~09:40总览了一遍题目,\(A\)题基础题,\(B\)题\(dp\),\(C\)题没头绪,\(D\)题推公式题。\(A\)题先打了个暴力,测大数据炸了,只能\(50\)分,试了一些邪门的优化,还是炸了,就去做\(B\)题了。09:40~10:30\(A\)题先写了一个\(O(N^2\timesQ)\)的\(dp\),因为是连续的一段区......
  • 20222311 2024-2025-1 《网络与系统攻防技术》实验四实验报告
    1.实验内容1.1恶意代码文件类型标识、脱壳与字符串提取对提供的rada恶意代码样本,进行文件类型识别,脱壳与字符串提取,以获得rada恶意代码的编写作者,具体操作如下:(1)使用文件格式和类型识别工具,给出rada恶意代码样本的文件格式、运行平台和加壳工具;(2)使用超级巡警脱壳机等脱壳软件,......