hdoj2054

坑爹题,WA了7次,终于AC了。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char a[100000],b[100000],s1[100000],s2[100000];
void deal(char s[],char d[])
{
	int len=strlen(s);
	int i,j,k=0,flag=0;
	for(int t=0;t<=len-1;t++)
		if(s[t]=='.')
		{
			flag=1;
			break;
		}
	for(i=0;i<=len-1;i++)
	{
		if(s[i]=='-')
		{
			d[k++]='-';
			continue;
		}
		else if(s[i]=='+')
		{
			continue;
		}
		else if(s[i]=='0' && s[i+1]!='.')
			continue;
		else if(s[i]=='0' && s[i+1]=='.')
		{
				d[k++]=s[i];
				i++;
				d[k++]=s[i];
				i++;
				break;
		}
		else
			break;
	}
	j=len-1;
	if(flag)
		for(j=len-1;j>=0;j--)
		{
			if(s[j]=='0')
				continue;
			else if(s[j]=='.')
			{
				j--;
				break;
			}
			else
				break;
		}
	for(i=i;i<=j;i++)
		d[k++]=s[i];
	d[k++]='\0';
return;
}
int main()
{
	while(scanf("%s %s",a+1,b+1)!=EOF)
	{
		getchar();
		int i=0,j=0;
		a[0]='0';
		b[0]='0';
		deal(a,s1);
		deal(b,s2);
		int len1=strlen(s1);
		int len2=strlen(s2);
		for(i=0;i<=len1-1;i++)
		{
			if(!(s1[i]=='-'||s1[i]=='+'||s1[i]=='.'||s1[i]=='0'))
				break;
		}
		for(j=0;j<=len2-1;j++)
		{
			if(!(s2[j]=='-'||s2[j]=='+'||s2[j]=='.'||s2[j]=='0'))
				break;
		}
		if(i==len1 && j==len2)
		{
			printf("YES\n");
			continue;
		}
		if(len1!=len2)
			printf("NO\n");
		else
		{
			int flag=1;
			for(i=0;i<=len1;i++)
			{
				if(s1[i]!=s2[i])
				{
					flag=0;
					break;
				}
			}
			if(flag)
				printf("YES\n");
			else
				printf("NO\n");
		}
		
	
	}
//system("pause");
return 0;
}

hdoj2553—N皇后

打表程序:

#include<stdio.h>
#include<stdlib.h>
int visit[15][15];
int count=0;
void flag(int x,int y,int n)
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		visit[i][y]++;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(i+j==x+y)
				visit[i][j]++;
			if(i-j==x-y)
				visit[i][j]++;
		}
	return;
}
void unflag(int x,int y,int n)
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		visit[i][y]--;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(i+j==x+y)
				visit[i][j]--;
			if(i-j==x-y)
				visit[i][j]--;
		}
	return;	


}
void dfs(int cur,int n)
{
	if(cur==n+1)
	{
		count++;
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(!visit[cur][i])
		{
			visit[cur][i]++;
			flag(cur,i,n);
			dfs(cur+1,n);
			visit[cur][i]--;
			unflag(cur,i,n);
		}
	}
return;
}
int main()
{
	for(int i=1;i<=10;i++)
	{
		for(int j=1;j<=i;j++)
			for(int k=1;k<=i;k++)
				visit[j][k]=0;
		count=0;
		dfs(1,i);
		printf("%d\n",count);
	}

system("pause");
return 0;
}

程序代码:

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int n;
	int result[11]={0,1,0,0,2,10,4,40,92,352,724};
	scanf("%d",&n);
	while(n!=0)
	{
		printf("%d\n",result[n]);
	
	
		scanf("%d",&n);
	}
return 0;
}

hdoj2510

dfs打表
题目代码:

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int n;
	int result[25]={0,0,0,4,6,0,0,12,40,0,0,171,410,0,0,1896,5160,0,0,32757,59984,0,0,431095,822229};
	scanf("%d",&n);
	while(n!=0)
	{
		printf("%d %d\n",n,result[n]);

		scanf("%d",&n);
	}
	return 0;
}

打表程序:

