## 命题要求 参照 [OI Wiki - 出题](https://oi-wiki.org/contest/problemsetting/) 公式、符号及排版等细节请尽可能参照 [Luogu 题解规范](https://help.luogu.com.cn/rules/academic/solution-standard) 中的前几张图片 --- ## 出题须知 在本系统出题，你需要向管理员提供**题面文件**、**数据文件**，必要时需提供**标准程序**及**明确不允许通过的程序**： - 在题面文件中，需要包含**题目描述**（包括题目背景与题意）、**输入格式描述**、**输出格式描述**、**样例输入输出**、**提示**（一般用于解释样例，对于放在题库中用于训练的题目可以适当添加做法提示）、**来源**（改自或者搬运自什么地方的题目，原创题可以添加署名）这六个模块，可以根据题目需求留空一些模块。本系统支持纯 HTML 或是 Markdown+LaTeX 格式的题面。题面中的变量请妥善使用 LaTeX 语法优化显示效果。 - 在数据文件中，每组测试数据分为 `.in` 与 `.out` 两个文件，分别代表输入数据与输出数据。文件名可以任意，但尽量不要取得太长，并且评测时会按照**文件名的字典序**进行评测。 题面请尽可能将题意描述完整、准确、清晰易懂，不应凭空冒出未加定义的概念（请注意题目所面向的对象，要让没基础的同学能够看懂），不应不加说明地使用与原义、常见义不同的词汇。 输入格式与输出格式的描述方法可以参考 Codeforces 或是 AtCoder 的格式，对各个变量的类型及数据范围等应当在该部分作出详细说明。 样例实际上只是为了能让做题者更为直观地理解题意及数据格式，因此最好放一些数据范围小的，简单的例子，并结合提示模块对其进行解释，最好能让做题者通过样例去判断自己是否读错题。当然，对于部分需要让做题者自行去发现的特殊数据点可以选择不放在样例中。 对于时间限制，请尽可能设置在**标准程序**所需时间的两倍以上，并注意**快速读入**及 **C++ 的关闭同步流**等方式对运行时间的影响，建议 C/C++ 语言标程的 IO 统一使用 stdio.h / cstdio 库的 scanf / printf 等函数。 对于空间限制，请出题者自行斟酌，建议也是开到**标准程序**的两倍以上，防止因为 $32$ 位整型与 $64$ 位整型的差别卡掉了应该算是正确的做法。明确卡空间的题目除外。 --- ## 造数据 造数据也是一项大工程，你需要保证设计出的测试点能够**覆盖整个数据范围**，并能覆盖到某些**特殊数据**，保证错误的解法无法通过。 在此基础上，请务必保证**测试点的数量**尽可能少，防止评测机评测压力过大的情况出现。当然如果做法较为简单（并不怎么消耗服务器资源）的话也可以按自己的想法多加些测试点。 如果题目的数据范围较大，例如某些数据的数量级达到 $10^5$ 以上时，测试点文件会轻松达到 $\text{MB}$ 级别。出现这种情况时请务必注意，一方面，大文件对于程序的 IO 消耗**非常大**，很容易就会出现卡常、卡读入的情况；另一方面，大文件对评测机的资源消耗也非常大，包括内存占用、IO 占用等。因此，如果在**同时降低数据范围及时间限制**之后题目还能正常卡掉错误复杂度的做法，请尽可能将数据范围缩小；如果不能，请保证设置在极大数据范围的测试点的数量尽可能少，放几个较为特殊的将时间复杂度不优秀的做法卡掉即可，对于错误的做法就用小范围的测试点去卡。 文件大小参考标准：尽可能单个文件控制在 $5\text{MB}$ 以下，$5\text{MB}$ 以上的测试点尽量少放，尽可能不放超过 $20\text{MB}$ 的测试点。 在范围较大的数据生成时，首先你可以想几个特殊的测试点结构，用程序把文件内容跑出来作为测试点，其后可以再通过**随机化**的方法再造几组。 如果你使用的是 C/C++ 语言，需要特别注意的是，**不要**使用 `rand()` 函数去造数据，这会导致随机数分布非常不均匀。 建议在 C++ 语言中使用 `mt19937` 随机数生成器，使用方法如下所示： ```cpp mt19937 _randomSeed(std::chrono::system_clock::now().time_since_epoch().count()); int getRandom(int l,int r) { return uniform_int_distribution<int>(l,r)(_randomSeed); } ``` 对于排列的随机化，建议使用 `shuffle` 函数，使用方法如下所示： ```cpp shuffle(startAddress, endAddress, _randomSeed); ``` 造完数据后，记得找些小伙伴帮忙测试下题目和数据。可以借助 `assert` 断言函数来测试测试点内各数值是否都在题面描述的范围内，例如： ```cpp assert(1 <= n && n <= 1000); assert(n - 1 <= m && m <= 2000); ``` 如果加上断言函数后程序执行出现了运行时错误，就需要注意数据范围是否出错了！ 最后，请注意程序数据点的规模应当有个循序渐进的过程，即前几个测试点最好是极小范围，适合出题者直接手造，中间的测试点的规模逐渐放大，直到最后几个测试点设置为极大范围。最好能根据测试点名的字典序来决定评测顺序，例如先评测小范围数据再评测大范围数据。 --- ## 题解编写 明确指出题目涉及的知识点，并详细照着思路讲一遍解决流程。 题解中不要凭空冒出来一些概念，例如动态规划的题解要讲清楚状态的定义。 具体实现细节可以穿插部分代码来讲解。 标程最好要简洁易懂，对于有大量冗余函数或是头文件的代码请务必精简化后再放到题解里！ --- ## Special Judge 的书写 如果你的题目需要 SPJ 用于判定最终答案的正确性，请务必书写一份 `compare.cpp` 文件，加上编译后生成的 `compare.exe` 程序，一同将其打包到**数据文件**中。 如果编译环境与 OJ 可运行的环境不一致，可能会导致 SPJ 运行时出现段错误，从而导致用户提交的代码获得**Presentation Error**。出现这种情况时，联系管理员使用服务器的环境重新编译一遍提交上去的 `compare.cpp` 文件即可。 对于 SPJ 的运行，系统在调用 `compare.exe` 时会传入 $4$ 个参数，分别表示**测试点输入文件**、**测试点输出文件**、**用户实际输出文件**以及**日志文件**（新增）的路径。你需要使用 FileIO 的方式打开这些文件，读取相关内容来比对用户作答的正确性，并通过程序的终止代码来返回正确性。如果答案正确，你的程序的终止代码应当为 `0`；如果答案错误，终止代码应当大于 `0`；如果出现格式错误（一般是 SPJ 运行时错误），终止代码应当小于 `0`。终止代码一般指 main 函数的返回值。 你可以直接拿下面这段部分封装的代码进行编写，其中 `specialJudge` 函数内已经编写好了一份用于检查程序输出与答案之间的浮点误差的判定： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define rep(i,a,b) for(auto i=(a);i<=(b);i++) #define repp(i,a,b) for(auto i=(a);i<(b);i++) #define per(i,a,b) for(auto i=(a);i>=(b);i--) #define perr(i,a,b) for(auto i=(a);i>(b);i--) #define all(a) (a).begin(),(a).end() #define mst(a,b) memset(a,b,sizeof(a)) #define pb push_back // ================================================ #define Status int #define AC 0 #define WA 1 #define PE -1 #ifndef MAX_PATH #define MAX_PATH 1023 #endif struct FilePointer { FILE *f; bool read(int &x) { return fscanf(f, "%d", &x) != EOF; } bool read(long long &x) { return fscanf(f, "%lld", &x) != EOF; } bool read(double &x) { return fscanf(f, "%lf", &x) != EOF; } bool readString(char *s, int maxLength) { string format = "%" + to_string(maxLength) + "s"; return fscanf(f, format.c_str(), s) != EOF; } bool expectEOF() { char x[2]; return fscanf(f, "%1s", x) == EOF; } } fin, fout, fans, ferr; void openFiles() { char in[MAX_PATH], ans[MAX_PATH], out[MAX_PATH], err[MAX_PATH]; gets(in); gets(ans); gets(out); gets(err); if((fin.f = fopen(in, "r")) == NULL) fprintf(stderr, "System Error: Can not open %s!\n", in); if((fans.f = fopen(ans, "r")) == NULL) fprintf(stderr, "System Error: Can not open %s!\n", ans); if((fout.f = fopen(out, "r")) == NULL) fprintf(stderr, "System Error: Can not open %s!\n", out); if((ferr.f = fopen(err, "w")) == NULL) fprintf(stderr, "System Error: Can not open %s!\n", err); } inline void floatValidator(double ans, double out, double eps, bool showData = true, int cas = 0) { if(isnan(out)) { if(!cas) fprintf(ferr.f, "Wrong Answer - found: 'nan'.", ans); else fprintf(ferr.f, "Wrong Answer on case #%d - found: 'nan'.", cas); exit(WA); } double err = fabs(ans - out) / max(1.0, fabs(ans)); if(err > eps) { if(showData) { if(!cas) fprintf(ferr.f, "Wrong Answer - expected: '%.10f', found: '%.10f', error = '%.10f'.", ans, out, err); else fprintf(ferr.f, "Wrong Answer on case #%d - expected: '%.10f', found: '%.10f', error = '%.10f'.", cas, ans, out, err); } else { if(!cas) fprintf(ferr.f, "Wrong Answer - the error between your answer and Jury's answer exceeds the limit."); else fprintf(ferr.f, "Wrong Answer on case #%d - the error between your answer and Jury's answer exceeds the limit.", cas); } exit(WA); } } void errout(int type, int cas = 0) { switch(type) { case 0: fprintf(ferr.f, "Redundant outputs."); return; case 1: if(cas) fprintf(ferr.f, "Wrong Answer on case #%d - insufficient output quantity.", cas); else fprintf(ferr.f, "Wrong Answer - insufficient output quantity."); return; case 2: if(cas) fprintf(ferr.f, "Wrong Answer on case #%d - your output is not within the range.", cas); else fprintf(ferr.f, "Wrong Answer - your output is not within the range."); return; case 3: if(cas) fprintf(ferr.f, "Wrong Answer on case #%d - your output format does not match the requirement.", cas); else fprintf(ferr.f, "Wrong Answer - your output format does not match the requirement."); return; case 4: if(cas) fprintf(ferr.f, "Wrong Answer on case #%d - your solution does not match the requirement.", cas); else fprintf(ferr.f, "Wrong Answer - your solution does not match the requirement."); return; case 5: if(cas) fprintf(ferr.f, "Wrong Answer on case #%d - Jury has a better solution.", cas); else fprintf(ferr.f, "Wrong Answer - Jury has a better solution."); return; default: return; } } // ================================================ Status specialJudge() { double x, y; fans.read(x); // 测试点.out文件内的数据 if(!fout.read(y)) { // 用户实际输出的数据 errout(1); return WA; // 无可读的输出内容 } floatValidator(x, y, 1e-6); // 误差超出预期 // ============================================ if(!fout.expectEOF()) { // 不允许输出多余内容，空格和换行除外 errout(0); return WA; } return AC; } Status main() { openFiles(); return specialJudge(); } ``` --- ## Interactor 的书写 如果你的题目是一道交互题，请务必书写一份 `interactor.h` 文件，并将其打包到**数据文件**中。同时，在你的题面描述部分第一行加上加粗后的 `这是一道交互题。` 文本，并在输入数据格式部分详细介绍交互方法。 建议该文件内统一使用 `Interactive` 作为类名，编写该类并将参数全部设置为 `private` 类型，将用户允许调用的方法全部设置为 `public` 类型。 请注意，本系统的交互题并非采用两程序 IO 交互通信方式实现，而是在用户提交代码后，主动在用户代码中引用 `interactor.h` 文件，让用户调用类接口所实现的。因此，对于输入输出文件的数据加密请务必做到位。 加密方式因人而异，请各位出题者自由发挥，下面这份代码介绍的是通过异或来将输入转成正确数值的方法： ```cpp #include <bits/stdc++.h> using namespace std; /* * 这份代码等同于题目 3931 - 猜数字 的实际交互文件，但在部分位置进行了修改 * 用户初始时调用 init() 接口获取 n 的值 * 猜测时调用 query(x) 接口，传入猜测的数值，并返回猜测结果 * 提交答案时调用 submit(x) 接口，传入答案 * 请注意，一旦某种错误发生，请立即停止程序（正常停止，调用 exit(0) 即可） * 如果需要告诉用户发生的是哪种错误，请将该错误按照一定的格式输出，搭配 Special Judge 将其导出到日志中 * 如果答案正确，最好设计一个跟本题实际数据相关的输出，防止用户投机取巧直接输出文本而通过本题 */ class Interactive { private: const int interactiveHash = 114514191; // 对于输入参数，请自行设置哈希值或其它形式，保证仅交互器可读即可 const int maxq = 30; int n, m, q; void validate() { // 数据验证，可写可不写，但为了防止出锅还是写一下 assert(1 <= n && n <= 1000000); assert(1 <= m && m <= n); } void terminate() { exit(0); } public: int init() { // 用户程序开始时调用的接口，可以将初始参数作为返回值传给用户 cin >> n >> m; n ^= interactiveHash; m ^= interactiveHash; q = 0; validate(); return n; } int query(int x) { if(++q > maxq) { cout << "WA@The number of queries has exceeded the limit!@"; terminate(); } if (x == m) return 0; return x < m ? -1 : 1; } void submit(int x) { if (x == m) cout << "AC@hAsHc0dE@"; else cout << "WA@Wrong answer, guess failed.@"; terminate(); } }; ``` 接上文中的交互代码，如果你需要在答案错误时告诉用户错误类型，请再搭配一段 Special Judge 将符合预设格式的文本输出到评测日志中。这里使用了两个 `@` 字符用于标志交互器的输出，开头两字符表示状态，防止用户自行打印数据。 ```cpp const char* acs = "AC@hAsHc0dE@"; // AC时输出的字符串保证与交互器内一致 char str[105]; Status specialJudge() { int len = 0, at = 0; while((str[len] = fgetc(fout.f)) != EOF && len < 100) { len++; if(str[len - 1] == '@' && ++at == 2) break; } str[len] = '\0'; if(strcmp(str, acs) == 0) return AC; if(len > 3 && at == 2 && str[2] == '@' && !(str[0] == 'A' && str[1] == 'C')) { str[len - 1] = '\0'; fprintf(ferr.f, str + 3); } return WA; } ``` --- 最后，各位同学如果有好的 idea 的话，可以直接联系网站管理员或者集训队队长等人出题哦！