专栏文章

我会随机说话

tty_mxzhn
算法·理论参与者 64已保存评论 68

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
68 条
当前快照
1 份
快照标识符
@mm0uqtsj
此快照首次捕获于
2026/02/25 01:01
2 周前
此快照最后确认于
2026/03/10 01:21
12 小时前
查看原文
省选将至，如何翻盘？
尝试随机说话。

做题状态

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

困境

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

解决困境

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

某些常见想法

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

题目特征

我们知道，很多人自己学习 OI 时会把题目串起来学，而不是随机做题。专题这种训练方法也是非常常见的。
  • 题目特征是在还没完全会一道题的情况下都可以发现的。或者说其实是题目的突破点？
  • 题目特征决定了使用的套路或联想的模型之类。
  • 枚举题目特征，是“枚举算法”的一种替代。
举个例子，这句话后面有一句透明的话。那么发现的人会觉得这是这篇文章的特征或突破点，但是不是。\color{white}那么发现的人会觉得这是这篇文章的特征或突破点，但是不是。
我们可以从很多方向去描绘题目的特征。
下面是一大段例子，不想看可以跳过。

例子

题意：nn 个点围成环，带权，每次操作环上相邻三个数 x,y,zx,y,z 变成 x+y,−y,y+zx+y,-y,y+z。问你最少多少次操作可以使得所有数非负。1≤n≤105,∣ai∣≤1041\le n\le 10^5,|a_i|\le 10^4。
原题：CTT2019Day3T2。
考虑序列上的问题，考虑前缀和数组，发现进行操作相当于交换前缀和数组上的相邻两个数。若有解则相当于求逆序对。
用优美的方法推广序列结论到环上。
将序列复制无穷份并拼接在一起。定义当前这个序列前面第一个数是 00，接下来设总和为 SS，初始序列（做了前缀和）为 aa，则无穷序列为 ...,a−2S,a−S,a,a+S,a+2S,......,a-2S,a-S,a,a+S,a+2S,...。
每次交换会交换无穷序列上与 i,i+1i,i+1 对 nn 同余的位置。
做法二：
题解做法，很巧妙。
考虑推广之前说的逆序对结论：记录无穷序列中每个数前面比他大的数 RiR_i。求 [0,n−1][0,n-1] 中所有 RiR_i 的和。
为啥是对的？因为每次操作显然带动了无穷序列的操作，而 RR 也是一个周期序列。
接下来就不需要分析策略了。直接计算 RR。
对于 ii 枚举一个 1≤j≤n1\le j\le n，则若 j≤ij\le i 则第一次出现时为 aja_j，否则第一次出现时为 aj−Sa_j-S。
发现若 aj>aia_j>a_i 且 j>ij>i 时额外贡献 −1-1 即可。接下来不讨论 jj 与 ii 的关系。
前提还是 aj>aia_j>a_i。若 aj mod S>ai mod Sa_j \bmod S> a_i\bmod S 则答案为 ⌊ajS⌋−⌊aiS⌋\lfloor\dfrac{a_j}{S}\rfloor-\lfloor\dfrac{a_i}{S}\rfloor。否则额外贡献 −1-1。
两个二维偏序！可以做到 O(nlog⁡n)O(n\log n) 的优秀复杂度。

啥道理

这个题需要你先在环上把操作像链一样说的人话一点。
发现如果按照题解这么说就是链上结论的自然推广。
逆序对就看成势能的角度去算一个答案。
所以这个题的特征就在于题目和弱化版的关系，环看做无穷序列之后，逆序对也成了自然的推广。
  • 题目特征可以说是这个题“可做的点”。本来这个题很难，理解了这个可做的点后，问题就会得到很大的推进。
  • 说自己“找不到可做的点”这句话可不能乱说。至少要想清楚这个题在说什么，并且必须是真的觉得这个题没有突破口后了。
  • 在做题这件事上我们都是随机漫步的蚂蚁。
  • 但是像盲人摸象一样的探索与发现正是解题的乐趣！
  • 高效且通用的做题方法是困难的，所以接下来将不再谈论这些东西。

题目难度评价

我暂且认为对题目难度的评价有助于学习。参考了 Lyz09 的想法。
其中：
  • 0\color{77ccaa}0 级几乎不可能做不出来。
  • 1\color{00cc00}1 级在正赛基本能做出来，但是比我水平高一档的人几乎不可能做不出来。
  • 2\color{00aa55}2 级在正赛基本做不出来，平时能做出来一些比例，水平比我高一档的人基本能做出来。
  • 3\color{776600}3 级在任何时候一般都做不出来，但是可以看得懂题解。
  • 4\color{ff0000}4 级看不懂题解，难以理解，不可战胜。
这些题目如果自己不会做可以看整体通过率之类的进行评价。
对于 1+\color{00cc00}1+ 难度的题目，应当尽量不要出现。
对于 2−\color{00aa55}2- 难度的题目，应当尽可能多的出现，这种可能是自己赛后又独立想出来了（赛时可能时间不够），或者是赛时切了或者是差不多就会。当然如果不小心看了题解那只能变成 2\color{00aa55} 2 级的题目了。
这种评价其实可能不准，因为可能自己再多想想就改变了评级。

更多评价

大致来讲，CSP 与 NOIP 的由我的评级如下：
CSP 2025
社团招新：【0】
道路修复：【0】
谐音替换：【1+】
员工招聘：【1】
NOIP 2025
糖果店：【0】
清仓甩卖：【1】
树的价值：【2-】
序列查询：【2】
如果你争就是我对，因为这个评级系统是主观评级。
如果按照我目前的期许，明年很多 22 级的题都会变成 2−2- 级，然后很多 33 级题就会降级到 22 级。
希望如此。
省选前的记录会放在这里。

关于题解

  • 题解首先的目的是为了整理自己的思路。
  • 我好像不急的时候会先写题解再写代码，也不知道这个做法对不对。
我认为，我以后的优质题解（水题解不算）需要具备以下几点：
  • 题解中含有代码的每一个大的步骤，以及要推的公式，也就是对着写就能过。
  • 题解里的每一个步骤需要大致清晰，使用数学公式或者画图便于形象的理解。
  • 题解的形象程度是很难足够的。
  • 阅读者学习到了题解的每一步，但是并不能学习到思考的过程。
或许比赛完后先不看题解也是一种选择？

关于笔记

  • 学习笔记的目的是学懂这个方向的内容。
  • 学习笔记应当首先明确全文的中心思想。
  • 针对中心思想，补充对应的例题并附带题解。
因为竞赛太难了，所以学习笔记没法解决这方向的所有难题，但是可以对这个方向产生一个印象。
以后想题的时候可以通过枚举印象的方式思考。

评论

共 68 条评论，欢迎与作者交流。

正在加载评论...