蓝桥杯幸运数(线段树)

时间:2021-07-18 06:00:58

不知道怎么搞的就报名了蓝桥杯,还报的B组的。。。

然后就开始刷刷历年的题目,结果发现题目、数据巨坑。 数据是怎么乱搞都能得个75。。。

这题幸运数测试数据也是太水了,以至于暴力的通通能过,目测题目最大数据也就是10^4+ 不超过10^5

本来想水水就算了的,但是不解为什么锦囊说用堆写。。。想了几天堆的解法,发现有点不好搞,但是用线段树就可以很好的解决了,因为考研很久没写过代码了,复习复习线段树就敲了下。。。

复杂度O(nlog(n)) ,线段树写的比较搓,常数有点大,提交800+ms飘过。

如果用题目给的n为上界,那么就直接0ms飘过了。

解法懂线段树的应该想想就能想的到。

 

  历届试题 幸运数  
时间限制:1.0s   内存限制:256.0MB
   
问题描述

幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成
。

首先从1开始写出自然数1,2,3,4,5,6,....

1 就是第一个幸运数。

我们从2这个数开始。把所有序号能被2整除的项删除,变为:

1 _ 3 _ 5 _ 7 _ 9 ....

把它们缩紧,重新记序,为:

1 3 5 7 9 .... 。这时,3为第2个幸运数,然后把所有能被3整除的序号位置的数删去。注意,是序号位置,不是那个数本身能否被3整除!! 删除的应该是5,11, 17, ...

此时7为第3个幸运数,然后再删去序号位置能被7整除的(19,39,...)

最后剩下的序列类似:

1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, ...
输入格式
输入两个正整数m n, 用空格分开 (m < n < 1000*1000)
输出格式
程序输出 位于m和n之间的幸运数的个数(不包含m和n)。
样例输入1
1 20
样例输出1
5
样例输入2
30 69
样例输出2
8

 

