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;
    } 
    
    

    大分讨.

    • 3
      @ 2026-10-28 16:37:17

      和lzm差不多,差别应该就是我用了数组存储(这个题不开long long的话会挂分,注意相乘的时候也要开)

      code:

      #include<bits/stdc++.h>
      using namespace std;
      string s;
      int n;
      int l[10000005],r[10000005],ansl[10000005],ansr[10000005];
      int ll,l1,rr,r1;
      long long sum;
      int main(){
      	cin>>n>>s;
      	rr=n,r1=n;
      	ll=-1,l1=-1;
      	for(int i=0;i<n;i++){
      		if(s[i]=='0'){
      			l[i]=ll;
      			ll=i;
      		}
      		else{
      			l[i]=l1;
      			l1=i;
      		}
      	}	
      	for(int i=n-1;i>=0;i--){
      		if(s[i]=='0'){
      			r[i]=rr;
      			rr=i;
      		}
      		else{
      			r[i]=r1;
      			r1=i;
      		}
      	}
      	for(int i=0;i<n;i++){
      		int lhh=(i-l[i]-1),syn=(r[i]-i-1);
      		sum=sum+lhh+syn;
      		if(lhh>0&&syn>0)sum+=(long long)lhh*syn;
      	}
      	for(int i=0;i<n-1;i++){
      		if(s[i]=='0'&&s[i+1]=='1'||s[i+1]=='0'&&s[i]=='1')sum-=1;
      	}
      	cout<<sum+n;
      	return 0;
      } 
      
      

      ps:最快的一期

      • @ 2026-10-28 16:38:03

        这篇题解还是太快了,一分钟写完了,然后就是我的可能比lzm的看着好写点?

      • @ 2026-11-11 14:44:22

        4个1e7大数组,我如何绷住。

    • 1
      @ 2026-10-28 17:24:53

      题意理解

      比赛时没有想明白这个孤独的串是啥意思,后来才明白,不仅如 0,1,011,1100,1,011,110 都是孤独的串,010010也是。

      思路构想

      我们可以发现,决定孤独的串的多少的数,只有两类。一类是紧跟着的那个数和它不一样,但是它前面的数和它一样的,如0011100111的第二个0。另一类则是它左边右边都和它不一样的数,如0010000100中的1。 对于第一类,我们可以往右推,直到右边第一个数和它一样,则从我们选的这个数那个一样的数左边一个数构成了一个孤独的串。如果一直到nn也没有一个数和我们选的这个数一样,则从这个数到nn这一长串都是孤独的串。由于左端点必须在这个串的字串内以保证这些串都是孤独的串,这个串的长度就是孤独的串的个数。然后从这个数左边的一个数开始找,向左找到第一个和它不一样的数,则这两个数之间的所有的数(不含端点)的个数又是孤独的串的个数。如果一直到1都没有找到和它不一样的数,则从1到这个数前一个数的个数就是孤独的串的个数。 对于第二类,我们需要找到它左边第一个和它一样的数,将这两个数之间数的个数(不含端点)计为cnt2cnt2。然后向右找第一个和它一样的数,把这两个数中间数的个数计为cnt1cnt1。然后由于必须要有这个数本身,子串数量就是cnt1∗cnt2cnt1 * cnt2。以这个数开头的孤独的串不会被其他的串记录,所以要再加一遍cnt1。

      注意陷阱

      1.子串是否相同只看左右端点,不看子串内容。 2.010等也是孤独的串,千万别漏掉 //这两个坑作者已经踩过多次,也是作者调了一下午都调不对这段代码的原因

      代码实现

      #include<bits/stdc++.h>
      #define int long long
      using namespace std;
      int n, ans = 0, cnt;
      string s;
      vector<int>v;
      vector<int>v2;
      signed main(){
      	ios::sync_with_stdio(0);
      	cin.tie(0), cout.tie(0);
          cin>>n>>s;
          s = 'A' + s;
          for(int i = 1; i < n; i ++){
              if(s[i] != s[i+1]){
                  if(s[i] != s[i-1]) v2.push_back(i);
                  else v.push_back(i);
              } 
          }
          for(int i : v){
              for(int j = i+1; j <= n; j ++){
                  if(s[i] == s[j]){
                      ans += j - i - 1;
                      break;
                  }
                  else if(j == n){
                      ans += j - i;
                      break;
                  }
              }
              if(s[i-1] == s[i]){
                  for(int j = i-1; j >= 1; j --){
                      if(s[i] != s[j]){
                          ans += i - j - 1;
                          break;
                      }
                      else if(j == 1){
                          ans += i - j;
                          break;
                      }
                  }
              }
              
          }
          //ans += n - now + 1 - cnt;
          for(int i : v2){
              int cnt1 = 0, cnt2 = 0;
              for(int j = i+1; j <= n; j ++){
                  if(s[i] == s[j]){
                      cnt1 += j - i - 1;
                      break;
                  }
                  else if(j == n){
                      cnt1 += j - i;
                      break;
                  }
              }
              ans += cnt1 ;
              for(int j = i-1; j >= 1; j --){
                  if(s[i] == s[j]){
                      cnt2 += i - j - 1;
                      break;
                  }
                  else if(j == 1){
                      cnt2 += i - j;
                      break;
                  }
              }
              ans += cnt2 * cnt1;
          }
          cout<<ans + n;
          
          return 0;
      }
      

      AC记录

      http://oi.sdshiyan.cn/record/6ae1b8f19eb2952289732df3

      • 1

      信息

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