月度归档：2013年07月

[POJ 1961] & [POJ 2406]

研一离校前最后的两题了。

两题都是KMP，题意也比较相近的：给出字符串s（长度最多10^6），求模式为r^k的以s[0]开头的子串的k值。好久没写KMP了，但推了下明确思路后还是两题都1A了，对算法理解得也算还行吧……：

1961:

int t,sl,p[1000000],d[1000000];
char s[1000001];

int main()
{
	int i,j,k;
	while(~scanf("%d%s",&sl,s)&&sl)
	{
		memset(d,0,sizeof d);
		p[0]=-1;
		d[0]=1;
		for(i=1,j=-1;i<sl;i++)
		{
			while(j!=-1&&s[i]!=s[j+1]) j=p[j];
			if(s[i]==s[j+1]) j++;
			p[i]=j;
			if(j!=-1&&i==j+((j+1)/d[j])) d[i]=d[j]+1;
			else d[i]=1;
		}
		printf("Test case #%d\n",++t);
		for(i=0;i<sl;i++)
			if(d[i]>1) printf("%d %d\n",i+1,d[i]);
		puts("");
	}
	return 0;
}

int t,sl,p[1000000],d[1000000];

char s[1000001];

int main()

{

int i,j,k;

while(~scanf("%d%s",&sl,s)&&sl)

{

memset(d,0,sizeof d);

p[0]=-1;

d[0]=1;

for(i=1,j=-1;i<sl;i++)

{

while(j!=-1&&s[i]!=s[j+1]) j=p[j];

if(s[i]==s[j+1]) j++;

p[i]=j;

if(j!=-1&&i==j+((j+1)/d[j])) d[i]=d[j]+1;

else d[i]=1;

}

printf("Test case #%d\n",++t);

for(i=0;i<sl;i++)

if(d[i]>1) printf("%d %d\n",i+1,d[i]);

puts("");

}

return 0;

}

2406:

int sl,p[1000000],d[1000000];
char s[1000001];

int main()
{
	int i,j,k,l;
	while(~scanf("%s",s))
	{
		sl=strlen(s);
		if(sl==1&&s[0]=='.') break;
		p[0]=-1;
		d[0]=1;
		for(i=1,j=-1;i<sl;i++)
		{
			while(j!=-1&&s[i]!=s[j+1]) j=p[j];
			if(s[i]==s[j+1]) j++;
			if(j!=-1&&i==j+(j+1)/d[j]) d[i]=d[j]+1;
			else d[i]=1;
		}
		printf("%d\n",d[sl-1]);
	}
	return 0;
}

int sl,p[1000000],d[1000000];

char s[1000001];

int main()

{

int i,j,k,l;

while(~scanf("%s",s))

{

sl=strlen(s);

if(sl==1&&s[0]=='.') break;

p[0]=-1;

d[0]=1;

for(i=1,j=-1;i<sl;i++)

{

while(j!=-1&&s[i]!=s[j+1]) j=p[j];

if(s[i]==s[j+1]) j++;

if(j!=-1&&i==j+(j+1)/d[j]) d[i]=d[j]+1;

else d[i]=1;

}

printf("%d\n",d[sl-1]);

}

return 0;

}

出乎意料地暑假竟然放满了。又可以制定各种不切实际的计划了吗？…

[Hackerrank]

发表回复

最近好多天都没更新，其实是跑去做比赛啦：20/20 Hack July

（又）是qoshi同学推荐的比赛，本来也想偷懒水水过去，但稍微做了下后发现还挺好玩。。。然后由于这比赛竟然持续9天，到后面就完全陷在里面无法自拔了。。。

hackerrank这个网站貌似是几个印度人办的，刚开张没多久的样子，不过界面做得好漂亮，很多设计也非常人性化，虽然BUG也不少，但总体来说在这里做题还是很享受的。

这次的20/20 Hack July比赛应该是类似月赛的形式吧，虽然不似codeforces、topcoder那么知名，但却也有不少神牛的（比如winger，09年ICPC世界冠军）。赛制是9天7题，包括5题算法题和2题GAME。其中算法题是按case给分的，没有罚时，没有提交惩罚。GAME则是提交AI程序，具体的内容包括两种，一种是单人，一种有对手的。

前3题都是比较简单的，第一题是输入一串字符，要求判断是否能构成对称字符串；第二题是输入一串字符，问总共能构成多少种对称字符串；第三题是问2^n的前k和后k个数字是多少，用了long double和2分后也是一下就过了。

第4题Computer Game则卡了3天。题意是输入n和两个int数组a[n]和b[n]，其中a[i]和b[j]间有边当且仅当它们非互质。问a[i]和b[j]两两配对，最多能有多少对？

