topcoder SRM 567 Div1 250+500

##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+2sqrt(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 <int> StringGame::getWinningStrings(vector <string> S) {
    vector<int> 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;
}