首页 > 代码库 > hoj 1867 经理的烦恼 树状数组
hoj 1867 经理的烦恼 树状数组
链接:http://acm.hit.edu.cn/hoj/problem/view?id=1867
谁说是入门题啊,真想拍他一巴掌
经理的烦恼
My Tags |
---|
Source : HCPC 2005 Spring | |||
Time limit : 2 sec | Memory limit : 32 M |
Submitted : 2578, Accepted : 606
Jerry是一家公司销售部门的经理。这家公司有很多连锁店,编号为1,2,3,... Jerry每天必须关注每家连锁店的商品数量及其变化,一项很乏味的工作。在连锁店比较少的时候,Jerry喜欢计算编号在[i,j]区间内的连锁店中商品数量为素数的有多少家,但是现在连锁店的数量急剧增长,计算量很大,Jerry很难得出结果。
View Code
输入格式
题目有多组输入。每组输入第一行有三个整数:C 连锁店的数量 N 指令的条数 M 每家连锁店初始的商品数量
接下来有N行,每行有一条指令。指令的格式为:
0 x y 连锁店x的商品数量变化值为y,y > 0商品数量增加, y < 0减少
1 i j 输出编号在[i,j]区间内的连锁店中商品数量为素数的有多少家
1 <= i, x, j < 1000000 连锁店中的商品数量a满足 0 <= a < 10000000,C = N = M = 0标志输入结束
输出格式
对于每组输入,输出它的序号。对于一组输入中的1指令输出要求的整数。每组输出后打印一行空行。
样例输入
100000 4 40 1 11 4 100 11 31 1 1120 3 01 1 200 3 31 1 200 0 0样例输出
CASE #1:02CASE #2:01
===================================================
要求把素数个数存入c[]中,然后就各种变形,素数表也打的很寒掺,不是太懂
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <algorithm>#define Maxx 1000011int n;int c[Maxx];int str[Maxx];//全局变量默认全部是0 bool prime[Maxx*10];void isPrime(){ int i; prime[0]=prime[1]=true; for(i=2;i*2<=Maxx*10;i++)prime[i*2]=true; for(i=3;i*i<=Maxx*10;i+=2) { if(!prime[i]) { for(int j=i*i;j<=Maxx*10;j+=2*i) prime[j]=true; } }}int lowbit(int x){ return x&(-x);}void Update(int x,int i){ while(x<=n) { c[x]+=i; x+=lowbit(x); }}int Sum(int x){ int s=0; while(x>0) { s+=c[x]; x-=lowbit(x); } return s;}int main(){ int a,b,i,j; int num=0; isPrime(); while(scanf("%d%d%d",&n,&a,&b)!=EOF&&(n+a+b)) { int x,y,z; int p=prime[b]?0:1; for(i=1;i<=n;i++) { str[i]=b; } for(i=1;i<=n;i++) { int k=lowbit(i); c[i]=k*p; } printf("CASE #%d:\n",++num); for(i=1;i<=a;i++) { scanf("%d %d %d",&x,&y,&z); if(x==0) { str[y]+=z; if(!prime[str[y]] && prime[str[y]-z])Update(y,1); if(prime[str[y]] && !prime[str[y]-z])Update(y,-1); } else { printf("%d\n",Sum(z)-Sum(y-1)); } } printf("\n"); } return 0;}
另一个代码:
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <algorithm>#include <math.h>#define Maxx 1000000+10int n;int str[Maxx],c[Maxx];int isPrime(int x){ int tmp=int(sqrt((double)(x))); for(int i=2;i<=tmp;i++) { if(x%i==0) return 0; } return 1;}int Lowbit(int x){ return x&(-x);}void Update(int x,int i){ while(x<=n) { c[x]+=i; x+=Lowbit(x); }}int Sum(int x){ int s=0; while(x>0) { s+=c[x]; x-=Lowbit(x); } return s;}int main(){ int m,a,b; int cas,x,y; int i,j; int num=0; int flag1,flag2; while(scanf("%d%d%d",&n,&a,&b)!=EOF&&(n+a+b)) { printf("CASE #%d:\n",++num); memset(c,0,sizeof(c)); for(i=1;i<=Maxx;i++) { str[i]=b; } if(isPrime(b)&&b!=1&&b!=0) { for(i=1;i<=n;i++) Update(i,1); } for(i=0;i<a;i++) { scanf("%d%d%d",&cas,&x,&y); if(cas == 0) { flag1=flag2=0; if(isPrime(str[x])&&str[x]!=0&&str[x]!=1) { flag1=true; } str[x]+=y; if(isPrime(str[x])&&str[x]!=0&&str[x]!=1) { flag2=true; } if(flag1==1&&flag2==0)Update(x,-1); if(flag1==0&&flag2==1)Update(x,1); } else { printf("%d\n",Sum(y)-Sum(x-1)); } } printf("\n"); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。