ydc的博客

日志

关于我

ydc

文章分类

PQ树模板

2014-11-23 21:26:46| 分类：集训队作业 | 标签： |举报 |字号大中小订阅

下载LOFTER 我的照片书 |

在做集训队作业的时候，做到了codeforces 243E的matrix这题

官方做法我不知道是什么……反正hza多年前告诉我有一种叫PQ树的数据结构能做

于是大好人hza发给了我PQ树的资料，是集训队作业里的

然后我就开始看了……

感觉如下：

一、PQ树太复杂了。思路虽然清晰但是要各种分情况讨论。唔，自相矛盾？好，那我告诉你实话吧：讨论着讨论着思路就一点都不清晰了

二、分情况讨论题最好不要想着一句话处理所有情况……因为一不小心没写好会滚雪球

三、爆数组的孩子上辈子是折翼的天使

四、以上三点都是建立在ydc实力太弱这个因素的前提下，如果你实力强，根本不会为这种事情纠结

UPD：

vfk用实践证明了第四点

复杂度应该是严格的O(n^2)

代码写的很丑，比别人的长很多很多……9K左右

我因为一个地方数组开小了，然后对拍了一个多小时甚至不止（一边颓废一边拿着对拍器在拍）都没拍出错，最后找出题人要了数据后发现本机A了才意识到不科学，最后在CF的custom下进行极其蛋疼的调试（各种输出中间变量）才找出那个爆数组的地方

