250:TheSquareRootDilemma

题意:

给你两个数,N,M,然后有一个整数a属于1到N,b属于1到M,问有几个a有序数对(a,b)满足(sqrt(a)+sqrt(b))^2是整数。。。

分析:

我们已经知道(sqrt(a)+sqrt(b))^2拆开就是a+b+2*sqrt(ab),那么只要满足ab是完全平方数就好了,我们考虑a,b都是一些质数次方的乘积,我们吧a,b中本来就有的完全平方数去掉,会发现,此时a=b,那么我们有一种方法就是枚举min(N,M)中没有完全平方数因子的数p,然后ans+=(int)sqrt(N/p)*(int)sqrt(M/p),然后输出ans就好了。。

代码:

int vis[N],ans;
int TheSquareRootDilemma::countPairs(int N, int M)
{
	ans=0;
	memset(vis,0,sizeof(vis));
	int minn=min(N,M);
	for(int i=1;i<=minn;i++)
		if(vis[i]==0)
		{
			ans+=(int)sqrt(N/i)*(int)sqrt(M/i);
			if(i!=1&&(LL)i*i<=minn)
				for(LL j=i*i;j<=minn;j+=i*i)
					vis[j]=1;
		}
	return ans;
}

500:StringGame

题意:

A,B两个人玩游戏,首先A从给出的字符串中选择一个,然后随意排序,并且给出一个字典序,接着B随意对剩下的串中的每一个串进行排序,如果B不能排出一个序列,他的字典序比A选择的小,那么A赢。。。输出A能赢的字符串。。。

分析:

我们思考我们选择一个串以后如何排列字典序最优,当我们有一个字符的数量多余其他所有,那么此时把它放在字典序前面,可以淘汰很多串,然后当我们不管怎么选择字典序时都有串小于当前串,那么直接淘汰当前串,走下一步就好了,复杂度是O(能过)。。。

代码:

int ch[55][55];
int check(int now,int num)
{
	int vis[50];memset(vis,0,sizeof(vis));vis[now]=1;
	int flag=num-1,fuck[50];
	memset(fuck,0,sizeof(fuck));
	while(flag)
	{
		int mdzz=0;
		for(int j=1;j<=26;j++)
			if(fuck[j]==0)
			{
				int sb=0;
				for(int i=0;i<num;i++)
				{
					if(i==now)continue;
					if(ch[i][j]<=ch[now][j]&&vis[i]==0)
						sb++;
				}
				if(sb==flag)
				{
					fuck[j]=1;
					mdzz=j;
					break;
				}
			}
		if(mdzz==0)
			return 0;
		for(int i=0;i<num;i++)
			if(ch[i][mdzz]<ch[now][mdzz]&&!vis[i])
				vis[i]=1,flag--;
	}
	return 1;
}
vector  StringGame::getWinningStrings(vector  S) {
    vector ans;ans.clear();
	memset(ch,0,sizeof(ch));
	int num=S.size(),len=S[0].size();
	for(int i=0;i<num;i++)
		for(int j=0;j<len;j++)
			ch[i][S[i][j]-'a'+1]++;
	for(int i=0;i<num;i++)
		if(check(i,num))
			ans.push_back(i);
	return ans;
}

 

Leave A Comment

发表评论

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