codeforce E – Binary Inversions题解()

题目:

给你一个01串,现在你可以(或者不用)选取其中一个元素进行一次反转操作0-1,1-0;从而使得串中的逆序对个数最多。
题目链接:codeforce origin problem

思路:

1. 如何统计逆序对的个数?

  • 从后向前扫描,定义zero,记录0的个数,如果遇到1,则逆序对增加的个数就等于的此时zero。
vector<int>a;
ll f(decltype(a)& d)
{
	ll zero = 0, sum = 0;
	rfor(i, d.size() - 1, 0)
	{
		//cout << d[i] << " ";
		if ( d[i] == 0 )
			zero++;
		else sum += zero;
	}
	return sum;
}

2.如何进行一次反转使得逆序对个数最多?

  • 我们考虑0-1反转,让逆序对数量更多,则应该让下标最小的0filp为1,这样子,逆序对个数最多。
  • 我们考虑1-0反转,让逆序对数量更多,则应该让下标最小的1filp为0,这样子,逆序对个数最多。

AC代码

//注意事项:记得开longlong,避免溢出
// 其次,不用经过反转01,可能已经是最大的了,需要先做记录

vector<int>a;
ll f(decltype(a)& d)
{
	ll zero = 0, sum = 0;
	rfor(i, d.size() - 1, 0)
	{
		//cout << d[i] << " ";
		if ( d[i] == 0 )
			zero++;
		else sum += zero;
	}
	return sum;
}
void solve()
{
	ll n;
	cin >> n;
	a.resize(n);
	ifor(i, 0, n - 1)
	{
		cin >> a[i];
	}
    ll  res;
	res = f(a);
	ifor(i, 0, n - 1)
	{
		if ( a[i] == 0 )
		{
			a[i] = 1;
			ll s1 = f(a);
			res = max(s1, res);
			a[i] = 0;
			break;
		} 
	}
	rfor(i, n-1, 0)
	{
		if ( a[i] == 1 )
		{
			a[i] = 0;
			ll s1 = f(a);
			res = max(s1, res);
			a[i] = 1;
			break;
		}
	}
	cout << res<<endl;
	a.clear();
}
int main(int args, char** argv)
{
	/*ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin.tie(nullptr);*/
	long t;
	cin >> t;
	while ( t-- )
	{
		solve();
	}
	return 0;
}
————————

题目:

给你一个01串,现在你可以(或者不用)选取其中一个元素进行一次反转操作0-1,1-0;从而使得串中的逆序对个数最多。
题目链接:codeforce origin problem

思路:

1. 如何统计逆序对的个数?

  • 从后向前扫描,定义zero,记录0的个数,如果遇到1,则逆序对增加的个数就等于的此时zero。
vector<int>a;
ll f(decltype(a)& d)
{
	ll zero = 0, sum = 0;
	rfor(i, d.size() - 1, 0)
	{
		//cout << d[i] << " ";
		if ( d[i] == 0 )
			zero++;
		else sum += zero;
	}
	return sum;
}

2.如何进行一次反转使得逆序对个数最多?

  • 我们考虑0-1反转,让逆序对数量更多,则应该让下标最小的0filp为1,这样子,逆序对个数最多。
  • 我们考虑1-0反转,让逆序对数量更多,则应该让下标最小的1filp为0,这样子,逆序对个数最多。

AC代码

//注意事项:记得开longlong,避免溢出
// 其次,不用经过反转01,可能已经是最大的了,需要先做记录

vector<int>a;
ll f(decltype(a)& d)
{
	ll zero = 0, sum = 0;
	rfor(i, d.size() - 1, 0)
	{
		//cout << d[i] << " ";
		if ( d[i] == 0 )
			zero++;
		else sum += zero;
	}
	return sum;
}
void solve()
{
	ll n;
	cin >> n;
	a.resize(n);
	ifor(i, 0, n - 1)
	{
		cin >> a[i];
	}
    ll  res;
	res = f(a);
	ifor(i, 0, n - 1)
	{
		if ( a[i] == 0 )
		{
			a[i] = 1;
			ll s1 = f(a);
			res = max(s1, res);
			a[i] = 0;
			break;
		} 
	}
	rfor(i, n-1, 0)
	{
		if ( a[i] == 1 )
		{
			a[i] = 0;
			ll s1 = f(a);
			res = max(s1, res);
			a[i] = 1;
			break;
		}
	}
	cout << res<<endl;
	a.clear();
}
int main(int args, char** argv)
{
	/*ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin.tie(nullptr);*/
	long t;
	cin >> t;
	while ( t-- )
	{
		solve();
	}
	return 0;
}