目标与展望 & 再谈“攻破难题的过程”

· · 算法·理论

我今天发现我之前写的三篇都在扯淡!!!!生气。于是我决定不再继续全站推荐,直到省选前再把我觉得有用的东西全站推荐。

目标与展望——起航!

研究思考形态的目的

做不出来一个题,要反思或者找原因的时候,首先可以分成:

特殊情况:NOIP2025T2 快速胡完之后一直调不出来,其实是胡的细节错了。(反复鞭尸)

但是思维过程问题需要细分,因为我现在很缺思维!!!

细分思维过程问题是研究思考形态的第一目的!!!这可以更好的归因。

再谈“攻破难题的过程”

什么会难倒我

可以找出两大类。我认为有第三大类,但是我还没找到。

注意此处说的两大类所对应的情况有交也不覆盖全部情况。之后的所有想法都默认这一点。

一、难以找到的性质

标题用了夸张手法,不一定都很难。

先说说怎么区分性质和转化。性质是弱化问题,一定有用。转化是双向转化,不一定有用。

例题一:LCA 这题,区间求和可以差分成两个前缀和。

由于钦定 l=1 一定比原问题更优,是性质

例题二:命运这题,很多区间限制,“区间中至少有一个 1”一类的限制使得“包含了别的区间”的区间没有用。删去这些区间答案不变。

由于删去这些区间一定比原问题更优,是性质。再次发现这些区间具有单调性,是一个数学性质

例题三:钦定代表元计数之类的题。这种题肯定需要性质。

性质对应的方法有:猜测性质,观察性质,寻找性质,打表发现性质,手玩发现性质。感觉到一个性质,周公托梦给我了一个性质。

二、诡谲的转化

这太难了 /ll

一种是瞪出一些很巧妙的数学公式。这其实是转化因为硬推是推不出这种数学公式的。

但是转化和性质是相辅相成的,需要知道一些性质才能想起什么什么问题我可以转化过去。比如二分图的 Hall 定理是一个转化,但是你知道要用这个转化是意识到了这个图是二分图。另外刻画问题也可以帮助我们发现性质。

例题一:Hall 定理逆用。长官这太难了。

例题二:网格图转二分图邻接矩阵。这个比较简单我都会。

转化相关的方法有:联想到另一个问题,刻画原问题,我们发现一个转化。

三、施法

可能是第二大类方法的一个分支?也就是施加巨大套路。

例如:对原问题施加分治。对原问题施加分块。对原问题施加容斥。

这些方法是经典而通用的。如果你不尝试这些方法可能连典题都做不出来啊!!倒闭。

在这些地方卡壳则需要严肃反思。

“数据结构”法术:通过规划计算顺序,平衡计算时间以优化计算效率的法术。

“数数”法术:通过推算组合式子,转化计数方式以优化计数效率的法术。

勘误 / 补充

NOIP2025T2 第一步应该是一个“做法”而不是一个性质。

虽然这一步有经验的做题者应该能够发现这个反悔贪心是极其优秀的。

做法其实可以划分到第一类,因为这个做法本质上没有脱离开这个问题。归类的方法应该以问题是否变化而分类。但是叫性质有点怪了。

而“员工招聘”的第一步确实是一个性质。不过设计 dp 是一个转化。

“树的价值”的第二步是一个很巧妙的转化。第三步是一个性质,其简化了 dp 的状态并使得其可以使用数据结构优化。

对第三大类的探索

可能是“拆分 / 规划”?

比如倒序考虑问题(规划顺序),拆分计数步骤(先做一个 dp,后做一个 dp),横着扫描线还是纵着扫描线?P7560。期望拆成每一步成功的概率?

对于这部分我知之甚少。如果有了解的人也烦请给我一篇博客 /ll

哦可能就是拆分。定义一下拆分是什么。

拆分就是自主弱化问题,先会做弱化版再做强化版。

可以分成三类。第一类是深入研究原问题,第二类是与原问题部分相关(是弱化版之类),第三类是和原问题没啥关系。