如何出（改编）一道ACM算法题？

Dear 丶 2023-06-01 14:57 9阅读 0赞

## 本文背景 ##

> 本人算法能力一般，但是为省赛和区域赛网络赛出过几道题，总结了一些自己的经验，希望与大家分享。本文不涉及具体的算法题，都是一些理论性的想法和一些建议。

## 题源 ##

如果你能在没有题源的情况下自己想出一道新的题目，想必也很难看到这篇文章了。题源是出题的第一步，相信到了需要出题的地步，正在看这篇博客的你一定有自己熟悉的刷题网站，而这个网站可以作为你的题源，因为熟悉。本人推荐两个题源网站：

[英文题源网站 Codeforce][Codeforce]

[中文题源网站 51nod][51nod]

拿到的题源一定要确保自己能够写出所有解法，可能题目有O(n^2)，O(nlog(n))，O(n)三种解法，如果有的话这三种解法你都要弄会，至少看了别人的答案后自己能够完全透彻理解。

一道题有如下几个组成部分，而作为出题者，关心的不只这几部分：

1.  题目名。根据出题要求，可以英文或者中文。
2.  复杂度要求。时间空间复杂度要求，一般时间复杂度更为重要。
3.  题目描述。也可称为题面或题意，一般会有一个故事来描述情形；也可没有故事，用抽象的数学图形或者操作步骤来描述题目。
4.  输入、输出格式。一般是输入占几行、输出占几行，输入哪些数据等的描述。
5.  输入、输出样例。
6.  题目提示Notes。一般是关于样例的解释，或者特殊格式出题的提示。Notes部分也可省略。

注意：你可能读到一半就去出题了，所以我打算将注意事项预先写在这里。即：你出好的题目一定要保证题目名、题目描述、输入、输出等在百度、谷歌等常用浏览器中都搜不到出题用的题源或者类似的题目。

## 题意改编 ##

关于题意改编，也就是题目描述部分，以下提供四种策略：

1.  **具体具体化**。（描述对象转移）题目可能有具体的某个人或者某件事情，进行某种操作，你可以将这个具体事件或具体的人，转移到最近发生的一些事情，或者你们同学比较熟悉的东西。例如：以你们协会或者小组或者某个老师作为题目的描述对象，这样更能增加题目的趣味性。
2.  **具体抽象化**。如果你嫌转移描述对象比较麻烦，你可以将题目抽象为某个抽象地数学模型，图形的排列，碰撞，走迷宫等，直接用数学模型来描述。
3.  **抽象抽象化**。也是采用描述对象转移的方法，你可以将某个数学模型，转移到另一个数学模型场景。
4.  **抽象具体化**。根据原先抽象加以具体描述。如果原先是一道水题，你可以将这道题改编成英文阅读理解题，不要忘记英文阅读也是ACM算法竞赛的一部分，读懂题目是做题的前置条件。

## 输入输出改编 ##

1.  **增加题源输入的前置条件**，你可以将输入改变成另一组和题源输入相关的输入，来增加题目难度。比如，题源输入的是排序好的数字，你可以将其输入改成乱序。
2.  **减少题源输入的前置条件**，直接输入原题处理后出来的数据，将其作为新题的输入。
3.  **针对输出也有以上两种情况**，分别对应增加减少难度，不再赘述。
4.  **输入输出还可以从格式角度改编**，修改某些条件后输出可以由【模式一】（输入->输出->输入->输出，循环多次）变成【模式二】（输入->输出，所有数据必须一次输入或输出，意味着要增加存储或者增加处理步骤）。当然这个操作也可逆。

## 复杂度改编 ##

1.  **修改复杂度的要求**，卡掉复杂度O(nlogn)以上的解法，增加题目难度。比如，原先要求2000ms，你可以将其改成500ms或者1000ms，具体数值依据具体情况而定，一般是500ms的整数倍。
2.  **修改输入输出要求**，增大或减少输入输出的数据量级，让题目更复杂或更简单。
3.  **修改数据大小要求**，比如原先数据为10^9，刚好为int型。如果你将数据大小修改为10^18，那就只能用long long型来存，可能会卡掉一些解法；如果你将数据大小修改为10^5，可能会多出一些做法，比如用hash表，然后前缀和、后缀和等处理。
4.  **修改数据类型要求**。原先输入为int，你将其改成double或者float，可能会增加一些难度，反之减少难度。

> 以上为针对题目的修改，一定要确保搜索引擎没法搜索到改好的题目。

## 如何生成样例 ##

### 生成输入数据 ###

一般我们需要20组左右的样例，保存在文件中

