CodeForces - 1514D Cut and Stick(线段树/随机数)

题目链接：点击查看

题目大意：给出一个长度为 $n$ 的数列，需要回答 $m$ 次询问，每次询问给出一段区间 $[l,r]$，输出至少需要将这段区间拆成的最少段数，使得每段区间中，假设区间长度为 $x$，那么出现次数最多的数字不能超过 $\lceil \frac{x}{2}\rceil$ 次

题目分析：对于某一段区间来说，假设区间长度为 $x$ ，出现次数最多的数字 $t$ 的出现次数为 $f$，满足 $f>\lceil \frac{x}{2}\rceil$ ，那么此时不等于 $t$ 的数字有 $x-f$ 个，贪心去分配的话，第一段可以放置：$x-f$ 个非 $t$ 的数字和 $x-f+1$ 个数字 $t$，剩下的每个数字 $t$ 独成一段，这样答案就是 $1+(f-(x-f+1))=2\ast f-x$

所以现在问题就转换为了快速求询问区间中的 $f$ 了，也就是区间众数，因为允许离线，所以理论上是可以直接用莫队去 $O(n\sqrt{n})$ 实现的，应该也可以用值域分块在线去写，时间复杂度是相同的，我直接写了一发 $O(n\sqrt{n\ast logn})$ 的，果不其然 T 掉了。。

不过本题其实并不需要求众数，只需要求出出现次数大于 $\lceil \frac{x}{2}\rceil$ 次的数字，对于没有达到这个阈值的，我们并不关心

这样就可以直接用线段树去实现了，因为如果满足大于了区间长度的一半的话，在 $pushup$ 的过程中一定是可以正确更新到的，结合二分找区间中某个数字的个数，时间复杂度为 $O(n\ast lo{g}^{2}n)$

还有一个比较玄学的解法，就是在区间中随机抓 $k$ 个数字，尝试令每个数字为区间的 $f$，不满足的概率为 $O(2^k)$，这里可以让 $k$ 取到 $40$，因为还是需要结合二分去查找区间数字的个数，所以时间复杂度为 $O(n\ast logn\ast k)$

代码：

线段树

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=3e5+100; int a[N]; vector<int>pos[N]; struct Node {int l,r,val; }tree[N<<2]; int get_num(int l,int r,int val) {return upper_bound(pos[val].begin(),pos[val].end(),r)-lower_bound(pos[val].begin(),pos[val].end(),l); } void pushup(int k) {int l=tree[k].l,r=tree[k].r;if(get_num(l,r,tree[k<<1].val)>get_num(l,r,tree[k<<1|1].val)) {tree[k].val=tree[k<<1].val;} else {tree[k].val=tree[k<<1|1].val;} } void build(int k,int l,int r) {tree[k]={l,r};if(l==r) {tree[k].val=a[l];return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); } int query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) {return 0;}if(tree[k].l>=l&&tree[k].r<=r) {return get_num(l,r,tree[k].val);}return max(query(k<<1,l,r),query(k<<1|1,l,r)); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;read(n),read(m);for(int i=1;i<=n;i++) {read(a[i]);pos[a[i]].push_back(i);}build(1,1,n);while(m--) {int l,r;read(l),read(r);printf("%d\n",max(1,query(1,l,r)*2-(r-l+1)));}return 0; }

随机数

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=3e5+100; int a[N]; vector<int>pos[N]; mt19937_64 eng(time(NULL)); int get_num(int l,int r,int val) {return upper_bound(pos[val].begin(),pos[val].end(),r)-lower_bound(pos[val].begin(),pos[val].end(),l); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;read(n),read(m);for(int i=1;i<=n;i++) {read(a[i]);pos[a[i]].push_back(i);}while(m--) {int l,r,ans=0;read(l),read(r);for(int i=1;i<=40;i++) {ans=max(ans,get_num(l,r,a[uniform_int_distribution<int>(l,r)(eng)]));}printf("%d\n",max(1,2*ans-(r-l+1)));}return 0; }

总结

以上是生活随笔为你收集整理的CodeForces - 1514D Cut and Stick(线段树/随机数)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。