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

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

冷不防 2022-06-04 04:36 291阅读 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题目链接

以下为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;
}