蓝桥杯(OI)赛制技巧:对拍

这篇具有很好参考价值的文章主要介绍了蓝桥杯(OI)赛制技巧:对拍。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

视频讲解

众所周知,OI赛制每道题提交之后都没有任何反馈,不会返还任何评测信息因为比赛的时候压根就没法评测,类似于你数学考试做卷子,考试的时候可以随便更改你写的内容等到考试结束就要交卷然后批改过几天才给分。
那当你一道题写完后,不知道自己是否是对的,自己也测了很多组数据,干瞪眼看也看不出来啥错的时候这时候就需要对拍来帮你验证自己写的是否正确,对拍简单的说就是写了一个简易得评测器。
对拍由三部分组成,一个是你准备交上去的程序,我们称为待测程序,一个是我们写的一个评测程序,通常是暴力写的,一定要保证他是对的,即使性能不好,还有一个就是随机生成数据的程序,接下来就吧随机生成的数据传给待测程序和评测程序,然后将他俩的结果进行比对,如果一样那大概率你写的这个就是对的,如果不一样那肯定就是错的(前提是你写的评测程序要是对的)。
这里说一下待测程序和评测程序区别,有些人可能会有疑问既然评测程序要保证是对的那为啥不直接交评测程序上去,这是个误区,评测程序是要保证对的但他的性能一般,举个例子,比如有个题数据量是1e6,你写了一个O(NlogN)的算法,但是不确定这个是不是对的,所以你写了一个暴力评测程序,因为是暴力写的所以正确率很高但是只能处理1e3的数据,所以我们就生成一些1e3以内的数据来用评测程序去验证你写的这个待测程序正确性,当然也不一定非得是暴力程序只要保证他一定是对的就行,性能无所谓当然越高越好这样能测的数据范围也越大,常见的有:

  • DFS(爆搜)测DP
  • Floyd测Dijkstra
  • Bellman-Ford测SPFA(已死勿扰)
  • Prim测Kruskal
  • …(挺多的其实)

那接下来就拿一道真题举个例子

真题链接

欢迎来我校OJ目前正在收录所有蓝桥杯历年真题已经收录了很多了
这里说一下打程序设计竞赛的时候看到一个题得一个分析切入点就是从数据量去反推他的时间复杂度,然后反推他可能涉及的算法。

yxc大佬总结的经验,一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下,C++代码中的操作次数控制在 1e7∼1e8
为最佳。
下面给出在不同数据范围下,代码的时间复杂度和算法该如何选择:

时间复杂度 常用算法
N≤30 => 指数级别 dfs+剪枝,状态压缩dp
N≤100 => O(N3) floyd,dp,高斯消元
N≤1000 => O(N2),O(N2logN) dp,二分,朴素版Dijkstra、朴素版Prim、Bellman-Ford
N≤10000 => O(N∗√N), 块状链表、分块、莫队
N≤100000 => O(NlogN) 各种sort,线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分
N≤1000000 => O(N)以及常数较小的 O(NlogN) 算法 单调队列、 hash、双指针扫描、并查集,kmp、AC自动机,常数比较小的 O(nlogn)的做法:sort、树状数组、heap、dijkstra、spfa
N≤10000000=> O(N) 双指针扫描、kmp、AC自动机、线性筛素数
N≤1e9=> O(√N) 判断质数
N≤1e18=> O(logN) 最大公约数,快速幂, 二分
N≤1e1000 => O(k) 高精度加减乘除
N≤10100000=> O(logK×loglogK) k表示位数,高精度加减、FFT/NTT

比如一道题数据量1e6那80%就是O(N)或者O(NlogN)这种时间复杂度,那可能设计的算法就那些再结合题分析就可以缩小设计算法范围可以帮助你去解决一道题。
这个题的思路也不需要过多的讲主要是说一下对拍咋写,视频里也说了我这里就贴一下模板代码

待测程序模板:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll temp[1500000], sum[1500000];
ll cal(ll n)
{
	return (n+1)*n/2;
}

