竞赛讨论区 > 关于小白月赛49C题暴力通过问题的说明
头像
王清楚
编辑于 2022-05-07 12:02
+ 关注

关于小白月赛49C题暴力通过问题的说明

很抱歉,牛客小白月赛49中,部分同学使用n^2的暴力做法过掉了C题。我解释一下这个问题的原因。
1.5月6日(比赛当天)下午,为了修复评测机判题时间抖动的问题,我们更换了评测机。新评测机会比旧评测机速度快,但是我当时没有意识到速度加快会放过暴力的问题,所以并没有通知出题人。
也就是说,出题人和审题人测暴力代码的时候,使用的是慢的评测机,所以赛前测试用的暴力代码被卡掉了。但是比赛时更换了更快的评测机。导致用户900ms左右的暴力可以通过。
2.我去后台查看了出题人的数据。T是造满的,n也有一组1e5的。
然后使用用户代码提交,确定是n^2的复杂度。而且能通过
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=52072101

关于为什么n^2可以过百万的数据,经询问技术后,得到的回复是clang++的编译优化。 优化完了就不是n^2了。

数据截图:

图片说明
图片说明

技术解释:

gcc -O2 for循环里面的基本都优化在外面了,第二层for循环就这么几句了汇编了
就是cmp orr bne , 就是cmp 比较一下k和n orr 就是位或3个数,bne就是记性跳到L8循环
也就是说for循环里面是有的,但是只有3个位或运算,其他的运算都在for循环外面
位或这个东西在计算机里面很快的
图片说明
图片说明

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