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

20251007 模拟测 总结

\(\mathcal{Preface}\)

分数 \(100+100+100+25=325\)

菜死了。

\(\mathcal{Problem \space{} A}\)

Tag:循环,暴力枚举。

送分题,由于 \(1 \le l \le r \le 3000\)\(1 \le nn \le 3000\),由此可知平方级别的时间复杂度是完全可以接受的,因此直接枚举除数 \(k\) 然后挨个算出值取 \(\min\) 就好了,注意如果有相同的取最小一个。

\(\mathcal{Problem \space{} B}\)

Tag:因数,循环。

\(ans=10^{k}\),然后看看,\(n\) 中有 \(x\)\(2\) 的因子,就让 \(ans \to ans \div 2^x\),有 \(y\)\(5\) 的因子,又让 \(ans \to ans \div 5^y\),最终的 \(ans\) 便是答案。

\(\mathcal{Problem \space{} C}\)

Tag:完全二叉树的性质,二叉树。

记录以每个点为根的子树包含的字母的情况。

如果这个包含字母情况中,只有至多 \(1\) 种字母的数量为奇数,才可以形成回文。

一开始先预处理最初的情况,算出答案输出。

然后考虑修改的情况,如果节点 \(u\) 上的字母被改动了,受影响的子树只有以自己的祖先节点为根的子树才会受到影响(自己以及父亲算作特殊的祖先)。而又由于题目给定的是一棵完全二叉树,因此深度只有 \(\log n\),暴力修改没有问题。

先判断之前有没有,之前有的话先让答案减一,然后再看改变之后有没有,改变之后有的话就让答案加一。

\(\mathcal{Problem \space{} D}\)

Tag:构造,思维,逆序对。

好神的题目,好神的做法!

由于要求逆序对和顺序对的数量相同,不难算出逆序对和顺序对的数量都是 \(\frac{n \times (n-1)}{4}\)。可以先让 \(sum = \frac{n \times (n-1)}{4}\)

首先考虑构造足够的顺序对。如果在序列前面放进一个 \(1\),那么会贡献 \(n-1\) 个顺序对,而不会出现逆序对;如果接着放进一个 \(2\),那么又会再贡献 \(n-2\) 个顺序对,同样不会出现逆序对;以此类推,如果顺着来的话,放一个 \(x\),就会贡献 \(n-x\) 个顺序对。

那么考虑依次枚举 \(i\)\(1\)\(n\),如果当前的顺序对数量 \(cnt\) 加上这一轮新加的 \(n-i\) 个之后还没有够到 \(sum\),也就是说当 \(cnt+(n-i) < sum\) 的情况下,直接让 \(a_i = i\),标记 \(i\) 数字已经填写,然后让 \(cnt \to cnt+(n-i)\)。但是如果超过了,就要往后找到一个恰好的 \(x\),使得 \(cnt + (n-x) = sum\),并让 \(a_i = x\),标记 \(x\) 已经填写;标记完了之后,顺序对的数量也就已经达标了,这个时候只要填入足够多的逆序对就可以了,很简单,把还剩下没填的数字全部倒序挨个填进 \(a\) 里就行了。

最后输出即可,代码很简单。

\(\mathcal{Summary}\)

T4 的构造方法确实挺厉害的,构造也确实不是强项,之后继续加油吧。正好又多知道一个构造的方法了,不断累积经验肯定也是有帮助的!

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

相关文章:

  • 2025国庆Day6
  • Claude 封杀中国后,我终于找到了平替!
  • [退役感言]You are my only one.
  • Mortal
  • python,shell,linux,bash概念的不同和对比联系 - 指南
  • 制作局域网连接打印机exe文件
  • 深入解析:linux——账号和权限的管理
  • pandoc使用
  • c#造个轮子--GIF录制工具
  • netdata
  • 关于Elment-plus的el-table组件无法通过原生JS监听scroll事件
  • arc3.2语言sort的时候报错:(sort < `(2 9 3 7 5 1)) 得写成此种:(sort > (pair (list 3 2)))
  • 噬菌体展示技术:从诺奖成果到疫苗研发,这一 “表型 - 基因型统一” 工具如何颠覆生物研究?
  • 从零开始学Flink:实时流处理实战
  • 高质量同人动画整理回顾记录的方式
  • 斑马打印机基础知识
  • 加拿大加密货币牌照:合规化加速数字资产成功
  • 深入解析:实时通信RTC与传统直播的异同
  • Exp2-后门原理与实践
  • 【Hexo】4.Hexo 博客文章进行加密 - 实践
  • 思考的动力
  • Software Foundations Vol.I : 多态与高阶函数(Poly)
  • 数学之美感悟。
  • 基于DeploySharp 的深度学习模型部署测试平台:支持YOLO全系列模型
  • 复制别人的vmware虚拟机无法联网ubuntu2204
  • 计算机网络学习分享-0
  • 预科02git使用
  • 预科01Python复习
  • 预科01Python学习
  • 5G-A:开启通信与行业变革的新时代 - 指南