• 欢迎光临~

ACM初学者指南学习心得

开发技术 开发技术 2022-12-28 次浏览

2022年快过完了,上学期有点摆烂,最近刚刚阳过,在家颓废了好几天。昨天看了一部电影《大学》,非常励志。看完电影,深感自己大学以来这一年半过得有点小糟糕,昨天被刺激了一下,今天下定决心今后不能再摸鱼了,要好好学习,努力奋斗。所以想每天记录一下自己的学习心得,既是对每一天的总结,也算是对自己学习的一种督促吧!

报名了2023年的蓝桥杯,今天看了老师发的初学者指南,感觉非常有用。

OJ

这个代理网站列出了著名的OJ。

数据的构造、对拍

  • 题目:给你n个整数,请按从大到小的顺序输出其中前m大的数。
  • 输入:每组测试数据有两行,第一行有两个数n, m(0 < n, m < 1000000),第二行包含n个各不相同,且都处于区间[-500000, 500000]的整数。
  • 输出:对每组测试数据按从大到小的顺序输出前m大的数。

如何构造极大范围内的随机数

例如,生成[1, 1000000]内的随机数。

但是,rand() 只能生成大小在[0, RAND_MAX]内的随机数。RAND_MAX=32768

2个方法:

(1)

rand()*rand() ,这样很简单,不过几乎不能产生素数。

(2)

unsigned long ulrand() {//生成一个大随机数
 return (
     (((unsigned long)rand() << 24) & 0xFF000000ul) 
     | (((unsigned long)rand() << 12) & 0x00FFF000ul) 
     | (((unsigned long)rand()) & 0x00000FFFul));
}

生成 [MIN, MAX]之间的一个随机数。

const int MAX = 1000000;//100万 
const int MIN = 0;

int big_rand = ulrand() % (MAX-MIN + 1) + MIN;//大随机数

如何去掉重复的随机数

简单又最快的方法:hash,用一个hash数组判断重复。(不过,这个方法的问题是:产生的随机数都在 [0,100万](或者可以扩大到[0,1000万] )之内)。

用hash判重和去重:

int myhash[MAX];//hash表
int mynum[MAX];//记录不同的随机数

下面处理随机数big_rand:

if(myhash[big_rand] == 0) { //第big_rand位置还没有
     myhash[big_rand] = 1;            
     //随机数big_rand ,登记在myhash[]的第big_rand个位置
     mynum[num]= big_rand;//记录随机数
     num++;//记录随机数的数量
}

【算法·哈希】哈希Hash判重算法入门_pigzhouyb的博客-CSDN博客_哈希判重

如何进行对拍

把程序提交到OJ之前,要先检验程序的正确性。前面已经有了输入测试数据,那么输出数据如何产生?
再写一个暴力的程序,它肯定会超时,但是结果是正确的。对照两个程序的输出是否一致。

比较2个程序的输出是否一样:

Windows:fc命令

Linux:diff命令

做好编程笔记

刷题需要做笔记!

程序员灯塔
转载请注明原文链接:ACM初学者指南学习心得
喜欢 (0)