Educational Codeforces Round 137 (Rated for Div. 2)

期望 + 暴力

[Problem - D - Codeforces](https://codeforces.com/contest/1743/problem/E)

题意

给出一个长度为 \(n\;(1<=n<=10^6)\) 的字符串 \(s\)，选取两个 \(s\) 的子串 \(a,b\), 使得 \(a\;or\;b\) 的值最大

保证 \(s\) 中每个位置出现 0 或 1 都是等概率的

思路

把 \(s\) 的前导 0 去掉，这些位置无法变成 1
\(a=s\) 一定是最优的，\(b\) 的选取是尽量把 \(a\) 的前面的 0 给补上
设 idx 为 \(a\) 中第一个 \(0\) 的位置，\(b\) 的开头一定是在 idx 之前，这样才能补上 idx 这个位置上的 0
从 0 到 idx - 1 暴力枚举 b 的开头即可，因为每个位置出现 0/1 是等概率的，所以 idx 不会很大

代码

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

typedef long long ll;

typedef pair<int, int> PII;

string s;

int n, t, cnt;

const int N = 110;

int pos[N], d[N];

vector<int> vt;

int main()

{

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> s;

	int idx = n;

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

	{

		if (s[i] == '1')

		{

			idx = i;

			break;

		}

	}

	if (idx == n)

	{

		cout << 0 << endl;

		return 0;

	}

	s = s.substr(idx);

	n = s.size();

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

	{

		if (s[i] == '0')

		{

			idx = i;

			break;

		}

	}

	string ans = s;

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

	{

		string now = s;

		for (int j = 0; idx + j < n; j++)

		{

			if (s[i + j] == '1')

				now[idx + j] = '1';

		}

		ans = max(ans, now);

	}

	cout << ans << endl;

    return 0;

}

巴特西

Educational Codeforces Round 137 (Rated for Div. 2) - D. Problem with Random Tests

期望 + 暴力

题意

思路

代码

最新文章

热门文章