牛客系列赛命题规范——V1.0(试运行版)

为了提高参赛选手体验,我们草拟了若干条出题相关规范。 希望征求算法竞赛选手的意见,评估每个条例的严肃等级。或者补充一些我们暂未想到的条例。

问卷填写地址:https://www.wjx.cn/vm/YDkoTJ2.aspx#

会定期更新问卷以及本帖内容公示当且的规范。

以下为根据问卷整理的相关规范,分为4个等级。

强制遵守(必须遵守,否则不允许题目用于公开比赛)

严格遵守(不得已出题人的习惯或者喜好为理由违反,除非与题目解题方式等产生较大影响时可以稍微违反)

建议遵守(在出题人的习惯范围内可以不遵守,但仍建议遵守)

无需遵守(仅作为提醒,无需出题人执行,这部分条例为某些出题人的习惯或收集到来自选手认为影响做题体验的反馈)

强制遵守

规则ID 规则描述
001 禁止在没有严格证明,并且没有使用暴力程序验证在数据范围内成立的情况下使用数学结论。(经典数学结论/数学定理/公理不在此行列)
002 判断是否成立,输出yes,no的题目中不能要求选手输出Ye5,n0等。
004 严格使用testlib.h编写val,否则必须使用过其他方式验证数据合法(例如在std中使用assert),但不建议使用testlib以外的方式校验数据。见:https://oi-wiki.org/tools/testlib/
005 禁止测试数据对std友好,必须包含将std卡到最大复杂度的测试数据。
006 输入、输出描述应该仅包含输入输出格式,数据范围,禁止仅在此处填写解题的关键条件。
007 输入输出描述必须包含变量、变量的数据范围、变量的输入输出格式,变量的含义,且使用LaTeX公式描述。(格式见释义)
008 树上题目/图论题目,若题目未特殊声明,后台数据禁止完全随机,必须保证暴力算法和搜索不能通过。
009 如与解题的核心算法考点/题目难度无关,当出现多解时必须编写spj。
010 图论问题必须显式的说明是单向边还是双向边,在输入描述中必须指出测试数据中是否包含自环、重边等信息。
011 树上问题如果是有根树,必须显式的指出根节点或输入根节点,不能让选手通过输入的方式自己推导根节点。
015 禁止出现虚假数据范围,当无其他条件导致题目数据无法达到最大时,必须保证后台测试数据包含对于每个变量均达到最大值/最小值的数据。
019 输出为实数的题目应使用spj,并且保证分别使用long double和double的情况下,绝对和相对误差的最小值不超过0.5*EPS。
020 禁止以“某道题目是难题”为由,将时间空间卡的特别死,仅让使用c/c++的选手通过。
022 禁止要求选手读取数据直到文件结尾EOF,应使用T表示测试用例的组数。
023 禁止限制选手是否输出行末空格,以及文件末的回车。必须保证无论选手是否输出行末空格,以及文件末的回车都能通过题目。
024 字符画题目禁止出现前导/后置空格
025 字符画题目禁止出现空格以外的空白字符。
026 若要求选手输入包含空白字符的字符串,必须在输入描述醒目位置提醒“输入一个包含空白字符的字符串”。
027 若要求选手输入字符串时包括空白字符整行读取,则必须给出该字符串的长度,例如:输入一个数字N表示字符串长度,接下来一行输入一个包含空白字符的字符串...。
028 c++ std禁止使用火车头。
029 c++ std禁止使用内联汇编/与平台相关的指令集优化。
030 c++ std禁止使用读入优化/非必要情况下的数组复用。
031 std标准程序使用的时间/空间限制,在不存在近似复杂度的非预期解法下不得超过时间/空间限制的50%,但任何条件下均严禁超过80%。
032 对于区分easy,hard version的题目,应在醒目位置(一般是题目开头位置)注明与另一个版本的差异。
033 题目中禁止不加千分符或者科学计数法的情况下出现重复数位较多的数字,且该数字有明显误导性,例如100000007,应改为或者100'000'007。
034 题目中空间限制不得低于64MB,否则可能会导致java等语言无法通过。
036 如与题目解题方式/题目难度无关,计算几何题目中输入点坐标时,使用整点而非浮点数。
039 输入的变量数目禁止达到及以上,当出现这种情况时,通过在题目中给出(随机)数据生成器的伪代码,或混合输入方式,例如输入1e5个变量,后序使用题目中提供生成器的方式。
040 输出的变量数目禁止达到及以上,当出现这种情况时,要求输出异或和、或者求和取余的方式。
042 强制在线题目必须在样例解释/备注中添加加密前的数据。
043 要求输出个答案的异或和等场景时,必须在样例解释中提供部分有意义的信息。
044 禁止在题目中要求选手使用std::random或mt19937等库函数代替输入。必须在题目中提供随机数生成器。
045 要求选手输出取模/取余的答案时,若原本的答案存在负数,则慎重考虑使用“取模”还是“取余”。必须给出原本答案是负数的例子或在题目描述中进行强调。
046 46、禁止对除数为负数的变量使用“取模”的概念,例如“模-5”。
047 NP问题带有剪枝的std,必须证明至少一个上界(无需保证上确界)满足最大范围数据的复杂度需求。
048 题目输入/输出中只能包含ASCII字符,禁止出现中文和unicode字符
049 在题目中提供数据生成器、强制在线的加解密算法必须真实有效,不得有误导或者任何欺骗行为
050 当题目需要输入字符串时,必须在输入描述中显式的指明字符串的字符集。
051 当题目描述中涉及到“集合”的概念时,需注意是否为“可重集”。当涉及到“子集”概念时,需注意是否为“真子集”,且是否包含“空集”。需在题目描述中显式给出,或不在题目描述中说明,但有样例支持且在样例解释中给出。
052 当题目涉及到子串/子区间/子序列/前缀/后缀等概念时,必须显式的注明①是否包含自身;②是否可以为空,或在样例中有所体现。
053 当涉及到有多少种不同的XX满足条件的描述时,需对“不同”做相应的解释。若题目首先需要选手进行某些“操作”,再求不同的“值”时,使用“本质不同”强调其值上的差别而非操作上的差异。例如:求本质不同的子序列/子串个数。
054 中文描述的题目中,使用“连续子区间/子段”代替“连续子序列”

