例题
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