站长百科 题解 CF327A Flipping Game 正文

题解 CF327A Flipping Game

2022-12-09,

前言

数据水的一批，\(\mathcal{O}(n^3)\) 给过我觉得是不应该的。

题意

有一个由 \(0\) 和 \(1\) 组成的序列 \(a_1,a_2,a_3,a_4....,a_n\) 。

规定可以选择一段区间取反。问取反后序列中最多有多少个 \(1\) 。

\(\sf Solution\)

\(\sf Step1\)

哇， \(n\) 只有 \(100\) ，可以暴力啦！

枚举区间左端点和右端点，然后 \(\mathcal{O}(n)\) 统计 \(1\) 的个数。

时间复杂度：\(\mathcal{O}(n^3)\)

\(\sf Step2\)

上面那种太无脑了，想想优化吧。

显然前缀和。

先预处理 \(1\) 的个数，取反时只需要区间查询，把 \(1\) 的个数和 \(0\) 的个数互换。

时间复杂度：\(\mathcal{O}(n^2)\)

\(\sf Code\)

#include<cstdio>

using namespace std;

int n,a[105],x,y,maxx;

int main()

{

	scanf("%d",&n);

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

		scanf("%d",&x),a[i]=a[i-1]+x;//预处理

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

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

		{

			x=a[j]-a[i-1];//计算区间中1的个数

			y=j-i+1-x;//计算区间中0的个数

			if(a[n]-x+y>maxx)//a[n]-x+y为取反后1的个数

				maxx=a[n]-x+y;//比较

		}

	printf("%d",maxx);

	return 0;

}

题解 CF327A Flipping Game的相关教程结束。

《题解 CF327A Flipping Game.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!