最后发一下代码，以表示我不是什么都没做

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxc 510
#define maxn maxc*10
using namespace std;
int son[maxn*3],l=10001,r=10000;
int isP[maxn];
int n,rt,top;
int to[maxn],next[maxn],start[maxn],father[maxn];
int pool_p[maxn],pool_e[maxn],n_p,n_e;
int have[maxn][2];
int newnode()
{
	int p=pool_p[n_p--];
	isP[p]=true;
	start[p]=0;
	return p;
}
void make(int a,int b)
{
	int x=pool_e[n_e--];
	to[x]=b,next[x]=start[a],start[a]=x,father[b]=a;
}
void clean(int p)
{
	for(int &i=start[p];i;i=next[i])
		pool_e[++n_e]=i;
}
void Reverse(int p)
{
	static int stack[maxn];
	int top=0;
	for(int &i=start[p];i;i=next[i])
		stack[++top]=i;
	start[p]=stack[top];
	for(;top;--top)
		next[stack[top]]=stack[top-1];
}
void Fail()
{
	printf("NO\n");
	exit(0);
}
void print(int p,int *ans,int &n)
{
	if(!start[p])
		ans[++n]=p;
	for(int i=start[p];i;i=next[i])
		print(to[i],ans,n);
}
void print(int p)
{
	if(p<=n)
		printf("I'm %d ",p);
	printf("(%d %c): ",p,isP[p]?'P':'Q');
	for(int i=start[p];i;i=next[i])
		printf("%d ",to[i]);
	printf("\n");
	for(int i=start[p];i;i=next[i])
		print(to[i]);
}
void update(int p)
{
	if(!start[p])
		return ;
	have[p][0]=have[p][1]=0;
	for(int i=start[p];i;i=next[i])
		have[p][0]|=have[to[i]][0],have[p][1]|=have[to[i]][1];
}
int find(int p,int c1,int c2)
{
	int cnt=0;
	for(int i=start[p];i;i=next[i])
		if(have[to[i]][0]==c1&&have[to[i]][1]==c2)
			++cnt;
	return cnt;
}
bool check(int p,int x)
{
	/*
		x=0 : none->half->all
		x=1 : all->half->none
	*/
	int a;
	if(x==0)
	{
		for(a=start[p];a&&!have[to[a]][1];a=next[a]);
		for(;a&&have[to[a]][0]&&have[to[a]][1];a=next[a]);
		for(;a;a=next[a])
			if(have[to[a]][0])
				return false;
		return true;
	}
	else
	{
		for(a=start[p];a&&!have[to[a]][0];a=next[a]);
		for(;a&&have[to[a]][0]&&have[to[a]][1];a=next[a]);
		for(;a;a=next[a])
			if(have[to[a]][1])
				return false;
		return true;
	}
}
void work(int p,int x,int dep)
{
	/*
		x=0 : t_L
		x=1 : t_R
	*/
	static int p_none[maxn],p_half[maxn],p_all[maxn];
	bool mark=true;
	int n1,n2,n3;
	if(isP[p])
	{
		mark=false;
		n1=0,n2=0,n3=0;
		for(int i=start[p];i;i=next[i])
		{
			int x=to[i];
			if(have[x][0]&&!have[x][1])
				p_none[++n1]=x;
			if(have[x][0]&&have[x][1])
				p_half[++n2]=x;
			if(!have[x][0]&&have[x][1])
				p_all[++n3]=x;
		}
		if(n2>1)
			Fail();
		clean(p);
		if(x==0)
		{
			for(int i=n3;i>=1;--i)
				make(p,p_all[i]);
			for(int i=n2;i>=1;--i)
				make(p,p_half[i]);
			for(int i=n1;i>=1;--i)
				make(p,p_none[i]);
			if(n2)
				work(p_half[1],0,dep+1);
		}
		else
		{
			for(int i=n1;i>=1;--i)
				make(p,p_none[i]);
			for(int i=n2;i>=1;--i)
				make(p,p_half[i]);
			for(int i=n3;i>=1;--i)
				make(p,p_all[i]);
			if(n2)
				work(p_half[1],1,dep+1);
		}
		n1=0,n2=0,n3=0;
		for(int i=start[p];i;i=next[i])
		{
			int x=to[i];
			if(have[x][0]&&!have[x][1])
				p_none[++n1]=x;
			if(have[x][0]&&have[x][1])
				p_half[++n2]=x;
			if(!have[x][0]&&have[x][1])
				p_all[++n3]=x;
		}
		clean(p);
		int u=n1>1?newnode():p,v=n3>1?newnode():p;
		if(x==0)
		{
			if(v!=p)
				make(p,v);
			for(int i=n3;i>=1;--i)
				make(v,p_all[i]);
			for(int i=n2;i>=1;--i)
				make(p,p_half[i]);
			for(int i=n1;i>=1;--i)
				make(u,p_none[i]);
			if(u!=p)
				make(p,u);
		}
		else
		{
			if(u!=p)
				make(p,u);
			for(int i=n1;i>=1;--i)
				make(u,p_none[i]);
			for(int i=n2;i>=1;--i)
				make(p,p_half[i]);
			for(int i=n3;i>=1;--i)
				make(v,p_all[i]);
			if(v!=p)
				make(p,v);
		}
		update(u),update(v),update(u),update(v);
		isP[p]=false;
	}
	if(mark)
	{
		int cnt=find(p,1,1),a;
		if(cnt>1)
			Fail();
		if(!check(p,x))
		{
			Reverse(p);
			if(!check(p,x))
				Fail();
		}
		if(cnt)
		{
			for(a=start[p];!have[to[a]][0]||!have[to[a]][1];a=next[a]);
			work(to[a],x,dep+1);
		}
	}
	static int tmp[maxn];
	int a,tot=0;
	for(a=start[p];a&&(!have[to[a]][0]||!have[to[a]][1]);a=next[a])
		tmp[++tot]=to[a];
	while(tot)
		son[--l]=tmp[tot--];
	for(;a&&have[to[a]][0]&&have[to[a]][1];a=next[a])
		pool_p[++n_p]=to[a];
	for(;a;a=next[a])
		son[++r]=to[a];
	clean(p);
	if(dep==1)
	{
		for(int i=r;i>=l;--i)
			make(p,son[i]);
		l=10001,r=10000;
	}
}
void Insert(int *a,int m)
{
	if(m<=1)
		return ;
	static int p_none[maxn],p_half[maxn],p_all[maxn],tmp[maxn];
	static bool col[maxc];
	memset(col,false,sizeof(col));
	for(int i=1;i<=m;++i)
		col[a[i]]=true;
	static int queue[maxn],pos[maxn];
	int front=0,rear=1;
	queue[rear]=rt;
	while(front<rear)
	{
		int p=queue[++front];
		have[p][0]=have[p][1]=0;
		for(int i=start[p];i;i=next[i])
		{
			queue[++rear]=to[i];
			pos[to[i]]=p==rt?to[i]:pos[p];
		}
	}
	for(int i=rear;i>=1;--i)
	{
		int p=queue[i];
		if(!start[p])
			have[p][col[p]]=1;
		update(p);
	}
	int p=rt;
	while(find(p,1,1)+find(p,0,1)<2)
	{
		int cnt=0,a;
		for(int i=start[p];i;i=next[i])
			if(have[to[i]][1])
				++cnt,a=to[i];
		p=a;
	}
	if(find(p,1,1)>2)
		Fail();
	if(!find(p,1,1))
	{
		if(!isP[p])
		{
			static int ans[maxn];
			int t=0;
			print(rt,ans,t);
			int c=0;
			for(int i=1;i<=n;++i)
				c+=col[ans[i]]&&!col[ans[i-1]];
			if(c>1)
				Fail();
		}
		else
		{
			if(find(p,0,1)==1)
				return ;
			int u=newnode(),n1=0,n3=0;
			for(int i=start[p];i;i=next[i])
			{
				if(have[to[i]][1])
					p_all[++n3]=to[i];
				else
					p_none[++n1]=to[i];
			}
			clean(p);
			for(int i=1;i<=n3;++i)
				make(u,p_all[i]);
			make(p,u);
			for(int i=1;i<=n1;++i)
				make(p,p_none[i]);
		}
		return ;
	}
	if(!isP[p])
	{
		int a;
		int nson=0,cnt=find(p,1,1);
		for(a=start[p];a&&!have[to[a]][1];a=next[a])
			tmp[++nson]=to[a];
		if(have[to[a]][1]&&!have[to[a]][0]&&cnt)
		{
			Reverse(p),nson=0;
			for(a=start[p];a&&!have[to[a]][1];a=next[a])
				tmp[++nson]=to[a];
		}
		if(cnt==1)
		{
			work(to[a],0,1);
			for(int i=start[to[a]];i;i=next[i])
				tmp[++nson]=to[i];
			pool_p[++n_p]=to[a];
			a=next[a];
			for(;a&&have[to[a]][1]&&!have[to[a]][0];a=next[a])
				tmp[++nson]=to[a];
			for(;a;a=next[a])
			{
				if(have[to[a]][1])
					Fail();
				tmp[++nson]=to[a];
			}
		}
		else
		{
			work(to[a],0,1);
			for(int i=start[to[a]];i;i=next[i])
				tmp[++nson]=to[i];
			pool_p[++n_p]=to[a];
			a=next[a];
			for(;a&&have[to[a]][1]&&!have[to[a]][0];a=next[a])
				tmp[++nson]=to[a];
			if(!have[to[a]][1]||!have[to[a]][0])
				Fail();
			work(to[a],1,1);
			for(int i=start[to[a]];i;i=next[i])
				tmp[++nson]=to[i];
			pool_p[++n_p]=to[a];
			a=next[a];
			for(;a;a=next[a])
			{
				if(have[to[a]][1])
					Fail();
				tmp[++nson]=to[a];
			}
		}
		clean(p);
		for(int i=nson;i>=1;--i)
			make(p,tmp[i]);
	}
	else
	{
		int n1=0,n2=0,n3=0;
		for(int i=start[p];i;i=next[i])
		{
			int x=to[i];
			if(have[x][0]&&!have[x][1])
				p_none[++n1]=x;
			if(have[x][0]&&have[x][1])
				p_half[++n2]=x;
			if(!have[x][0]&&have[x][1])
				p_all[++n3]=x;
		}
		if(n2>2)
			Fail();
		clean(p);
		if(n2>1)
			work(p_half[2],1,1),make(p,p_half[2]);
		for(int i=n3;i>=1;--i)
			make(p,p_all[i]);
		if(n2)
			work(p_half[1],0,1),make(p,p_half[1]);
		for(int i=n1;i>=1;--i)
			make(p,p_none[i]);
		int u,v;
		if(n3>1)
		{
			clean(p);
			u=newnode();
			if(n2>1)
				make(p,p_half[2]);
			make(p,u);
			if(n2)
				make(p,p_half[1]);
			for(int i=n1;i>=1;--i)
				make(p,p_none[i]);
			for(int i=n3;i>=1;--i)
				make(u,p_all[i]);
			update(u);
		}
		if(n2==1&&!n3)
			return ;
		if(n2==0)
			return ;
		v=newnode();
		isP[v]=false;
		int nson=0;
		for(int i=start[p_half[1]];i;i=next[i])
			son[++nson]=to[i];
		clean(p_half[1]),pool_p[++n_p]=p_half[1];
		if(n3>0)
			son[++nson]=n3>1?u:p_all[1];
		if(n2>1)
		{
			for(int i=start[p_half[2]];i;i=next[i])
				son[++nson]=to[i];
			for(;nson;--nson)
				make(v,son[nson]);
			clean(p_half[2]),pool_p[++n_p]=p_half[2];
		}
		for(;nson;--nson)
			make(v,son[nson]);
		clean(p);
		if(!n1)
		{
			pool_p[++n_p]=p;
			if(p==rt)
				rt=v;
			else
			{
				int q=father[p],nson=0;
				for(int i=start[q];i;i=next[i])
					son[++nson]=to[i]==p?v:to[i];
				clean(q);
				for(;nson;--nson)
					make(q,son[nson]);
			}
		}
		else
		{
			for(int i=n1;i>=1;--i)
				make(p,p_none[i]);
			make(p,v);
		}
	}
}
void read()
{
	scanf("%d",&n);
	for(int i=10*n;i>=1;--i)
		pool_p[++n_p]=i,pool_e[++n_e]=i;
	for(int i=1;i<=n;++i)
		newnode();
	rt=newnode();
	for(int i=1;i<=n;++i)
		make(rt,i);
	static char map[maxc][maxc];
	static int a[maxc];
	for(int i=1;i<=n;++i)
	{
		scanf("%s",map[i]+1);
		int tot=0;
		for(int j=1;j<=n;++j)
			if(map[i][j]=='1')
				a[++tot]=j;
		Insert(a,tot);
		/*
		printf("YES\n");
		static int ans[maxn];
		int t=0;
		print(rt,ans,t);
		for(int j=1;j<=i;++j,printf("\n"))
			for(int k=1;k<=n;++k)
				printf("%c",map[j][ans[k]]);
		printf("\n");
		print(rt);
		printf("\n\n");
		*/
	}
	printf("YES\n");
	static int ans[maxn];
	int tot=0;
	print(rt,ans,tot);
	for(int i=1;i<=n;++i,printf("\n"))
		for(int j=1;j<=n;++j)
			printf("%c",map[i][ans[j]]);
	/*
	for(int i=1;i<=n;++i)
		printf("%d ",ans[i]);
	printf("\n");
	*/
}
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	read();
	fclose(stdin);
	fclose(stdout);
	return 0;
}

