250:PenguinSledding

题意:

给你点的大小范围,然后给你一些边,让你选出一些边的子集,不管子集中的点在坐标轴上怎么排列都不会有边交叉。。。

分析:

以为题目中给定的点和边都特别少,我们考虑如何选,那么有两种选法,一种是三条边正好围成三角形,另一种是菊花图,这样就保证最长的链长度小于等于2。。。

代码:

long long rode[60][60],edge[60],ans;
long long KSM(long long x,long long k)
{
	long long ret=1,flag=x;
	while(k)
	{
		if(k&1)ret*=flag;
		flag*=flag;
		k>>=1;
	}
	return ret;
}
long long PenguinSledding::countDesigns(int numCheckpoints, vector  checkpoint1, vector  checkpoint2) {
    memset(rode,0,sizeof(rode));
	memset(edge,0,sizeof(edge));
	ans=0;
	for(int i=0;i<checkpoint1.size();i++)
	{
		if(rode[checkpoint1[i]][checkpoint2[i]]==0)
		{
			rode[checkpoint1[i]][checkpoint2[i]]=rode[checkpoint2[i]][checkpoint1[i]]=1;
			edge[checkpoint1[i]]++;
			edge[checkpoint2[i]]++;
		}
	}
	for(int i=1;i<=numCheckpoints;i++)
		for(int j=i+1;j<=numCheckpoints;j++)
			for(int k=j+1;k<=numCheckpoints;k++)
				if(rode[i][j]&&rode[j][k]&&rode[k][i])
					ans++;
	for(int i=1;i<=numCheckpoints;i++)
		ans+=KSM(2,edge[i])-1;
	ans-=checkpoint1.size()-1;
	return ans;
}

500:PenguinEmperor

题意:

有一个环,你刚开始在0好点,环上一共有n个点,每天你可以顺时针或逆时针走,在第i天你可以走i步,给出n和天数k,(n<350&&k<1e18),问k天后你在0号点的方案数。。。

分析:

我们考虑在天数大于n后,每天走的步数相当于k%n步,然后这样子我们发现n天一个循环,然后每n天我们走路转移的状态是一样的,我们可以从第n天的状态,推出2n天的状态。。。然后这时我们就可以用快速幂来处理这个k了,复杂度是O(n^2*logk)。。。然后因为博主太菜了,打崩了好久。。。

代码:

 

vector merge(vector a,vector b)
{
	int len=a.size();
	vector c(len,0);
	for(int i=0;i<len;i++)
		for(int j=0;j<len;j++)
			(c[(i+j)%len]+=a[i]*b[j])%=mod;
	return c;
}
vector pow(vector a,LL k)
{
	if(k==0){a=vector(a.size(),0);a[0]=1;return a;}
	if(k%2==0)return pow(merge(a,a),k/2);
	else return merge(a,pow(a,k-1));
}
int PenguinEmperor::countJourneys(int numCities, long long daysPassed) {
    vector x(numCities,0);
	vector y(numCities,0);
	x[0]=y[0]=1;
	for(int i=1;i<numCities;i++)
	{
		vector move(numCities,0);
		move[i]=move[numCities-i]=1;
		x=merge(move,x);
		if(i<=daysPassed%numCities)
			y=merge(move,y);
	}
	vector ans=merge(y,pow(x,daysPassed/numCities));
	return ans[0];
}

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注