//-:0
//+:1
#include<stdio.h>
#include<stdlib.h>
int result[27];
int map[26][26];
int count=0;
int num1=0;
int num2=0;
int n;
void dfs(int cur,int v)
{
	if(v==1)
		num1++;
	else
		num2++;
	map[1][cur]=v;
	if(cur==n)
	{
		int num1_temp=num1;
		int num2_temp=num2;
		for(int j=2;j<=n;j++)
			for(int k=1;k<=n-(j-1);k++)
			{
				if(map[j-1][k]^map[j-1][k+1])
				{
					map[j][k]=0;
					num2++;
				}
				else
				{
					map[j][k]=1;
					num1++;
				}
			}
		if(num1==num2)
		{
			count++;
		}
		num1=num1_temp;
		num2=num2_temp;
		return;
		
	}
	for(int i=0;i<=1;i++)
	{
		dfs(cur+1,i);
		if(i==1)
			num1--;
		else
			num2--;
	}
return;
}
int main()
{
	result[1]=0;
	result[2]=0;
	for(n=3;n<=22;n++)
	{
		if(((1+n)*n/2)&1)
		{
			result[n]=0;
			continue;
		}
		count=0;
		num1=0;
		num2=0;
		dfs(1,0);
		num1=0;
		num2=0;
		dfs(1,1);
		result[n]=count;
	}
	
	for(int i=3;i<=22;i++)
	{
		printf("%d %d\n",i,result[i]);
	}

//system("pause");
return 0;
}

hdoj2502

水水更健康,,位运算~

#include<stdio.h>
#include<stdlib.h>
int a[24];
__int64 result[25];
int main()
{
	int i,t;
	a[0]=1;
	a[1]=2;
	result[1]=1;
	result[2]=3;
	for(i=2;i<=23;i++)
		a[i]=a[i-1]*2;
	for(i=3;i<=20;i++)
	{
		int j;
		__int64 sum=0;
		for(j=a[i-1];j<=a[i]-1;j++)
		{
			for(int k=1;k<=i;k++)
			{
				if(j&a[k-1])
					sum++;
			}
		}
		result[i]=sum;
	}
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		printf("%I64d\n",result[n]);
	}
//system("pause");
return 0;
}

hdoj1426

昨天整个下午写和调试这道题到晚上12点多,外加今天一个小时,终于看到了那个ACcept。感动差点就哭了~
其间经历了WA->TLE->WA->OLE->TLE->WA……长期循环,最终发现时judge函数次里面的if块没加括号,原来以为不加可以的,后来想到不加括号可能使else if接错地方。。

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
typedef struct Q{
	int x,y;
}Q;
int iq=0;
Q queue[100];
int map[12][12];
bool flag=false;
bool heng[10][10];
bool shu[10][10];
bool small[10][10];
bool judge(int cnt,int v)
{
	if(heng[queue[cnt].x][v]==true)
		return false;
	if(shu[queue[cnt].y][v]==true)
		return false;
	int x=queue[cnt].x,y=queue[cnt].y;
	if(x<=3)
	{
		if(y<=3)
		{
			if(small[1][v]==true)
				return false;
		}
		else if(y>=7)
		{
			if(small[3][v]==true)
				return false;
		}
		else
		{
			if(small[2][v]==true)
				return false;
		}
	}
	else if(x>=7)
	{
		if(y<=3)
		{
			if(small[7][v]==true)
				return false;
		}
		else if(y>=7)
		{
			if(small[9][v]==true)
				return false;
		}
		else
		{
			if(small[8][v]==true)
				return false;
		}
	}
	else
	{
		if(y<=3)
		{
			if(small[4][v]==true)
				return false;
		}
		else if(y>=7)
		{
			if(small[6][v]==true)
				return false;
		}
		else
		{
			if(small[5][v]==true)
				return false;
		}
	}
	return true;
}
void dfs(int cur)
{
	int i,j;
	if(flag)
		return;
	if(cur==iq)
	{
		flag=true;
		for(int t=1;t<=9;t++)
			for(int k=1;k<=9;k++)
			{
				if(k!=9)
					printf("%d ",map[t][k]);
				else
					printf("%d\n",map[t][k]);
			}
		return;
	}
	for(i=1;i<=9;i++)
	{
		if(judge(cur,i))
		{
			int x=queue[cur].x;
			int y=queue[cur].y;
			map[x][y]=i;
			heng[x][i]=true;
			shu[y][i]=true;
			if(x<=3)
			{
				if(y<=3)
					small[1][i]=true;
				else if(y>=7)
					small[3][i]=true;
				else
					small[2][i]=true;
			}
			else if(x>=7)
			{
				if(y<=3)
					small[7][i]=true;
				else if(y>=7)
					small[9][i]=true;
				else
					small[8][i]=true;
			}
			else
			{
				if(y<=3)
					small[4][i]=true;
				else if(y>=7)
					small[6][i]=true;
				else
					small[5][i]=true;
			}
			dfs(cur+1);
			map[x][y]=0;
			heng[x][i]=false;
			shu[y][i]=false;
			if(x<=3)
			{
				if(y<=3)
					small[1][i]=false;
				else if(y>=7)
					small[3][i]=false;
				else
					small[2][i]=false;
			}
			else if(x>=7)
			{
				if(y<=3)
					small[7][i]=false;
				else if(y>=7)
					small[9][i]=false;
				else
					small[8][i]=false;
			}
			else
			{
				if(y<=3)
					small[4][i]=false;
				else if(y>=7)
					small[6][i]=false;
				else
					small[5][i]=false;
			}

		}
	}
return;
}
int main()
{
	char s;
	int i,j,cases=1;
	while(cin>>s)
	{
		for(i=1;i<=9;i++)
			for(j=1;j<=9;j++)
			{
				heng[i][j]=false;
				shu[i][j]=false;
				small[i][j]=false;
			}
		iq=0;
		flag=false;
		if(s=='?')
		{
			map[1][1]=0;
			queue[iq].x=1;
			queue[iq++].y=1;
		}
		else
		{
			map[1][1]=s-'0';
			heng[1][map[1][1]]=true;
			shu[1][map[1][1]]=true;
			small[1][map[1][1]]=true;
		}
		for(i=1;i<=9;i++)
		{
			for(j=1;j<=9;j++)
			{
				if(i!=1||j!=1)
				{
					cin>>s;
					if(s=='?')
					{
						map[i][j]=0;
						queue[iq].x=i;
						queue[iq++].y=j;
					}
					else
					{
						map[i][j]=s-'0';
						heng[i][map[i][j]]=true;
						shu[j][map[i][j]]=true;
						if(i<=3)
						{
							if(j<=3)
								small[1][map[i][j]]=true;
							else if(j>=7)
								small[3][map[i][j]]=true;
							else
								small[2][map[i][j]]=true;
						}
						else if(i>=7)
						{
							if(j<=3)
								small[7][map[i][j]]=true;
							else if(j>=7)
								small[9][map[i][j]]=true;
							else
								small[8][map[i][j]]=true;
						}
						else
						{
							if(j<=3)
								small[4][map[i][j]]=true;
							else if(j>=7)
								small[6][map[i][j]]=true;
							else
								small[5][map[i][j]]=true;
						}
						
					}
				}
			}
			
		}
		if(cases!=1)
			printf("\n");
		dfs(0);
		cases++;
	}

//system("pause");
return 0;
}