当然做完这题预示着

当然意义不大……因为试题泛做6~12都已经公布了快一个月了

最后希望能继续推土机下去，不过我也知道这只是一个愿望……

评论这张

转发至微博

阅读(1338)| 评论(5)

历史上的今天

this.p={  m:2,
              b:2,
              loftPermalink:'',
              id:'fks_087070086081088071093087082064072084080069084094095067080086',
              blogTitle:'PQ树模板',
              blogAbstract:'在做集训队作业的时候，做到了codeforces 243E的matrix这题<wbr\><div\>官方做法我不知道是什么……反正hza多年前告诉我有一种叫PQ树的数据结构能做</div\><div\>于是大好人hza发给了我PQ树的资料，是集训队作业里的</div\><div\>然后我就开始看了……</div\><div\><br\></div\><div\>感觉如下：</div\><div\>一、PQ树太复杂了。思路虽然清晰但是要各种分情况讨论。唔，自相矛盾？好，那我告诉你实话吧：讨论着讨论着思路就一点都不清晰了</div\><div\>二、分情况讨论题最好不要想着一句话处理所有情况……因为一不小心没写好会滚雪球</div\><div\>三、爆数组的孩子上辈子是折翼的天使</div\><div\>四、以上三点都是建立在ydc实力太弱这个因素的前提下，如果你实力强，根本不会为这种事情纠结</div\><div\>UPD：</div\>',
              blogTag:'集训队作业',
              blogUrl:'blog/static/2160890402014102392111491',
              isPublished:1,
              istop:false,
              type:0,
              modifyTime:1416819834558,
              publishTime:1416749206264,
              permalink:'blog/static/2160890402014102392111491',
              commentCount:5,
              mainCommentCount:2,
              recommendCount:0,
              bsrk:-100,
              publisherId:0,
              recomBlogHome:false,
              currentRecomBlog:false,
              attachmentsFileIds:[],
              vote:{},
              groupInfo:{},
              friendstatus:'none',
              followstatus:'unFollow',
              pubSucc:'',
              visitorProvince:'',
              visitorCity:'',
              visitorNewUser:false,
              postAddInfo:{},
              mset:'000',
              mcon:'',
              srk:-100,
              remindgoodnightblog:false,
              isBlackVisitor:false,
              isShowYodaoAd:false,
              hostIntro:'',
              hmcon:'0',
              selfRecomBlogCount:'0',
              lofter_single:'<iframe width="140" height="560" style="overflow:hidden;" src="http://www.lofter.com/mailEntry.do?blogad=1&blog" frameBorder="0"></iframe>'
            }

