文文笔记(I)——特殊尝试！套路性的出题过程~

· · 个人记录

首先抱歉之前的 adhoc 计划咕掉了，因为最近题都补不完所以没时间到处找 adhoc 来做。当然不是说我最近一个没做，做的都是内部题目也不好发出来，反正就是各种不方便，以后有空了可能会重新启动吧（（（

文文笔记记录的是我的已公开题目的出题过程，至于为什么叫文文笔记，因为我主要供题侧在 Wdoi，而笔记也很随性，适合我所需要的记录。

犇犇的调查中大家投的最多的是 P8544，这道题的出题过程很有意思，虽然我个人认为其在我所出过的高难度题里有趣程度很低（但我公开的高难度题其实不多，大家可以期待一下），但正是因为它的特殊性所以才值得我一讲。

这题最特殊的地方，是我从最早开始就确定了出题的目的——这事实上并不是一个正确的行动，过早的对思路进行限制容易导致最终得到的 idea 并不理想。但出于练习的目的划定出题的范围也不坏，不是吗？事实上，这题其实是我的一道“练习题”，用来补足刷题上的不足，没想到吧！

划定目的是需要一定灵感的，如果从来没进行过这样的尝试，或者对这样的尝试感到费力，那么不妨来看看我在此题出题前设立的目的：

大家可能会觉得这太 naive 了对吧，但事实上这个目的很有意思，怎么样才能算“第一步不是 wqs 二分”？

你可能会发现，能够找到的 wqs 二分练习题，在题目里都有形如“恰好 k 个”的限制，所以第一步即为进行 wqs 二分，去除限制，之后吧啦吧啦一通操作，可能是直接 dp，可能套了决策单调性，总而言之，第一步都是发现这题有着 wqs 二分算法的经典标记，所以直接套上就行，证明什么的也抛到一旁去。“既然找不到想要的题，那就自己出一道吧。”但当这种幼稚的想法成功被实现，那么产生的成果毫无疑问是 educational 的。

但想要达成这样的目标是艰难的——因为如果是容易的，那么早该有人出过这样的题才对。为了最后的成功，不妨分步进行出题，那些天马行空般的 idea 枚举方式并不适合这样的出题方式，明确的目的性往往伴随着缜密的计划，出题也不例外。

第一步，明确自己要出什么样的题。首先，我先了解了一般的 wqs 二分题的证明方法——构建费用流模型得到凸性，然后完成证明。所以我得到了一个小目标，也就是出一道网络流题。

第二步，思考你能对 idea 做出的改变，反向推出你需要的 idea 是什么样的。当你将第一步里所提到的目标达到时，你需要修改它以满足终极的目标。但在你决定修改前，可以试着考虑一下什么样的初始 idea 适合修改。思考了我所做过的 wqs 二分题的形式，我希望我的网络题满足以下条件：

  1. 输入应该是数列/矩阵，而不应该是一张图；
  2. 建图方式尽可能规整，至少我希望输入不对图的形态有影响（但可能对边权有）。

第三步，竭尽所能地思考，最终确定一个可行 idea。这一步就因人而异了，对我而言，我喜欢把一个我感兴趣的具体的东西抽象成题。在漫无边际的思考中，我经历了以下过程（这个过程是最有趣的部分，如何借助技巧将最简单的思考转化为一个最终的 idea）：

可以发现，wqs 二分题需要“选 k 个”这样的关键条件，这起到了对思维剪枝的作用。至于怎么把它藏起来，那是之后的事。

借助这样的思考，我成功得到了一道略显无聊的题，即 P8544 的给定原始矩阵版本，其具象题面如下：

但目前的题意还不能使用 wqs 二分解决，套路地，我们尝试用序列来构造矩阵——这是因为 wqs 二分更适合序列上的 dp。在这过程中，最重要的是解题能力。通过序列构造矩阵的方法不多，而简单的构造方式就更少了（困难的方式会导致题目很不可做，因为使用 dp 解决网络流题本身就是困难的）。在解题时记得大胆猜想，猜想非常重要！当你得到解法后，可以多给几个人看，让他们来帮助你找到证明。当然你也可以选择直接求助他人，不过得到帮助的概率会降低，而且我个人认为解决自己出的一道未知题目的能力也是非常重要的。

最终，我得到了 P8544，并且通过大胆猜想得到了解法（后续是 cxy 和小波等帮我补全了证明，感谢他们）。我将具象题面抽象化后，通过“构造 k 列矩阵”的包装来使得 wqs 二分不那么显然，可以看到这是有成效的。

这就是我出题的全部历程，我认为 P8544 是很好的 wqs 二分练习题，也想把它推荐给 wqs 二分的初学者，希望大家多多来做呀~也希望大家能够在这一笔记中学到一些出题方法，并出出更好的题目！

大家下一期《文文笔记》再见！