---

（牛客周赛 9）C.小美的01串翻转

原创 已于 2023-08-28 18:27:07 修改 · 粉丝可见 · 1.2k 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132544573

题目：

样例：

cobol<br/>10001<br/>

8

思路：

这里是连续的找子串，权值的意思是  我们取反操作了多少次，

我们有假设长度是 5 ，字符串是 10001

那么相邻不一样的字符串有两种情况   01010  或者  10101，那么它的权值分别是 4 和 1

又因为，我们是找到该字符串的所有子串之和是多少，所以在这里，我们应该知道子串是连续的，

并且我们是一步一步进行取反01 和 10 的情况，记录这样操作的次数，取最少操作数累加即可。

代码详解如此下：

#include <iostream>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;

inline void solve()
{
	string s;
	getline(cin, s);
	int ans = 0;
	int n = s.size();
	for (int i = 0; i < n; ++i)
	{
		int res[2] = {0, 0};

		//	 从这里 j == i 开始就是也计算上了子串
		for (int j = i; j < n; ++j)
		{
			// 如果符合 11 或者 00 说明需要操作 一次,
			// 或者 01 的时候我们记录的是强制变成 10 情况，
			// 或者又将 10 强制变成 01的情况
			if ((j % 2 == 0 && s[j] == '1') || (j % 2 == 1 && s[j] == '0'))
			{
				res[0]++;
			}
			else
				res[1]++;

			// 累加我们所有子串的权值
			ans += min(res[0], res[1]);
		}
	}

	cout << ans << endl;
}


int main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}

最后提交：