当前位置:网站首页>【8.8】代码源 - 【不降子数组游戏】【最长上升子序列计数(Bonus)】【子串(数据加强版)】
【8.8】代码源 - 【不降子数组游戏】【最长上升子序列计数(Bonus)】【子串(数据加强版)】
2022-08-10 01:54:00 【ZhgDgE】
#886. 不降子数组游戏
题意:
题解:(分块/三分) 代码源每日一题Div1 不降子数组游戏
思路:首先,先手选了一个点,后手必定要选 L , R L,R L,R 其中的一个,这样才能使分数最大。那么把我们选择的点的下标作为自变量,分数作为因变量,这个函数是一个下凸函数(不会证),三分出极值点即可。
问题转化为,给定区间 [ l , r ] [l,r] [l,r] 问这个区间的分数。我们对原序列进行分块,划分为若干非降子区间。子区间内部一个长度为 l e n len len 的子区间的分数是 l e n ( l e n + 1 ) 2 \frac {len(len+1)}2 2len(len+1) ,那么我们对块预处理前缀和,以及预处理每个元素所在块的编号,以及左边界右边界。我们询问一个区间 [ l , r ] [l,r] [l,r] ,分数就是区间内的整块的区间分数和加上两个残块的分数。
AC代码:http://oj.daimayuan.top/submission/326684
#884. 最长上升子序列计数(Bonus)
题意:求最长上升子序列的个数。区间长度 n ( 1 ≤ n ≤ 4 ⋅ 1 0 5 ) n(1\leq n\leq 4\cdot 10^5) n(1≤n≤4⋅105) 。
题解:(DP/线段树/树状数组)最长上升子序列计数(Bonus)
思路:可以权值线段树或树状数组。我用的树状数组。
定义 l e n ( i ) len(i) len(i) 表示以 a i a_i ai 结尾的 LIS 长度, c n t ( i ) cnt(i) cnt(i) 表示对应的 LIS 方案。转移: l e n ( i ) = 1 + max j < i , a j < a i l e n ( j ) , c n t ( i ) = ∑ j < i , l e n ( j ) + 1 = l e n ( i ) c n t ( j ) len(i)=1+\max_{j<i,a_j<a_i}len(j),cnt(i)=\sum_{j<i,len(j)+1=len(i)}cnt(j) len(i)=1+maxj<i,aj<ailen(j),cnt(i)=∑j<i,len(j)+1=len(i)cnt(j)
对于 a i a_i ai ,我们要找到 a j ( j < i , a j < a i ) a_j(j<i,a_j<a_i) aj(j<i,aj<ai) 的信息,这个信息可以按照值域为下标存到树状数组,然后查询前缀信息。那么我们就需要查询值域前缀的最大值,以及最大值的对应计数。这个需要树状数组维护二元组。
树状数组维护前缀最大值以及前缀最大值的计数:
struct trie{
int n;
int tr[N], tr2[N]; // tr 是前缀最大值, tr2 是前缀最大值的计数
void init(int n){
this -> n = n;
rep(i, 0, n) tr[i] = tr2[i] = 0;
}
void add(int x, int k, int c){
for(int i = x; i <= n; i += i & -i){
if(tr[i] < k) tr[i] = k, tr2[i] = c;
else if(tr[i] == k) tr2[i] = (tr2[i] + c) % p;
}
}
PII query(int x){
PII res = {
0, 0};
for(int i = x; i ; i -= i & -i){
if(res.fi < tr[i]) res.fi = tr[i], res.se = tr2[i];
else if(res.fi == tr[i]) res.se = (res.se + tr2[i]) % p;
}
return res;
}
};
AC代码:http://oj.daimayuan.top/submission/326785
#922. 子串(数据加强版)
题意:给定一个长度为 n ( 1 ≤ n ≤ 2500 ) n(1\leq n\leq 2500) n(1≤n≤2500) 的 01 01 01 串,问有多少种划分,使得每一个划分出来的子串的 1 1 1 的个数组成的序列是回文的,答案对 998244353 998244353 998244353 取模。
题解:(插板法)代码源每日一题 Div1 子串(数据加强版)
思路:原题的数据可以用区间 DP 来做。用双指针优化,左指针从左到右枚举划分点,右指针滑动到对应点,然后统计。
题解则是用组合计数。
AC代码:边界不好搞,没有AC。
边栏推荐
- Screen 拆分屏幕
- Unity reports Unsafe code may only appear if compiling with /unsafe. Enable “Allow ‘unsafe’ code” in Pla
- 空间复杂度为O(1)的归并排序
- 【论文粗读】(NeurIPS 2020) SwAV:对比聚类结果的无监督视觉特征学习
- Initial attempt at UI traversal
- 《GB39732-2020》PDF下载
- 【wpf】拖拽的简单实现
- volatile 关键字(修饰符 volatile 告诉编译器,变量的值可能以程序未明确指定的方式被改变)
- 你有对象类,我有结构体,Go lang1.18入门精炼教程,由白丁入鸿儒,go lang结构体(struct)的使用EP06
- 中英文互译在线翻译-在线翻译软件
猜你喜欢
sqlmap dolog外带数据
OpenCV图像处理学习四,像素的读写操作和图像反差函数操作
高并发+海量数据下如何实现系统解耦?【下】
Deep Learning (5) CNN Convolutional Neural Network
[Turn] Typora_Markdown_ picture title (caption)
In automated testing, test data is separated from scripts and parameterized methods
【SSRF漏洞】实战演示 超详细讲解
LeetCode 每日一题——1413. 逐步求和得到正数的最小值
通关剑指 Offer——剑指 Offer II 012. 左右两边子数组的和相等
xss的DOMPurify过滤框架:一个循环问题以及两个循环问题
随机推荐
xss的DOMPurify过滤框架:一个循环问题以及两个循环问题
Unity reports Unsafe code may only appear if compiling with /unsafe. Enable “Allow ‘unsafe’ code” in Pla
如何让数据库中的数据同步
小程序开发的报价为什么有差别?需要多少钱?
type-C 边充电边听歌(OTG) PD芯片方案,LDR6028 PD充电加OTG方案
Under pressure, there must be cowards
SQL注入的order by ,limit与宽字节注入
In the 2022 gold, nine, silver and ten work tide, how can I successfully change jobs and get a high salary?
Experimental support for decorators may change in future releases.Set the "experimentalDecorators" option in "tsconfig" or "jsconfig" to remove this warning
Janus actual production case
高压之下,必有懦夫
Maya制作赛博朋克机器人模型
T5:Text-toText Transfer Transformer
微生物是如何影响身体健康的
月薪35K,靠八股文就能做到的事,你居然不知道
OpenCV图像处理学习二,图像掩膜处理
夏克-哈特曼波前传感器
sqlmap dolog外带数据
多线程之自定义线程池
【引用计数器及学习MRC的理由 Objective-C语言】