2
1
2016
0

【郑州培训】上机测试Day3

A：把一个串分成不超过k个部分，每个部分分别取字典序最大的串，在取所取出的串中字典序最大的，求可以取到的最小串。 

后缀数组+二分答案 

理解一种数据结构的原理≠可用这种数据结构解题 

而后缀数组，只要理解三个数组的含义就可以了： 

一个串的所有后缀按照字典序由小到大排序后 

sa[i]:第i小的后缀在原串的位置 

rank[i]:原串中第i位的后缀的序号 

sa[]<->rank[] 

height[i]:第i小的后缀与第i-1小的后缀的前缀公共长度 

后缀数组的几个应用： 

求两个串的LCS（最长公共子串） 

poj1743 在一个串中找不重叠最长相同子串 

先二分答案，把题目变成判定性问题：判断是否存在两个长度为k的子串是相同的，且不重叠。 

解决这个问题的关键还是利用 height数组。把排序后的后缀分成若干组，其中每组的后缀之间的height值都不小于k。 

如果一组内sa的最大值与最小值的差>=k，则k成立，继续试图扩大k，直到确定答案 

运行错误??!! 

 

std code from %%%ydc:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define each(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)
#define maxn 100010
using namespace std;
typedef long long LL;
char str[maxn];
int rank[maxn],Sa[maxn],height[maxn];
int n,m;
void sort(int *a,int *b,int *c,int n,int m)
{
	static int sum[maxn];
	for(int i=0;i<=m;++i)
		sum[i]=0;
	for(int i=1;i<=n;++i)
		++sum[c[i]];
	for(int i=1;i<=m;++i)
		sum[i]+=sum[i-1];
	for(int i=n;i>=1;--i)
		b[sum[c[a[i]]]--]=a[i];
}
void make_Sa()
{
	static int x[maxn],y[maxn];
	for(int i=1;i<=n;++i)
		rank[i]=i,x[i]=str[i];
	sort(rank,Sa,x,n,256);
	rank[Sa[1]]=1;
	for(int i=2;i<=n;++i)
		rank[Sa[i]]=rank[Sa[i-1]]+(x[Sa[i]]!=x[Sa[i-1]]);
	for(int i=1;i<=n;i<<=1)
	{
		for(int j=1;j<=n;++j)
			Sa[j]=j,x[j]=rank[j],y[j]=j+i<=n?rank[j+i]:0;
		sort(Sa,rank,y,n,n),sort(rank,Sa,x,n,n);
		rank[Sa[1]]=1;
		for(int j=2;j<=n;++j)
			rank[Sa[j]]=rank[Sa[j-1]]+(x[Sa[j]]!=x[Sa[j-1]]||y[Sa[j]]!=y[Sa[j-1]]);
		if(rank[Sa[n]]==n)
			return ;
	}
}
void debug()
{
	for(int i=1;i<=n;++i)
		printf("%s %d\n",str+Sa[i],height[i]);
}
void make_height()
{
	for(int i=1,j=0;i<=n;++i)
	{
		if(j>0)
			--j;
		if(rank[i]!=1)
			while(str[i+j]==str[Sa[rank[i]-1]+j])
				++j;
		height[rank[i]]=j;
	}
}
pair<int,int> calc(LL rk)
{
	for(int i=1;i<=n;++i)
	{
		LL sum=n-Sa[i]+1-height[i];
		if(rk<=sum)
			return make_pair(i,rk);
		rk-=sum;
	}
	return make_pair(-1,-1);
}
bool check(LL rk)
{
	pair<int,int> tmp=calc(rk);
	int x=tmp.first,len=tmp.second+height[x];
	if(x==-1)
		return true;
	static int dp[maxn],L[maxn];
	memset(L,0,sizeof(L));
	L[Sa[x]+len]=Sa[x];
	int minv=len;
	for(int i=x+1;i<=n;++i)
	{
		minv=min(minv,height[i]);
		L[Sa[i]+minv]=max(L[Sa[i]+minv],Sa[i]);
		if(minv==0)
			return false;
	}
	int l=0;
	for(int i=1;i<=n;++i)
	{
		l=max(l,L[i]);
		dp[i]=dp[l]+1;
	}
	return dp[n]<=m;
}
void binary(LL l,LL r)
{
	while(l<r)
	{
		LL mid=(l+r)>>1;
		check(mid)==false?l=mid+1:r=mid;
	}
	pair<int,int> a=calc(l);
	for(int i=1;i<=a.second+height[a.first];++i)
		printf("%c",str[Sa[a.first]+i-1]);
	printf("\n");
}
int main()
{
	freopen("str.in","r",stdin);
	freopen("str.out","w",stdout);
	scanf("%d %s",&m,str+1);
	n=strlen(str+1);
	make_Sa();
	make_height();
	binary(1,(LL)n*n);
	return 0;
}

 

 

