Codeforces Round #589 (Div. 2)

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
bool jzk(int k)
{
	bool vis[10];
	memset(vis, 0, sizeof(vis));
	while (k)
	{
		if (vis[k % 10] == true)
			return false;
		vis[k % 10] = true;
		k /= 10;
	}
	return true;
}
int main()
{
	int a, b;
	sc("%d%d", &a, &b);
	for (int i = a; i <= b; i++)
	{
		if (jzk(i))
		{
			pr("%d", i);
			return 0;
		}
	}
	pr("-1");
}

B - Filling the Grid

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int a[1005][1005];
//bai -1 hei 1
int hang[1005], lie[1005];
const ll mod = 1e9 + 7;
ll power(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
int main()
{
	int n, m;
	sc("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		sc("%d", &hang[i]);
		
		for (int j = 1; j <= hang[i]; j++)
			a[i][j] = 1;
		a[i][hang[i] + 1] = -1;
	}
	for (int i = 1; i <= m; i++)
	{
		sc("%d", &lie[i]);
		
		for (int j = 1; j <= lie[i]; j++)
		{
			if (a[j][i] == -1)
			{
				pr("0\n");
				return 0;
			}
			a[j][i] = 1;
		}
		if (a[lie[i] + 1][i] == 1)
		{
			pr("0\n");
			return 0;
		}
		a[lie[i] + 1][i] = -1;
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (a[i][j] == 0)
				cnt++;
		}
	}
	ll ans = power(2, cnt);
	pr("%lld\n", ans);
}

C - Primes and Multiplication

由题意可知，题目就是要求对于每个 x 分解并去重后的质因数（假设其中一个质因数是 p ），需要求出 [1,n] ，这 n 个数字质因数分解后，假设有 cnt 个 p ，最后结果就是 p^cnt

所以我们只要能求出 [1,n] 的每个数字的质因数包括多少个给定的质数 p ，考虑枚举出现多少个 p ，那么出现至少一次 p 的个数是 n/p ，出现至少二次 p 的个数是 n/(p*p)，直到 p^k>n，循环结束。

乘法要转成出发，防止溢出。

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const ll mod = 1e9 + 7;
vector<int>v;
ll power(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return res;
}
void get(ll k)
{
	for (ll i = 2; i * i <= k; i++)
	{
		if (k % i == 0)
		{
			v.push_back(i);
			while (k % i == 0)
				k /= i;
		}
	}
	if (k > 1)
		v.push_back(k);
}
int main()
{
	ll x, n;
	sc("%lld%lld", &x, &n);
	get(x);
	ll ans = 1;
	int len = v.size();
	for (int i = 0; i < len; i++)
	{
		ll cnt = 0;
		for (int j = 1; j <= 70; j++)
		{
			ll temp = v[i];
			for (int k = 1; k < j; k++)
			{
				if (temp > (double)n / (double)v[i])
					goto qwe;
				temp *= v[i];
			}
			cnt += n / temp;
		}
		qwe:;
		ans = ans * power(v[i], cnt) % mod;
	}
	pr("%lld\n", ans);
}

D - Complete Tripartite

1、首先我们假设点 1 是第一个独立集的，那么所有跟 1 没有连边的点一定要是第一个独立集的（反证法，如果不是第一个独立集的话，他们之间一定要有边）

2、枚举所有点，如果它没有颜色，就给一个新的颜色，这样可以求出能构成的独立集的个数。

3、判断边是否合法，不能暴力枚举三个独立集，可能超时。

4、考虑先判断 m 条边是否足够，然后遍历每条边，由于没有重边和自环，所以如果每条边都合法的话，最后一定是合法的。

Codeforces Round #589 (Div. 2)

全站热榜