3 条题解

  • 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

    信息

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