当前位置: 首页 > news >正文

4 对拍杂谈

对拍杂谈

0 前言

关于对拍,一句话描述清楚它的重要性:相当于数学中的验算。

我们oi中不能只凭感觉来判断一个程序的正确性,而要靠对拍来确定程序正确性。

当然,对拍过了也不能说明你的程序就一定正确,毕竟数据是你自己造的,暴力也是你自己写的,如果你没有考虑清楚,那么你的对拍其实是白费力气。

1 对拍的结构

对拍之前,我们要先了解一下对拍的结构。

对拍由以下几个程序构成:正解、暴力、随机数据生成器、拍子

正解就是你写的不确定正确性,但是时空复杂度符合题目要求的预备正解
暴力要特殊说明一下,暴力程序可以很慢,但是一定要保证绝对正确(甚至可以指数复杂度)

拍子就是将几个程序放在一起疯狂运行,然后判断你的正解答案和暴力的答案是否相同,从而达到判断正确性的效果。

2 暴力

先说暴力,刚才提到了暴力要绝对正确,因为如果你的暴力不能保证正确,那你的整个拍子就白写了。

我曾经遇到过一种情况,就是写了拍子,然后暴力程序的核心思路和正解相同,只是改了正解的其中一部分地方,也就相当于这个暴力只检查了改动的一部分的正确性,后来拍了半个小时,都没有问题,交上去 50 。

所以不要贪时间复杂度,怎么正确怎么来,当然如果有一个时间复杂度更优的也能保证绝对正确,那么当然是选更优的。

3 随机数据生成器

这个主要是一些板子,以及一些语法问题。

3.1 随机函数

这里为了保证随机数质量,我使用 mt19937 来生成随机数

mt19937 会返回一个无符号整数,范围是 \(0 \sim 2^{32} - 1\)

mt19937_64 返回一个无符号整形,范围是 \(0 \sim 2^{64} - 1\)

3.2 在一秒内生成多组数据

我们平常使用随机数据种子一般会设为 time0 ,但这样实际上有些缺点,因为如果你快速运行这个程序,就会发现其在一秒内生成的数据是相同的。

什么,你不信?我们写个程序验证一下。

random.cpp

#include <iostream>
#include <algorithm>
#include <random>using namespace std;int main () {mt19937 rng (time (0));cout << rng () << endl;return 0;
}

ts.cpp

#include <iostream>
#include <algorithm>using namespace std;int main () {double st = clock ();while (true) {system ("./random");double now = clock ();if ((now - st) / 1000 > 0.5) break;}cout << (clock () - st) / 1000 << "ms" << endl;return 0;
}

直接看运行 ts.cpp 的结果

image-20251004204526060

现在信了吧,所以如果我们用 time0 做种子,在高速生成随机数据的时候会出现很多随机数据,试想一秒只能跑一组同样的随机数据,效率太低。

怎么解决,我们动态读入种子,保证每次的种子不同,这样就能够保证随机数据的强度。

random.cpp

#include <iostream>
#include <algorithm>
#include <random>using namespace std;// 生成一个无符号整数 0 ~ 2^32 - 1
mt19937 rng;int main () {int sd;freopen ("seed.txt", "r", stdin);cin >> sd;rng.seed (sd);cout << rng () << endl;freopen ("seed.txt", "w", stdout);cout << (int)rng () << endl;return 0;
}

再次运行 ts.cpp ,看看结果

image-20251004210000992

http://www.hskmm.com/?act=detail&tid=24454

相关文章:

  • Matlab R2024b下载及详细安装教程,附永久免费Matlab安装包
  • Luogu P1966
  • 题解:P14036 [PAIO 2025] Rooks
  • 2025/8/26
  • 27 考研初试时间大约是什么时候?
  • 数据结构 - 跳表 Skip List
  • 06. 定时器
  • NOIP之前的复健记录
  • Linux 命令行安装达梦数据库
  • Google开源Tunix:JAX生态的LLM微调方案来了
  • 实用指南:Matlab通过GUI实现点云的快速全局配准(FGR)
  • 『OI 回忆录』停课有感
  • 『回忆录』初三第三学月
  • 完整教程:MySQL 5.7 主主复制 + Keepalived 高可用配置实例
  • 题解:P14074 [GESP202509 五级] 有趣的数字和
  • 解码Huffman 编码与 Huffman 树
  • 『回忆录』初三来高中的半学期
  • 10.1 容器云部署准备(一) - 实践
  • 关于缓冲区以及输出方式
  • 漏洞赏金计划的困境:i915漏洞与ChromeOS、Intel赏金项目剖析
  • RippleNet: Propagating User Preferences on the Knowledge Graph for Recommender Systems
  • 特地拎出来的总结
  • 2025异型件厂家推荐:邯郸市烁燊紧固件,广泛应用于建筑、桥梁、机械、电力、交通等诸多领域
  • Allow or block media autoplay in Firefox
  • [WC2018] 即时战略
  • 实用指南:Unity学习之C#的反射机制
  • HDF5文件 ——之三
  • 代码随想录算法训练营|Day 25
  • 深入解析:SAE J3072-2024插电式电动汽车(PEV)中的车载逆变器系统安全标准介绍
  • 冷僻模板整理