AtCoder Beginner Contest 194

A I Scream

int main()

{

	IOS;

	int a, b;

	cin >> a >> b;

	if(a + b >= 15 && b >= 8) puts("1");

	else if(a + b >= 10 && b >= 3) puts("2");

	else if(a + b >= 3) puts("3");

	else puts("4");

	return 0;

}

B

int n;

int a[N], b[N];

int main()

{

	scanf("%d", &n);

	int res = INF;

	for(int i = 1; i <= n; ++ i)

	{

		scanf("%d%d", &a[i], &b[i]);

		res = min(res, a[i] + b[i]);

	}

	for(int i = 1; i <= n; ++ i)

		for(int j = 1; j <= n; ++ j)

			if(i != j) res = min(max(a[i], b[j]), res);

	printf("%d\n", res);

	return 0;

}

C Squared Error

\(\sum\limits_{i=2}^N\sum\limits_{j=1}^{i-1}(A_i-A_j)^2\) = \(\sum\limits_{i=1}^NA_i^2 * (N - 1) - \sum\limits_{i=2}^NA_i\sum\limits_{j=1}^{i - 1}2 * A_j\)

用前缀和优化后复杂度 \(O(n)\)

int n;

int a[N], sum[N];

int main()

{

	scanf("%d", &n);

	LL res = 0;

	for(int i = 1; i <= n; ++ i)

	{

		scanf("%d", &a[i]);

		res += (LL)a[i] * a[i] * (n - 1);

		res -= (LL)sum[i - 1] * a[i] * 2;

		sum[i] = sum[i - 1] + a[i];

	}

	printf("%lld\n", res);

	return 0;

}

D Journey

令当前已经访问过的顶点集合为 \(S\)，下一次能使得 \(|S|\) 增加 \(1\) 的概率为 \(\dfrac{N - |S|}{N}\), 首中即停止，符合几何分布，已知几何分布的期望是 \(\dfrac{1}{p}\)，故期望是 \(\sum\limits_{i = 1}^{n - 1}\dfrac{N}{N - i}\)

int n;

int main()

{

	cin >> n;

	double res = 0;

	for(int i = 1; i < n; ++ i) res += (double)n / i;

	printf("%.10lf\n", res);

	return 0;

}

E Mex Min Editorial

对于相同的两个数 \(x\)，如果它们之间的距离大于 \(M\)，则代表有一段长度为 \(M\) 的区间中没有 \(x\), \(x\)则可以作为答案

为了处理边界情况，在 \(0\) 和 \(n + 1\) 的位置上放置每一个数

int n, m;

int last[N];

int main()

{

	scanf("%d%d", &n, &m);

	int res = INF;

	for(int i = 1; i <= n; ++ i)

	{

		int x;

		scanf("%d", &x);

		if(i - last[x] > m) res = min(x, res);

		last[x] = i;

	}

	for(int i = 0; i <= n; ++ i)

		if(n + 1 - last[i] > m)

			res = min(i, res);

	printf("%d\n", res);

	return 0;

}

F Digits Paradise in Hexadecimal

令 \(f[i][j]\) 为前 \(i\) 位选了 \(j\) 种的方案数，且选出的方案都严格小于上界

当上一位未达到上界时：

\(f[i + 1][j] += f[i][j] * j\)

\(f[i + 1][j + 1] += f[i][j] * (16 - j)\)

因为要处理前导零，所以从 \(0\) 转移要特殊处理：

\(f[i + 1][1] += f[i][0] * 15\)

\(f[i + 1][0] += f[i][0]\)

再统计上一位达到上界时，当前位取 \(0\) ~ \(v[i] - 1\) 的贡献

最后特判掉所有位都取到上界是否符合题意

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)

const int P = 1e9 + 7;

const double PI = acos(-1.0);

const int INF = 0x3f3f3f3f;

const int N = 3e6 + 10;

int main()

{

	IOS;

	int n;

	string str;

	vector<int> v;

	cin >> str >> n;

	for(auto x : str)

		if(x >= '0' && x <= '9') v.push_back((int)(x - '0'));

		else v.push_back((int)(10 + x - 'A'));

	vector<vector<int> > f(str.size() + 1, vector<int>(18, 0));

	int state = 0;

	for(int i = 0; i < (int)str.size(); ++ i)

	{

		for(int j = 1; j <= 16; ++ j)

		{

			f[i + 1][j] = (f[i + 1][j] + (LL)f[i][j] * j % P) % P;

			f[i + 1][j + 1] = (f[i + 1][j + 1] + (LL)f[i][j] * (16 - j) % P) % P;

		}

		f[i + 1][1] = (f[i + 1][1] + (LL)f[i][0] * 15 % P) % P;

		f[i + 1][0] = (f[i + 1][0] + f[i][0]) % P;

		for(int j = 0; j < v[i]; ++ j)

		{

			int nstate = state;

			if(i || j) nstate |= (1 << j);

			f[i + 1][__builtin_popcount(nstate)] += 1;

		}

		state |= (1 << v[i]);

	}

	int res = f[str.size()][n] + (__builtin_popcount(state) == n);

	cout << res << endl;

	return 0;

}

巴特西

AtCoder Beginner Contest 194

A I Scream

B

C Squared Error

D Journey

E Mex Min Editorial

F Digits Paradise in Hexadecimal

最新文章

热门文章