首页 > 代码库 > 2016大连网络赛

2016大连网络赛

2024-08-12 23:26:35   222人阅读

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 }
View Code

 

2016大连网络赛


联系
我们