6
11
2016
0

【UR #12A】【树状数组】实验室外的攻防战

int n;
int a[N],b[N];
bool pd()
{
	F(i,1,n) if(a[i]!=b[i]) return false;
	return true;
}
bool dfs()
{
	if(pd()) return true;
	F(i,1,n-1){
		if(a[i]>a[i+1]){
			swap(a[i],a[i+1]);
			if(dfs()) return true;
			swap(a[i],a[i+1]);
		}
	}
	return false;
}
int main()
{
	n=read();
	F(i,1,n) a[i]=read();
	F(i,1,n) b[i]=read();
	puts(dfs()?"YES":"NO");
	return 0;
}

将序列转化为n进制数,-1保证每一位数字均在0~n-1之间

const int N=(int)1e5+10;
typedef long long LL;
int n,target;
int a[N],b[N];
int hash(int *d)
{
	int val=0;
	F(i,1,n) val=val*n+d[i]-1;
	return val;
}
bool vis[16777216];//8^8
bool dfs(int cur)
{
	if(cur==target) return true;
	if(vis[cur]) return false;
	vis[cur]=true;
	F(i,1,n-1){
		if(a[i]>a[i+1]){
			swap(a[i],a[i+1]);
			if(dfs(hash(a))) return true;
			swap(a[i],a[i+1]);
		}
	}
	return false;
}
int main()
{
	scanf("%d",&n);
	F(i,1,n) scanf("%d",&a[i]);
	F(i,1,n) scanf("%d",&b[i]);
	target=hash(b);
	puts(dfs(hash(a))?"YES":"NO");
	return 0;
}
int main()
{
	n=read();
	F(i,1,n) a[i]=read(),rnk1[a[i]]=i;
	F(i,1,n) b[i]=read(),rnk2[b[i]]=i;
	F(i,1,n)
		F(j,i+1,n)
			if(rnk1[i]<rnk1[j]&&rnk2[i]>rnk2[j]){
				puts("NO");return 0;
		}
	puts("YES");
	return 0;
}
const int N=(int)1e5+10;
typedef long long LL;
int n,rnk1[N],rnk2[N];
struct Fenwick{
	int c[N];
	void clear(){mec(c,0);}
	int lowbit(int x){return x&(-x);}
	void modify(int pos,int val)
	{
		while(pos<=n){
			c[pos]=max(c[pos],val);
			pos+=lowbit(pos);
		}
	}
	int query(int pos)
	{
		int res=0;
		while(pos){
			res=max(res,c[pos]);
			pos-=lowbit(pos);
		}
		return res;
	}
}B;
int main()
{
	int x;
	scanf("%d",&n);
	F(i,1,n) scanf("%d",&x),rnk1[x]=i;
	F(i,1,n) scanf("%d",&x),rnk2[x]=i;
	F(i,1,n){
		if(B.query(rnk1[i])>rnk2[i]){
			puts("NO");
			return 0;
		}
		B.modify(rnk1[i],rnk2[i]);
	}
	puts("YES");
	return 0;
}
Category: 树套树 | Tags: | Read Count: 110

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com