【Round #36 (Div. 2 only) B】Safe Spots
div round Only 36 safe
2023-09-14 09:03:50 时间
【题目链接】:https://csacademy.com/contest/round-36/task/safe-spots/
【题意】
给你n个数字构成的序列;
每个位置上的数都由0和1组成;
对于每个0;
假设其位置为i;
如果[i-k..i+k]这个范围内1的个数不超过1,则称它合法;
问符合要求的这样的0的个数.
【题解】
前缀和.
直接获取sum[i+k]-sum[i-k-1]就是这个范围里面1的个数了;
(程序用的是其他方法..维护第i个数字前k个数里面有多少个1。以及后面k个数字里面有多少个1)
【Number Of WA】
0
【反思】
第一反应不是前缀和的做法说明我还很菜?
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define Open() freopen("F:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 1e5;
int n,k,a[N+100],pre[N+100],after[N+100],now;
int main(){
//Open();
Close();
cin >> n >> k;
rep1(i,1,n)
cin >> a[i];
now = 0;
rep1(i,1,n){
pre[i] = now;
if (a[i]==1) now++;
if (i-k>=1 && a[i-k]==1) now--;
}
now = 0;
rep2(i,n,1){
after[i] = now;
if (a[i]==1) now++;
if (i+k<=n && a[i+k]==1) now--;
}
int ans = 0;
rep1(i,1,n)
if (a[i]==0 && pre[i]+after[i]<=1)
ans++;
cout << ans << endl;
return 0;
}
相关文章
- Codeforces Round #277(Div. 2) (A Calculating Function, B OR in Matrix, C Palindrome Transformation)
- vue.js 3.2.20:拖动创建div及移动、缩放、删除等操作
- div 隐藏
- 【Codeforces Round #650 (Div. 3) D】Task On The Board
- 【Codeforces Round #648 (Div. 2) D】Solve The Maze
- 【Educational Codeforces Round 88 (Rated for Div. 2) A】Berland Poker
- 【Educational Codeforces Round 48 (Rated for Div. 2) D】Vasya And The Matrix
- 【Codeforces Round #476 (Div. 2) [Thanks, Telegram!] A】Paper Airplanes
- 【Codeforces Round #459 (Div. 2) C】The Monster
- 【Codeforces Round #453 (Div. 2) B】Coloring a Tree
- 【Codeforces Round #301 (Div. 2) C】 Ice Cave
- 【AIM Tech Round 4 (Div. 1) B】Interactive LowerBound
- 【Codeforces Round #429 (Div. 2) C】Leha and Function
- 【 Codeforces Round #425 (Div. 2) D】Misha, Grisha and Underground
- 【CS Round #37 (Div. 2 only) B】Group Split
- 【CS Round #37 (Div. 2 only) A】Boring Number
- 【CS Round #37 (Div. 2 only) D】Reconstruct Graph
- 【Round #36 (Div. 2 only) C】Socks Pairs
- 【Codeforces Round #422 (Div. 2) A】I'm bored with life
- 【Codeforces Round #420 (Div. 2) A】Okabe and Future Gadget Laboratory
- 通过jquery获得某个元素的位置, 透明div, 弹出框, 然后在旁边显示toggle子级联菜单-hover的bug解决
- Codeforces Round #256 (Div. 2/C)/Codeforces448C_Painting Fence(分治)
- Codeforces Round #459 (Div. 2)
- Codeforces Round #362 (Div. 2)
- Codeforces Round #416 (Div. 2) 本来以为这个时间是晚上的,下午就没做