{list a as x}
    {if !!x}
    <div class="iblock nbw-fce nbw-f40">
      <a class="fc03 noul" target="_blank" hidefocus="true" href="http://blog.163.com/${x.visitorName}/">
      {if x.visitorName==visitor.userName}
      <img alt="${x.visitorNickname|escape}" onerror="this.src=location.f40" class="cwd bdwa bdc0" src="${fn1(x.visitorName)}&r=${visitor.imageUpdateTime}"/>
      {else}
      <img alt="${x.visitorNickname|escape}" onerror="this.src=location.f40" class="cwd bdwa bdc0" src="${fn1(x.visitorName)}"/>
      {/if}
      </a>
      <div class="cwd vname thide">
        {if x.moveFrom=='wap'}
          <a class="noul pnt" target="_blank" href="http://blog.163.com/services/wapblog.html?frompersonalbloghome"><span title="来自网易手机博客" class="iblock wapIcon"> </span></a>
        {elseif x.moveFrom=='iphone'}
          <a class="noul pnt" target="_blank"><span title="来自iPhone客户端" class="iblock iphoneIcon"> </span></a>
        {elseif x.moveFrom=='android'}
          <a class="noul pnt" target="_blank"><span title="来自Android客户端" class="iblock androidIcon"> </span></a>
        {elseif x.moveFrom=='mobile'}
          <a class="noul pnt" target="_blank" href="http://blog.163.com/services/emsblog.html?frompersonalbloghome"><span title="来自网易短信写博" class="iblock wapIcon"> </span></a>
        {/if}
        <a class="fc03 m2a"  target="_blank" hidefocus="true" href="http://blog.163.com/${x.visitorName}/">
          ${fn(x.visitorNickname,8)|escape}
        </a>
      </div>
    </div>
    {/if}
    {/list}

