codefroces 873 B. Balanced Substring && X73(前缀和思想)
You are given a string s consisting only of characters 0 and 1. A substring [l, r] of s is a string slsl + 1sl + 2... sr, and its length equals to r - l + 1. A substring is called balanced if the number of zeroes (0) equals to the number of ones in this substring.
You have to determine the length of the longest balanced substring of s.
The first line contains n (1 ≤ n ≤ 100000) — the number of characters in s.
The second line contains a string s consisting of exactly n characters. Only characters 0 and 1 can appear in s.
If there is no non-empty balanced substring in s, print 0. Otherwise, print the length of the longest balanced substring.
8
11010111
4
3
111
0
In the first example you can choose the substring [3, 6]. It is balanced, and its length is 4. Choosing the substring [2, 5] is also possible.
In the second example it's impossible to find a non-empty balanced substring.
前缀和离散化
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <map>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 1044266558
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
char s[];
int a[],n,ans=,val=;
int main()
{
scanf("%d%s",&n,&s);
memset(a,,sizeof(a));
for(int i=;i<n;i++)
{
ans+=s[i]==''?-:;
if(ans==) val=i+;
else
{
if(!a[ans+n]) a[ans+n]=i+;
else val=max(val,i-a[ans+n]+);//若中间值存在必为0,因此左右指针对应的值相等
}
}
printf("%d\n",val);
return ;
}
给你一个数组,求数组中连续区间内和为73的区间个数
输入n(0<n<=100000),接下来输入n个数ai(0<ai<75);
输出
连续区间内和为73的区间个数,若没有输出"X"
前缀和维护数组。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <map>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 1044266558
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
ll val[],n,ans=,k=;
map<ll,ll>a;
int main()
{
scanf("%lld",&n);
a[]=;
for(int i=;i<=n;i++) scanf("%lld",&val[i]);
for(int i=;i<=n;i++)
{
ans+=val[i];
a[ans]++;
if(ans>=) k+=a[ans-];
}
if(k) printf("%lld\n",k);
else printf("X\n");
return ;
}
最新文章
- javascript - 享元模式
- 谷歌 Uncaught SecurityError: Failed to execute &#39;replaceState&#39; on &#39;History 错误
- ORA-29339错误解决办法
- away3d学习
- sql server2008评估期已过...问题
- js把div固定在页面的右下角
- Leetcode OJ : Restore IP Addresses backtrack暴搜 C++ solution
- sae-xhprof调试性能
- 盘点 Github 所用到的开源项目
- 【D3.V3.js系列教程】--(十五)SVG基本图形绘制
- H5与CS3权威下.18 and 19 选择器(1)
- JDBC连接SQL Server 2005步骤详解
- java程序运行结果
- The Last Week
- Linux下常用配置文件
- 集合-HashMap
- Django之ORM初始
- Git本地上传到服务器
- Java 并发编程——volatile与synchronized
- Camera &; Render