CF1753B 题解

前言

题目传送门！

更好的阅读体验？

其实挺简单的，赛时多打了个等号，被人叉了。

思路

关键是 \(n! \times (n + 1) = (n + 1)!\)。

原因很显然：\((1 \times 2 \times \cdots \times n) \times (n + 1) = (n + 1)!\)。

知道这个，这道题不就做完了吗。统计每一个数码的个数，每次能进位就进位（指 \((n + 1)\) 个 \(n!\) 进出一个 \((n + 1)!\)）。

要求成立，当且仅当 \(1\) 至 \((x – 1)\) 都进没了，只有 \(x\) 的桶里有数。

具体看代码吧，非常容易理解。

代码

//赛时代码
#include <bits/stdc++.h>
using namespace std;
int cnt[500005];
int main()
{
	ios::sync_with_stdio(false);
	int n, x;
	cin >> n >> x;
	for (int i = 1; i <= n; i++)
	{
		int a;
		cin >> a;
		cnt[a]++; //统计
	}
	for (int i = 1; i < x; i++) cnt[i + 1] += (cnt[i] / (i + 1)), cnt[i] %= (i + 1); //"进位"
	for (int i = 1; i < x; i++)
		if (cnt[i])
		{
			cout << "No";
			return 0;
		}
	if (cnt[x]) cout << "Yes";
	else cout << "No";
	return 0;
}

希望能帮助到大家！

原文地址：http://www.cnblogs.com/liangbowen/p/16823055.html