首页 > 代码库 > cf C. Inna and Candy Boxes

cf C. Inna and Candy Boxes

2024-11-17 18:43:02   202人阅读

题意：给你一个长度为n的只含有1和0的字符串，w个询问，每次询问输入l,r；在[l,r]中在l+k-1、l+2*k-1、......r的位置都必须为1，如果不为1的，变成1，记为一次操作，其它的地方的都必须为0，不为0的地方要变成1，也记为一次操作，最后问在区间[l,r]最少几次操作。

思路：可以用树状数组记录在某个地方的右方有多少个1，然后在 预处理出从1，2，..k的为开头的在i+c*k-1的位置上前面有多少个1，最后的答案是拿走的1+添加的1，拿走的1的个数等于现有的1的个数-位置正确的1的个数。 添加的1的个数等于需要添加的个数的总数-位置正确的1的个数。

技术分享
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 100010 5 using namespace std; 6  7 int n,k,w; 8 char str[maxn]; 9 int a[maxn];10 int c[maxn];11 int dp[maxn];12 int sum[maxn];13 14 int lowbit(int x)15 {16     return x&-x;17 }18 19 void insert(int x,int d)20 {21     while(x<maxn)22     {23        c[x]+=d;24        x+=lowbit(x);25     }26 }27 28 int Getsum(int x)29 {30     int ans=0;31     while(x>0)32     {33         ans+=c[x];34         x-=lowbit(x);35     }36     return ans;37 }38 39 40 int main()41 {42     while(scanf("%d%d%d",&n,&k,&w)!=EOF)43     {44          scanf("%s",str+1);45          memset(sum,0,sizeof(sum));46          memset(a,0,sizeof(a));47          memset(c,0,sizeof(c));48          for(int i=1; i<=n; i++)49          {50             if(str[i]==‘1‘)51             {52                 insert(i,1);53             }54          }55          for(int i=1; i<=k; i++)56          {57              int cnt=0;58              for(int c=1; i+c*k-1<=n; c++)59              {60                   cnt+=(str[i+c*k-1]-‘0‘);61                   dp[i+c*k-1]=cnt;62              }63          }64          for(int i=1; i<=w; i++)65          {66              int l,r;67              int ans=0;68              scanf("%d%d",&l,&r);69              int num=(r-l+1)/k;70              ans+=Getsum(r)-Getsum(l-1);71              ans-=dp[r]-dp[l-1];72              ans+=num;73              ans-=dp[r]-dp[l-1];74              printf("%d\n",ans);75          }76     }77     return 0;78 }
View Code

 

cf C. Inna and Candy Boxes


联系
我们