蓝桥杯幸运数(线段树)蓝桥杯幸运数(线段树)
  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <string.h>
  4 #include <stdlib.h>
  5 #include <algorithm>
  6 using namespace std;
  7 #define N 1000010
  8 
  9 //来一发线段树
 10 int n,m;
 11 int l[4*N],r[4*N],mi[4*N],flag[4*N],pos[4*N];//pos用来记录区间最小值得位置
 12 int save[N];
 13 int mipos;
 14 
 15 
 16 void down(int s)
 17 {
 18     flag[2*s]+=flag[s];
 19     mi[2*s]-=flag[s];
 20 
 21     flag[2*s+1]+=flag[s];
 22     mi[2*s+1]-=flag[s];
 23 
 24     flag[s]=0;
 25 }
 26 
 27 void up(int s)
 28 {
 29     if(mi[2*s]<=mi[2*s+1]) pos[s]=pos[2*s];
 30     else pos[s]=pos[2*s+1];
 31     mi[s]=min(mi[2*s],mi[2*s+1]);
 32 }
 33 
 34 void build(int tl,int tr,int s)
 35 {
 36     l[s]=tl; r[s]=tr;
 37     if(tl==tr)
 38     {
 39         flag[s]=0;//没有标记
 40         mi[s]=1111111;
 41         pos[s]=tl;
 42         return ;
 43     }
 44     int mid=(tl+tr)/2;
 45     build(tl,mid,2*s);
 46     build(mid+1,tr,2*s+1);
 47     up(s);
 48 }
 49 
 50 
 51 void modify(int id,int num,int s)
 52 {
 53     if(l[s]==id&&r[s]==id)
 54     {
 55         mi[s]=num;
 56         flag[s]=0;
 57         return ;
 58     }
 59     if(flag[s]!=0)
 60     {
 61         down(s);
 62     }
 63     int mid=(l[s]+r[s])/2;
 64     if(id<=mid) modify(id,num,2*s);
 65     else modify(id,num,2*s+1);
 66     up(s);
 67 }
 68 
 69 int query(int tl,int tr,int s)
 70 {
 71     if(l[s]==tl&&tr==r[s])
 72     {
 73         //不能在这里搞,要在下一个弄,因为这个时候你不知道最小值是那个
 74         return mi[s];
 75     }
 76     if(flag[s]!=0) down(s);
 77     int mid=(l[s]+r[s])/2;
 78     if(tr<=mid) return query(tl,tr,2*s);
 79     else if(tl>mid) return query(tl,tr,2*s+1);
 80     else{
 81         return min(query(tl,mid,2*s),query(mid+1,tr,2*s+1));
 82     }
 83 }
 84 
 85 void allsub(int tl,int tr,int s)
 86 {
 87     if(l[s]==tl&&r[s]==tr)
 88     {
 89         flag[s]++;
 90         mi[s]--;
 91         return ;
 92     }
 93     if(flag[s]!=0) down(s);
 94     int mid=(l[s]+r[s])/2;
 95     if(tr<=mid) allsub(tl,tr,2*s);
 96     else if(tl>mid) allsub(tl,tr,2*s+1);
 97     else
 98     {
 99         allsub(tl,mid,2*s);
100         allsub(mid+1,tr,2*s+1);
101     }
102     up(s);
103 }
104 
105 //这个可以弄掉去
106 /*
107 void findmi(int tl,int tr,int num,int s)
108 {
109     if(l[s]==r[s])
110     {
111         //现在找到位置了,然后修改就行了
112         modify(l[s],save[l[s]],1);
113         if(l[s]!=1) allsub(1,l[s]-1,1);
114         return ;
115     }
116     if(flag[s]!=0) down(s);
117     int mid=(l[s]+r[s])/2;
118     if(tr<=mid) findmi(tl,tr,num,2*s);
119     else if(tl>mid) findmi(tl,tr,num,2*s+1);
120     else
121     {
122         //负责度有点问题啊,我操!
123         if( query(tl,mid,1) == num) findmi(tl,mid,num,2*s);
124         else findmi(mid+1,tr,num,2*s+1);
125     }
126 }
127 */
128 
129 void findmi(int tl,int tr,int num,int s)
130 {
131     if(l[s]==tl&&tr==r[s])
132     {
133         if(mi[s]==num) mipos=min(mipos,pos[s]);
134         return ;
135     }
136     if(flag[s]!=0) down(s);
137     int mid=(l[s]+r[s])/2;
138     if(tr<=mid) findmi(tl,tr,num,2*s);
139     else if(tl>mid) findmi(tl,tr,num,2*s+1);
140     else{
141         findmi(tl,mid,num,2*s);
142         findmi(mid+1,tr,num,2*s+1);
143     }
144 }
145 
146 int main()
147 {
148     //scanf("%d%d",&n,&m);
149     build(1,1000000,1);
150     int cnt=0;
151 
152     save[++cnt]=2;
153     modify(cnt,2,1);
154     for(int i=3;i<=1000000;i++)
155     {
156         //应该是从3开始
157 
158         int tmi=query(1,cnt,1);
159         if(tmi==1) //说明发现了一个行的
160         {
161             mipos=1111111;
162             //找出一个为1的最小的,并修改
163             findmi(1,cnt,tmi,1);
164             modify(mipos,save[mipos],1);
165             if(mipos!=1) allsub(1,mipos-1,1);
166         }else //得到一个幸运数
167         {
168             //现有的全部减1
169             allsub(1,cnt,1);
170             save[++cnt]=i;
171             modify(cnt,i-cnt,1);
172         }
173     }
174     //速度太慢有待改进
175 
176     int n,m;
177     scanf("%d%d",&n,&m);
178     int ans=0;
179     for(int i=1;i<=cnt;i++)
180     {
181         if(save[i]<m&&save[i]>n) ans++;
182     }
183     printf("%d\n",ans);
184     return 0;
185 }
ACCODE