严格遵守

规则ID 规则描述
012 除非任何有意义的样例都会暴露核心算法,否则禁止仅提供1组无意义的样例输入/输出。
035 计算几何题目中,构造任何边界数据都要求至少大于10倍EPS以上。
038 禁止在题目中有明显的语言倾向,若仅描述某种算法的实现,禁止出现特定语言实现的代码,应使用伪代码代替。

建议遵守

规则ID 规则描述
003 对于逻辑上判断yes,no的题目,应使用spj忽略大小写。且在输出描述中提醒:“你可以输出任意大小写的"Yes"或者"No"”
013 在不暴露核心算法的前提下,博弈类题目需提供至少1组先手胜利,1组后手胜利的样例输入/输出。
014 在不暴露核心算法/坑点的前提下,对于输出格式中的任何分支都要满足,例如"无解输出-1,否则xxx",除非任何无解样例都会暴露核心算法/坑点,否则样例中必须包含无解。
016 禁止与题目完全无关的大段背景描述(超过300字)。
017 题目描述的信息密度不易过大,同一句话中禁止包括复数个的解题关键条件。
021 出题人应保证除c/c++以外,python和java的其中一种可以通过题目。
037 如果输入变量的个数多余,则必须在题目描述醒目位置提醒其数据范围,建议选手使用过快速的输入方式。

无需遵守

规则ID 规则描述
018 数学概率、期望问题,在与解题和题目难度无关的情况下,一律使用模系实数。
041 整形变量的范围超过long long 范围时,必须在输入描述的醒目位置提醒。

规则释义/举例

规则005

