百科问答小站 logo
百科问答小站 font logo



在信息学竞赛中,你见过哪些"这都能AC!?"的题? 第1页

  

user avatar   emptysetvvvv 网友的相关建议: 
      

哈哈哈哈各种乱搞大法。

某次校内模拟赛 T3,题意大致如下:

题目描述
给定 个节点的树,求树上有多少个三元组 (两两不同)满足其中任意两个点的树上距离不超过给定常数 .
数据范围 .
时间限制 2s

现场感觉可能是个不太套路的点分治,敲了几十行发现不太对劲咋一坨细节想不清楚,再一看表发现就剩一个小时多一点,估计以我的代码能力是写完也调不出来愉快爆零那种。正当我打算打出 GG 退出游戏的时候,突然灵光一闪虎躯一震,朴素的暴力也不过是 ,评测姬是 64 位,再考虑到吸氧,还跑不满,那么如果....[斜眼笑]

我立即写了一个 dfs 略加剪枝的预处理,用bitset 乱搞存距离是否不超过 ,然后暴力有序枚举前两个点在bitset里查,总复杂度 ,忐忑不安的提交了(就是个很无聊的暴力)。

结果震撼我妈这暴力跑得飞快 20 个测试点只有一个点跑了 1s 以上成功 AC,绝了。

最后正解出来的确是个点分治,但是比较麻烦里面还要强制离线又要动态维护什么的还要考虑计重反正是我绝对写不出来的,哈哈哈哈幸亏老子当时没有死刚正解(原谅我比较弱)。


要说最震撼的,还是某次模拟赛,std 有问题数据全部出锅。

然而,就在这种情况下,依然有某位神犇猜测到数据出锅而成功 AC 了...

全场目瞪狗呆,或许,这就是神犇之所以是神犇吧[颤抖]。




  

相关话题

  奥赛生做高考题是种怎样的体验? 
  偏序性质的有向无环图的最大独立集如何求解? 
  在编程中有没有巧妙运用数学知识解决过问题? 
  如何评价 2021 年 ICPC 银川赛区? 
  你在写程序的时候经历过哪些有趣的事? 
  为什么埃式筛法的时间复杂度是O(nloglogn)? 
  将并行计算纳入算法竞赛,是否合适? 
  大学生如何实现一个数据库? 
  如何看待两次 IOI 金牌,一次 ACM 全球总决赛亚军的清华大学计算机系毕业生去高中当信息学教师? 
  因为哪件事你对曾勃粉转黑? 

前一个讨论
为什么现在的网络风气越来越保守和缺乏包容度呢?
下一个讨论
郭德纲有多博学?





© 2024-11-08 - tinynew.org. All Rights Reserved.
© 2024-11-08 - tinynew.org. 保留所有权利