此题测试时预处理等了很久,结果470ms过了。。。。。。

题意:开始不怎么懂,结果发现是这个:

   波兰裔美国数学家斯塔尼斯拉夫·乌拉姆(Stanislaw Ulam)在20世纪50年代中期开发出了另一种筛法:从正整数序列开始,先将数列中的第2n个数(偶数)删除,只留下奇数;这样剩下的数列中第二项是3,因此将新数列的第3n个数删除;再剩下的新数列中的第三项为7,因此将新数列的第7n个数删除;再剩下的新数列中的第四项为9,因此将新数列的第9n个数删除;这样继续下去,最终有一些数永远地逃离了被删除的命运而留下来,这就是为什么乌拉姆把它们称作“幸运数”。

  求的是给你一些(<=100000)数字n(0<n<=2000000),问他是否可以被分成两个幸运数:L1<=L2,并保证(L2-L1)最小

题解:首先预处理出所有数字中有哪些幸运数字,然后我们可以看到给你的数字个数比数字大小要小,所以不需要预处理出所有数字的答案。

可以看到删除2n,3n,7n。。。这些次数并不是太多(大概一万多次),所以我开始模拟链表,每一位存下一个数的位置,但是这样却是非常慢的,因为每次都要遍历剩下的所有位置。而通过观察看出,因为每次需要删除固定一些位置的数字(类似约瑟夫环),然后后面的数字都要前移,所以数组链表直接模拟均要遍历多次数组。

但我们把问题直接转化出来就是:数组中有 1-n 各一个数字,每次需要删除pos位置上的数字,删除后这个数字后它就不能占位置了,求最后还有哪些数字。这样我们可以使用树状数组,再套二分,因为前缀和是单调非递减的。我们可以在a数组开始每一位都放1,接着二分找等于pos并第一个出现pos是哪个下标(1-n),再维护树状数组。这样就可以使用O(Log2 n*Log2 n)求出每次应该删除哪个下标的值,直接标记就好。接着每次求答案时直接暴力从n/2向下查询

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=<<;
const double Pi=acos(-1.0);
const int Mod=1e9+;
const int Max=;
int num[Max],vis[Max],bit[Max],n;//幸运数字有哪些 标记 树状数组记录
map<int,int> mp;
int ans1,ans2;
int lowbit(int x)
{
return x&(-x);
}
void Add(int x,int y)
{
while(x<Max)
{
bit[x]+=y;
x+=lowbit(x);
}
return;
}
int Sum(int x)
{
int sum=;
while(x)
{
sum+=bit[x];
x-=lowbit(x);
}
return sum;
}
int Dic(int sma,int big,int val)//使用的是前缀和的单调性,所以找大于等于的最前一个
{
while(sma<big)
{
int mid=(sma+big>>);
if(Sum(mid)>=val)
big=mid;
else
sma=mid+;
}
return big;
}
int Init(int n)
{
mp.clear();
memset(bit,,sizeof(bit));
for(int i=; i<n; ++i)
{
if(i&)
{
vis[i]=;
Add(i,);
}
else
vis[i]=;
}
int pos,flag,tmp;
for(int i=; ; ++i) //二分树状数组
{
flag=;
tmp=Dic(,n,i);
for(int j=;; ++j)
{
pos=Dic(,n,(tmp-)*j+);//二分处理第i个数的位置
if(Sum(pos)!=(tmp-)*j+||!vis[pos])//没有了
break;
flag=;
vis[pos]=;
Add(pos,-);//每次更新
}
if(!flag)
break;
}
int coun=;
for(int i=; i<n; ++i)
{
if(vis[i])
{
num[coun]=i;
mp[i]=coun++;
}
}
return coun;
}
map<int,int>::iterator it;
void Solve(int n)
{
it=mp.lower_bound(n/);
if(it->first!=n/)
--it;
// printf("%d\n",it->first);
for(int i=it->second;;--i)
{
if(vis[num[i]]&&vis[n-num[i]])
{
ans1=num[i];
ans2=n-num[i];
return;
}
}
return;
}
int main()
{
int len=Init();
int n;
while(~scanf("%d",&n))
{
if(n&)
printf("%d is not the sum of two luckies!\n",n);
else
{
Solve(n);
printf("%d is the sum of %d and %d.\n",n,ans1,ans2);
}
}
return ;
}
05-11 18:08
查看更多