AtCoder Beginner Contest 215

2021/8/26 23:08:10

编程Tag： int max DP mid col ge 215 Atcoder Beginner

本文主要是介绍AtCoder Beginner Contest 215，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

E - Chain Contestant

给定一个由 \(A - J\) 组成的串，求从中选出子序列满足相同的字符必须相临的方案数。

如果直接 \(dp\) , 无法得知前面是否已经出现过某种颜色。发现字符种类仅有 \(10\) 种，于是可以状态压缩记录某种颜色是否出现过。
令 \(dp[i][j][k]\) 为从前 \(i\) 个字符中选择，颜色状态为 \(j\)，最后选择的颜色为 \(k\) 的合法方案数。
初始状态为 \(dp[i][1 << col_i][col_i] = 1\)
\(dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - (1 << k)][t]\;\;(选)\)
\(dp[i][j][k] = dp[i - 1][j][k]\;\;(不选)\)
答案即为 \(\sum\limits_{i = 0}^{1023}\sum\limits_{j = 0}^9dp[n][i][j]\)。复杂度 \(O(2^{10} * n * 10)\)

Sample Code (C++)

int n;
char str[N];
LL dp[N][1 << M][M];

int main()
{
	cin >> n >> (str + 1);
	for(int i = 1; i <= n; ++ i)
	{
		int col = str[i] - 'A';
		dp[i][1 << col][col] = 1;
		for(int j = 0; j < (1 << 10); ++ j)
		{
			for(int k = 0; k < 10; ++ k)
				if(j >> k & 1) 
				{
					dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % P;	
					if(col == k) dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % P;
				}
			if(j >> col & 1)
				for(int t = 0; t < 10; ++ t)	
					if((j - (1 << col)) >> t & 1)
						dp[i][j][col] = (dp[i][j][col] + dp[i - 1][j - (1 << col)][t]) % P;
		}
	}
	LL res = 0;
	for(int i = 0; i < (1 << 10); ++ i)
		for(int j = 0; j < 10; ++ j)
			res = (res + dp[n][i][j]) % P;
	cout << res << endl;
	return 0;
}

F - Dist Max 2

给一组点，定义两点之间的距离为 \(min(|x_i - x_j|, |y_i - y_j|)\), 求两个不同点的最大距离。

最小值最大化问题，考虑二分答案。
若一个答案 \(k\) 合法，则必须满足存在两个点使得 \(|x_i - x_j| \ge k\), 并且 \(|y_i - y_j| \ge k\), 于是可以考虑一个类似于滑动窗口的做法，将点按照 \(x\) 排序，对于当前点 \(P\) 来说，若队列中的点 \(Q\) 与 \(P\) 的 \(x\) 坐标差 \(\ge k\) , 则 \(Q\) 可以加入答案集合，维护答案集合的最大值和最小值，判断当前点是否可以从答案集合中找出一个合法点，即 \(y_{max} - y_p \ge k\) 或 \(y_p - y_{min} \ge k\) 。
复杂度 \(O(nlogn + nlogx_{max})\)

Sample Code (C++)

vector<PII> v;

bool check(int mid)
{
	queue<PII> q; int Max = 0, Min = INF;
	for(auto p : v)
	{
		while(!q.empty() && p.fi - q.front().fi >= mid) 
		{
			Max = max(Max, q.front().se);
			Min = min(Min, q.front().se);
			q.pop();
		}
		if(Max - p.se >= mid || p.se - Min >= mid) return 1;
		q.push(p);
	}
	return 0;
}

int main()
{
	IOS; int n; cin >> n;
	for(int i = 0; i < n; ++ i) { int x, y; cin >> x >> y; v.push_back({x, y}); }
	sort(v.begin(), v.end());
	int l = 0, r = 1e9, res;
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(check(mid)) { res = mid; l = mid + 1; }
		else r = mid - 1;
	}	
	cout << res << endl;
	return 0;
}

这篇关于AtCoder Beginner Contest 215的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

AtCoder Beginner Contest 215

E - Chain Contestant

F - Dist Max 2

相关编程文章