【bzoj4810】[Ynoi2017]由乃的玉米田 莫队算法+STL-bitset
算法 STL 莫队
2023-09-11 14:22:40 时间
题目描述
由乃在自己的农田边散步,她突然发现田里的一排玉米非常的不美。这排玉米一共有N株,它们的高度参差不齐。
由乃认为玉米田不美,所以她决定出个数据结构题
这个题是这样的:
给你一个序列a,长度为n,有m次操作,每次询问一个区间是否可以选出两个数它们的差为x,或者询问一个区间是
否可以选出两个数它们的和为x,或者询问一个区间是否可以选出两个数它们的乘积为x ,这三个操作分别为操作1
,2,3选出的这两个数可以是同一个位置的数
输入
第一行两个数n,m
后面一行n个数表示ai
后面m行每行四个数opt l r x
opt表示这个是第几种操作,l,r表示操作的区间,x表示这次操作的x
定义c为每次的x和ai中的最大值,ai >= 0,每次的x>=2n,m,c <= 100000
输出
对于每个询问,如果可以,输出yuno,否则输出yumi
样例输入
5 5
1 1 2 3 4
2 1 1 2
1 1 2 2
3 1 1 1
3 5 5 16
1 2 3 4
样例输出
yuno
yumi
yuno
yuno
yumi
题解
莫队算法+STL-bitset
先将询问离线排序,对于每个询问,把它区间内包含的所有数放在一个桶里。
如果是3询问,直接暴力O(√n)枚举约数,即可。
对于询问1,一个naive的做法是枚举每个数,判断是否有比它小x的数。
我们可以使用bitset压位,优化这个过程,将bitset数组左移或右移x位并与原数组取与,判断是否存在。
对于询问2,将a+b=x转化为(100000-a)-b=100000-x后按照同样的方法处理。
#include <cstdio> #include <cmath> #include <bitset> #include <algorithm> #define N 100010 using namespace std; bitset<N> a , b; struct data { int opt , l , r , x , bl , id; }q[N]; int v[N] , cnt[N] , ans[N]; bool cmp(data a , data b) { return a.bl == b.bl ? a.r < b.r : a.bl < b.bl; } bool judge(int x) { int i; for(i = 1 ; i * i <= x ; i ++ ) if(x % i == 0 && cnt[i] && cnt[x / i]) return 1; return 0; } int main() { int n , m , si , i , lp = 1 , rp = 0; scanf("%d%d" , &n , &m) , si = (int)sqrt(n); for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &v[i]); for(i = 1 ; i <= m ; i ++ ) scanf("%d%d%d%d" , &q[i].opt , &q[i].l , &q[i].r , &q[i].x) , q[i].bl = (q[i].l - 1) / si , q[i].id = i; sort(q + 1 , q + m + 1 , cmp); for(i = 1 ; i <= m ; i ++ ) { while(rp < q[i].r) cnt[v[++rp]] ++ , a[v[rp]] = b[100000 - v[rp]] = 1; while(lp > q[i].l) cnt[v[--lp]] ++ , a[v[lp]] = b[100000 - v[lp]] = 1; while(rp > q[i].r) cnt[v[rp]] -- , a[v[rp]] = b[100000 - v[rp]] = cnt[v[rp]] , rp -- ; while(lp < q[i].l) cnt[v[lp]] -- , a[v[lp]] = b[100000 - v[lp]] = cnt[v[lp]] , lp ++ ; if(q[i].opt == 1) ans[q[i].id] = (a & (a >> q[i].x)).any(); else if(q[i].opt == 2) ans[q[i].id] = (a & (b >> (100000 - q[i].x))).any(); else ans[q[i].id] = judge(q[i].x); } for(i = 1 ; i <= m ; i ++ ) printf("%s\n" , ans[i] ? "yuno" : "yumi"); return 0; }
相关文章
- 神经网络与机器学习 笔记—Rosenblatt感知器收敛算法C++实现
- (《机器学习》完整版系列)第7章 贝叶斯分类器——7.10 EM算法的使用场景及步骤(反复循环执行E步和M步)
- STL非变易算法
- K-近邻算法之案例:鸢尾花种类预测--数据集介绍
- 百度面试——AI算法岗
- C#,图像二值化(24)——局部阈值算法的NiBlack算法及源程序
- C#,计算几何,计算机图形学(Computer Graphics)洪水填充算法(Flood Fill Algorithm)与源代码
- STL - 函数作为算法的参数
- Dijkstra——通过不断松弛来解决单源最短路径问题的算法
- 孙玄&辜教授:基于Linux内核的时间轮算法设计实现【附代码】
- 《数据结构与算法 C语言版》—— 1.7上机实验
- 【C++】STL常用算法
- K-D TREE算法原理及实现
- 华为OD机试 - 最少停车数(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 智能算法——蚁群算法
- STL algorithm算法lexicographical_compare(30)
- 收集到的--关于算法很好的网址
- 【bzoj2506】calc 根号分治+STL-vector+二分+莫队算法
- 【bzoj3207】花神的嘲讽计划Ⅰ Hash+STL-map+莫队算法