LightOJ 1097 - Lucky Number 线段树
2024-10-19 08:47:31
http://www.lightoj.com/volume_showproblem.php?problem=1097
题意:一个自然数序列,先去掉所有偶数项,在此基础上的序列的第二项为3,则删去所有3的倍数的元素,再是7……重复操作,最后问第n项的值
思路:使用线段树构造序列,对一个数进行标记是否已被删去,和为元素个数。由于样例给出了大小,所以很容易控制空间。
/** @Date : 2016-12-05-19.34
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version :
*/ #include<bits/stdc++.h>
#define LL long long
#define PII pair
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std; const int INF = 0x3f3f3f3f;
const int N = 1429431;
const double eps = 1e-8; struct yuu
{
int l, r;
int sum;
}tt[N * 3]; int ans[100010]; void pushup(int p)
{
tt[p].sum = tt[p << 1].sum + tt[p << 1 | 1].sum;
} void build(int l, int r, int p)
{
tt[p].l = l;
tt[p].r = r;
if(l == r)
{
tt[p].sum = l & 1;
return ;
}
int mid = (l + r) >> 1;
build(l , mid, p << 1);
build(mid + 1, r, p << 1 | 1);
pushup(p); } void updata(int x, int p)
{
if(tt[p].l == tt[p].r)
{
tt[p].sum = 0;
return ;
}
if(x <= tt[p << 1].sum)
updata(x, p << 1);
else
updata(x - tt[p << 1].sum, p << 1 | 1);
pushup(p);
} int query(int len, int p)
{
if(tt[p].l == tt[p].r)
return tt[p].l; if(len <= tt[p << 1].sum)
query(len, p << 1);
else query(len - tt[p << 1].sum, p << 1 | 1); }
int main()
{
int c = 1;
ans[1] = 1;
build(1, 1429431, 1);
for(int i = 2; i <= 1429431; i++)
{
int p = query(i, 1);
for(int j = 0; p + j <= 1429431; j+=p-1)
updata(p+j, 1);
if(c >= 100000)
break;
ans[++c] = query(i, 1);
}
int T;
int cnt = 0;
cin >> T;
while(T--)
{
int n;
cin >> n;
printf("Case %d: %d\n", ++cnt, query(n, 1));
}
return 0;
}
最新文章
- HDU 1003 maxsum
- js运动框架之一条乱跑的虫子
- 将sqlserve数据绑定到dataGridView中及一些操作
- alipay iOS SDK
- flask安装
- P3245: 最快路线
- bzoj 3289 Mato的文件管理(莫队算法+BIT)
- JMS - 基本概念
- [Bhatia.Matrix Analysis.Solutions to Exercises and Problems]ExI.5.4
- tarjan缩点
- iOS 开发新版 动态库framework
- jsonp的原理和实现
- js判断空值
- SHA256withRSA证书签名,私钥签名/公钥验签
- EEPROM
- c/c++关于指针的一点理解
- windows系统关闭某个端口的服务(以443端口为例子)
- python之tkinter使用-窗口居中显示
- Tensorflow读写TFRecords文件
- Django入门与实践-第14章:用户注册(完结)