Codeforces 660C - Hard Process - [二分+DP]

时间:2022-09-03 22:17:59

题目链接:http://codeforces.com/problemset/problem/660/C

题意:

给你一个长度为 $n$ 的 $01$ 串 $a$,记 $f(a)$ 表示其中最长的一段连续 $1$ 的长度。

现在你最多可以将串中的 $k$ 个 $0$ 变成 $1$,求操作后的 $f(a)$。

题解:

(说实话这道题不看tag我不一定能想得出来……)

首先考虑二分枚举答案,对于一个假定的 $f(a)=x$,我们需要判断能不能满足:

用 $dp[i]$ 表示 $a[i-x+1], \cdots, a[i]$ 的这一段上 $1$ 的数目,那么只要存在一个 $dp[i] + k \ge x$ 就代表这个答案 $f(a)=x$ 是可行的。

另外,考虑到二分的边界问题比较难处理,故在区间被缩得比较小的时候可以改用暴力枚举。

同时,考虑到还有输出的问题,可以在让二分的check(mid)函数不是单纯返回 $0,1$,还可以再返回一个数代表答案子串的位置。

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
const int maxn=3e5+;
int n,k;
int a[maxn];
int f[maxn];
P check(int x)
{
int mx=, p=x;
for(int i=;i<=x;i++) f[i]=f[i-]+a[i], mx=max(mx,f[i]); for(int i=x+;i<=n;i++)
{
f[i]=f[i-]-a[i-x]+a[i];
if(f[i]>mx) mx=f[i], p=i;
}
return mp(mx+k>=x,p);
}
int main()
{
cin>>n>>k;
for(int i=;i<=n;i++) scanf("%d",&a[i]); int l=k, r=n, ans, pos;
while(l<=r)
{
if(r-l<=)
{
for(int mid=r;mid>=l;mid--)
{
P res=check(mid);
if(!res.fi) continue;
ans=mid, pos=res.se;
break;
}
break;
}
int mid=(l+r)/;
if(check(mid).fi) l=mid;
else r=mid;
} cout<<ans<<endl;
for(int i=;i<=pos-ans;i++) printf("%d ",a[i]);
for(int i=pos-ans+;i<=pos;i++) printf("1 ");
for(int i=pos+;i<=n;i++) printf("%d ",a[i]);
}

Codeforces 660C - Hard Process - [二分+DP]的更多相关文章

  1. hdu 3433 A Task Process 二分&plus;dp

    A Task Process Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) T ...

  2. Codeforces 660C Hard Process【二分 Or 尺取】

    题目链接: http://codeforces.com/problemset/problem/660/C 题意: 给定0.1组成的数组,可以改变k个0使其为1,问最终可以得到的连续的1的最大长度. 分 ...

  3. Codeforces 994F Compute Power 二分&plus;DP

    题意:给n个任务 每个任务有两个值$a,b$ 现有许多机器 每台最多可以执行两次任务 若存在第二次任务则满足$a_{second}<a_{first}$ 定义代价$val = \frac { \ ...

  4. hdu3433A Task Process&lpar; 二分dp)

    链接 二分时间,在时间内dp[i][j]表示截止到第i个人已经做了j个A最多还能做多少个B #include <iostream> #include<cstdio> #incl ...

  5. Codeforces 660C Hard Process(尺取法)

    题目大概说给一个由01组成的序列,要求最多把k个0改成1使得连续的1的个数最多,输出一种方案. 和CF 676C相似. #include<cstdio> #include<algor ...

  6. codeforces 660C Hard Process

    维护一个左右区间指针就可以. #include<cstdio> #include<cstring> #include<iostream> #include<q ...

  7. 二分&plus;DP HDU 3433 A Task Process

    HDU 3433 A Task Process Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/ ...

  8. codeforces 808 E&period; Selling Souvenirs &lpar;dp&plus;二分&plus;思维&rpar;

    题目链接:http://codeforces.com/contest/808/problem/E 题意:最多有100000个物品最大能放下300000的背包,每个物品都有权值和重量,为能够带的最大权值 ...

  9. Hard Process&lpar;二分&rpar;

    Hard Process Time Limit:1000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u Submi ...

随机推荐

  1. Python matplotlib笔记

    可视化的工具有很多,如Tableau,各种JS框架,我个人感觉应该是学JS最好,因为JS不需要环境,每个电脑都有浏览器,而像matplotlib需要Python这样的开发环境,还是比较麻烦的,但是毕竟 ...

  2. Xcode7中,如何新建category分类

    易忘,所以留存: 1, 2, 3, 结果如下: 补充: http://tech.meituan.com/DiveIntoCategory.html

  3. eclipse运行时编码设置

    eclipse运行时编码设置:

  4. IE6 IE7&colon; div中table宽度100&percnt;导致的宽度问题

    问题现象:定义了DOCTYPE的页面 当表格的内容比div的高度还要高时,div会出现滚动条,同时在IE6和IE7下会出现问题: IE6:此时table的100%宽度还是没有滚动条那是的宽度,出现滚动 ...

  5. 64位CentOS 6&period;4下安装wine(32位)

    1. 到http://dl.fedoraproject.org/pub/epel/6/x86_64/repoview/epel-release.html下载epel-release-6-8.noarc ...

  6. &lbrack;AngularJS&rsqb; Services&comma; Factories&comma; and Providers -- value &amp&semi; Providers

    Creating a Value Object Sometimes you have javascript object defined: //value object var droidValue ...

  7. 通过Excel来集中管理资源文件

     在支持双语或多语种项目中,常常需要编辑多个文件来添加资源项,感觉比较繁琐,所以想做一个可以集中管理资源文件的工具.借助Excel,使用Excel来记录,并且通过Excel可以进行分页分模块来规划 ...

  8. ffmpeg利用libav库把yuv视频流转换为TS串流

    今天到月末了,才发我这个月的第一篇文章,因为这个月前三周一直在看ffmpeg的libavcodec和libavformat两个库源码.实验室要做一个“小传大”的软件,就是android手机或平板电脑的 ...

  9. setTimeout代替setInterval的写法以及setInterval的弊端以及越来越快的解决办法

    平常经常遇到的一个问题,很多人想间隔时间执行一些事件的时候,第一时间就会想到用setInterval,但是setInterval村子啊不少弊端哦. 弊端1:setInterval会无视错误代码,即使代 ...

  10. JIRA应用的内存参数设置不当&plus;容器没有对资源进行限制导致服务挂掉的例子

    背景: 应用的部署结构是这样的:使用rancher管理的Docker集群,有三台物理主机,二十多个Docker容器, 提供的功能是问题跟踪(JIRA),文档管理(Confluence),代码托管(sv ...