Codeforces 873 B. Balanced Substring(前缀和 思维)
2024-09-23 17:36:47
题目链接: Balanced Substring
题意:
求一个只有1和0的字符串中1与0个数相同的子串的最大长度。
题解:
我的解法是设1的权值是1,设0的权值是-1,求整个字符串的前缀和并记录每个前缀和出现的最后位置。因为两个相同的前缀和之间的子串一定符合条件,最后只用遍历一次,将每个前缀与和这个前缀值相同的位置之间的长度求出来就是符合条件的子串长度。但是这里一定要注意!在整个子串未开始遍历的时候这个子串的前缀和也是0。我就是在这个地方错了,这里给出错地方的数据。
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5+;
const int INF = 1e5;
char vec[MAX_N];
int res[MAX_N],val[MAX_N*];
int N,M,t,num;
void init()
{
res[] = ;
memset(val,,sizeof(val));
}
int main()
{
cin>>N;
scanf("%s",vec+);
for(int i=;i<=N;i++)
{
if(vec[i] == '') res[i+] = res[i] - ;
else res[i+] = res[i] + ;
val[res[i+] + INF] = i;
}
int ans = -;
for(int i=;i<=N+;i++)
{
ans = max(ans,val[res[i]+INF] - i + );
}
cout<<ans<<endl;
return ;
} /*
18
011010101110111101 ans : 8
*/
最新文章
- ESLint的使用笔记
- php修改
- 基于华清远见STM32f051的 IIC从模式实现方法
- 区别CALL SCREEN/SET SCREEN/LEAVE TO SCREEN
- WebResource-asp.net自定义控件引用外部资源方法
- 解析数据存储MySQL
- 夺命雷公狗---node.js---4net模块(上)
- 用Delphi7开发Web Service程序 转
- 根据控件Id得到控件
- 串口屏之------Usart GPU 使用手册
- 借助树的概率dp(期望)+数学-好题-hdu-4035-Maze
- Java EE登陆界面生成随机数防止恶意注册或者登录
- ios开发获取SIM卡信息
- RecyclerView中装饰者模式应用
- MYSQL 面试查询系列问题
- JQuery插件:ScrollTo平滑滚动到页面指定位置
- java十进制转三十六进制
- 【Linux】排序命令sort
- 简易 Token 验证的实现
- [转] iOS开发工具——网络封包分析工具Charles
热门文章
- FileTable的创建和使用
- UNIX高级环境编程(9)进程控制(Process Control)- fork,vfork,僵尸进程,wait和waitpid
- 【原创】Qt 使用ODBC driver 连接SQL Server
- 在 vSphere 5.x/6.0 中配置 Network Dump Collector 服务 (2002954)
- Sql Server 流程控制语句
- php解决约瑟夫环的问题
- 将jpg压缩成webp格式的图片
- 3226. [SDOI2008]校门外的区间【线段树】
- [USACO08NOV]Cheering up the Cow
- linux下ab网站压力测试命令