Technocup 2017 - Elimination Round 2 D. Sea Battle

忘是亡心i 2022-07-14 01:00 96阅读 0赞

算是正式开始康复训练啦

这是一题简单的思维题…  
第一想法是鸽巢原理，因为“最小数量“，“至少一个“等关键词。  
那么，就要先知道鸽巢的总数，也就是可能是船的位置的数量。这个时候就要用贪心做，然后只需要保存每个船整个身位中的一个点就行。  
然后用鸽巢原理输出数目和顺序就行。

#include <cstdio> 
    #include <cstring> 
    #include <algorithm> 
    using namespace std;  
    const int maxn = 2*1e5+10;  
    char str[maxn];  
    int ans[maxn];  
    int main()  
    {  
        int n,a,b,k;  
        while(scanf("%d%d%d%d",&n,&a,&b,&k)!=EOF)  
        {  
            scanf("%s",str+1);  
            int m=0,cnt=0;  
            for(int i=1;i<=n;++i)  
            {  
                if(str[i]=='0')  
                {  
                    cnt++;  
                    if(cnt==b)  
                    {  
                        ans[m++]=i;  
                        cnt=0;  
                    }  
                }  
                if(str[i]=='1')  
                    cnt=0;  
            }  
            printf("%d\n",m+1-a);    
            for(int i=0;i<m-a+1;i++)  
                printf("%d ",ans[i]);   
            printf("\n");  
        }  
        return 0;   
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，96人围观）

还没有评论，来说两句吧...

相关阅读

相关【枚举+DP】Technocup 2021 - Elimination Round 2 C. Bouncing Ball

[Problem - C - Codeforces][] 题意： ![de0a1baa634d4b9db8eb4740c021f59d.png][] ![b28272a1

红太狼/ 2024年03月22日 18:59/ 0 赞/ 3 阅读

相关 B. Elimination

题目在下方注意：（1）all of them，指的是同一拨人（2）max(a,b) 可以返回返回较大值 (3)其中的思想还得后续好好分析 There

逃离我推掉我的手/ 2022年12月20日 12:57/ 0 赞/ 89 阅读

相关 Technocup 2017 - Elimination Round 2 D. Sea Battle

算是正式开始康复训练啦这是一题简单的思维题… 第一想法是鸽巢原理，因为“最小数量“，“至少一个“等关键词。那么，就要先知道鸽巢的总数，也就是可能是船的位置的数量。

忘是亡心i/ 2022年07月14日 01:00/ 0 赞/ 97 阅读

相关 Codeforces Round #402 (Div. 2) （A-D）

[CF \402 div2][CF _402 div2] A题：数学。具体看代码吧。很容易明白的。 include<bits/stdc++.h> usi

客官°小女子只卖身不卖艺/ 2022年07月12日 15:16/ 0 赞/ 189 阅读

相关 Codeforces Round #510 (Div. 2) D. Petya and Array

题目：[点击打开链接][Link 1] 题意：给定一个数组，问有多少个不同的区间\[l,r\] (l<=r)使得区间和小于给定的数t。分析：先求个前缀和，则问题转化

朱雀/ 2022年05月15日 18:24/ 0 赞/ 204 阅读

相关 Codeforces Round #403 (Div. 2, based on Technocup 2017 Finals)

[Codeforces Round \403 (Div. 2, based on Technocup 2017 Finals)][Codeforces Round _403

我会带着你远行/ 2022年03月30日 09:57/ 0 赞/ 235 阅读

相关【Codeforces 738D】Sea Battle（贪心）

[http://codeforces.com/contest/738/problem/D][http_codeforces.com_contest_738_problem_D]

一时失言乱红尘/ 2022年03月30日 06:44/ 0 赞/ 187 阅读

相关 CodeForces 729D Sea Battle

题目衔接：[http://codeforces.com/problemset/problem/729/D][http_codeforces.com_problemset_pro

一时失言乱红尘/ 2022年02月23日 05:12/ 0 赞/ 180 阅读

相关 Codeforces Round #553 (Div. 2) （A,B,C,D）

终测一个题A，B被hack了。好好补题啦题目链接：[https://codeforces.com/contest/1151][https_codeforces.com_co

分手后的思念是犯贱/ 2022年02月16日 15:53/ 0 赞/ 203 阅读

相关 Educational Codeforces Round 69 (Rated for Div. 2) D

题目大意: 给出一个序列,和\\(m,k\\),求\\(\\sum\_\{i=l\}^\{r\}\{a\_i\}-k\\left \\lceil \\frac\{

深碍√TFBOYSˉ_/ 2021年10月29日 10:12/ 0 赞/ 198 阅读