B：一个长、宽、高分别为X、Y、Z的几何体，要求遍历每个边一次，可以重复遍历，求最少经过的边数。 

 

第一次做构造题，很有意思。所谓构造题大概就是比较偏数学的题吧... 

温习一下欧拉路的概念： 

如果给定无孤立结点图G，若存在一条路，经过图中每边一次且仅一次，这条路称为欧拉路；

如果给定无孤立结点图G，若存在一条回路，经过图中每边一次且仅一次，那么该回路称为欧拉回路。

存在欧拉回路的图，称为欧拉图。 

对于无向图G，具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度结点。

有零个奇数度结点，存在欧拉回路；有两个奇数度结点，存在欧拉路。 

 

问题转化为添加最少的边让图变得可一笔画，即要构造方案减少奇点个数。 

分类讨论，脑子一晃..似乎晃不粗来哈： 

设Z>X,Z>Y 

1. 一条线 

2. 一个平面 

3. 高度为2—一条边分别连接上、下两面的点 边数=奇点数/2+1 

4. 高度为3——连接上下面的点、同一面里外的点均需长度为2的线段，但前者可能比后者优 

5. 高度大于3——2条边连接同一面里外两点 

其中4、5分类：（边缘点数为奇数的面为奇面） 

6个奇面、6个偶面、4奇2偶 

推导关系式、汇总。

 

Also std code from %%%ydc:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
LL work(LL a,LL b,LL c)
{
	LL ans=a*b*(c-1)+a*c*(b-1)+b*c*(a-1);
	if(a==1)
	{
		if(b==1||(b==2&&c==2))
			return ans;
		else if(b%2==0||c%2==0)
			return ans+b+c-5;
		else
			return ans+b+c-4;
	}
	else if(a==2)
		return ans+(b-2)*(c-2)+3;
	else if(a==3)
	{
		if(b%2==0&&c%2==0)
			return ans+b+c+(b-2)*(c-2)+2;
		else if(b%2!=0&&c%2!=0)
			return ans+(a-2)*(b-2)+(a-2)*(c-2)+(b-2)*(c-2)+9;
		else
			return ans+(a-2)*(b-2)+(a-2)*(c-2)+(b-2)*(c-2)+7;
	}
	else
		return ans+(a-2)*(b-2)+(a-2)*(c-2)+(b-2)*(c-2)+9;
}
int main()
{
    freopen("cube.in","r",stdin);
    freopen("cube.out","w",stdout);
	LL a,b,c;
	int T=0;
	while(cin>>a>>b>>c)
		cout<<"Case #"<<(++T)<<": "<<work(min(min(a,b),c),a+b+c-min(min(a,b),c)-max(max(a,b),c),max(max(a,b),c))<<endl;
	return 0;
}

 

 

C：直接发题目！： 

Splay的熟练运用 

突破口：如果取一个长度大于2K 的，从中间劈开，两边取较大值一定不会更劣。  