hdoj1584

http://blog.csdn.net/longyuan20102011/article/details/7246994
看了这个结题报告才写出来的。。思路确实挺巧妙的,想到了就很简单。原来自己想的时候是枚举每次可以移动的位置。。要保存很多信息,写起来很麻烦。
思路:用pos[i]=j表示牌面为i的牌在位置j,visit[i]表示牌面为i的牌是否已经移动过
几个要点:
1.一张牌只需移一次,所有总共移九次
2.牌面为i的牌只能移到牌面为i+1的牌上面。
3.要移动牌面为i的牌时,如果i+1、i+2、……、i+k都已经移动过,i+k+1未移动过,那么显然i要移到牌面为i+k+1的牌所在位置(因为此时i+1、i+2、……、i+k肯定在i+k+1这张牌上面)
4.从上一条可以得出:每次移动都是将一张没有移动过的牌移到另一张没有移动过的牌的所在位置,移动过的牌所在位置此时都为空。
5.牌面为i的牌移动之后不需要相应改动pos[i],因为第4条可知,这张牌以后不会再用到
所以可见,每一次枚举要移动哪张牌(未移动过的),至于移动到哪,可以枚举牌面比它大的牌,移到第一张未移动过的牌上面

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<limits.h>
#include<string.h>
int ans;
int visit[11];
int pos[11];
void dfs(int num,int sum)
{
	int i,j;
	if(sum>ans)
		return;
	if(num==9)
	{
		ans=sum;
		return;
	}
	for(i=1;i<=10;i++)
	{
		if(!visit[i])
		{
			visit[i]=1;
			for(j=i+1;j<=10;j++)
			{
				if(!visit[j])
					break;
			}
			if(j==11)
			{
				visit[i]=0;
				continue;
			}
			dfs(num+1,sum+abs(pos[i]-pos[j]));
			visit[i]=0;
		}
	}
	return;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int i,a;
		ans=INT_MAX;
		memset(visit,0,sizeof(visit));
		for(i=1;i<=10;i++)
		{
			scanf("%d",&a);
			pos[a]=i;
		}
		dfs(0,0);
		printf("%d\n",ans);
	
	}