这是一题典型的最大二分匹配。一开始我是建了一张大图，即边表里直接存a[i]到b[j]的边，过了几组小数据，后面都是超内存了（稠图的情况）。这个时候，Arios（又）来拯救我了……被告知可以考虑建两个边表，第一个存的是a[i]到p[k]，第二个存p[k]到b[j]，其中p[k]是某个素数。这样内存的问题解决了，开始TLE了。那几天里想了很多优化（大多没有用），又看了其他一些二分图匹配算法（也没比匈牙利好），也随便记录下吧就当是愚蠢的见证。。。说说最主要的优化点，其实就在于每轮匈牙利时，遍历边表时，由于边表是两重的，是可以从之前遍历到的位置开始继续遍历的，例如a[n]={2,4,7},b[n]={8,6,10}，a[0]、a[1]都通过p[0]=2与b[0]、b[1]、b[2]相连，在迭代的过程中，如果a[0]时已经遍历到了b[1]，那么到a[1]时直接检查b[2]就可以了，前面的元素都是已经在父迭代里遍历过的，这样可以将遍历复杂度降到O(9*N)，这个9是因为每个int最多有9个不同的素因子。另外就是再开了一个表，用来记录某素因子对应的第一个还没匹配的b[j]，每轮匈牙利时先尝试O（1）地匹配尚未匹配的元素。

另外还加了一堆稀里糊涂的scanf(“%d”)改getchar()，递归改非递归，按b[i]素因子个数小到大建表等等……也不知到哪个有用哪个没用，程序也写得一团遭，但总算是过了……这题最后就17个人拿了满分，应该也算本场最难的一题了吧。

第5题，这题我纯粹是利用规则漏洞了。主要是题目重复提交竟然不罚分，a、b的范围太小，时间复杂度卡得也不紧，直接O(lgN)试出test case然后O(9*10^10)离线算出结果就过了。Arios这题推出了数学解法，再次OTL一下。。。

第6题，单人GAME，这题大家分数都差不多了。

第7题Ultimate Tic Tac Toe，我觉得是本场最好玩的一题了。正如其名“最终井字棋”，它的棋盘分为大井字和小井字，大井字里每格是一个小井字，每个小井字的胜负判定和原本的井字棋相同，大井字根据小井字的结果来判断胜负，也即某方赢了某格小井字棋，就相当与在大井字里走了一步。这里有个先后手间的制约：先手如果走的是某个小井字的i,j位置，那么后手需要在第i,j个小井字里走；但如果第i,j个小井字胜负已定，那么后手可以选大井字中的任意位置。最后的胜负由大井字的结果决定。

规则还是很简单的……但要写出百战百胜的AI，也不是一件容易的事……根据Arios的说法，这种称为“博弈搜索”，即根据既定的盘面评估出自己最优的走法，然后分析对手最优走法以作修正，依次迭代迭代直到一定深度。

最后几天其实大家都已经拿完前面所有分了，因此排名也就全看这一题了。这题我的评分策略应该还是不准确，总是有几个人让我保持全败记录（winger貌似对所有人都轻松全胜…）。期间也出现过一些低级错误（交错语言直接扣4分啦，程序各种TLE判负啦）……最后排名第9，也还算过得去吧。

然后就是最后的global leaderboard了，虽然只是很小规模的比赛，但还是做得很开心。。。希望这次能收到T-shirt吧。。。

[POJ 3368]

发表回复

Frequent values

说好的RMQ问题，结果又用线段树A了…

题意是：一个长度为n(1<=n<=100000)的非递减序列，共q(1<=1<=100000)次询问，求下标(l,h)范围内出现最频繁的元素的次数。一开始照着RMQ问题想，还看了个ST算法（O(NlgN)预处理，O(1)在线查询），结果也没想明白怎么用。又回头想了下，发现线段树是可以用的。由于序列非递减，连续的相同元素压缩成一个点作为线段树叶结点，记录元素在原数组中的下标范围；树分叉结点则保存子树下最频繁次数值，插入时则是按照压缩后的点编号进行处理，由此建树O(NlgN)，每次查询是O(lgN)。

#include<cstdio>
#include<cstring>

int n,q,a[100001],b[100000][2],bl,ml;

struct node
{
	int l,h,d;
	node *lc,*rc;
}mem[200000],*root;

void ins(int e,int L,int R,node *p)
{
	if(L==R)
	{
		p->l=b[e][0];
		p->h=b[e][1];
		p->d=p->h-p->l+1;
		return;
	}
	int m=L+R>>1;
	if(!p->lc)
	{
		p->lc=&mem[ml++];
		p->lc->l=p->lc->h=0;
		p->lc->lc=p->lc->rc=0;
		p->lc->d=0;
		p->rc=&mem[ml++];
		p->rc->l=p->rc->h=0;
		p->rc->lc=p->rc->rc=0;
		p->rc->d=0;
	}
	if(e<=m)
	{
		ins(e,L,m,p->lc);
		if(p->lc->l) p->l=p->lc->l;
		if(p->lc->d>p->d) p->d=p->lc->d;
	}
	else
	{
		ins(e,m+1,R,p->rc);
		if(p->rc->h) p->h=p->rc->h;
		if(p->rc->d>p->d) p->d=p->rc->d;
	}
}

int que(int l,int h,node *p)
{
	if(!p->lc) return h-l+1;
	if(l==p->l&&h==p->h) return p->d;
	int m=p->lc->h;
	if(h<=m) return que(l,h,p->lc);
	if(l>m) return que(l,h,p->rc);
	int a=que(l,m,p->lc),b=que(m+1,h,p->rc);
	return a>b?a:b;
}

bool input()
{
	ml=bl=0;
	int i,j,k,L,R;
	if(scanf("%d%d",&n,&q)!=2) return 0;
	for(i=0;i<n;i++) scanf("%d",a+i);
	a[n++]=100001;
	for(i=1,k=0;i<n;i++)
	{
		if(a[i]!=a[i-1])
		{
			b[bl][0]=k+1;
			b[bl][1]=i;
			k=i;
			bl++;
		}
	}
	root=&mem[ml++];
	root->l=root->h=root->d=0;
	root->lc=root->rc=0;
	L=0;
	R=bl-1;
	for(i=0;i<bl;i++) ins(i,L,R,root);
	return 1;
}

void solve()
{
	int l,h;
	while(q--)
	{
		scanf("%d%d",&l,&h);
		printf("%d\n",que(l,h,root));
	}
}

int main()
{
	while(input()) solve();
	return 0;
}

#include<cstdio>

#include<cstring>

int n,q,a[100001],b[100000][2],bl,ml;

struct node

{

int l,h,d;

node *lc,*rc;

}mem[200000],*root;

void ins(int e,int L,int R,node *p)

{

if(L==R)

{

p->l=b[e][0];

p->h=b[e][1];

p->d=p->h-p->l+1;

return;

}

int m=L+R>>1;

if(!p->lc)

{

p->lc=&mem[ml++];

p->lc->l=p->lc->h=0;

p->lc->lc=p->lc->rc=0;

p->lc->d=0;

p->rc=&mem[ml++];

p->rc->l=p->rc->h=0;

p->rc->lc=p->rc->rc=0;

p->rc->d=0;

}

if(e<=m)

{

ins(e,L,m,p->lc);

if(p->lc->l) p->l=p->lc->l;

if(p->lc->d>p->d) p->d=p->lc->d;

}

else

{

ins(e,m+1,R,p->rc);

if(p->rc->h) p->h=p->rc->h;

if(p->rc->d>p->d) p->d=p->rc->d;

}

int que(int l,int h,node *p)

{

if(!p->lc) return h-l+1;

if(l==p->l&&h==p->h) return p->d;

int m=p->lc->h;

if(h<=m) return que(l,h,p->lc);

if(l>m) return que(l,h,p->rc);

int a=que(l,m,p->lc),b=que(m+1,h,p->rc);

return a>b?a:b;

}

bool input()

{

ml=bl=0;

int i,j,k,L,R;

if(scanf("%d%d",&n,&q)!=2) return 0;

for(i=0;i<n;i++) scanf("%d",a+i);

a[n++]=100001;

for(i=1,k=0;i<n;i++)

{

if(a[i]!=a[i-1])

{

b[bl][0]=k+1;

b[bl][1]=i;

k=i;

bl++;

}

root=&mem[ml++];

root->l=root->h=root->d=0;

root->lc=root->rc=0;

L=0;

R=bl-1;

for(i=0;i<bl;i++) ins(i,L,R,root);

return 1;

}

void solve()

{

int l,h;

while(q--)

{

scanf("%d%d",&l,&h);

printf("%d\n",que(l,h,root));

}

int main()

{

while(input()) solve();

return 0;

}

[POJ 1151]

发表回复

Atlantis

本来是属于线段树的，但数据范围太小，硬是用暴力A掉了 -____-##

相比之前的好题……本题简直可以用“丑陋”来形容……比起线段树的运用和构思算法本身，更麻烦的反而是坐标离散化，而且由于POJ本身的问题，G++对double处理有缺陷（后来发现是输入用%lf输出用%f），转用C++后，对STL的编译又和G++的不一样……结果就是写好程序后各种卡编译错误……

#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;

int n,a[201],el,t,xl,yl;
double sum,x[200],y[200];

struct node
{
	double e;
	int i;
	bool operator < (const node &p) const
	{
		return e<p.e;
	}
};

struct edge
{
	double x1,x2,y;
	int x1i,x2i,yi,c;
	bool operator < (const edge &p) const
	{
		return y<p.y;
	}
}e[200];

inline void adde(double x1,double y1,double x2,double y2)
{
	e[el].x1=x1; e[el].x2=x2; e[el].y=y1; e[el].c=1; el++;
	e[el].x1=x1; e[el].x2=x2; e[el].y=y2; e[el].c=-1; el++;
	x[xl++]=x1; x[xl++]=x2;
	y[yl++]=y1; y[yl++]=y2;
}

int main()
{
	int i,j,k,l;
	double x1,y1,x2,y2;
	node p;
	while(~scanf("%d",&n)&&n)
	{
		el=0;
		sum=0;
		xl=yl=0;
		set<node>SX,SY;
		set<node>::iterator sit;
		for(i=0;i<n;i++)
		{
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			adde(x1,y1,x2,y2);
		}
		sort(e,e+el);
		sort(x,x+xl);
		sort(y,y+yl);
		for(i=j=1;i<xl;i++)
			if(x[i]!=x[i-1]) x[j++]=x[i];
		xl=j;
		for(i=0;i<xl;i++)
		{
			p.e=x[i];
			p.i=i;
			SX.insert(p);
		}
		for(i=j=1;i<yl;i++)
			if(y[i]!=y[i-1]) y[j++]=y[i];
		yl=j;
		for(i=0;i<yl;i++)
		{
			p.e=y[i];
			p.i=i;
			SY.insert(p);
		}
		for(i=0;i<el;i++)
		{
			p.e=e[i].x1;
			e[i].x1i=SX.find(p)->i;
			p.e=e[i].x2;
			e[i].x2i=SX.find(p)->i;
			p.e=e[i].y;
			e[i].yi=SY.find(p)->i;
		}
		memset(a,0,sizeof a);
		for(i=0;i<el&&e[i].yi==e[0].yi;i++)
		{
			a[e[i].x1i]+=e[i].c;
			a[e[i].x2i]-=e[i].c;
		}
		while(i<el)
		{
			y1=y[e[i-1].yi];
			y2=y[e[i].yi];
			for(j=k=0;j<=xl;j++)
			{
				if(a[j])
				{
					k+=a[j];
					if(k-a[j]==0) x1=x[j];
					else if(k==0)
					{
						x2=x[j];
						sum+=(x2-x1)*(y2-y1);
					}
				}
			}
			for(l=e[i].yi;i<el&&e[i].yi==l;i++)
			{
				a[e[i].x1i]+=e[i].c;
				a[e[i].x2i]-=e[i].c;
			}
		}
		printf("Test case #%d\n",++t);
		printf("Total explored area: %.2lf\n",sum);
		puts("");
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

#include<cstdio>

#include<cstring>

#include<set>

#include<algorithm>

using namespace std;

int n,a[201],el,t,xl,yl;

double sum,x[200],y[200];

struct node

{

double e;

int i;

bool operator < (const node &p) const

{

return e<p.e;

}

};

struct edge

{

double x1,x2,y;

int x1i,x2i,yi,c;

bool operator < (const edge &p) const

{

return y<p.y;

}

}e[200];

inline void adde(double x1,double y1,double x2,double y2)

{

e[el].x1=x1; e[el].x2=x2; e[el].y=y1; e[el].c=1; el++;

e[el].x1=x1; e[el].x2=x2; e[el].y=y2; e[el].c=-1; el++;

x[xl++]=x1; x[xl++]=x2;

y[yl++]=y1; y[yl++]=y2;

}

int main()

{

int i,j,k,l;

double x1,y1,x2,y2;

node p;

while(~scanf("%d",&n)&&n)

{

el=0;

sum=0;

xl=yl=0;

set<node>SX,SY;

set<node>::iterator sit;

for(i=0;i<n;i++)

{

scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);

adde(x1,y1,x2,y2);

}

sort(e,e+el);

sort(x,x+xl);

sort(y,y+yl);

for(i=j=1;i<xl;i++)

if(x[i]!=x[i-1]) x[j++]=x[i];

xl=j;

for(i=0;i<xl;i++)

{

p.e=x[i];

p.i=i;

SX.insert(p);

}

for(i=j=1;i<yl;i++)

if(y[i]!=y[i-1]) y[j++]=y[i];

yl=j;

for(i=0;i<yl;i++)

{

p.e=y[i];

p.i=i;

SY.insert(p);

}

for(i=0;i<el;i++)

{

p.e=e[i].x1;

e[i].x1i=SX.find(p)->i;

p.e=e[i].x2;

e[i].x2i=SX.find(p)->i;

p.e=e[i].y;

e[i].yi=SY.find(p)->i;

}

memset(a,0,sizeof a);

for(i=0;i<el&&e[i].yi==e[0].yi;i++)

{

a[e[i].x1i]+=e[i].c;

a[e[i].x2i]-=e[i].c;

}

while(i<el)

{

y1=y[e[i-1].yi];

y2=y[e[i].yi];

for(j=k=0;j<=xl;j++)

{

if(a[j])

{

k+=a[j];

if(k-a[j]==0) x1=x[j];

else if(k==0)

{

x2=x[j];

sum+=(x2-x1)*(y2-y1);

}

for(l=e[i].yi;i<el&&e[i].yi==l;i++)

{

a[e[i].x1i]+=e[i].c;

a[e[i].x2i]-=e[i].c;

}

printf("Test case #%d\n",++t);

printf("Total explored area: %.2lf\n",sum);

puts("");

}

return 0;

}

[POJ 2352]

发表回复

Stars

继续线段树+树状数组练手题。

这题先对某坐标轴方向排序后，便能将二维降为一维处理了。没太大难度。

线段树：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,ml,cnt[15000];

struct star
{
	int x,y;
	bool operator <(const star &p) const
	{
		if(y<p.y) return 1;
		if(y>p.y) return 0;
		if(x<p.x) return 1;
		return 0;
	}
}s[15000];

struct node
{
	bool b;
	int d;
	node *l,*r;
}mem[64000],*root;

inline void ins(int i)
{
	int L=0,R=32000,m,lev=0;
	node *p=root;
	while(1)
	{
		m=L+R>>1;
		p->d++;
		if(L==R)
		{
			lev+=p->d-1;
			cnt[lev]++;
			break;
		}
		if(p->b)
		{
			p->b=0;
			p->l=&mem[ml++];
			p->l->b=1;
			p->l->d=0;
			p->r=&mem[ml++];
			p->r->b=1;
			p->r->d=0;
		}
		if(i<=m)
		{
			R=m;
			p=p->l;
		}
		else
		{
			lev+=p->l->d;
			L=m+1;
			p=p->r;
		}
	}
}

int main()
{
	int i,j,k;
	while(~scanf("%d",&n))
	{
		ml=0;
		root=&mem[ml++];
		root->b=1;
		root->d=0;
		memset(cnt,0,sizeof cnt);
		for(i=0;i<n;i++) scanf("%d%d",&s[i].x,&s[i].y);
		sort(s,s+n);
		for(i=0;i<n;i++) ins(s[i].x);
		for(i=0;i<n;i++) printf("%d\n",cnt[i]);
	}
	return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,ml,cnt[15000];

struct star

{

int x,y;

bool operator <(const star &p) const

{

if(y<p.y) return 1;

if(y>p.y) return 0;

if(x<p.x) return 1;

return 0;

}

}s[15000];

struct node

{

bool b;

int d;

node *l,*r;

}mem[64000],*root;

inline void ins(int i)

{

int L=0,R=32000,m,lev=0;

node *p=root;

while(1)

{

m=L+R>>1;

p->d++;

if(L==R)

{

lev+=p->d-1;

cnt[lev]++;

break;

}

if(p->b)

{

p->b=0;

p->l=&mem[ml++];

p->l->b=1;

p->l->d=0;

p->r=&mem[ml++];

p->r->b=1;

p->r->d=0;

}

if(i<=m)

{

R=m;

p=p->l;

}

else

{

lev+=p->l->d;

L=m+1;

p=p->r;

}

int main()

{

int i,j,k;

while(~scanf("%d",&n))

{

ml=0;

root=&mem[ml++];

root->b=1;

root->d=0;

memset(cnt,0,sizeof cnt);

for(i=0;i<n;i++) scanf("%d%d",&s[i].x,&s[i].y);

sort(s,s+n);

for(i=0;i<n;i++) ins(s[i].x);

for(i=0;i<n;i++) printf("%d\n",cnt[i]);

}

return 0;

}

树状数组：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,c[32002],cnt[15000];

struct star
{
	int x,y;
	bool operator < (const star &p) const
	{
		if(y<p.y) return 1;
		if(y>p.y) return 0;
		if(x<p.x) return 1;
		return 0;
	}
}a[15000];

inline void add(int x)
{
	int i;
	for(i=1;x<32002;i<<=1)
	{
		if(x&i)
		{
			c[x]++;
			x+=i;
		}
	}
}

inline int que(int x)
{
	int i,sum=0;
	for(i=1;x;i<<=1)
	{
		if(x&i)
		{
			sum+=c[x];
			x-=i;
		}
	}
	return sum;
}

int main()
{
	int i,j,k;
	while(~scanf("%d",&n))
	{
		memset(c,0,sizeof c);
		memset(cnt,0,sizeof cnt);
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&a[i].x,&a[i].y);
			a[i].x++;
			a[i].y++;
		}
		sort(a,a+n);
		for(i=0;i<n;i++)
		{
			add(a[i].x);
			cnt[que(a[i].x)-1]++;
		}
		for(i=0;i<n;i++) printf("%d\n",cnt[i]);
	}
	return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,c[32002],cnt[15000];

struct star

{

int x,y;

bool operator < (const star &p) const

{

if(y<p.y) return 1;

if(y>p.y) return 0;

if(x<p.x) return 1;

return 0;

}

}a[15000];

inline void add(int x)

{

int i;

for(i=1;x<32002;i<<=1)

{

if(x&i)

{

c[x]++;

x+=i;

}

inline int que(int x)

{

int i,sum=0;

for(i=1;x;i<<=1)

{

if(x&i)

{

sum+=c[x];

x-=i;

}

return sum;

}

int main()

{

int i,j,k;

while(~scanf("%d",&n))

{

memset(c,0,sizeof c);

memset(cnt,0,sizeof cnt);

for(i=0;i<n;i++)

{

scanf("%d%d",&a[i].x,&a[i].y);

a[i].x++;

a[i].y++;

}

sort(a,a+n);

for(i=0;i<n;i++)

{

add(a[i].x);

cnt[que(a[i].x)-1]++;

}

for(i=0;i<n;i++) printf("%d\n",cnt[i]);

}

return 0;

}

[POJ 1195]

发表回复

Mobile phones

二维树状数组。

推出一维的后便很易想出二维解法了，单次更新/查询的时间复杂度升为O(lgN*lgN)，因此还是可以接受的。

久违的1A。。。

int s,c[1025][1025];

void add()
{
	int i,j,x,y,yy,a;
	scanf("%d%d%d",&x,&y,&a);
	++x; ++y;
	for(i=1;x<=s;i<<=1)
	{
		if(x&i)
		{
			for(j=1,yy=y;yy<=s;j<<=1)
			{
				if(yy&j)
				{
					c[x][yy]+=a;
					yy+=j;
				}
			}
			x+=i;
		}
	}
}

int val(int x,int y)
{
	int i,j,k=0,yy;
	for(i=1;x;i<<=1)
	{
		if(x&i)
		{
			for(j=1,yy=y;yy;j<<=1)
			{
				if(yy&j)
				{
					k+=c[x][yy];
					yy-=j;
				}
			}
			x-=i;
		}
	}
	return k;
}

void que()
{
	int l,b,r,t;
	scanf("%d%d%d%d",&l,&b,&r,&t);
	printf("%d\n",val(r+1,t+1)-val(l,t+1)-val(r+1,b)+val(l,b));
}

int main()
{
	int i;
	while(~scanf("%*d%d",&s))
	{
		memset(c,0,sizeof c);
		while(scanf("%d",&i))
		{
			if(i==1) add();
			else if(i==2) que();
			else break;
		}
	}
	return 0;
}

int s,c[1025][1025];

void add()

{

int i,j,x,y,yy,a;

scanf("%d%d%d",&x,&y,&a);

++x; ++y;

for(i=1;x<=s;i<<=1)

{

if(x&i)

{

for(j=1,yy=y;yy<=s;j<<=1)

{

if(yy&j)

{

c[x][yy]+=a;

yy+=j;

}

x+=i;

}

int val(int x,int y)

{

int i,j,k=0,yy;

for(i=1;x;i<<=1)

{

if(x&i)

{

for(j=1,yy=y;yy;j<<=1)

{

if(yy&j)

{

k+=c[x][yy];

yy-=j;

}

x-=i;

}

return k;

}

void que()

{

int l,b,r,t;

scanf("%d%d%d%d",&l,&b,&r,&t);

printf("%d\n",val(r+1,t+1)-val(l,t+1)-val(r+1,b)+val(l,b));

}

int main()

{

int i;

while(~scanf("%*d%d",&s))

{

memset(c,0,sizeof c);

while(scanf("%d",&i))

{

if(i==1) add();

else if(i==2) que();

else break;

}

return 0;

}

[POJ 3321]

发表回复

Apple Tree

树状数组例题。

“用DFS求出树结点对应的区间范围”比较难想……后面的区间值修改和查询都比较简单了。分别用了线段树和树状数组进行了求解。

线段树：

#include<cstdio>
#include<cstring>

int n,m,hd[100000],b[100000],nt[100000][2],el,t,ml;
char s[2];

struct edge
{
	int j,p;
}e[200000];

struct node
{
	bool b;
	int sum;
	node *l,*r;
}mem[400000],*root;

inline void adde(int i,int j)
{
	e[el].j=j; e[el].p=hd[i]; hd[i]=el++;
	e[el].j=i; e[el].p=hd[j]; hd[j]=el++;
}

void dfs(int i)
{
	int j,k,l;
	nt[i][0]=t++;
	for(l=hd[i];l!=-1;l=e[l].p)
	{
		j=e[l].j;
		if(b[j]) continue;
		b[j]=1;
		dfs(j);
	}
	nt[i][1]=t++;
}

void add(int e,int c)
{
	int L=0,R=t,m;
	node *p=root;
	while(1)
	{
		p->sum+=c;
		if(L==R) break;
		m=L+R>>1;
		if(p->b)
		{
			p->b=0;
			p->l=&mem[ml++];
			p->r=&mem[ml++];
			p->l->b=p->r->b=1;
			p->l->sum=p->r->sum=0;
		}
		if(e<=m)
		{
			R=m;
			p=p->l;
		}
		else
		{
			L=m+1;
			p=p->r;
		}
	}
}

int que(int l,int r,int L,int R,node *p)
{
	int m=L+R>>1;
	if(p->b||l==L&&r==R) return p->sum;
	if(r<=m) return que(l,r,L,m,p->l);
	if(l>m) return que(l,r,m+1,R,p->r);
	return que(l,m,L,m,p->l)+que(m+1,r,m+1,R,p->r);
}

int main()
{
	int i,j,k,l;
	while(~scanf("%d",&n))
	{
		el=t=ml=0;
		root=&mem[ml++];
		root->b=1;
		root->sum=0;
		memset(hd,-1,sizeof hd);
		for(i=1;i<n;i++)
		{
			scanf("%d%d",&j,&k);
			adde(j-1,k-1);
		}
		memset(b,0,sizeof b);
		b[0]=1;
		dfs(0);
		--t;
		for(i=0;i<n;i++)
			add(nt[i][0],1);
		scanf("%d",&m);
		while(m--)
		{
			scanf("%s%d",s,&i);
			--i;
			if(s[0]=='Q') printf("%d\n",que(nt[i][0],nt[i][1],0,t,root));
			else
			{
				if(b[i]) add(nt[i][0],-1);
				else add(nt[i][0],1);
				b[i]^=1;
			}
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

#include<cstdio>

#include<cstring>

int n,m,hd[100000],b[100000],nt[100000][2],el,t,ml;

char s[2];

struct edge

{

int j,p;

}e[200000];

struct node

{

bool b;

int sum;

node *l,*r;

}mem[400000],*root;

inline void adde(int i,int j)

{

e[el].j=j; e[el].p=hd[i]; hd[i]=el++;

e[el].j=i; e[el].p=hd[j]; hd[j]=el++;

}

void dfs(int i)

{

int j,k,l;

nt[i][0]=t++;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].j;

if(b[j]) continue;

b[j]=1;

dfs(j);

}

nt[i][1]=t++;

}

void add(int e,int c)

{

int L=0,R=t,m;

node *p=root;

while(1)

{

p->sum+=c;

if(L==R) break;

m=L+R>>1;

if(p->b)

{

p->b=0;

p->l=&mem[ml++];

p->r=&mem[ml++];

p->l->b=p->r->b=1;

p->l->sum=p->r->sum=0;

}

if(e<=m)

{

R=m;

p=p->l;

}

else

{

L=m+1;

p=p->r;

}

int que(int l,int r,int L,int R,node *p)

{

int m=L+R>>1;

if(p->b||l==L&&r==R) return p->sum;

if(r<=m) return que(l,r,L,m,p->l);

if(l>m) return que(l,r,m+1,R,p->r);

return que(l,m,L,m,p->l)+que(m+1,r,m+1,R,p->r);

}

int main()

{

int i,j,k,l;

while(~scanf("%d",&n))

{

el=t=ml=0;

root=&mem[ml++];

root->b=1;

root->sum=0;

memset(hd,-1,sizeof hd);

for(i=1;i<n;i++)

{

scanf("%d%d",&j,&k);

adde(j-1,k-1);

}

memset(b,0,sizeof b);

b[0]=1;

dfs(0);

--t;

for(i=0;i<n;i++)

add(nt[i][0],1);

scanf("%d",&m);

while(m--)

{

scanf("%s%d",s,&i);

--i;

if(s[0]=='Q') printf("%d\n",que(nt[i][0],nt[i][1],0,t,root));

else

{

if(b[i]) add(nt[i][0],-1);

else add(nt[i][0],1);

b[i]^=1;

}

return 0;

}

树状数组：

#include<cstdio>
#include<cstring>

int n,m,hd[100000],el,b[100000],nt[100000][2],t,c[200001];
char s[2];

struct edge
{
	int j,p;
}e[200000];

inline void adde(int i,int j)
{
	e[el].j=j; e[el].p=hd[i]; hd[i]=el++;
	e[el].j=i; e[el].p=hd[j]; hd[j]=el++;
}

void dfs(int i)
{
	int j,l;
	nt[i][0]=t++;
	for(l=hd[i];l!=-1;l=e[l].p)
	{
		j=e[l].j;
		if(b[j]) continue;
		b[j]=1;
		dfs(j);
	}
	nt[i][1]=t++;
}

inline void add(int e,int d)
{
	int i;
	for(i=1;e<t;i<<=1)
	{
		if(e&i)
		{
			c[e]+=d;
			e+=i;
		}
	}
}

inline int val(int e)
{
	int i,j;
	for(i=1,j=0;e;i<<=1)
	{
		if(e&i)
		{
			j+=c[e];
			e-=i;
		}
	}
	return j;
}

inline int que(int l,int r)
{
	return val(r)-val(l-1);
}

int main()
{
	int i,j,k,l;
	while(~scanf("%d",&n))
	{
		el=0;
		t=1;
		memset(hd,-1,sizeof hd);
		memset(c,0,sizeof c);
		for(i=1;i<n;i++)
		{
			scanf("%d%d",&j,&k);
			adde(j-1,k-1);
		}
		memset(b,0,sizeof b);
		b[0]=1;
		dfs(0);
		for(i=0;i<n;i++) add(nt[i][0],1);
		scanf("%d",&m);
		while(m--)
		{
			scanf("%s%d",s,&i);
			--i;
			if(s[0]=='Q') printf("%d\n",que(nt[i][0],nt[i][1]));
			else
			{
				if(b[i]) add(nt[i][0],-1);
				else add(nt[i][0],1);
				b[i]^=1;
			}
		}
	}
	return 0;
}

#include<cstdio>

#include<cstring>

int n,m,hd[100000],el,b[100000],nt[100000][2],t,c[200001];

char s[2];

struct edge

{

int j,p;

}e[200000];

inline void adde(int i,int j)

{

e[el].j=j; e[el].p=hd[i]; hd[i]=el++;

e[el].j=i; e[el].p=hd[j]; hd[j]=el++;

}

void dfs(int i)

{

int j,l;

nt[i][0]=t++;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].j;

if(b[j]) continue;

b[j]=1;

dfs(j);

}

nt[i][1]=t++;

}

inline void add(int e,int d)

{

int i;

for(i=1;e<t;i<<=1)

{

if(e&i)

{

c[e]+=d;

e+=i;

}

inline int val(int e)

{

int i,j;

for(i=1,j=0;e;i<<=1)

{

if(e&i)

{

j+=c[e];

e-=i;

}

return j;

}

inline int que(int l,int r)

{

return val(r)-val(l-1);

}

int main()

{

int i,j,k,l;

while(~scanf("%d",&n))

{

el=0;

t=1;

memset(hd,-1,sizeof hd);

memset(c,0,sizeof c);

for(i=1;i<n;i++)

{

scanf("%d%d",&j,&k);

adde(j-1,k-1);

}

memset(b,0,sizeof b);

b[0]=1;

dfs(0);

for(i=0;i<n;i++) add(nt[i][0],1);

scanf("%d",&m);

while(m--)

{

scanf("%s%d",s,&i);

--i;

if(s[0]=='Q') printf("%d\n",que(nt[i][0],nt[i][1]));

else

{

if(b[i]) add(nt[i][0],-1);

else add(nt[i][0],1);

b[i]^=1;

}

return 0;

}

[POJ 2104]

发表回复

K-th Number

划分树。

题意是，给一个长度为n的数组，之后有m次询问，每次询问为三元组（l,r,k），问数组中第l到第r个元素间第k小的元素是什么。

又是一题很有意思的题目，常规解法的时间复杂度在这里是完全不可行的，必须预先建树后才能O(lgN)地回答每次询问。但看了划分树的建树思想后还是推了很久。

划分树是基于线段树的，其基本思想在于父节点上[L,R]区间上[l,r]中的第k小元素，如何O(1）时间地递推到左子树或右子树中，这样总共O(lgN)次后便能得到答案。

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,a[100000],b[100000],sa[100000],el[2000000],ml,ell;

struct node
{
	int s;
	node *l,*r;
}mem[2000000],*root;

void init(int L,int R,node *p)
{
	int m=L+R>>1,e=0,i,j,k;
	p->s=ell;
	for(i=L;i<=R;i++)
	{
		e+=a[i]<=sa[m]?1:0;
		el[ell++]=e;
	}
	for(i=j=L,k=m+1;i<=R;i++)
	{
		if(a[i]<=sa[m]) b[j++]=a[i];
		else b[k++]=a[i];
	}
	memcpy(a+L,b+L,4*(R-L+1));
	if(L==R) return;
	p->l=&mem[ml++];
	p->r=&mem[ml++];
	init(L,m,p->l);
	init(m+1,R,p->r);
}

inline int calc(int l,int r,int k)
{
	int m,L=0,R=n-1,f;
	node *p=root;
	while(L!=R)
	{
		m=L+R>>1;
		if(!l) f=el[p->s+r];
		else f=el[p->s+r]-el[p->s+l-1];
		if(k<=f)
		{
			if(l) l=el[p->s+l-1];
			r=el[p->s+r]-1;
			p=p->l;
			R=m;
		}
		else
		{
			k-=f;
			if(l) l=l-el[p->s+l-1];
			r=r-el[p->s+r];
			p=p->r;
			L=m+1;
		}
	}
	return sa[L];
}

int main()
{
	int i,j,k;
	while(~scanf("%d%d",&n,&m))
	{
		ml=ell=0;
		root=&mem[ml++];
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			sa[i]=a[i];
		}
		sort(sa,sa+n);
		init(0,n-1,root);
		while(m--)
		{
			scanf("%d%d%d",&i,&j,&k);
			printf("%d\n",calc(i-1,j-1,k));
		}
	}
	return 0;
}

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

int n,m,a[100000],b[100000],sa[100000],el[2000000],ml,ell;

struct node

{

int s;

node *l,*r;

}mem[2000000],*root;

void init(int L,int R,node *p)

{

int m=L+R>>1,e=0,i,j,k;

p->s=ell;

for(i=L;i<=R;i++)

{

e+=a[i]<=sa[m]?1:0;

el[ell++]=e;

}

for(i=j=L,k=m+1;i<=R;i++)

{

if(a[i]<=sa[m]) b[j++]=a[i];

else b[k++]=a[i];

}

memcpy(a+L,b+L,4*(R-L+1));

if(L==R) return;

p->l=&mem[ml++];

p->r=&mem[ml++];

init(L,m,p->l);

init(m+1,R,p->r);

}

inline int calc(int l,int r,int k)

{

int m,L=0,R=n-1,f;

node *p=root;

while(L!=R)

{

m=L+R>>1;

if(!l) f=el[p->s+r];

else f=el[p->s+r]-el[p->s+l-1];

if(k<=f)

{

if(l) l=el[p->s+l-1];

r=el[p->s+r]-1;

p=p->l;

R=m;

}

else

{

k-=f;

if(l) l=l-el[p->s+l-1];

r=r-el[p->s+r];

p=p->r;

L=m+1;

}

return sa[L];

}

int main()

{

int i,j,k;

while(~scanf("%d%d",&n,&m))

{

ml=ell=0;

root=&mem[ml++];

for(i=0;i<n;i++)

{

scanf("%d",&a[i]);

sa[i]=a[i];

}

sort(sa,sa+n);

init(0,n-1,root);

while(m--)

{

scanf("%d%d%d",&i,&j,&k);

printf("%d\n",calc(i-1,j-1,k));

}

return 0;

}