首页 > 代码库 > 2016大连网络赛 1008 & hdu5875 (优先队列+离线)=不确定暴力
2016大连网络赛 1008 & hdu5875 (优先队列+离线)=不确定暴力
题意:给你一个区间,求a_l%a_(l+1)%a_(l+2)%…%a_r 的值
分析:听说一个数在给定区间中只有不是很多的位置可一连续对它求模,所以想到一个比较暴力有可行的方法,猜想复杂度应该是nlogn。具体是这样的,从左到有枚举每个位置,
L[]记录[1,r]中所有元素连续取模到r的值。一开始把a[1]加进优先队列pq,对于第二位置,若pq.top()>=a[i],取出并取模,然后更新对应的位置l的答案,并把取模后答案插入优先队列,然后处理有区间是2的所有询问。对于第i个位置,若pq.top()>=a[i],取出并取模,然后更新对应位置l的答案,然后把取模后答案插入pq,然后处理右区间是i的所有询问。看上去是O(n^2)复杂度,其实并不会达到这么大,对于证明嘛…并不造..xjb乱猜。
差点忘记说坑了,要是用离线化做的话,询问是有相同的。(一开始用map记录gg了)
/************************************************Author :DarkTongCreated Time :2016/9/10 20:54:34File Name :1008.cpp*************************************************/#include <bits/stdc++.h>using namespace std;typedef unsigned long long ULL;typedef long long LL;const int INF = 0x3f3f3f3f;const double eps = 1e-9;const int maxn = 100000 + 100;typedef pair<int, int> Pair;int ans[maxn], L[maxn];vector<Pair> R[maxn]; //(L, id)priority_queue<Pair> cal; //(num, pos)int main(){ int T, cas=1, n; scanf("%d", &T); while(T--) { while(!cal.empty()) cal.pop(); for(int i=0;i<maxn;++i) R[i].clear(); scanf("%d", &n); for(int i=1;i<=n;++i) scanf("%d", &L[i]); int l, r, q; scanf("%d", &q); for(int i=1;i<=q;++i) { scanf("%d%d", &l, &r); R[r].push_back(make_pair(l, i)); } for(int i=1;i<=n;++i) { int l, r; while(!cal.empty()&&cal.top().first>=L[i]) { l = cal.top().second; r = i; L[l] = cal.top().first%L[i]; cal.pop(); cal.push(make_pair(L[l], l)); } cal.push(make_pair(L[i], i)); for(int j=0;j<R[i].size();++j) { l = R[i][j].first; ans[R[i][j].second] = L[l]; } } for(int i=1;i<=q;++i) printf("%d\n", ans[i]); } return 0;}
2016大连网络赛 1008 & hdu5875 (优先队列+离线)=不确定暴力
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。