//system("pause");
return 0;
}

poj2828——逆向思维的线段树

调试了好久,最后发现原来是顺着插入了。。
事后看了下被人的解题报告,主要是想看下怎样输出,自己用O(nlogn)时间输出,看了别人的代码,发现自己又二了,输出可以O(1)。。在update时找到插入位置后记录插入的叶子节点的l或r域即可,然后update()函数返回后写到结果数组的对应位置。暂时不改了,睡觉去也~

#include<stdio.h>
#include<stdlib.h>
typedef struct Tree{
	int l,r;
	int empty;
	int v;
}Tree;
Tree tree[800010];
int pos[200005],v[200005];
void pushup(int rt)
{
	tree[rt].empty=tree[rt<<1].empty+tree[rt<<1|1].empty;
	return;
}
void build(int rt,int l,int r)
{
	tree[rt].l=l;
	tree[rt].r=r;
	if(l==r)
	{
		tree[rt].empty=1;
		return;
	}
	int m=(l+r)/2;
	build(rt<<1,l,m);
	build(rt<<1|1,m+1,r);
	pushup(rt);
	return;
}
int query(int rt,int num)
{
	if(tree[rt].l==tree[rt].r)
	{
		return tree[rt].v;
	}
	int m=(tree[rt].l+tree[rt].r)/2;
	if(num<=m)
		return	query(rt<<1,num);
	else
		return query(rt<<1|1,num);
}
void update(int rt,int pos,int v)
{
	if(tree[rt].l==tree[rt].r)
	{
		tree[rt].v=v;
		tree[rt].empty=0;
		return;
	}
	int m=(tree[rt].l+tree[rt].r)/2;
	if(pos<=tree[rt<<1].empty)
		update(rt<<1,pos,v);
	else
		update(rt<<1|1,pos-tree[rt<<1].empty,v);
	pushup(rt);
	return;
}
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		int i,p;
		build(1,1,n);
		for(i=1;i<=n;i++)
		{
			scanf("%d %d",&p,&v[i]);
			pos[i]=++p;
		}
		for(i=n;i>=1;i--)
			update(1,pos[i],v[i]);
		for(i=1;i<=n-1;i++)
			printf("%d ",query(1,i));
		printf("%d\n",query(1,n));

	}

//system("pause");
return 0;
}

hdoj1698——成段修改,区间求和

效率不给力,800多秒。。

#include<stdio.h>
#include<stdlib.h>
typedef struct Tree{
	int l,r;
	int sum;
	int color;
	int lazy;
}Tree;
Tree tree[400005];
void pushup(int rt)
{
	tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
	return;
}
void pushdown(int rt)
{
	int color=tree[rt].color;
	tree[rt<<1].lazy=1;
	tree[rt<<1|1].lazy=1;
	tree[rt<<1].color=color;
	tree[rt<<1|1].color=color;
	tree[rt<<1].sum=color*(tree[rt<<1].r-tree[rt<<1].l+1);
	tree[rt<<1|1].sum=color*(tree[rt<<1|1].r-tree[rt<<1|1].l+1);
	tree[rt].lazy=0;
	return;
}
void build(int rt,int l,int r)
{
	tree[rt].l=l;
	tree[rt].r=r;
	tree[rt].lazy=0;
	tree[rt].color=1;
	if(l==r)
	{
		tree[rt].sum=1;
		return;
	}
	int m=(l+r)/2;
	build(rt<<1,l,m);
	build(rt<<1|1,m+1,r);
	pushup(rt);
	return;
}
void update(int rt,int L,int R,int z)
{
	if(L<=tree[rt].l && tree[rt].r<=R)
	{
		tree[rt].color=z;
		tree[rt].sum=z*(tree[rt].r-tree[rt].l+1);
		tree[rt].lazy=1;
		return;
	}
	if(tree[rt].lazy)
		pushdown(rt);
	int m=(tree[rt].l+tree[rt].r)/2;
	if(L<=m)
		update(rt<<1,L,R,z);
	if(R>m)
		update(rt<<1|1,L,R,z);
	pushup(rt);
	return;
}
int main()
{
	int j,t;
	scanf("%d",&t);
	for(j=1;j<=t;j++)
	{
		int i,n,q;
		scanf("%d %d",&n,&q);
		build(1,1,n);
		int x,y,z;
		for(i=1;i<=q;i++)
		{
			scanf("%d %d %d",&x,&y,&z);
			update(1,x,y,z);
		}
		printf("Case %d: The total value of the hook is %d.\n",j,tree[1].sum);
	}
//system("pause");
return 0;
}

