2506: calc - #include <Seter> - using namespace Orz;

2506: calc

Seter posted @ 2011年12月22日 18:23 in BZOJ with tags Enumeration , 2561 阅读

http://www.zybbs.org/JudgeOnline/problem.php?id=2506

RunID User Problem Result Memory Time Language Code Length Submit Time
180816 Seter 2506 Accepted 11576 kb 516 ms C/Edit 1231 B 2011-12-22 18:04:32

Rank1,这个故事告诉我们,桶排还是很快的……

找这道题题解的时候去了CXM大神的”题解“,然后果断被神犇们虐暴……最后根据题解里的提示自己YY出了这题……

一看这题木果断没感觉,然后感觉在线算法不行,果断想离线算法……

先把每次询问拆成1..l-1和1..r,离线后每次询问的就是A(1..x)中模p=k的数的个数。于是按照x排序,每次维护一个增量。

如果所有的p<=100,那这题就是水题了,维护一个s[i][j]表示模i为j的数的个数,然后每插入一个数a,则对于i=1..100,s[i][a%i]+=1

那么对于p>=100怎么办呢?考虑p>=100时有d个不同的数字模p=k:k,k+p,k+2p...k+(d-1)p,k+(d-1)p<=n,得到d<=101。

这说明,对于p>=100,最多只有101个不同的数字可能是答案!于是将每个数出现了几次记录下来,每次暴力找就行了。

 

#include <stdio.h>
char str[3000000],*p=str,*o=str;
int n,m,ans[200000],a[100000],in[200000][4],*ins[200000],s[101][100],u[10001],rka[100001],*rk=rka+1;
inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}void print(x){
	char buf[5],*b=buf;
	if(!x)*o++=48;
	else{while(x)*b++=x%10+48,x/=10;
	while(b--!=buf)*o++=*b;}
	*o++='\n';
}main(){
	int i=-1,r,P,k,t=-1,max;fread(p,1,3000000,stdin);n=getint()-1;
	for(m=getint()<<1;i++!=n;a[i]=getint());
	for(i=-1;++i!=m;in[i][3]=i){
		rk[in[i][0]=getint()-2]++;r=getint()-1;in[i][1]=P=getint();in[i][2]=k=getint();in[i][3]=i;
		rk[in[++i][0]=r]++;in[i][1]=P;in[i][2]=k;
	}for(i=-1;i++!=n;rk[i]+=rk[i-1]);
	for(i=-1;++i!=m;ins[--rk[in[i][0]]]=in[i]);
	for(i=-1,max=0;++i!=m;){
		while(t<ins[i][0]){
			u[a[++t]]++;
			if(a[t]>max)max=a[t];
			for(k=0;k++!=100;s[k][a[t]%k]++);
		}if(ins[i][1]<=100)ans[ins[i][3]]=s[ins[i][1]][ins[i][2]];
		else for(k=ins[i][2]-ins[i][1];(k+=ins[i][1])<=max;)ans[ins[i][3]]+=u[k];
	}for(i=-2;(i+=2)!=m;)print(ans[i^1]-ans[i]);
	*--o=0;return puts(str),0;
}
By Seter
  • 无匹配
SimonCao 说:
2011年12月23日 21:51

OrzOrzOrz.......乃天天D我这种傻叉有意思么。。。

Avatar_small
Seter 说:
2011年12月24日 08:53

反Orz光波——ymymymymym进队的!

Emma 说:
2022年12月23日 19:03

Accidentally I have come across this website and little bit confused about the details shared over here. Calc is the free spreadsheet program real estate agency Mariposa you've always needed. Newcomers find it intuitive and easy to learn, while professional data miners and number crunchers appreciate the comprehensive range of advanced functions. Good to see the details shared over here.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee