当前位置: 首页 > news >正文

DP 基础题乱做

恶补基础 DP.

CF1061C 多样性

转移是经典的子序列 DP,考虑前 \(i\) 个数,子序列长度为 \(j\) 的方案数. 转移:

\[f_{i,j}=\begin{cases} f_{i-1,j-1}+f_{i-1,j}&j\mid a_i\\ f_{i-1,j}&otherwise. \end{cases} \]

可以滚动数组优化一维. 考虑优化,第二种转移直接继承,第一种转移不必枚举 \(j\),可以 \(O(\sqrt v)\) 处理出所有约数,从大到小转移(与 \(0/1\) 背包原理类似). 总时间复杂度 \(O(n\sqrt v)\).

CF2121H 冰宝贝

看到范围是区间,一个直接的想法是离散化. 然而我们可以换维,直接把值域当做 DP 值,把子序列长度开一维状态来记录. 另一个贪心的想法是我们一定要让子序列末尾尽量小,于是设计出一个状态:\(f_{i,j}\) 表示考虑前 \(i\) 个区间,不降子序列长度为 \(j\) 时末尾最小值,转移:

\[f_{i,j}=\begin{cases} f_{i-1,j-1}&l_i\le f_{i-1,j-1}\le r_i\\ f_{i-1,j} &otherwise. \end{cases} \]

优化仍然可以先滚动一维. 从 \(f\) 下标的角度看转移,就是区间 \([l_i,r_i]\) 整体右移了一位. 若当前最长子序列的末尾不大于 \(r_i\),右移后不会有重叠的位置,最长子序列 \(+1\). 否则存在一个位置 \(p\) 重叠,考虑保留哪个更优. 注意到 \(f_j\) 显然不降,于是应该删掉原来 \(p\) 位置上的值,最长子序列长度不变.

考虑维护,实际上我们只关心查询最长子序列的长度,维护在有序的一列数中插入一个数,删除一个数,并且补位. 发现所有操作都可以用 multiset 维护,时间复杂度 \(O(\sum n\log n)\).

点击查看代码
#include<bits/stdc++.h>
using namespace std;const int maxn = 2e5 + 10;
int T, n;void solve() {cin >> n;multiset<int> s; s.insert(0);while(n--) {int l, r; cin >> l >> r;auto p = s.upper_bound(r);s.insert(l); if(p != s.end()) s.erase(p);cout << s.size() - 1 << " ";} cout << "\n";return;
}int main() {ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> T; while(T--) solve();return 0;
}

AT_agc054_b [AGC054B] 贪心划分

agc 特有的结论计数题,鉴定为纯粹的脑筋急转弯.

结论:确定两人最终选择的物品集合后,两人拿物品的排列唯一确定,即二者构成双射. 可能不难感受到正确性,然而独立想到并不容易.

所以直接背包跑选 \(i\) 个物品凑到 \(sum\over2\) 的方案数,再赋予排列顺序加起来即可.

AT_agc054_c [AGC054C] 粗略排序

神人题.

考虑对于一个排列怎么交换使其合法. 发现由于所有数都比 \(1\) 大,\(1\) 至少要挪到位置 \(k+1\),除非本来就在 \(k+1\) 前面,同理可以推广到数 \(i\) 至少要挪到 \(k+i\).

那么对于一个操作后的排列,\(p_i=i+k\) 的位置原来就只可能在区间 \([i+k,n]\),乘起来即可.

http://www.hskmm.com/?act=detail&tid=36914

相关文章:

  • [题解]P4616 [COCI 2017/2018 #5] Pictionary
  • 二三级区别
  • 第九章-Where-1S-tHe-Hacker
  • CF 2023D Many Games
  • 2025.10.22考试记录
  • 2025多校冲刺CSP模拟赛7 题目分析
  • Typora的多端同步方案,如何多台计算机共享md文件?Windows和Mac通过定时执行git来同步markdown文件
  • Trie树
  • Seg T
  • 2025.10.22总结 - A
  • 蛋白表达系统的技术布局与应用
  • 软件工程学习日志2025.10.22
  • CF2077B Finding OR Sum
  • 10月22日
  • OOP-实验二
  • P2272 [ZJOI2007] 最大半连通子图
  • 2025年,哪些微信公众号排版工具能带来效率变革?
  • 我对软件工程的理解
  • PCB线圈生成工具
  • 软件工程第三次作业--结对项目
  • AI股票预测分析报告 - 2025年10月22日
  • CF2144D
  • 折腾笔记[33]-使用uiautomation自动重复读取图片(被控程序为.net框架)
  • switch的简单运用
  • 软工第三次作业——结对项目
  • 10.22总结
  • AutoGen框架入门:5个核心概念搭建智能体协作系统
  • 使用google上colab编辑器
  • 16
  • 英语_阅读_The power of curiosity_待读