Round#835(Div.4)E. Binary Inversions

news/2024/4/19 17:12:58/

 题目链接:Problem - E - Codeforces

 题目概述:给一个只含零一的数组。我们可以选择数组内的任意元素,至多执行下列操作一次。(只能选择一个元素执行操作)。操作为:反转你选择的元素(1变为0,0变为1)。

求操作后(可以不执行),数组里能得到的符合下列情况(a_{i}>a_{j}i<j)的组合的数量。

思路:

先处理出每个元素前边有多少个一,后边有多少个零(自身为一或零算上自身)可以用pair来存。前一后零即为符合条件的情况。

这样我们就可以根据每一个一以及它后面的零的个数(根据零道理一样)来求在执行操作前符合条件的组合数量sum。

假设我们要执行操作,我们可以遍历每个元素,求得变化后带来的增量(可能为负增量)的最大值max。具体为:我们令 first为 a[i] 的前缀1的个数,second为后缀的0的个数。对于1变成0,我们的增量为first - 1 -second;对于0 变为 1,我们的增量为 second - 1 - first。 

最后sum减去max即为答案。

注意数据范围,sum 记得开long long

代码:

#include <bits/stdc++.h>
using namespace std;
const int N =2e5+10;
int a[N];
pair<int,int>c[N];
void solve()
{int n;cin >> n;for(int i = 0;i < n;i++){cin >> a[i];}int one = 0,zero = 0;for(int i = 0,j = n - 1;i < n&&j >= 0;i++,j--){if(a[i]) {one ++;}if(!a[j]) {zero ++;}c[i].first = one;//每个元素前面有多少个一c[j].second = zero;//每个元素后边有多少个零//若自身为一或零,也算上自身}long long sum = 0;for(int i = 0;i < n;i++){if(a[i]) sum += c[i].second;//对于每一个一来求和他匹配的零个数//和就是操作前的匹配数}long long max = 0;for(int i = 0;i < n;i++)//求进行一次操作后能得到的最增量{if(a[i]){int t3 = c[i].first - 1 - c[i].second;if(max < t3){max = t3;}}else{int t3 =  c[i].second- 1 - c[i].first;if(max < t3){max = t3;}}}sum += max;//操作后得到答案为和加上增量cout << sum <<"\n";
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while(t--){solve();}return 0;
}


http://www.ppmy.cn/news/300067.html

相关文章

Codeforces Round #835 (Div. 4)A.B.C.D.E.F

A. Medium Number 题目链接&#xff1a; Problem - A - Codeforces 题面&#xff1a; 题意&#xff1a; 给定三个数&#xff0c;求中间那个数的值 思路&#xff1a; 我们可以分别求出三个数的总和&#xff0c;最大值和最小值&#xff0c;在通过总和减最大值和最小值的方…

Codeforces Round #835 (Div. 4)题解

补完一套div4&#xff0c;此图为证 提交记录 说明 题目链接 一共7个题&#xff0c;做出前5题&#xff0c;排到接近四千名了。前5题就是模拟或者像前缀和后缀和之类的简单题&#xff0c;没什么好说的。比较难想的是F&#xff0c;好想但是细节多难调的是压轴题G。 A题 Medium N…

Codeforces Round #835 (Div. 4) 题解 A-G

A 题目链接&#xff1a;https://codeforces.com/contest/1760/problem/A input&#xff1a; 9 5 2 6 14 3 4 20 2 1 1 2 3 11 19 12 10 8 20 6 20 3 4 1 3 19 8 4output&#xff1a; 5 4 2 2 12 10 6 3 8题意&#xff1a; 给三个数&#xff0c;输出中间值。 思路&#xff1…

F. Quests Codeforces Round #835 (Div. 4)(二分答案)

传送门 题意&#xff1a; 有n个任务。如果你在这天完成第i个任务&#xff0c;你将获得ai币。每天只能完成一个任务。并且做完这个任务后k天内都不能再做这个任务(例如&#xff0c;如果k3&#xff0c;你做了任务1&#xff0c;那么后三题都不能做此任务&#xff0c;只能在第五天…

Codeforces Round #835 (Div. 4) C. Advantage

Codeforces Round #835 (Div. 4) C. Advantage Make a copy of the array s s s: call it t t t. Sort t t t in non-decreasing order, so that t 1 t_1 t1​ is the maximum strength and t 2 t_2 t2​ — the second maximum strength. Then for everyone but the be…

个人练习-Leetcode-835. Image Overlap

题目链接&#xff1a;https://leetcode.cn/problems/image-overlap/ 题目大意&#xff1a;给出两个位图矩阵img1[][]和img2[][]&#xff0c;其中元素只有0和1。一次平移是指将一个图像里【所有的1】都向左/右/上/下移动一格。求经过若干次平移后&#xff0c;两个图像能重叠的1…

24考研835软件工程经验贴

大家好&#xff0c;今天给大家介绍一下我在考研这一年之中有关于835软件工程的一些经验和误区。 1.经验之谈 首先&#xff0c;我是一个二战的考生&#xff0c;一战给我带来的经验有几点。第一&#xff0c;数学、专业课这两门越早复习越好&#xff0c;越拖到后面你就会发现来不及…

835:排列

总时间限制: 5000ms 内存限制: 65536kB 描述 题目描述&#xff1a;大家知道&#xff0c;给出正整数n&#xff0c;则1到n这n个数可以构成n&#xff01;种排列&#xff0c;把这些排列按照从小到大的顺序&#xff08;字典顺序&#xff09;列出&#xff0c;如n3时&#xff0c…

海南大学电子信息(085400)原软件工程835

欢迎学弟学妹报考海南大学 你是不是没有资料&#xff1f; 海南大学软件工程835&#xff08;网安和计科&#xff09;&#xff0c;由多名软工学长学姐共同编写&#xff0c;专业课知识框架清晰&#xff0c;包含16-22各年份真题&#xff08;内含答案&#xff09;、总结知识点、专…

Codeforces Round #835 (Div. 4)A~D

Codeforces Round #835 (Div. 4&#xff09; A. Medium Number 感受&#xff1a;太简单了&#xff01;&#xff01;&#xff01;简单简单简单&#xff01; 题意&#xff1a;三个数找中间数 我的思路&#xff1a;sort() 题解&#xff1a;这没啥思路感觉 #include <iost…

Codeforces Round #835 (Div. 4) A~G

原题链接&#xff1a;Codeforces Round #835 (Div. 4) 目录 A. Medium Number B. Atillas Favorite Problem C. Advantage D. Challenging Valleys E. Binary Inversions F. Quests G. SlavicGs Favorite Problem A. Medium Number 题意&#xff1a;输出三个数的中间…

ipad协议835最新版

微信作为中国最流行的社交媒体应用之一&#xff0c;其协议安全性一直备受关注。逆向微信协议可以帮助我们更好地理解微信的工作原理&#xff0c;进而开发出更好的第三方应用或者提高自己的安全意识。本文将介绍微信逆向协议开发的基本流程和注意事项。 ## 什么是微信逆向协议&a…

Codeforces Round #835 (Div. 4)

文章目录 一、A - Medium Number二、B - Atillas Favorite Problem三、C - Advantage四、D - Challenging Valleys五、E - Binary Inversions六、F - Quests七、G - SlavicGs Favorite Problem 一、A - Medium Number 代码: #include <bits/stdc.h> #define ios ios::s…

Codeforces Round #835 (Div. 4) G. SlavicG‘s Favorite Problem

翻译&#xff1a; 给您一个带有&#x1d45b;顶点的加权树。回想一下&#xff0c;树是一个没有任何循环的连通图。加权树是每条边都有一定权重的树。树是无向的&#xff0c;它没有根。 因为树木让你厌烦&#xff0c;所以你决定挑战自己&#xff0c;在给定的树上玩一款游戏。 …

Codeforces Round #835(div4) A~G题解

前言 也是好久没有打div4了&#xff0c;上一次还是半年前的第二场cf比赛&#xff0c;记得当时过了3题&#xff0c;非常开心。这一次过了5个题&#xff0c;D题调试时间太久&#xff0c;导致F题最后没时间调试了。总之还不错。 Codeforces Round #835(div4)补题链接 A. Medium …

Codeforces Round #835 (Div. 4) A~F题解

原题地址&#xff1a;Codeforces Round #835 (Div. 4) 题目&#xff1a;A. Medium Number 题意&#xff1a; 没什么好说的&#xff0c;输出中间那个数即可 代码&#xff1a; #include<bits/stdc.h> #include<iostream> #include<algorithm> #include<…

【Codeforces Round #835 (Div. 4)】A——G题解

文章目录 A Medium Number题意思路代码 B Atillas Favorite Problem题意思路代码 C Advantage题意思路代码 D Challenging Valleys题意思路代码 E Binary Inversions题意思路代码 F Quests题意思路代码 G SlavicGs Favorite Problem题意思路代码 A Medium Number 题意 三个数…

微信 iPad 835协议

微信 iPad 协议是指用于在 iPad 设备上使用微信应用的技术协议。一般来说&#xff0c;通过该协议可以将微信账号同步到 iPad 设备上&#xff0c;并且可以在 iPad 上发送和接收微信消息&#xff0c;查看好友列表、聊天记录等功能。微信 iPad 协议是通过私有API实现的。 需要一定…

大厂设计师都在用的9个灵感工具

每一件伟大的设计作品都离不开设计师灵感的爆发。设计师有很多灵感来源&#xff0c;比如精美的摄影图片、酷炫的网站设计、APP的特色功能、友好的用户体验动画&#xff0c;或者一篇文章。 设计师每天都需要收集灵感&#xff0c;把灵感收集当成日常生活。在这篇文章中&#xff…

高通 Msm835平台充电功能的开发与调试

目录 平台充电相关代码&#xff1a; 835平台kernel充电相关代码&#xff1a; 关机充电的系统相关代码&#xff1a; 835平台UEFI 充电相关代码&#xff1a; 835平台电池曲线&#xff1a; 电池曲线大体内容如下: kernel 电池曲线的提交&#xff1a; XBL 关于充电曲线的提…