首页 > 编程语言 >【学习笔记】随机化算法

【学习笔记】随机化算法

时间:2023-11-10 21:15:01浏览次数:38  
标签:a1 return int 笔记 随机化 算法 随机 include

例题

P7831[COCI2009-2010#3] PATULJCI 题解

首先对每个颜色开一个vector<int>保存其位置,随后对于一段区间\([l,r]\)和一个颜色\(c\),可以很快速的求出\([l,r]\)内\(c\)出现的次数。

然后进行随机化,每次随机一个元素并查看他的出现次数。

若随机\(t\)次,那么随机不到的概率是\(\frac{1}{2 ^ t}\),当\(t\)取50时约等于\(10 ^ {-15}\),可以认为几乎不可能。

代码:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int t = 50;
int a1[300010],n,c,m,a,b;
vector<int> E[30010];
int query(int l,int r) {
	for(int i = 1;i <= t;i++) {
		int p = l + rand() % (r - l + 1);
		int res = upper_bound(E[a1[p]].begin(),E[a1[p]].end(),r) - lower_bound(E[a1[p]].begin(),E[a1[p]].end(),l);
		if(res > (r - l + 1) / 2) {
			return a1[p];
		}
	}
	return -1;
}
int main()
{
	cin >> n >> c;
	for(int i = 1;i <= n;i++) {
		cin >> a1[i];
		E[a1[i]].push_back(i);
	}
	for(int i = 1;i <= c;i++) {
		E[i].push_back(n + 1);
	}
	cin >> m;
	for(int i = 1;i <= m;i++) {
		cin >> a >> b;
		int ans = query(a,b);
		if(~ans) cout << "yes" << " " << ans << "\n";
		else cout << "no" << "\n";
	}
}

标签:a1,return,int,笔记,随机化,算法,随机,include
From: https://www.cnblogs.com/IANYEYZ/p/17825044.html

相关文章

  • openGauss学习笔记-119 openGauss 数据库管理-设置数据库审计-设置文件权限安全策略
    openGauss学习笔记-119openGauss数据库管理-设置数据库审计-设置文件权限安全策略119.1背景信息数据库在安装过程中,会自动对其文件权限(包括运行过程中生成的文件,如日志文件等)进行设置。其权限规则如下:数据库程序目录的权限为0750。数据库数据文件目录的权限为0700。ope......
  • 11/10训练笔记
    P7831[CCO2021]TravellingMerchant题解考虑出度为0的点显然不行随后,进行一个类似于拓扑排序的过程即可注意到需要建反图原图也得保留注意判-1代码:#include<iostream>#include<algorithm>#include<cstring>#include<vector>#include<queue>usingnamespacestd;str......
  • 【学习笔记】初等数论-组合计数
    加法原理若完成一件事的方法有\(n\)类,其中第\(i(1\lei\len)\)类方法包括\(a_i\)种不同的方法,且这些方法互不重合,则完成这件事共有\(\sum\limits_{i=1}^{n}a_i\)种不同的方法。乘法原理若完成一件事的步骤有\(n\)个,其中第\(i(1\lei\len)\)个步骤包括\(a......
  • 《信息安全系统设计与实现》学习笔记9
    《信息安全系统设计与实现》学习笔记9第六章信号和信号处理信号和中断广义的“进程”从事日常事务的人在用户模式或内核模式下运行的Unix/Linux进程执行机器指令的CPU“中断”是发送给“进程”的事件,它将“进程”从正常活动转移到其他活动,称为“中断处理”......
  • Java笔记—Java接口
    Interface接口简介接口(英文:Interface),在JAVA编程语言中是一个抽象类型,是抽象方法的集合,接口通常以interface来声明。一个类通过继承接口的方式,从而来继承接口的抽象方法。接口并不是类,编写接口的方式和类很相似,但是它们属于不同的概念。类描述对象的属性和方法。接口则包含类要实现......
  • Vue源码学习(十六):diff算法(三)暴力比对
    好家伙,这是diff的最后一节了 0.暴力比对的使用场景 没有可复用的节点:当新旧虚拟DOM的结构完全不同,或者某个节点不能被复用时,需要通过暴力比对来创建新的节点,并在真实DOM上进行相应的插入操作。0.1.例子一://创建vnodeletvm1=newVue({data:{name:'张三'......
  • 20211325 2023-2024-1 《信息安全系统设计与实现(上)》第九周学习笔记
     202113252023-2024-1《信息安全系统设计与实现(上)》第九周学习笔记一、任务要求自学教材第6章,提交学习笔记(10分),评分标准如下1.知识点归纳以及自己最有收获的内容,选择至少2个知识点利用chatgpt等工具进行苏格拉底挑战,并提交过程截图,提示过程参考下面内容(4分)“我在学***X知......
  • 回溯算法
    回溯算法处理5w条数据优化❓:我想根据当前节点id回溯出他的路径层级扁平数组......
  • LRU算法 C++
    #pragmaonce#include<list>#include<unordered_map>usingnamespacestd;classLRUCache{public:LRUCache(intcapacity):cap(capacity){m.reserve(capacity);m.max_load_factor(0.75);}intget(intkey)......
  • 梦断代码 读书笔记 02
    工程师和艺术家软件开发者是工程师还是艺术家。这个问题,总结了软件开发过程中无数细节问题,这些问题统统没有答案。软件开发领域的圣战比宗教中的还要多。从项目管理到软件设计,只有模糊的建议,以经验性方法为主导,估算工期的方法叫“拍”:一拍脑袋有了,一拍胸口干了,一拍大腿坏了,一拍......