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

基本的方法

定一移一

很多双变量情况,可以先固定一个,然后变化另一起,防止双变换带来的不确定,与时间上的复杂。

二分答案

这也是固定双变量问题的好方法,而时间复杂度只增加的一个 \(\operatorname O(\log n)\)。没事就想想二分答案。

二分答案可以固定一层限制,如选的点等等。大小的限制等等。对于难求的值也可以使用。可以使代码更简洁明了。

P2370 yyy2015c01 的 U 盘 - 洛谷

统一恒定

对统一的值进行标记、赋值,可以减少错误增加效果

整体移动

即跳过全部的,剩下的就是空的。

如:一组标记为 \(-1,-2,\dots,-n\) 的数,和一组标记为 \(1, 2, 3,\dots, n\) 同时存储。只需把负数取正然后统一加 \(n\),即可(即跳过正数组的下标区间)。

进制式转换(二维坐标一维化)

按照进制模式生成不重复的下标,如一个点 \((x,y)\),假设这个矩阵大小为 \(n \times m\) 那么就可以用 \(k = max(n, m)\) 进制在第一位存 \(y\),第二位存 \(x\)

\(5\) 进制中,第一位权值为 \(1\),第二位权值为 \(5\),每位可以存下 \(5\) 个数字 \([0,4]\),可以将横纵坐标放入对应位中构成 \(5\) 进制数字,如点 \((3,4)\) 可化为 \(5\) 进制下的 \(34 (5)\) 即十进制下的 \(19 (10)\),用这个 \(19\) 作为下标进行储存。因为在 \(k\) 进制下,下标不会重复,所以在十进制下的下标也不会重复。

即点 \((x,y)\) 的一维化下标为 \(x \times k + y\)

按位分离

即将一个数字按每一位分离的方法。一般是通过取余 10,再除 10,不断得到最后一位数
一般代码为:

vector<int> res;
while (x)
{res.push_back(x % 10);x /= 10;
}

时间、空间与实现

一般来说,用空间换时间,用时间换代码的实现难度。

在空间允许下,用空间换时间是一种非常好的方法,而用时间换实现难度,是为了方便维护,减少思考成本。从而更快得解题

背包的条件限制

如果把体积当成价值来看的话,那么我们做一个限制大小为 \(j\) 的背包,就相当于,找出不超过 \(j\) 的最大值,那么正反都做一遍,那得到的就是最接近 \(j\) 的值。这是一种很牛的趋向找法。

如这题的 01 背包做法:P2392 kkksc03考前临时抱佛脚 - 洛谷

本质上,背包就是求在有限制情况下的最值或方案数。

数据的精准分析

对于时间,进行精准分析判断是否可行。

292. 炮兵阵地 - AcWing题库

数值标记

我们往往可以用一个数来标记一个点的存在,最后统计就直接求数的和就可以了。

利用一些可以互相消去的数值,进行统计,会有意想不到的效果。

如,求区间覆盖次数:我们可以给一个区间的左端点 \(l\) 标记为 \(1\),右端点 \(r\) 的下一位标记为 \(-1\),那么只要在 \([l,r]\) 内,求 \([1, x]\) 的和就能算出有多少区间覆盖。

如这题:P14239 [CCPC 2024 Shandong I] 多彩的线段 2 - 洛谷 就可以这样操作。

数值标记,使用前 \(n\) 个和的方法,化区间修改,单点查询,为单点修改,区间查询。

目的效应

对于动态处理的东西,我们可以尝试去预处理,使其在某一点直接处理完毕。无论什么事情我们只讲求目的,比如,我们要把特定物体在特定是时间消失,那么每次找出特定石头,可能需要遍历所有物体,而我们可以提前找出每个石头应该在哪里消失,然后在到那一次的时候直接处理结果就行。简单说,我们可以 “求” 出目的,即正着推出,也可以找出每个目的的归宿,直接效应。

http://www.jsqmd.com/news/31543/

相关文章:

  • 2025.11.4模拟赛总结
  • 备考笔记7
  • 服务器取证基本知识学习
  • 实用指南:【18】C实战篇——C语言 文件读写【fputc、fgetc、fputs、fgets】
  • 详细介绍:常见反爬虫策略与破解方案汇总
  • 初始three.js
  • 2025 年 11 月财税合规审计报告服务商权威推荐榜:专业审计、税务合规、财务风控,企业财税合规审计报告公司精选
  • 2025 年 11 月财税合规服务厂家推荐排行榜,电商/跨境电商/出口退税/股权设计/平台报送/亚马逊/Temu/1039/海外公司/审计报告全案解决方案
  • 2025 年 11 月一般纳税人财税合规服务商权威推荐榜:专业税务筹划与合规管理解决方案深度解析
  • AI分为ANI和AGI
  • L09_ java内注解反射的简单理解(作为小白,菜鸟的理解)
  • P5369 最大前缀和
  • 奋飞咨询:以专业之光,照亮企业可持续发展通途
  • 日总结 21
  • cpp生成1到n生成全排列的三种方法
  • CF1815D
  • 南京大学/NJU 人工智能/AI 计算机系统基础/ICS 编程作业/PA 记录
  • 直播带货话术不会写?这个AI指令帮你搞定
  • Java数组——数组的使用
  • NOIP2025加训
  • 20232427 2025-2026-1 《网络与系统攻防技术》实验四实验报告
  • Windows 系统下通过 VMware 17 安装 macOS 的教程
  • 【Redis】实操:cluster集群部署
  • 2025.11.4 - A
  • 移动通信基站
  • kaggle提交 名字不是submission.csv的提交方法
  • 实用指南:【Nest】登录鉴权
  • 程序员修炼之道:从小工到专家-2
  • 设计模式--外观模式:简化繁琐环境的统一接口
  • 从零实现3D Gaussian Splatting:完整渲染流程的PyTorch代码详解