我会随机说话

ty_mxzhn · 2026-02-22 12:54:22 · 算法·理论

省选将至，如何翻盘？

尝试随机说话。

做题状态

做题状态可能比做题方法和比赛策略更加重要。
好的做题状态应该是敏锐和专注的，并且对比赛有整体观，学会把控时间。
当然这种状态一般无法持续。

困境

困境的定义没有统一的标准，但是思考了较长时间是前提条件。
对我来讲，我会说我“找不到这题可做的点”。
发现困境是重要的，这代表对这题的思考进入了一个新的阶段。

解决困境

首先一个处境被称作困境的时候，解决它一定是难的。
所以如果没能解决，不应该苛责自己。
一个困境对应恰好一个突破点。
枚举突破点是解决困境的惯用手段。
解决不了困境，一定是有原因的。找到原因，迎刃而解。

某些常见想法

直观。代数直观将问题刻画为代数式，几何直观将问题转到平面上或者其他形象的模型里。随后得到启示。
拆分。解决 subtask 或者自己设计的弱化版问题，从各种手段降低解决这个问题的难度。随后得到启示。
联想。尝试理解出题者的意图，理解问题本身的特征与巧思。找到类似的模型。随后得到启示。
打表或者乱猜等等都可以作为你的武器。

题目特征

我们知道，很多人自己学习 OI 时会把题目串起来学，而不是随机做题。专题这种训练方法也是非常常见的。

题目特征是在还没完全会一道题的情况下都可以发现的。或者说其实是题目的突破点？
题目特征决定了使用的套路或联想的模型之类。
枚举题目特征，是“枚举算法”的一种替代。

举个例子，这句话后面有一句透明的话。\color{white}那么发现的人会觉得这是这篇文章的特征或突破点，但是不是。

我们可以从很多方向去描绘题目的特征。

下面是一大段例子，不想看可以跳过。

例子

题意：n 个点围成环，带权，每次操作环上相邻三个数 x,y,z 变成 x+y,-y,y+z。问你最少多少次操作可以使得所有数非负。1\le n\le 10^5,|a_i|\le 10^4。

原题：CTT2019Day3T2。

考虑序列上的问题，考虑前缀和数组，发现进行操作相当于交换前缀和数组上的相邻两个数。若有解则相当于求逆序对。

用优美的方法推广序列结论到环上。

将序列复制无穷份并拼接在一起。定义当前这个序列前面第一个数是 0，接下来设总和为 S，初始序列（做了前缀和）为 a，则无穷序列为 ...,a-2S,a-S,a,a+S,a+2S,...。

每次交换会交换无穷序列上与 i,i+1 对 n 同余的位置。

做法二：

题解做法，很巧妙。

考虑推广之前说的逆序对结论：记录无穷序列中每个数前面比他大的数 R_i。求 [0,n-1] 中所有 R_i 的和。

为啥是对的？因为每次操作显然带动了无穷序列的操作，而 R 也是一个周期序列。

接下来就不需要分析策略了。直接计算 R。

对于 i 枚举一个 1\le j\le n，则若 j\le i 则第一次出现时为 a_j，否则第一次出现时为 a_j-S。

发现若 a_j>a_i 且 j>i 时额外贡献 -1 即可。接下来不讨论 j 与 i 的关系。

前提还是 a_j>a_i。若 a_j \bmod S> a_i\bmod S 则答案为 \lfloor\dfrac{a_j}{S}\rfloor-\lfloor\dfrac{a_i}{S}\rfloor。否则额外贡献 -1。

两个二维偏序！可以做到 O(n\log n) 的优秀复杂度。

啥道理

这个题需要你先在环上把操作像链一样说的人话一点。

发现如果按照题解这么说就是链上结论的自然推广。

逆序对就看成势能的角度去算一个答案。

所以这个题的特征就在于题目和弱化版的关系，环看做无穷序列之后，逆序对也成了自然的推广。

题目特征可以说是这个题“可做的点”。本来这个题很难，理解了这个可做的点后，问题就会得到很大的推进。
说自己“找不到可做的点”这句话可不能乱说。至少要想清楚这个题在说什么，并且必须是真的觉得这个题没有突破口后了。

在做题这件事上我们都是随机漫步的蚂蚁。
但是像盲人摸象一样的探索与发现正是解题的乐趣！
高效且通用的做题方法是困难的，所以接下来将不再谈论这些东西。

题目难度评价

我暂且认为对题目难度的评价有助于学习。参考了 Lyz09 的想法。

其中：

这些题目如果自己不会做可以看整体通过率之类的进行评价。

对于 \color{00cc00}1+ 难度的题目，应当尽量不要出现。

对于 \color{00aa55}2- 难度的题目，应当尽可能多的出现，这种可能是自己赛后又独立想出来了（赛时可能时间不够），或者是赛时切了或者是差不多就会。当然如果不小心看了题解那只能变成 \color{00aa55} 2 级的题目了。

这种评价其实可能不准，因为可能自己再多想想就改变了评级。

关于题解

题解首先的目的是为了整理自己的思路。
我好像不急的时候会先写题解再写代码，也不知道这个做法对不对。

我认为，我以后的优质题解（水题解不算）需要具备以下几点：

题解中含有代码的每一个大的步骤，以及要推的公式，也就是对着写就能过。
题解里的每一个步骤需要大致清晰，使用数学公式或者画图便于形象的理解。

题解的形象程度是很难足够的。
阅读者学习到了题解的每一步，但是并不能学习到思考的过程。

或许比赛完后先不看题解也是一种选择？

关于笔记

学习笔记的目的是学懂这个方向的内容。
学习笔记应当首先明确全文的中心思想。
针对中心思想，补充对应的例题并附带题解。

因为竞赛太难了，所以学习笔记没法解决这方向的所有难题，但是可以对这个方向产生一个印象。

以后想题的时候可以通过枚举印象的方式思考。