CodeForces/390C

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
Inna and Candy Boxes	★☆☆☆☆	答案正确	100	2015-02-26 15:35:16	数组不够大（1）

• 来自寒假练习：2015 Winter Day 3 div1 C题
• 原题链接：http://codeforces.com/problemset/problem/390/C

题意

已知n个盒子里分别是否有糖，给出若干查询l,r，使得只有第l+k-1,l+2k-1,l+3k-1, ..., ri有糖，需要变更几个盒子的状态（所有变更都是临时的）。

题解

• 前缀数组a[i]=s[i]+s[i-k]+...+s[0]，由于k很小，所以只要枚举(l,r-k+1)~(l+k-1,r)用前缀数组相减的方式求答案即可。

代码

390C.cpp代码已折叠 展开折叠内容

#include<cstdio> #include<iostream> #include<string> #include<vector> #include<iomanip> #include<algorithm> #include<cstring> #include<cmath> #include<bitset> #include<set> #include<sstream> #include<utility> using namespace std; //数据类型// #define llu unsigned long long #define lld long long //定义默认类型// typedef lld num; #define dsi(n) num n;scanf("%lld",&n) #define si(n) scanf("%lld",&n) //其它// #define reset(x) memset(x,0,sizeof(x)) #define ci const num& #define sqr(x) ((x)*(x)) #define f(i,n) for(num i=1;i<=n;++i) #define ff(i,r,n) for(num i=r;i<=n;++i) #define fi(n) f(i,n) #define f0(i,n) for(num i=0;i!=n;++i) #define fd(i,n) for(num i=n;i>=1;--i) #define foreach(i,s) for(typeof(s.begin()) i=s.begin();i!=s.end();++i) #define rforeach(i,s) for(typeof(s.rbegin()) i=s.rbegin();i!=s.rend();++i) #define iforeach(i,s) int idx=0;for(typeof(s.begin()) i=s.begin();i!=s.end();++i,++idx) #define Vector2 pair<num,num> #define vector2(x,y) make_pair(x,y) #define x first #define y second string s; num a[100100];//fixed:数组不够大// int main() { dsi(n); dsi(k); dsi(q); cin>>s; f0(i,s.size()) { if(i>=k)a[i]=a[i-k]+(s[i]=='1'); else a[i]=(s[i]=='1'); //fixed:删掉调试用的...// } fi(q) { dsi(l);dsi(r); --l;--r; num ans=(r-l+1)/k-(a[r]-a[l-1]); for(int i=l,j=r-k+1;j<r;++i,++j)//fixed:j<r非<=// { if(i>=k)ans+=a[j]-a[i-k];//fixed:i-k不是i-1// else ans+=a[j]; } cout<<ans<<endl; } return 0; }