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

CF1542

CF1542E2 Abnormal Permutation Pairs

既然要求了字典序,那么我们可以枚举两个排列的最长公共前缀长度 \(L\) 并钦定 \(p_{L+1}<q_{L+1}\),此时 \(L+1\) 之后的位置就可以随意选了,所以我们再 DP 只需要考虑逆序对的限制。设 \(cnt_1\) 为排列 \(p\) 的逆序对数量,\(cnt2\) 为排列 \(q\) 的逆序对数量,由于 DP 状态不能同时表示 \(cnt1,cnt2\) ,考虑令 \(f_{i,j}\) 表示确认了 \(i\) 位、\(cnt1-cnt2=j\) 的方案数。

显然有转移式

\[\begin{align} f_{i,j}&=\sum_{p1=1}^i\sum_{p2=1}^i f_{i-1,j-p1+p2}\\ \end{align} \]

显然是可以将式子拆成每个值乘上贡献次数之和的形式的,转移只需维护 \(\sum f_{i,j},\sum f_{i,j}\times j\) 的前缀和。求出每个值后枚举 \(L,p_{L+1},q_{L+1}\) 再求和即可

CF1542D Priority Queue

考虑求每个数 \(a_i\) 会在多少个方案中被统计到,因为数据范围很小,所以我们每个数都可以 \(O(n^2)\) 算方案数。设状态 \(f_{i,j}\) 表示考虑到第 \(i\) 位、有 \(j\) 个数比当前数小的方案数。根据状态进行一个分讨,每个元素都考虑它保留或被删除的转移即可。复杂度 \(O(n^3)\)

CF1542C Strange Function

考虑若 \(f(n)=i\),那么有 \(lcm(1,2,...,i-1)\mid n,lcm(1,2,...,i)\nmid n\)。由于 \(lcm\) 呈指数级增加,所以我们可以枚举前缀的 \(lcm\) 。那么在 \(n\) 范围内,\(i\) 的贡献次数即为 \(\lfloor\frac{n}{lcm_{i-1}}\rfloor-\lfloor\frac{n}{lcm_{i}}\rfloor\)

后两题简单题,咕咕咕

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

相关文章:

  • Manim实现涟漪扩散特效
  • CRMEB标准版PHP移动订单功能深度解析:多端同步方案
  • CICD流程建设之持续测试实践指南
  • Xcode 26.0.1 (17A400) 发布 - Apple 平台 IDE
  • Tenable Nessus 10.10 (macOS, Linux, Windows) - 漏洞评估解决方案
  • CNN+MNIST - 实践
  • SonarQube Server 2025 Release 5 (macOS, Linux, Windows) - 代码质量、安全与静态分析工具
  • 超快轻量级离线翻译服务器MTranServer在腾讯云轻量应用服务器上的全流程部署指南 - 实践
  • 微算法科技(NASDAQ: MLGO)利用高级 Blowfish 加密标准实现区块链集成信息共享
  • 专业讲解大模型登记(纯干货)
  • Docker常用命令速查
  • 离线安装docker
  • MX 练石 2025 NOIP #9
  • dockerfile
  • PostgreSQL 的索引Ooracle、Mysql索引的类型对比和说明
  • Docker打包CMake项目镜像操作步骤
  • Linux dmesg 内核日志查看工具详解
  • 【智慧】 gym104385
  • __repr__魔术方法
  • 基于萤火虫算法(FA)优化支持向量机(SVM)参数的分类实现
  • OSS cp(下载文件)
  • 有范同城旅游广告小程序系统:赋能旅游行业数字化运营新生态
  • Active Directory安全指南:默认域管理员账户的安全管理
  • 微云二手车运营版系统:多端覆盖的二手车平台解决方案
  • Linux常见命令1
  • 下载并安装ossutil
  • Unigine整合Myra UI Library全纪录(1)
  • new 为数组开辟内容空间的时候,数组大小这个额外的信息是如何存储的? int * p = new int[5]; 指针p 指向的的int 数据地址还是数组大小的地址?
  • 欧拉函数学习笔记
  • PDF论文文字公式提取,翻译与对照代码(自用)