不能出现例如std在随机数据下存在某种特定剪枝可以立刻返回,用时100ms,而特定构造可以将其卡到800ms,题目时限设置1s。对于这种情况必须保证其时限为2s以上。

规则007

以a+b问题为例,当题目为整体得分(ACM赛制)时:

第一行输入一个正整数表示测试用例的组数。

对于每组测试用例,输入一行两个整数

第一行输入一个正整数$T(1\leq T \leq 10^{9})$表示测试用例的组数。

对于每组测试用例,输入一行两个整数$a,b(-10^{9}\leq a,b \leq 10^{9})$。

当题目为部分得分(OI赛制)时:

第一行输入一个正整数表示测试用例的组数。

对于每组测试用例,输入一行两个整数

对于前的测试数据,保证

对于前的测试数据,保证

对于不包括在前的另外的数据,保证

对于的测试数据,保证

第一行输入一个正整数$T$表示测试用例的组数。

对于每组测试用例,输入一行两个整数$a,b$。

对于前$10\%$的测试数据,保证$1\leq a,b\leq 10$。

对于前$30\%$的测试数据,保证$1\leq a,b\leq 10^{9}$。

对于不包括在前$30\%$的另外$10\%$的数据,保证$a=0$。

对于$100\%$的测试数据,保证$1\leq T \leq 10^{9},-10^{9}\leq a,b \leq 10^{9}$。

另:对于存在部分得分(OI赛制)的情况下,可不在“输入描述”中给出任何数据范围,该为填入“备注”一栏。

规则008

例如使用纯随机生成器时,树深度期望为log,暴力可以通过。随机图跑最短路时,spfa的运行速度惊人的快,最短路须有卡spfa的特殊构造等。

规则009

不得以怕麻烦为理由要求选手输出最小/最大字典序的特解。但允许题目本身考察的内容就为最小/最大字典序,或最小/最大字典序为题目难度设计的一部分。

规则015

不得出现某个题目,在输入描述中填写个数字,但此题仅与有关,解题实际上不需要关注后序输入。

规则018

面向语言初学者/小白认为模系实数与难度有关,应考虑使用浮点数

规则024

可以采取以下两种方式

1、用.代替空白字符

......
../\..
./..\.
______

2、要求最外围输出边框

********
*      *
*  /\  *
* /  \ *
*______*
********

规则028

火车头特指以下代码

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)

规则030

cin关闭同步、getchar read不在此列。

如下代码不被认为是读入优化,因为在O2优化开关下,此优化不一定总是产生正收益,故仅作为出题人编码习惯处理。

int read()
{
	int s=0;
	char x=getchar();
	while(x<'0'||x>'9') x=getchar();
	while(x>='0'&&x<='9') s=s*10+x-'0',x=getchar();
	return s;
}

规则035

例如禁止出现构造三点近似共线,且斜率的情况。

规则043

例如要求输出个答案的异或和,可做出如下解释:,输出3。

规则044

由于不同编译器不保证std::random或者mt19937等随机数算法使用完全相同的随机数表,使用此方法会导致数据在不同平台不一致。

规则045

不同语言对于“取余”在负数中有着完全不同的实现和处理方式,但“取模”有着明确的数学定义,例如,但对于“取余”,在没有特别声明的情况下,均是正确的答案。

规则049

不得出现例如谋道题目在描述中要求选手强制在线,但强制在线的加密算法存在漏洞可以绕过改为离线算法,某道题目称自己提供随机数生成器,但该生成器存在数据分布不均的特性或者存在循环节,且std使用了该特性。

全部评论
许多比赛题目的排版都不美观或有错误,这篇文章也是。希望对这方面也能加以改进。
6 回复 分享
发布于 03-23 23:59 江苏
046 内容里多了 46、
1 回复 分享
发布于 2023-12-13 18:46 浙江
66
点赞 回复 分享
发布于 10-18 18:39 江西

相关推荐

11-11 10:52
点赞 评论 收藏
分享
评论
9
收藏
分享
牛客网
牛客企业服务