首页 > 代码库 > CodeForces 738D Sea Battle

CodeForces 738D Sea Battle

抽屉原理。

先统计最多有$sum$个船可以放,假设打了$sum-a$枪都没打中$a$个船中的任意一个,那么再打$1$枪必中。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<ctime>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0);void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){    char c = getchar();    x = 0;    while(!isdigit(c)) c = getchar();    while(isdigit(c))    {        x = x * 10 + c - 0;        c = getchar();    }}int n,a,b,k;char s[200010];struct X{    int L;    int cnt;}t[200010];int sz,cnt;int sum;int main(){    cin>>n>>a>>b>>k;    cin>>s;    for(int i=0;s[i];)    {        if(s[i]==0)        {            int j;            for(j=i;s[j];j++)            {                if(s[j]==0) continue;                break;            }            j--;            t[sz].L=i;            t[sz].cnt=j-i+1;            sz++;            i=j+1;        }        else i++;    }    for(int i=0;i<sz;i++) sum=sum+t[i].cnt/b;    int now=0;    printf("%d\n",sum-a+1);    for(int i=0;i<sz;i++)    {        for(int j=1;j<=t[i].cnt/b;j++)        {            printf("%d ",t[i].L+j*b);            now++;            if(now==sum-a+1) break;        }        if(now==sum-a+1) break;    }    return 0;}

 

CodeForces 738D Sea Battle