int main()
{
	freopen("input.txt","r",stdin);//生成得数据文件
	freopen("output1.txt","w",stdout);//输出文件
	//下面填你的待测程序
	/*
	ios::sync_with_stdio(false);
	ll index = 1;
	ll endL;
	while(1)
	{
		temp[index] = temp[index-1] + index;
		sum[index] = sum[index-1] + temp[index];
		if(temp[index] > 1e12)
		{
			endL = index;
			break;
		}
		index++;
	}

	ll T;
	cin >> T;
	ll l, r, res;
	for(ll i = 0; i < T; i++)
	{
		cin >> l >> r;
		ll leftL = lower_bound(temp, temp+endL, l) - temp;
		ll rightL = lower_bound(temp, temp+endL, r) - temp;
		res = sum[rightL-1] - sum[leftL-1];
		res -= cal(l-temp[leftL-1]-1);
		res += cal(r-temp[rightL-1]);
		cout << res+1 << endl;
	}
	*/
	return 0;
}

评测程序模板:

#include<iostream>
using namespace std;
typedef long long ll;
ll f(ll x){
	ll res=0,cou=0,sum=0;
	while(res+cou<=x){
		cou+=res;
		sum+=cou;
		res++;
	}
	sum+=(1+x-cou)*(x-cou)/2;
	return sum;
}
int main(){
	freopen("input.txt","r",stdin);//生成得数据文件
	freopen("output2.txt","w",stdout);//输出文件
	//下面写你的评测程序咋对咋来
	/*
	ios::sync_with_stdio(false);
	ll n,l,r;
	cin>>n;
	while(n--){
		cin>>l>>r;
		cout<<f(r)-f(l-1)<<endl;
	}
	*/





	return 0;
}

随机生成数据模板:

#include<iostream>
#include<ctime>
#include<fstream>
using namespace std;
void data(){
	ofstream fout("input.txt");//将数据录入到input文件
	//根据题生成所需得数据然后数据范围要根据你的暴力程序去确定范围
	/*
	int n=rand()%101;
	int l,r;
	fout<<n<<endl;
	while(n--){
		l=rand()%101,r=rand()%101;
		fout<<l<<" "<<r<<endl;
	}
	*/
	fout.close();

}
bool test(){
	data();//生成数据
	system("test.exe");//运行待测程序
	system("bl.exe");//运行评测程序
	return !system("fc output1.txt output2.txt");//比对这俩的输出是否一样
}
int main(){
	srand(time(NULL));
	for(int i=0;i<100;i++){//随便测个100次
		if(!test()) break;
	}
	return 0;
}

我这个对拍程序其实一般,有很多大佬的对拍板子性能更好,还有一些专门生成图或者树这些的板子你们也可以搜一下看看,但对付蓝桥杯这个应该够用。文章来源地址https://www.toymoban.com/news/detail-422363.html