std code from %%%ydc once again..:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 100010
using namespace std;
typedef long long LL;
void Read(int &digit)
{
	digit=0;
	char c;
	for(c=getchar();c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
struct Fraction
{
	LL fenzi,fenmu;
	Fraction() {}
	Fraction(LL fenzi,LL fenmu): fenzi(fenzi),fenmu(fenmu) {}
	friend bool operator < (const Fraction &a,const Fraction &b)
	{
		return a.fenzi*b.fenmu>a.fenmu*b.fenzi||(a.fenzi*b.fenmu==a.fenmu*b.fenzi&&a.fenmu<b.fenmu);
	}
	friend bool operator == (const Fraction &a,const Fraction &b)
	{
		return a.fenzi*b.fenmu==a.fenmu*b.fenzi&&a.fenmu==b.fenmu;
	}
	//���ڴ������䳤�Ȳ�����20�����Բ��ᱬlong long  
};
int n,m,nQuery;
void update(Fraction &a,Fraction b,int &c,int d)
{
	if(b<a||(b==a&&c>d))
		a=b,c=d;
}
struct msgnode
{
	LL presum[25],sufsum[25];
	int len;
	Fraction ans;
	int from;
	friend msgnode operator + (const msgnode &a,const msgnode &b)
	{
		static msgnode c;
		c.len=a.len+b.len;
		c.ans=a.ans,c.from=a.from;
		update(c.ans,b.ans,c.from,b.from+a.len);
		for(int i=1;i<=a.len&&i<=2*m;++i)
			c.presum[i]=a.presum[i];
		for(int i=a.len+1;i<=a.len+b.len&&i<=2*m;++i)
			c.presum[i]=c.presum[a.len]+b.presum[i-a.len];
		for(int i=1;i<=b.len&&i<=2*m;++i)
			c.sufsum[i]=b.sufsum[i];
		for(int i=b.len+1;i<=a.len+b.len&&i<=2*m;++i)
			c.sufsum[i]=c.sufsum[b.len]+a.sufsum[i-b.len];
		for(int i=m;i<=2*m;++i)
			for(int j=max(1,i-b.len);j<i&&j<=a.len;++j)
				update(c.ans,Fraction(a.sufsum[j]+b.presum[i-j],i),c.from,a.len-j+1);
		return c;
	}
};
msgnode single(int val)
{
	static msgnode a;
	a.ans=Fraction(0,1);
	a.presum[1]=a.sufsum[1]=val;
	a.len=1;
	if(m==1)
		a.ans=Fraction(val,1),a.from=1;
	return a;
}
struct Node
{
	Node *fa,*son[2];
	int val;
	msgnode ans;
	void update()
	{
		ans=single(val);
		if(son[0])
			ans=son[0]->ans+ans;
		if(son[1])
			ans=ans+son[1]->ans;
	}
}pool[maxn],*Root;
int w[maxn];
void read()
{
	Read(n),Read(nQuery),Read(m);
	for(int i=1;i<=n;++i)
		Read(w[i]);
}
Node* Build(int l,int r)
{
	int mid=(l+r)>>1;
	Node *p=pool+mid,*q;
	p->val=w[mid];
	if(l<mid)
		q=Build(l,mid-1),p->son[0]=q,q->fa=p;
	if(mid<r)
		q=Build(mid+1,r),p->son[1]=q,q->fa=p;
	p->update();
	return p;
}
void Rotate(Node *p,Node *x)
{
	bool mark=p==x->son[1];
	Node *y=p->son[mark^1],*z=x->fa;
	if(y!=0)
		y->fa=x;
	if(z!=0)
		z->son[x==z->son[1]]=p;
	p->son[mark^1]=x,p->fa=z,x->son[mark]=y,x->fa=p,x->update();
}
void Splay(Node *p,Node *goal)
{
	while(p->fa!=goal)
	{
		Node *x=p->fa,*y=x->fa;
		if(y==goal)
			Rotate(p,x);
		else if((p==x->son[0])^(x==y->son[0]))
			Rotate(p,x),Rotate(p,y);
		else
			Rotate(x,y),Rotate(p,x);
	}
	if(goal==0)
		Root=p;
	p->update();
}
Node* Select(int rank,Node *goal)
{
	Node *p=Root;
	int s=p->son[0]?p->son[0]->ans.len+1:1;
	while(s!=rank)
	{
		if(s<rank)
			rank-=s,p=p->son[1];
		else
			p=p->son[0];
		s=p->son[0]?p->son[0]->ans.len+1:1;
	}
	Splay(p,goal);
	return p;
}
void remove(int l,int r)
{
	Node *p=Select(l,0),*q=Select(r+2,p);
	q->son[0]=0,Splay(q,0);
}
void work(int l,int r)
{
	Node *p=Select(l,0),*q=Select(r+2,p),*x=q->son[0];
	int st=p->ans.len-q->ans.len-1+x->ans.from,len=x->ans.ans.fenmu;
	printf("%d %d\n",st,st+len-1);
	remove(st,st+len-1);
}
void Query()
{
	Root=Build(0,n+1);
	int l,r;
	while(nQuery--)
	{
		Read(l),Read(r);
		work(l,r);
	}
}
int main()
{
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
	read();
	Query();
	fclose(stdin);
	fclose(stdout);
	return 0;
}

 

Category: 未分类 | Tags: 后缀数组 构造题 图论 平衡树 | Read Count: 406
Small_feed 评论 (0)

登录 *


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