【尺取法/二分+优化】Audition SPOJ - CRAN04

冷不防 2022-06-04 04:36 165阅读 0赞

Think:  
1知识点：尺取法/二分+优化(k == 0时判断小区间长度进而通过公式计算)

2题意：  
（1）：判断在一个长度为n(n <= 1e6)的01序列中判断有多少个区间内的1的数量为k  
3思路：  
（1）：尺取法+(k == 0时特殊判定)  
（2）：二分+(k == 0时特殊判定)  
4反思：  
（1）：尺取法需要加强理解  
（2）：未考虑到临界数据(eg:k == 0)时的时间复杂度  
（3）：未考虑到临界数据(eg:k == 0)时需要通过long long 存储满足条件的区间的数量

[vjudge题目链接][vjudge]

以下为Accepted代码——二分+优化

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    int rec[1004014], sum[1004014];
    char str[1004014];
    
    int main(){
        LL T, n, k, ans;
        scanf("%lld", &T);
        while(T--){
            scanf("%lld %lld", &n, &k);
            scanf("%s", str);
            for(int i = 0; i < n; i++){
                rec[i+1] = str[i] - '0';
            }
            if(!k) {
                ans = 0;
                LL t, j;
                for(LL i = 1; i <= n; i++){
                    if(rec[i]) continue;
                    for(j = i+1; j <= n; j++){
                        if(rec[j]) break;
                    }
                    if(j <= n) {
                        t = (j-1)-i+1;
                        ans += t*(t+1)/(LL)2;
                        i = j;
                    }
                    else {
                        t = n-i+1;
                        ans += t*(t+1)/(LL)2;
                        break;
                    }
                }
                printf("%lld\n", ans);
                continue;
            }
            sum[0] = 0;
            for(int i = 1; i <= n; i++){
                sum[i] = sum[i-1] + rec[i];
            }
            ans = 0;
            LL t, l, r, mid, mt;
            for(int i = 1; i <= n; i++){
                t = sum[i] + k - rec[i];
                l = i, r = n;
                while(l <= r){
                    mid = (l+r)/2;
                    if(sum[mid] == t) break;
                    if(sum[mid] < t) {
                        l = mid+1;
                    }
                    else if(sum[mid] > t){
                        r = mid-1;
                    }
                }
                if(l > r) continue;
                else {
                    ans++;
                    mt = mid-1;
                    while(mt >= i){
                        if(sum[mt] == t) ans++;
                        else break;
                        mt--;
                    }
                    mt = mid+1;
                    while(mt <= n){
                        if(sum[mt] == t) ans++;
                        else break;
                        mt++;
                    }
                }
            }
            printf("%lld\n", ans);
        }
        return 0;
    }

以下为Accepted代码——尺取法+优化

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    int rec[1004014];
    char str[1004014];
    
    int main(){
        int T, n, k;
        LL ans;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &n, &k);
            scanf("%s", str);
            for(int i = 1; i <= n; i++){
                rec[i] = str[i-1] - '0';
            }
            ans = 0;
            if(!k) {
                LL t, j;
                for(LL i = 1; i <= n; i++){
                    if(rec[i]) continue;
                    for(j = i+1; j <= n; j++){
                        if(rec[j]) break;
                    }
                    if(j <= n) {
                        t = (j-1)-i+1;
                        ans += t*(t+1)/(LL)2;
                        i = j;
                    }
                    else {
                        t = n-i+1;
                        ans += t*(t+1)/(LL)2;
                        break;
                    }
                }
            }
            else {
                int id, cnt = 0;
                LL a = 0, b = 0;
                for(int i = 1; i <= n; i++){
                    if(rec[i] == 1){
                        cnt++;
                        if(cnt == 1) id = i;
                        else if(cnt == k+1){
                            ans += (a+1)*(b+1);
                            a = 0, b = 0, cnt -= 1;
                            id++;
                            while(id <= n && rec[id] == 0){
                                a++;
                                id++;
                            }
                        }
                    }
                    else {
                        if(cnt == 0) a++;
                        else if(cnt == k) b++;
                    }
                }
                if(cnt == k) ans += (a+1)*(b+1);/*尺取遍历结束之后正好cnt累计到达k的情况需要考虑*/
            }
            printf("%lld\n", ans);
        }
        return 0;
    }

[vjudge]: https://vjudge.net/problem/SPOJ-CRAN04