poj3468——成段加减,区间求和

第一道成段更新的线段树题,看了很久,终于基本上掌握了lazy的思想和实现过程。纪念下
11139010 shadowxuhao 3468 Accepted 6332K 1844MS C++ 1720B 2012-12-26 16:52:02

#include<stdio.h>
#include<stdlib.h>
typedef struct Tree{
	int l,r;
	__int64 add;
	__int64 sum;
}Tree;
Tree tree[400005];
void pushup(int rt)
{
	tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
	return;
}
void pushdown(int rt)
{
	__int64 add=tree[rt].add;
	tree[rt<<1].add+=add;
	tree[rt<<1|1].add+=add;
	tree[rt<<1].sum+=add*(tree[rt<<1].r-tree[rt<<1].l+1);
	tree[rt<<1|1].sum+=add*(tree[rt<<1|1].r-tree[rt<<1|1].l+1);
	tree[rt].add=0;
	return;
}
void build(int rt,int l,int r)
{
	tree[rt].l=l;
	tree[rt].r=r;
	tree[rt].add=0;
	if(l==r)
	{
		scanf("%I64d",&tree[rt].sum);
		return;
	}
	int m=l+(r-l)/2;
	build(rt<<1,l,m);
	build(rt<<1|1,m+1,r);
	pushup(rt);
	return;
}
void update(int rt,int L,int R,__int64 v)
{
	if(L<=tree[rt].l && tree[rt].r<=R)
	{
		tree[rt].add+=v;
		tree[rt].sum+=v*(tree[rt].r-tree[rt].l+1);
		return;
	}
	if(tree[rt].add!=0)
		pushdown(rt);
	int m=tree[rt].l+(tree[rt].r-tree[rt].l)/2;
	if(L<=m)
		update(rt<<1,L,R,v);
	if(R>m)
		update(rt<<1|1,L,R,v);
	pushup(rt);
	return;
}
__int64 query(int rt,int L,int R)
{
	if(L<=tree[rt].l && tree[rt].r<=R)
		return tree[rt].sum;
	if(tree[rt].add)
		pushdown(rt);
	int m=tree[rt].l+(tree[rt].r-tree[rt].l)/2;
	__int64 ret=0;
	if(L<=m)
		ret+=query(rt<<1,L,R);
	if(R>m)
		ret+=query(rt<<1|1,L,R);
	return ret;
}
int main()
{
	int i,n,q;
	scanf("%d %d",&n,&q);
	build(1,1,n);
	getchar();
	for(i=1;i<=q;i++)
	{
		char c;
		int a,b;
		__int64 v;
		scanf("%c",&c);
		if(c=='C')
		{
			scanf("%d %d %I64d",&a,&b,&v);
			getchar();
			update(1,a,b,v);
		}
		else
		{
			scanf("%d %d",&a,&b);
			getchar();
			printf("%I64d\n",query(1,a,b));
		}
	}

//system("pause");
return 0;
}

hdoj2141

昨天想手写下二分,找到了这道题。结果TLE了N次,今晚发现原来是枚举了大数组,二分查找了小数组,这样效率还是没足够提高,应当反过来。
这类题思路:当多重循环超时时,观察是否可以加入二分,二分查找较大的数组,减少循环层数,剩下的枚举。

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
__int64 sum[260000];
__int64 bsearch(__int64 a[],int x,int y,int v)//左闭右开区间[x,y)
{
	int m;
	while(x<y)
	{
		m=x+(y-x)/2;
		if(a[m]==v)
			return m;
		else if(v<a[m])
			y=m;
		else
			x=m+1;
	}
	return 0;
}
int main()
{
	int l,n,m,cases=0;
	while(scanf("%d %d %d",&l,&n,&m)!=EOF)
	{
		int i,j,k=0;
		int a[510],b[510],c[510];
		for(i=1;i<=l;i++)
			scanf("%d",&a[i]);
		for(i=1;i<=n;i++)
			scanf("%d",&b[i]);
		for(i=1;i<=m;i++)
			scanf("%d",&c[i]);
		sort(c+1,c+1+m);

		for(i=1;i<=l;i++)
			for(j=1;j<=n;j++)
				sum[++k]=a[i]+b[j];
		sort(sum+1,sum+1+k);
		int s;
		bool flag=true;
		scanf("%d",&s);
		for(i=1;i<=s;i++)
		{
			__int64 q;
			bool state=false;
			scanf("%I64d",&q);
			for(j=1;j<=m;j++)
			{
				if(bsearch(sum,1,k+1,q-c[j]))
				{
					if(flag)
					{
						printf("Case %d:\n",++cases);
						flag=false;
					}
					printf("YES\n");
					state=true;
					break;
				}
			}
			if(flag)
			{
				printf("Case %d:\n",++cases);
				flag=false;
			}
			if(!state)
				printf("NO\n");
		}

	}
//system("pause");
return 0;
}

hdoj2492

再一次栽倒在__int64上了,无限WA,。
思路:枚举2到n-1的每一个人作为裁判。假设第i个人左边有left_low[i]个人rank比他小,left_high[i]个人rank比他大,右边有right_low[i]个人rank比他小,right_high[i]个人rank比他大,那么第i个人做裁判可以形成的组合数为:left_low[i]*right_high[i]+left_high[i]*right_low[i],总的组合数全部相加就行了。
这就需要用到两次线段树,区段表示rank值,线段树的结点保存的是对应区段已有的数据量。首先从左向右依次插入,这样当插入a[i]时,线段树中的数据是a[i]左边的数据,反之,如果从右往左插入,则线段树中的数据是a[i]右边的数据。这样只要在插入前查询[1,a[i]-1][a[i]+1,100000]分别有多少个数,就能知道a[i]左边(从右向左是右边)有多少个数小于a[i],有多少个数大于a[i]。

#include<stdio.h>
#include<stdlib.h>
typedef struct Tree{
	int l,r;
	int sum;
}Tree;
typedef struct Judge{
	int left_low,left_high,right_low,right_high;
}Judge;
Tree tree[510000];
Judge judge[20005];
int a[20005];
void pushup(int rt)
{
	tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
	return;
}
void build(int rt,int l,int r)
{
	tree[rt].l=l;
	tree[rt].r=r;
	tree[rt].sum=0;
	if(l==r)
		return;
	int m=(l+r)/2;
	build(rt<<1,l,m);
	build(rt<<1|1,m+1,r);
	pushup(rt);
	return;
}
void update(int rt,int v)
{
	if(tree[rt].l==tree[rt].r)
	{
		tree[rt].sum=1;
		return;
	}
	int m=(tree[rt].l+tree[rt].r)/2;
	if(v<=m)
		update(rt<<1,v);
	else
		update(rt<<1|1,v);
	pushup(rt);
	return;
}
int query(int rt,int L,int R)
{
	if(L<=tree[rt].l && tree[rt].r<=R)
	{
		return tree[rt].sum;
	}
	int m=(tree[rt].l+tree[rt].r)/2;
	int ret=0;
	if(L<=m)
		ret+=query(rt<<1,L,R);
	if(R>m)
		ret+=query(rt<<1|1,L,R);
	return ret;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int i,n;
		build(1,1,100000);
		scanf("%d",&n);
		scanf("%d",&a[1]);
		update(1,a[1]);
		for(i=2;i<=n-1;i++)
		{
			scanf("%d",&a[i]);
			judge[i].left_low=query(1,1,a[i]-1);
			judge[i].left_high=query(1,a[i]+1,100000);
			update(1,a[i]);
		}
		scanf("%d",&a[n]);
		update(1,a[n]);
		build(1,1,100000);
		update(1,a[n]);
		for(i=n-1;i>=2;i--)
		{
			judge[i].right_low=query(1,1,a[i]-1);
			judge[i].right_high=query(1,a[i]+1,100000);
			update(1,a[i]);
		}
		update(1,a[1]);
		__int64 sum=0;
		for(i=2;i<=n-1;i++)
			sum+=judge[i].left_low*judge[i].right_high+judge[i].left_high*judge[i].right_low;
		printf("%I64d\n",sum);
	}
//system("pause");
return 0;
}

poj2001

两点收获:
1.scanf()读取字符串时,EOF也算一个;用gets()读取字符串时,NULL行也算一个,所以注意读取的个数要减一
2.实在无法AC时,把gets()换成scanf()试试。。。~

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Trie{
	int v;
	int count;
	struct Trie* next[27];
}Trie;
Trie *root=(Trie*)malloc(sizeof(Trie));
void insert(char s[])
{
	int i,len=strlen(s);
	Trie *p=root,*q;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(p->next[x])
		{
			p=p->next[x];
			(p->count)++;
		}
		else
		{
			q=(Trie*)malloc(sizeof(Trie));
			for(int j=1;j<=26;j++)
				q->next[j]=NULL;
			q->v=0;
			q->count=1;
			p->next[x]=q;
			p=q;
		}
	}
	p->v=1;
	return;
}
int find(char s[])
{
	int i,len=strlen(s);
	Trie *p=root;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(p->next[x])
		{
			p=p->next[x];
			if(p->count==1)
				break;
		}
	}
	if(i==len)
		return i-1;
	else
		return i;
}
void del(Trie *root)
{
	int i;
	for(i=1;i<=26;i++)
	{
		if(root->next[i])
			del(root->next[i]);
	}
	free(root);
	return;
}
int main()
{
	char s[1010][25];
	int i;
	for(i=1;i<=26;i++)
		root->next[i]=NULL;
	root->v=0;
	root->count=0;
	i=0;
	while(scanf("%s",s[++i])!=EOF)
	{
		getchar();
		insert(s[i]);
	}
	int n=i-1;
	for(i=1;i<=n;i++)
	{
			int len=find(s[i]);
			printf("%s ",s[i]);
			for(int j=0;j<=len;j++)
				printf("%c",s[i][j]);
			printf("\n");
	}
	del(root);
//system("pause");
return 0;
}

hdoj1394——两种方法求逆序数

先保存下写的代码,有时间回过来写解题思路。。
线段树球逆序数:

#include<stdio.h>
#include<stdlib.h>
typedef struct Tree{
	int l,r;
	int sum;
}Tree;
Tree tree[10005];
void pushup(int rt)
{
	tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
	return;
}
void build(int rt,int l,int r)
{
	tree[rt].l=l;
	tree[rt].r=r;
	if(l==r)
	{
		tree[rt].sum=0;
		return;
	}
	int m=(l+r)/2;
	build(rt<<1,l,m);
	build(rt<<1|1,m+1,r);
	pushup(rt);
	return;
}
void update(int rt,int v)
{
	if(tree[rt].l==tree[rt].r)
	{
		tree[rt].sum++;
		return;
	}
	int m=(tree[rt].l+tree[rt].r)/2;
	if(v<=m)
		update(rt<<1,v);
	else
		update(rt<<1|1,v);
	pushup(rt);
	return;
}
int query(int rt,int L,int R)
{
	if(L<=tree[rt].l && tree[rt].r<=R)
		return tree[rt].sum;
	int ret=0;
	int m=(tree[rt].l+tree[rt].r)/2;
	if(L<=m)
		ret+=query(rt<<1,L,R);
	if(R>m)
		ret+=query(rt<<1|1,L,R);
	return ret;
}
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		int i,a[5010],sum=0;
		build(1,1,n);
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			a[i]++;
			sum+=query(1,a[i]+1,n);
			update(1,a[i]);
			
		}
		int min=sum;
		for(i=1;i<=n;i++)
		{
			sum=sum-(a[i]-1)+(n-1-(a[i]-1));
			if(sum<min)
				min=sum;
		}
		printf("%d\n",min);
			
	}
//system("pause");
return 0;
}

归并排序求逆序数:

#include<stdio.h>
#include<stdlib.h>
int count;
void merge(int a[],int p,int r,int q)
{
    int begin1=p,end1=r,begin2=r+1,end2=q;
    int temp[5010],k=0;
    while(begin1<=end1 && begin2<=end2)
    {
        if(a[begin1]>a[begin2])
        {
            temp[++k]=a[begin2];
            begin2++;
            count+=end1-begin1+1;
        }
        else
        {
            temp[++k]=a[begin1];
            begin1++;
        }
    }
    while(begin1<=end1)
    {
        temp[++k]=a[begin1];
        begin1++;
    }
    while(begin2<=end2)
    {
        temp[++k]=a[begin2];
        begin2++;
    }
    for(int i=p;i<=q;i++)
        a[i]=temp[i-p+1];
    return;
}
void mergesort(int a[],int p,int q)
{
    if(p<q)
    {
        int r=(p+q)/2;
        mergesort(a,p,r);
        mergesort(a,r+1,q);
        merge(a,p,r,q);
    }
    return;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i,a[5010],b[5010];
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            a[i]++;
            b[i]=a[i];
        }
        count=0;
        mergesort(a,1,n);
        int sum=count,min=count;
        for(i=1;i<=n;i++)
        {
            sum=sum-(b[i]-1)+(n-1-(b[i]-1));
            if(sum<min)
                min=sum;
        }
        printf("%d\n",min);
    }
return 0;
}

acm常见错误(添加中。。)

一直想写这些总结一下自己过去常犯的错误,但是总是忘记。。

(1)数组开小了

(2)精度问题,数开小了(__int64定义成int)

(3)精度问题,数转换错误(__int64赋值给int)

(4)char数组定义成int

(5)==写成=(很难查到的错误)

(6)变量未初始化

(7)变量初始化错误,想当然的初始化,特别是数组,有时候a[0]、a[len-1]等需要初始化为和其他元素不同的值,但不仔细分析就全赋为0就出错了

(8)getchar()(字符串相关题目,都懂得~~)

(9)语句块漏写括号(这个其实已经消灭了)

(10)if语句块大量嵌套时,一定要加上括号,防止else和else if混接在错误的if之后。养成良好习惯。。(上一条刚说已经消灭了,昨天做hdoj1426又出现这个错误了。。2012.12.28)

 

hdoj3743——归并排序求逆序数

在学线段树的时候遇到逆序数的题,先巩固下归并排序和逆序数。

逆序对:数列a[]中,a[i]>a[j](i

逆序数:一个数列中逆序对的对数称为逆序数。

归并排序求逆序数(nlog(n)):

       在归并排序的二路合并阶段(显然合并是自底向上的,所以可以保证合并时两个序列分别有序),如果第二个序列的当前值小于第一个数列的当前值,则显然前一个数列当前值到第一个数列结尾的元素和第二个序列的当前值构成逆序对。描述得有些不好,见代码。

为什么通过不断求两个子序列间的逆序数可以最终得到原数列的逆序数?

答:因为归并排序的分治后,在合并阶段,子序列间元素的相对位置没有改变。这个比较难表达,要自己体会。

例如:a[i]在数列one中,a[j]在数列two中,假设a[i]>a[j]并且one在前,two在后,现在已经求出了one的逆序数(通过合并one的两个子数列),求出了two的逆序数,即one和two都排成有序了,接下来要将one和two合并。显然a[i]和a[j]的相对位置还是没变。仍然构成逆序对。

说白了就一句话,子数列的排序并不影响父数列中元素的逆序关系。因而不断求出小范围内的逆序数,再不断扩大范围就可以最终求出总的逆序数。好了,这样就“证明”了归并排序求逆序数的正确性。

接下来还有一个问题:如果规定为使数列升序,只能通过交换相邻元素实现,那么交换次数和该数列逆序数的关系?

答:交换次数=逆序数

为什么呢?很简单,基于以下三点:

(1)逆序的数必须交换

(2)一次交换只能改变两个数的逆序关系

(3)如果两个数逆序,则必然需且仅需1次交换。

也就是说通过一次交换可以使1个逆序对消失。这样结论就很清楚了。。

总结:我想通过归并不仅可以求逆序数,题目改变一下也是可以做的,如要找出a[i]+b*i-c>a[j]+b*j-c(i<j)的对数,那么通过小小修改,或是对原数列进行预处理就行了。关键是理解本质。。想了这些之后,我自己的思路也理清了,轻松不少。(当然自己的思绪还是有错误的地方)

下面放上代码(顺便作为自己以后解题的模板):

 

 

 

#include<stdio.h>
#include<stdlib.h>
__int64 a[1000002];
__int64 temp[1000002];
__int64 count=0;
void merge(__int64 a[],int p,int r,int q)
{
	int begin1=p,end1=r,begin2=r+1,end2=q;
	int k=0;
	while(begin1<=end1 && begin2<=end2)
	{
		if(a[begin1]>a[begin2])
		{
			temp[++k]=a[begin2];
			begin2++;
			count+=end1-begin1+1;
		}
		else
		{
			temp[++k]=a[begin1];
			begin1++;
		}
	}
	while(begin1<=end1)
	{
		temp[++k]=a[begin1];
		begin1++;
	}
	while(begin2<=end2)
	{
		temp[++k]=a[begin2];
		begin2++;
	
	}
	for(int i=p;i<=q;i++)
		a[i]=temp[i-p+1];
	return;


}
void mergesort(__int64 a[],int p,int q)
{
	if(p<q)
	{
		int r=(p+q)/2;
		mergesort(a,p,r);
		mergesort(a,r+1,q);
		merge(a,p,r,q);
	}
	return;
}
int main()
{
	int n,i;
	while(scanf("%d",&n)!=EOF)
	{
		count=0;
		for(i=1;i<=n;i++)
			scanf("%I64d",&a[i]);
		mergesort(a,1,n);
		printf("%I64d\n",count);
	}

//system("pause");
return 0;
}