到了这里,关于蓝桥杯(OI)赛制技巧:对拍的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯单片机类按键代码讲解和考点探究(三行代码消抖讲解)

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 CON3中将1,2用跳线帽短接是矩阵键盘,可用范围为S4到S19。将2,3短接则是独立按键,可用范围是S4到S7. 按键原理讲解 单取一个按键,一端接到GND,一段接到单片机的IO口上(以下称I口,输入口)。当按

    2023年04月20日
    浏览(71)
  • 【蓝桥杯嵌入式】蓝桥杯第十二届省赛程序真题,真题分析与代码讲解

    🎊【蓝桥杯嵌入式】专题正在持续更新中,原理图解析✨,各模块分析✨以及历年真题讲解✨都在这儿哦,欢迎大家前往订阅本专题,获取更多详细信息哦🎏 🎏【蓝桥杯嵌入式】蓝桥杯第十届省赛真题 🎏【蓝桥杯嵌入式】蓝桥杯第十三届省赛程序真题 🪔本系列专栏 -  

    2023年04月15日
    浏览(92)
  • 浅谈 OI 中各种合并操作

    合并操作一直是 OI 中一大考点,今天请各位跟着笔者来梳理一下各种合并操作。 几乎可以说是最经典的合并了。 假定我们可以在 (O(k)) 的时间内往某个集合中插入一个数,那么我们就可以在 (O(n log n k)) 的时间内合并若干个 元素总量为 (n) 的集合。 看到查询绝对众数我

    2024年02月05日
    浏览(32)
  • 【蓝桥杯嵌入式】蓝桥杯嵌入式第十四届省赛程序真题,真题分析与代码讲解

     🎊【蓝桥杯嵌入式】专题正在持续更新中,原理图解析✨,各模块分析✨以及历年真题讲解✨都已更新完毕,欢迎大家前往订阅本专题🎏 🎏【蓝桥杯嵌入式】蓝桥杯第十届省赛真题 🎏【蓝桥杯嵌入式】蓝桥杯第十二届省赛程序真题 🎏【蓝桥杯嵌入式】蓝桥杯第十三届省

    2023年04月15日
    浏览(104)
  • 蓝桥杯统计子矩阵前缀和C++(附图文超详细讲解)(保姆级)

    给定一个 N × M 的矩阵 A,请你统计有多少个子矩阵 (最小 1 × 1,最大 N × M) 满足子矩阵中所有数的和不超过给定的整数 K?  第一行包含三个整数 N, M 和 K.  之后 N 行每行包含 M 个整数,代表矩阵 A. 一个整数代表答案。 满足条件的子矩阵一共有 19,包含: 大小为 1 × 1 的有

    2023年04月08日
    浏览(39)
  • 【OI学习笔记】基础算法-前缀和与差分算法

    板块:基础算法、线性优化 难度:较易 前置知识:C++基础语法 在一维空间中,对于一个数据总量为 n n n 的数组 a a a ,有数据 a [ 1 ] , a [ 2 ] , a [ 3 ] , . . . , a [ n − 1 ] , a [ n ] a[1],a[2],a[3],...,a[n-1],a[n] a [ 1 ] , a [ 2 ] , a [ 3 ] , ... , a [ n − 1 ] , a [ n ] ,定义一个数组 s u m sum s u m ,

    2024年02月08日
    浏览(51)
  • OI 数论中的上界估计与时间复杂度证明

    其实不少高等数学 / 数学分析教材在讲解无穷小的比较时已经相当严谨地介绍过大 O、小 O 记号,然而各种历史习惯记法的符号滥用(abuse of notation) [1] 直到现在都让笔者头疼. These notations seem to be innocent, but can be catastrophic without careful manipulation. For example, n = O ( n 2 ) ∧ n 2 =

    2023年04月18日
    浏览(37)
  • 如何参与Cetus和Oi! Network联合ISO认购和空投奖励?

    Cetus是建立在Sui和Aptos链上的集中流动性分散交易协议(DEX)。 作为Sui链上的基石项目,近日成功完成了由OKX Ventures和KuCoin Ventures领导的种子轮融资。 Cetus和Oi! Network联合ISO认购和空投公告: 普惠奖:10:00 UTC 5月6日前,达到最低500 $MOM质押的条件,在Oi! Network上完成3个和Cetus

    2024年02月05日
    浏览(34)
  • 深入讲解VsCode各场景高级调试与使用技巧

    VsCode自从诞生以来,以其各自优异的特性迅速走红。尤其是对于前端开发小伙伴来说,几乎成为必不可少的开发工具。所以,熟练掌握VsCode的各自使用技巧与调试技巧会让你的日常开发工作效率倍增。本文将会以大量图文的方式,从下面几个方面详细介绍VsCode的各种技巧:

    2024年02月06日
    浏览(53)
  • DFS(深度优先搜索)详解(概念讲解,图片辅助,例题解释,剪枝技巧)

    目录 那年深夏 引入 1.什么是深度优先搜索(DFS)? 2.什么是栈? 3.什么是递归? 图解过程  问题示例 1、全排列问题 2、迷宫问题 3、棋盘问题(N皇后)  4、加法分解 模板 剪枝 1.简介 2.剪枝的原则   3.剪枝策略的寻找的方法 4.常见剪枝方法 最后 他终于抬起头,眨了眨眼睛

    2023年04月08日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包