A-御坂美琴

https://ac.nowcoder.com/acm/contest/271/A
这道题发现我是倒着做的，就是把大的分解成小的，然后clf是正着做的，因为一个数分成两半，要不就相等，要不就相差1，于是就从小的两两组合，结果就WA了，比赛的时候我也感觉这样没什么问题呀，就是想不出什么错误样例，最后只能对拍了，找到一个：
input：
4 4
5 5 6 6
output：
misaka
这道题收获就收获在这里，我觉得应该会有不少人会正着做，然后被坑。。。

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
LL a[maxn];
priority_queue<LL,vector<LL>,less<LL> >que;
int main()
{
	LL N,M;
	while(cin>>N>>M)
	{
		while(!que.empty())que.pop();
		que.push(N);
		LL sum=0;
		for(int i=1;i<=M;i++)cin>>a[i],sum+=a[i];
		if(sum!=N)
		{
			puts("ham");
			continue;
		}
		sort(a+1,a+1+M);
		int t=M;
		int flag=0;
		while(1)
		{
			LL tp=que.top();
			que.pop();
			if(tp==a[t])
			{
				t--;
				if(t==0&&que.size()==0)
				{
					flag=1;
					break;
				}
				continue;
			}
			if(tp==1)break;
			LL t1=tp/2;
			LL t2=tp-t1;
			if(t1==a[t])
			{
				que.push(t2);
				t--;
			}
			else if(t2==a[t])
			{
				que.push(t1);
				t--;
			}
			else
			{
				que.push(t1);
				que.push(t2);
			}
			if(que.size()>M)break;
		}
		if(flag)puts("misaka");
		else puts("ham");
	}
}

B-白井黑子

https://ac.nowcoder.com/acm/contest/271/B
<mark>多组输入超时</mark>
因为各个位的来乘积，所以乘的数最大是9，因此所能出现的数中质因子就只有2 3 5 7这四个数
假如要看一个数能不能找到另一个数相乘然后表示成一个自然数的K次方，就先把这个数分解，假设这个数分解后为 $2^{A 1} 3^{B 1} 5^{C 1} 7^{D 1}$ ，然后要找的另一个数就是 $2^{A 2} 3^{B 2} 5^{C 2} 7^{D 2}$
如果：
$(A_{1} + A_{2}) % K = = 0$
$(B_{1} + B_{2}) % K = = 0$
$(C_{1} + C_{2}) % K = = 0$
$(D_{1} + D_{2}) % K = = 0$

这个是不是就有点想那个很经典的题：n个数里面找两个数相加等于m，解法就是枚举每一个数，然后看这个数的补集是不是在这n个数里面

而我们这道题差不多也就是这个意思，只不过补集同时是4个数的补集，求和也不是等于m，而是取模等于0

而这道题还有点特殊的地方需要特判
就是当K=0的时候，任何数的0次方都是等于1的，而两个数相乘，除了两个数都是1的情况，就不可能乘出1来，所以把减去都是1的这种情况的对数就行了

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
vector<LL>a[maxn];
LL f1(LL n)//求位数乘积
{
	if(n==0LL)return 0LL;//注意是0的话直接返回0
	LL res=1;
	while(n)
	{
		if(n%10LL==0)return 0LL;
		res*=n%10;
		n/=10;
	}
	return res;
}
LL f2(LL n,LL t)
{
	if(n==0LL)return 0LL;
	LL res=0;
	while(n%t==0)
	{
		n/=t;
		res++;
	}
	return res;
}
map<vector<LL>,LL>Mp;
LL data[maxn];
int main()
{
	LL N,K;
	cin>>N>>K;//多组输入超时

	Mp.clear();
	LL ans=0;
	LL zero=0,one=0;
	for(int i=1; i<=N; i++)
	{
		cin>>data[i];
		data[i]=f1(data[i]);
		if(data[i]==0LL)zero++;
		else if(data[i]==1LL)one++;
	}
	if(K==0LL)
	{
		cout<<N*(N-1)/2-one*(one-1)/2<<endl;//减去1成对的对数
		return 0;
	}
	for(int i=1; i<=N; i++)
	{
		LL t=data[i];
		if(t==0)continue;
		a[i].resize(4);
		if(t==1LL)a[i][0]=a[i][1]=a[i][2]=a[i][3]=0;
		else
		{
			a[i][0]=f2(t,2)%K;
			a[i][1]=f2(t,3)%K;
			a[i][2]=f2(t,5)%K;
			a[i][3]=f2(t,7)%K;
		}
		LL res=0;
		vector<LL>tp;//找a[i]的补集
		tp.resize(4);
		for(int j=0;j<4;j++)tp[j]=(K-a[i][j])%K;
		ans+=Mp[tp];//加上补集的个数 
		Mp[a[i]]++;
	}
	LL n=zero;
	ans+=n*(N-n)+n*(n-1)/2;
	cout<<N*(N-1)/2-ans<<endl;
}

2018牛客Wannafly29

文章目录

A-御坂美琴

B-白井黑子