1.  首先一定有一些边界输入，需要你自己添加，比如边界情况，特殊情况等等。
2.  当你添加了数据量相对小的边界输入后，可能有一些数据量大的边界输入无法手动添加，可以写一个代码，添加极限数据量的边界输入。
3.  剩下的可以写一个代码让python随机生成不同阶次的样例。比如你的数据量大小为10^6，你可以生成数个数据量100、数据量1000、数据量10000、数据量100000、数据量1000000的输入。

### 生成输出数据 ###

将产生的20组输入样例在你的标准程序中，输出结果在文件中，保存为输出样例。这里一定要保证你的标程的正确性，以及输入输出的合法性（符合题目描述）。

你需要将生成好的输入输出拿出一两组放在题目描述中，当然你可以拿出特殊数据，让参赛者 AC；也可以只拿出常规数据，让做题者一直 WA。生成好的样例规范命名，如下图所示：

这张图片转载自本人CSDN博客:  
![watermark,type\_ZmFuZ3poZW5naGVpdGk,shadow\_10,text\_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naml1ZGluZw==,size\_16,color\_FFFFFF,t\_70][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naml1ZGluZw_size_16_color_FFFFFF_t_70]

## 写标程+OJ服务器实际运行 ##

做完上面这几部之后，一道题目基本上出完了，接下来你需要将这些数据和样例在你们的OJ服务器上运行，确保时间，空间都符合要求。在测试中，你需要将你预想能通过的几种复杂度的解法都在服务器上跑一遍，确保题目的解法可行性。

## 总结 ##

本人大四的时候给省赛出了一道题目，并不难，但是数据处理等卡住了很多队伍。

我认为让一部分会高级操作、数据处理比较熟悉，或者对时间复杂度优化比较熟悉的题，有区分度的题才是好题。

需要卡住的是那些只会暴力解法的队伍。

本人经验分享结束，暂且只记得这么多了，后面可能还会更新。

希望读这篇博客的你能出出一道让自己和大家都满意的题目。

## 本文声明 ##

本文并非鼓励大家采用这种方法出题，本文想表达的是凭空造轮子很难，但是可以找到一个基本题，将起抽象出来，然后自己扩充，这个扩充也有一定的难度，可能也有新的idea，或者完全变成了另一道题，由出题者的能力决定，但是扩充比造轮子简单很多，毕竟轮子不是人人能造。

如果你能力足够强，虽然你很难看到此文，但是我仍希望文章中某个小建议能帮到你。

如果你能力一般，与我一样在迫不得已的情况下需要出题，部分可以参考本文，还是希望你在此基础上能灵感闪现，出几道有灵魂的题。

当然，如果你并非在大型比赛出题，知识出题训练，想整出大量的新题，本文可能对你有很大帮助。

发这篇文章的缘由是，这是我自己写的笔记，后来发现网上没有类似的，就发出来了，可能写的不太好，但是我希望能帮到情况和我当时类似的人。

## 个人情感 ##

我们学院没有老师训练acm，全靠我们几个感兴趣的自己在学。在我们偏远的大西北，偏偏我们还是最好的学校，我们上上任院长比较有远见，连续多年申请acm省赛举办资格，可能出于对偏远地区考虑，我们还申请到了。但是我们没有老师出题，没有人带，搞了个acm协会还经常拖欠经费，学院不肯花钱。照理我们确实没有出题的资格，但是我们不想让我们喜欢的东西，唯一的机会就这么消失掉，省赛只能硬着头皮出题，区域赛邀请赛只能半自费去参加。

奇迹的是，我们那个院长还申请到了举办区域赛的资格，我们几个既是后勤，又是技术维护，还是参赛人员。比赛的那几天，每天都在修学校那些用了好多年破烂机器，学校各个部门见到没收益都不做事，我们得到处跑，到处开证明，晚上基本上没合眼。所以是通宵熬夜直接出现在赛场，赛前还要换件衣服当技术人员解决参赛者们的问题。

我描述这些只是表示，不是人人都有那么好的环境来训练，还有很多和我一样境遇的同学，我希望你们不要因为困难就放弃。我们学院没老师，就学长带学弟，奖牌都放协会，一代一代往下传，后来者不埋怨我们这些学长什么都没做，就足够了。

也希望在艰苦环境中学习的ACMer大家不要放弃，总有人会你比更艰苦。如果你是先行者，你为学弟学妹们做的好事他们会记住；如果你是后来者，你要相信你的前几届已经做出很大努力了。  
我已经大学毕业了正在考研，几乎没有机会再出现在赛场，但是算法是我感兴趣的事物，我不会放弃，我会坚持学习下去。

谨以此文，与君共勉！

转载于:https://www.cnblogs.com/zhangjiuding/p/11334926.html

[Codeforce]: https://codeforces.com/problemset
[51nod]: http://www.51nod.com
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naml1ZGluZw_size_16_color_FFFFFF_t_70]: /images/20230601/06270cfe752e43278c85850afec14bc1.png