<#--最新日志，群博日志--> <#--推荐日志-->

<p class="fc06">推荐过这篇日志的人：</p>
    <div>
      {list a as x}
      {if !!x}
      <div class="iblock nbw-fce nbw-f40">
        <a class="fc03 noul" target="_blank" hidefocus="true" href="http://blog.163.com/${x.recommenderName}/">
        <img alt="${x.recommenderNickname|escape}" onerror="this.src=location.f40" class="cwd bdwa bdc0" src="${fn1(x.recommenderName)}"/>
        </a>
        <div class="cwd thide">
          <a class="fc03 m2a" target="_blank" hidefocus="true" href="http://blog.163.com/${x.recommenderName}/">
            ${fn(x.recommenderNickname,6)|escape}
          </a>
        </div>
      </div>
      {/if}
      {/list}
    </div>
    {if !!b&&b.length>0}
    <p  class="fc06">他们还推荐了：</p>
    <ul>
    {list b as y}
      {if !!y}
        <li class="rrb"><span class="iblock">·</span><a class="fc03 m2a" target="_blank" href="http://blog.163.com/${y.recommendBlogPermalink}/?from=blog/static/2160890402014102392111491">${y.recommendBlogTitle|escape}</a></li>
      {/if}
    {/list}
    </ul>
    {/if}

<#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇，下一篇--> <#-- 热度 -->

{list a as x}
    {if !!x}
    <div class="hotItem iblock nbw-fce nbw-f40">
      <a class="fc03 noul" target="_blank" hidefocus="true" href="http://blog.163.com/${x.publisherUsername}/">
      {if x.publisherUsername==visitor.userName}
      <img alt="${x.publisherNickname|escape}" onerror="this.src=location.f40" class="cwd bdwa bdc0" src="${fn1(x.publisherUsername)}&r=${visitor.imageUpdateTime}"/>
      {else}
      <img alt="${x.publisherNickname|escape}" onerror="this.src=location.f40" class="cwd bdwa bdc0" src="${fn1(x.publisherUsername)}"/>
      {/if}
      </a>
      <div class="cwd vname thide">
        <a class="fc03 m2a"  target="_blank" hidefocus="true" href="http://blog.163.com/${x.publisherUsername}/">
          ${fn(x.publisherNickname,8)|escape}
        </a>
      </div>
      <a class="f-myLikeIcons hottype {if x.type==1} js-liketype{elseif x.type==2} js-reblogtype{elseif x.type==3} js-sharetype{else}{/if}" target="_blank" hidefocus="true" href="http://blog.163.com/${x.publisherUsername}/"> </a>
    </div>
    {/if}
    {/list}

<#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->

页脚

我的照片书 - 手机博客 - 下载LOFTER APP - 订阅此博客

ydc的博客

导航

日志

PQ树模板

历史上的今天

最近读者

热度

评论

页脚