【codechef】 Count Substrings (大数技巧题)(二分+计数,易超
You are given a string?S?of length?N?consisting only of?0s and?1s. You are also given an integer?K. You have to answer?Q?queries. In the?ith?query,two integers?Li?and?Ri?are given. Then you should print the number of substrings of?S[L,R]?which contain at most?K?0s and at most?K?1s where?S[L,R]?denotes the substring from?Lth?to?Rth?characters of the string?S.? InputThe first line of input contains an integer?T,denoting the number of test cases. Then?T?test cases follow. The first line of each test case contains three space-separated integers?N,?K?and?Q?as described in the problem. The second line contains a string?S?of length?N. Then the next?Q?lines describe the query,where the?ith?line of them contains two space-separated integers?Li?and?Ri. OutputFor each query,print the required answer in a single line. Constraints and Subtasks
Input: 1 8 2 3 01110000 1 4 2 4 5 8 Output: 8 5 7 http://www.codechef.com/problems/STRSUB/
这题非常非常莫名其妙地WA了20次!!! 下面是这道题目的两种解法: #include<iostream> #include<algorithm> #include<string> #include<map> #include<set> #include<cmath> #include<string.h> #include<stdlib.h> #include<cstdio> #define ll long long using namespace std; int main(){ int t; cin>>t; while(t--){ ll n,m,k,a,b; string x; cin>>n>>m>>k; cin>>x; ll y[n+5]={0}; ll sum[n+5]={0}; ll c=0,d=0,r=0; for(int i=0;i<n;++i){ while(r<n){ //这个r很好,大大缩短了时间(以后的i的r只要在前面基础上累加就行了) if(x[r]=='1'&&c<m){ c++; r++; } else if(x[r]=='0'&&d<m){ d++; r++; } else{ break; } } y[i+1]=r; //以每个位置作为开头时的结尾位置 sum[i+1]+=sum[i]+r-i; //这个位置之前(包括这个位置),所有以这些位置为起点的符合条件的子集长度和,即有多少个子集 if(x[i]=='1') c--; else d--; } while(k--){ cin>>a>>b; int left=upper_bound(y+a,y+b,b)-y; //取等于时的最后一个下标,如果没有等于的,取大于的第一个下标 if(y[left]>b) //当这个下标取的是大于的第一个下标 left--; cout<<sum[left]-sum[a-1]+(b-left)*(b-left+1)/2<<endl;//sum的差表示left前(包括)子集总数,后面可以看成C(b-left,2)+b-left(单个点也是子集) } } return 0; }或 int main(){ int t; cin>>t; while(t--){ ll n,b; string x; cin>>n>>m>>k; cin>>x; ll y[n+5]={0}; //不知道为什么写y[100005]就是超时? ll sum[n+5]={0}; //不知道为什么写y[100005]就是超时? ll c=0,r=0; for(int i=0;i<n;++i){ while(r<n){ //这个r很好,大大缩短了时间(以后的i的r只要在前面基础上累加就行了) if(x[r]=='1'&&c<m){ c++; r++; } else if(x[r]=='0'&&d<m){ d++; r++; } else{ break; } } y[i+1]=r; //以每个位置作为开头时的结尾位置 sum[i+1]+=sum[i]+r-i; //这个位置之前(包括这个位置),所有以这些位置为起点的符合条件的子集长度和,即有多少个子集 if(x[i]=='1') c--; else d--; } while(k--){ cin>>a>>b; ll left=a,right=b; ll mid; while(left<right){ //注意这里没有等于 mid=(left+right)/2; if(y[mid]>b) //这个地方我b写成r,WA了无数次(教训啊) right=mid-1; else left=mid+1; } if(y[left]>b) //这一步很重要(为什么取left而不是mid?) left--; cout<<sum[left]-sum[a-1]+(b-left)*(b-left+1)/2<<endl;//sum的差表示left前(包括)子集总数,后面可以看成C(b-left,2)+b-left(单个点也是子集) } } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |