首页 > 代码库 > 2016大连网络赛
2016大连网络赛
1008 Function
题解:如果a>=b,那么a%b<=a/2;
一个数n从本来的位置递减到0最多只需要logn次,也就是往右递减的位置最多不超过30个,那么我们就可以预处理出每个数往右递减的位置,然后离线询问,
用一个优先队列存储数和数所在的位置,比如8 7 6 9 10,先push(8,1)进去,然后每次把队首拿出来,8%7=1,把(1,1)push进去,然后把(8,1)pop出来,(7,2)push进去,优先队列最大值优先,当队首元素小于当前元素的时候,把当前元素和位置push进去,开始枚举下一个数
1 #include <iostream> 2 #include <algorithm> 3 #include <stdio.h> 4 #include <string.h> 5 #include <stdlib.h> 6 #include <queue> 7 using namespace std; 8 const int maxn=1e5+10; 9 struct node10 {11 int id;12 int data;13 int cnt;14 friend bool operator < (const node&a,const node&b)15 {16 return a.data<b.data;17 }18 };19 struct node220 {21 int pos;22 int data;23 void init()24 {25 pos=0;26 }27 };28 node a[maxn];29 node2 pos[maxn][32];30 priority_queue<node> q;31 int main()32 {33 int T;34 scanf("%d",&T);35 while(T--)36 {37 while(!q.empty()) q.pop();38 int n;39 scanf("%d",&n);40 for(int i=1;i<=n;i++)41 {42 int x;43 scanf("%d",&x);44 a[i].data=http://www.mamicode.com/x;45 a[i].id=i;46 a[i].cnt=0;47 pos[i][0].data=http://www.mamicode.com/x;48 pos[i][0].pos=i;49 for(int j=1;j<=30;j++)50 {51 pos[i][j].init();52 }53 }54 q.push(a[1]);55 for(int i=2;i<=n;i++)56 {57 node tmp;58 while(q.top().data>=a[i].data)59 {60 tmp=q.top();61 q.pop();62 tmp.data%=a[i].data;63 tmp.cnt+=1;64 pos[tmp.id][tmp.cnt].pos=i;65 pos[tmp.id][tmp.cnt].data=http://www.mamicode.com/tmp.data;66 q.push(tmp);67 68 }69 q.push(a[i]);70 }71 int m;72 scanf("%d",&m);73 while(m--)74 {75 int l,r;76 int ans;77 scanf("%d %d",&l,&r);78 if(l==r){79 printf("%d\n",a[l].data);80 continue;81 }82 else83 {84 for(int i=0;i<=30;i++)85 {86 87 if(pos[l][i].pos>r||pos[l][i].pos==0) break;88 ans=pos[l][i].data;89 }90 printf("%d\n",ans);91 }92 }93 94 }95 return 0;96 }
2016大连网络赛
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。