Codeforces 729D Sea Battle(简单思维题)
2024-09-01 14:13:19
http://codeforces.com/contest/738/problem/D
https://www.cnblogs.com/flipped/p/6086615.html 原
题意:海战棋游戏,长度为n的01串,1代表炸过且没有船的位置,0代表没有炸过的位置。有a个船,长度都是b,求打到一艘船至少还需要多少炸弹,并输出炸的位置。
分析:每连续的b个0就要炸一次,不然不知道有没有是不是刚好一艘船在这b个位置上面。贪心可知炸这b个的最后一个最划算。因为只要炸到一艘即可,所以答案减去a-1,即有a-1艘可以不管它。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long
#define se second
#define fi first
const int Mos = 0x7FFFFFFF; //
const int nMos = 0x80000000; //-2147483648
const int N=2e5+; int n,a,b,k;
char g[N];
int d[N]; int main()
{
cin>>n>>a>>b>>k;
scanf("%s",g+); int cnt=,m=;
for(int i=;i<=n;i++)
{
if(g[i]=='')
{
cnt++;
if(cnt==b)
{
cnt=;
d[m++]=i;
}
}
if(g[i]=='') cnt=;
}
m-=(a-);
cout<<m<<endl;
for(int i=;i<m-;i++)
cout<<d[i]<<" ";
cout<<d[m-]<<endl;
}
最新文章
- 【自己给自己题目做】:如何在Canvas上实现魔方效果
- 如何在Kali Linux中搭建钓鱼热点
- SpringMVC使用静态资源
- 内存分配(c/c++)
- css知识汇总
- ModelState用法
- 青瓷qici - H5小游戏 抽奖机 0 创建工程
- teachable-machine:探索机器学习如何工作,浏览器中实时浏览
- Spring动态切换多数据源解决方案
- HTML5新增特性
- Jenkins&#160;Jenkins结合GIT&#160;Maven持续集成环境配置
- A2D JS框架
- 读vue-0.6-observer.js源码
- java 转换流 打印流 数据流
- VMware 虚拟机磁盘
- 2.Geany安装后编译器配置
- The attribute required is undefined for the annotation type XmlElementRef
- 架构图+kubernetes 问题理解 -- kube-pproxy - endpoint
- 【Devops】【docker】【CI/CD】关于jenkins构建成功后一步,执行的shell命令详解+jenkins容器运行宿主机shell命令的实现方法
- 浅谈:当程序员的N多好处,逆袭高富师