萌娘百科衷心希望新型冠状病毒肺炎疫情早日结束!
关于解决“不完整”模板及分类问题的提案关于专题的提案关于权限申请中『萌娘百科的提问』的提案正在讨论中,欢迎参与!
  • 你好~!欢迎来到萌娘百科!如果您是第一次来到这里,点这里加入萌娘百科!
  • 欢迎具有翻译能力的同学~有意者请点→Category:需要翻译的条目
  • 如果您在萌娘百科上发现某些内容错误/空缺,请勇于修正/添加!编辑萌娘百科其实很容易!
  • 觉得萌娘百科有趣的话,请推荐给朋友哦~
  • 萌娘百科群119170500欢迎加入,加入时请写明【萌娘百科+自己的ID】~
  • 萌娘百科Discord群组已经建立,请点此加入!

OI梗

萌娘百科,万物皆可萌的百科全书!转载请标注来源页面的网页链接,并声明引自萌娘百科。内容不可商用。
(重定向自Farmer John
跳转至: 导航搜索
大萌字.svg
萌娘百科欢迎您参与完善本条目☆Kira~

可以从以下几个方面加以改进:

  • 部分用语介绍待补充
  • 部分用语内容可缩减
欢迎正在阅读这个条目的您协助编辑本条目。编辑前请阅读Wiki入门条目编辑规范,并查找相关资料。萌娘百科祝您在本站度过愉快的时光。

本条目收录与OI(信息学竞赛,英语:Olympiad in Informatics)及其参赛选手圈子有关的流行文化。

本条目仅收录常见梗,过于专业的用语不予收录,寻找专业用语请去OI Wiki等专业网站。

OI用语

%%%

膜拜大佬的场面

"%%%"是汉语“膜拜”的同义词,百分号越多,语气越强

"%"是数学中的百分号,同时在包括CC++等大多数编程语言中%也指取余或取模(类似除法中的余数,但对于负数取模和取余不同)

因"%"可读作模,并且较易于书写,它常被用于膜拜大佬,或吐槽意想不到但又很牛的操作,常与神犇同时出现。

例如:

  • --这道题很简单,(贴出代码)
    --%%%%%%%%%
  • --(贴出一份暴力但是可行的代码)
    --%%%%%%%%%
  • %*n (n>=3)
  • while(1) putchar('%');

蒟蒻

蒟蒻jǔ ruò(拉丁文学名:Amorphophallus konjac)本义是天南星科魔芋属多年生宿根性块茎草本植物[1]及以其为原料制作的食物。

因谐音"巨弱",在OI圈中通常用作谦辞,表示自己很弱拜托,你很弱诶,常与神犇连用。

蒟蒻这种说法在界外人士看上去很弱智,毕竟哪有自己说自己蠢的。

但是如上文,蒟蒻其实更像是一种自谦,方便自己不要脸的去问人题以及一种对他人工作的肯定。

几乎没有OIer会说别人是蒟蒻,毕竟每个人的潜力都是无限的,这也是OI圈里不成文的礼仪之一。

这也在你的计算范围之内吗?OIer!

例如:

神犇/巨佬

bēn巨佬等是OI圈内的敬辞,通常在各大OI社区(如洛谷等)中代替大牛大佬

“神犇”为“大牛”一词的升级版,“巨佬”(或“硕佬”)则是“大佬”的升级版(此外还有“奆佬”“㚐奆佬”“夶奆佬”这样的叠字版)。

常用于称赞指代方技术高超,常与%%%同时出现,一般用作第三人称。一般不用于自称

例如:蒟蒻前来膜拜神犇。

有时在OI题目中出现,用于夸奖做出AC题的人或鼓励人们做题(e.g.)。

著名神犇

水题

(待补充) 水题是指一道题过于简单,一般为竞赛的第一题。

此处“水”字的意义应该与百度贴吧中的水贴的水意义相同,意为无内涵。当然也可以理解为灌水

此类题目可以是

  • 字符串处理,如:(待补充)
  • 简单的数据处理,如:(待补充)
  • 嗯,即使是水题也有可能拿高精度加减来坑人。有时还会有一些恶心人的题限制数组大小逼你开vector,或者是让手打队列瘫痪逼你用queue,这种水题做的时候一定要注意数据范围和时间,空间!还是那句话,不开long long见祖宗。(本条为编写本条者的亲身经历)
  • BFS(深度优先遍历)用递归灌“水”DFS(广度优先遍历)用队列灌“水”(bushi)(怎么了,灌水就不是水了吗?)
  • 水题偶尔也会出现斐波那契,杨辉三角,角谷猜想之类的超简单动态规划,不过基本上都会把转移方程直接给你。

注意事项:

  • 不开long long见祖宗;
  • 不写freopen见祖宗;
  • 大数据处理取模取错见祖宗;
  • 数组开小见祖宗;
  • 内存超限见祖宗;
  • 文件名打错见祖宗;

自动机

自动机是OI圈中的一种表述,多为玩笑话,oo自动机表示自己的某个程序于OJOnline Judge上提交后全为oo状态(如WAWrong Answer)。

oo自动机原型为AC自动机,本义为一种字符串匹配的算法,具体参见AC自动机

由于其中的AC与OJ上的评测状态A CAccepted相同,不少人就拿此吐槽,还衍生出了其他的用法。例如:

  • 自动AC机(自动AC的代码)但千万不要这么做,你会被惩罚的(比如在洛谷上变成棕名)
  • RE自动机(全部都发生运行时错误R ERuntime Error数组越界除零溢出之类的)
  • WA自动机(提交上去全部答案错误W AWrong Answer
  • TLE自动机(全部超过时间限度T L ETime Limit Exceeded时间时间复杂度过高或程序中有无法退出的循环或递归)
  • MLE自动机(全部超出空间限度M L EMemory Limit Exceeded数组开得过大或递归过深)
  • OLE自动机(全部都输出了多余的东西O L EOutput Limit Exceeded
  • 元胞自动机

卡常

卡常OI娘调教OIer的一种方式,但由于大多数OIer不是抖M,所以OI娘的调教方式会令OIer难受。

“卡常”全称“卡常数”,指OI娘的题目会通过特殊数据去卡算法的常数项而并非本身的时间复杂度。卡常方式大致上可以分为两种,硬件卡常和算法卡常。

卡常原理

1.计算姬硬件卡常

出于计算姬的计算原理,当计算姬在计算除法,求余,开方等算法需要消耗的时间是直接进行位运算的数十倍乃至百倍。

目前时间复杂度最好的除法算法是利用牛顿-拉弗森方法完成的,可以将浮点数除法和IEEE 754定义下的浮点数求余运算的时间复杂度降低到与乘法相当;与之相仿的时,判断一个大整数是否是完全幂次数已经有线性时间的算法。然而,这些算法相对于浮点数加减法来说,仍然有很大差异。而涉及到超越函数的浮点数运算往往是通过帕德近似甚至麦克劳林级数展开所完成的,在时间上是低效的。

导致可怜的OIer被迫使用更加难以编写的位运算代替以上运算方式,并且,硬件卡常相当难以被发现。

比较难的OI还会卡计算姬的特性出题,类似下文:

P4064硬件卡常部分(原作者已授权)原地址

所以我们会用到与桶排类似的一种算法,基数排序。

不知道什么是基数排序的自行百度。

它的复杂度是O(n⋅max(ai)/base)

其中base是选取的基数大小,一般来说在不超过内存限制的情况下,选择的基数越大排序越快。

注意是一般情况下,不包括需要卡常数的时候。

然后考虑选择什么样的基数,由于目标大小是2^32-1以内,所以我们可以选择2^16或者2^8作为基数进行排序。(2^4太小,排序次数有点多了,不考虑)。

那么问题来了,选择哪个?

你可能觉得选择2^16作为基数只需要排两次就能出结果,应该比2^8排四次要快吧?

大错特错!常数要是算的这么简单,为什么大学还要学计算机组成原理?

要明白这个,首先引入一个东西,高速缓存器。

这当中就运用了计算姬的高速储存器关于“命中率”的原理,完美的体现了OI娘的S属性

2.OIer算法卡常

这种卡常是由算法本身的常数项(内部执行次数)与算法的不稳定性产生的,也是大家最常讨论的“卡常”

问题在于,前者可以优化,后者只能换算法,所以经常使OIer崩溃。

比较容易卡的算法有:快排(不稳定),动态规划(常数项大)以及大家喜闻乐见的SPFA

卡SPFA算法的方式相当多,包括但不限于网格图,稠密图,以及菊花图,因此卡常在某种意义上也成了OIer之间的调侃。

用法:

  • 看到有人用SPFA跑没负边的最短路
    • 你居然用SPFA,不怕它去世卡常吗?
  • 看到有人在可以用其他排序手段但任然用快排
    • 小心人家卡你常哦
  • OI成绩出来后发现原本不应该超时的题超时
    • Shift,这个垃圾竞赛卡我常!!!事实上很有可能是你算错时间复杂度了
著名卡常题

爆零

爆零在是OI圈指在一场考试中获得零分。

(待补充)

OI典故/成句

关于SPFA,它死了

SPFA算法示意图

关于oooo,它死了是一句OI圈的吐槽用语,表示oooo已经失去效力。

这个梗的由来是NOI2018。NOI2018 d1t1 归程需要使用最短路算法,而可用的一种最短路算法SPFA的时间复杂度是不确定的。所以出题人卡了这个算法的时间[2],并在讲评ppt上表示“关于SPFA,它死了”,这个梗因此诞生。

后来,当NOIP(全国青少年信息学奥林匹克联赛)在2019年因未知原因停办[3]后,洛谷站长kkksc03在第九次洛谷Fan Meeting上用“关于NOIP,它死了”进行了吐槽[4],将这个梗进一步发扬光大。(目前NOIP已复活[5]

用法举例:

  • 关于SPFA,它死了
  • 关于NOIP,它死了
  • 关于NOIP,它复活了
  • 关于CSP,它SPFA了
  • (待补充)

I AK IOI

某位OIer的失智发言

I AK IOI(oo AK xx)是OI圈的一个成句,常见于洛谷等具有讨论功能的OJ或其他社交平台。

其中AK意为“All-Killed”表示一套题里全部满分,与之相对的有AF “All-Failed”;后方的“IOI”则是OI的国际总决赛。

但是根据OI界日常装弱的气氛,这种说法存在可能性本应不大。

实际上,这很有可能源于OIer日常夸别人神犇配上的一句话,或者只是某种事实的阐述。

需要注意的是,并不能随便说一个人AK了某某竞赛,这很有可能会被当做阴阳怪气

如果你本来的目的就是如此那就不必在乎了

用法举例:

  • NOIp-J终试结果出来后
    • 哇,我居然AK了NOIp!
  • 某个用户的比赛期间有人满分
    • 恭喜 XX AK了某某比赛
  • 阴阳怪气(损人用)
    • 你个巨佬,YOU AK IOI CTSC !!!
  • I wanna AK IOI

骗分导论

全句为骗分过样例,暴力出奇迹。暴搜挂着机,打表出省一

你的NOIP.jpeg

是OIer自创的一句玩笑话。指在某些看起来难实际上用枚举、打表(如说在运算中需要求质数,在线求会比较慢,于是就离线先算好,把整个质数表存在一个常量数组里面,就是打表。)这种比较简单的算法来使此题AC或拿分从而不至于爆零。如在JSOI2018的绝地反击题中需要用到计算几何+二分图匹配,在一些人不会的情况下,有人才发现maxni=1dist((x0,y0),(xi,yi))−r只要能够算出来直接就能拿到50分。

骗分虽然有效,但是是歪门邪道,不要靠着每道题骗分的想法去比赛。(其实能骗到分就已经非常香了)

另外,有人才把这句话P在了《你的名字。》的海报上,有好几版,这里放出最经典的一版。

o年OI一场空,xxxx见祖宗

o年OI一场空,xxxx见祖宗是一句用于吐槽自己或他人在OI赛场上的表现的成句。

在每次OI比赛中,总有人写了一些沙雕的代码,而他们又总是后知后觉,在各大论坛上诉苦哭天喊地。本句具体出处未知。

用法举例(此处的“十”仅为示例,应用时可根据实际酌情更改):

  • 十年OI一场空,没开ull见祖宗 //因为n<=64,long long 只能表示2^63-1,所以有一个测试点过不去
  • 十年OI一场空,开了long long见祖宗 //同上
  • 十年OI一场空,SPFA见祖宗 //SPFA算法复杂度为O(km),但是在某些特殊构造丧心病狂的数据上会退化到 O(nm)
  • 十年OI一场空,文件打错见祖宗。//NOI系列竞赛需要使用文件输入输出,而如果文件名书写错误或没写就会失掉整题的分

rp++

rp是“人品”的缩写,代指运气;++是C语言家族中的自加号(+1)。OI圈内常用rp++祝福自己或他人在比赛时能人品爆发。

类似的用法还有rp++;while(1) rp++;、“rp爆unsigned long long”等。

关于RP,在某道变量名为rp的题中,会有人把某些语句改成不影响结果的rp++

我来NOIP只做三件事!oo!oo!oo!

我来NOIP只做三件事!oo!oo!oo!是从电影《让子弹飞》中截取片段进行填词,大多是自嘲当自己在试机或者竞赛时不会做题时的表现。最后一群人跪下的画面非常喜感。

我来NOIP只做3件事.gif

用法举例:

  • “我来NOIP只做三件事!爆零!睡觉!扫雷!(跪)”
  • “我来NOIP只做三件事!拿饭票!吃饭!走人!(跪)”
  • “我来NOIP只做三件事!爆零!爆零!还是TMD爆零!(跪)”
  • “我来NOIP只做三件事!骗分!打表!省一!(跪)”

A+B

输入两个整数 a,b,输出它们的和
——A+B Problem[6]

由于实现极为简单,故常作为OJ的试机题,以使新用户熟悉OJ的操作。

因为非常简单,所以经常被巨佬们乱搞,成为史上做法最多的题。

目前可以做的算法

  • 标准做法
  • 某死了的算法,dijkstra,prim,遍历等图论算法
  • 动归
  • dfs,bfs
  • 作为珂学家,是时候用珂朵莉树OLD DRIVER TREE做A+B problem了!
  • (待补充)
  • 详见各OJ题解区

说句闲话:研究xx的最好方法是/oo将会臭名昭著

说句闲话:研究xx的最好方法是/oo将会臭名昭著是OI圈的一个成句,来自于洛谷上某人抄袭题解后发的帖,他在帖中侮辱管理员和洛谷,导致他如愿以偿地被棕名(已变回灰名)。由于洛谷的几乎所有管理员回复了该帖,它成为洛谷史上最大管理员狂欢,它在OI圈中广泛传播,至今仍有人考古,也有人模仿它的格式发帖和回复。

OI中常出现的人物

Farmer John

Farmer John是USACO题目的通配角色USACO最大工具人

USACO每套题必会出现的人物,其工具人效果超出任何一类题目中的角色。

每天都要干农活,养无数的奶牛,有时还会被奶牛坑。

像是大多数的OI(如NOIp和CSP)中的人物名字都是换着来的,只有USACO是在反复迫害Farmer John。

现在已经成为众多OIer的迫害对象,在洛谷等用户可出题OJ被广为流传。

其他通配角色

  • 小A
  • uim
  • 八尾勇
  • 正妹
  • JOI君
  • Bessie

常出现的ACG角色

其他

OI数字梗

主条目:数字梗#算法竞赛

OI中的ASCII艺术

主条目:ASCII艺术#OI中的ASCII艺术

注释和外部链接

  1. zhwiki:蒟蒻
  2. 简单的阐述一下,就是SPFA算法消耗的时间有可能在极端情况成为一般情况的数千倍,相比之下同样可以使用的Dijkstra算法则不会有此特性。
  3. 停办通知
  4. 【FMT#9】洛谷 Fan Meeting Live #9 回放 第3:23秒
  5. 重办通知
  6. https://www.luogu.com.cn/problem/P1001