3 条题解

  • 4
    @ 2026-10-28 8:52:35

    赛时只想到了这种方法,就是统计以每一个位置为结尾的“孤独串”的个数,没想到换别的角度能够减少不少讨论分支。

    直接维护四个变量 A、B、C、D,分别代表上一个、上一个的上一个 1 和 0 的位置。

    然后直接分情况讨论,每种分支考虑得仔细一点就不会有问题了。

    复杂度 O(n)。

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 1e7 + 5;
    typedef long long ll;
    char s[N];
    ll X, n, A, B, C, D;
    int main() {
    	cin >> n;
    	for(int i=1; i<=n; ++i) cin >> s[i];
        if(s[1] == '0') A = 1;
        else C = 1;
    	for(int i=2; i<=n; ++i) {
    		if(s[i] == '0') {
    			if(!A) X += i;
    			else {
    				X += i - A;
    				if(C && !D) {
    					if(A > C) X += C;
    					else X += A;
    				}
    				else if(C && D) {
    					if(A > C) X += C - D;
                        else if(A < C && A > D) X += A - D;
    				}
    			}
    			B = A, A = i;
    		}
    		else {
    			if(!C) X += i;
    			else {
    				X += i - C;
                    if(A && !B) {
                        if(C > A) X += A;
                        else X += C;
                    }
                    else if(A && B) {
                        if(C > A) X += A - B;
                        else if(C < A && C > B) X += C - B;
                    }
    			}
    			D = C, C = i;
    		}
    	}
    	cout << X + 1;
    	return 0;
    } 
    
    

    大分讨.

    信息

    ID
    115
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    82
    已通过
    19
    上传者