1 条题解

  • 0
    @ 2021-11-06 18:39:18

    90pts:
    取所有子串,然后判断是否含有'5'。
    Code:

    #include<bits/stdc++.h>   
    using namespace std;
    
    int main()
    {
        string s;cin>>s;
        int n = s.length();
        int ans = 0;
        for(int i=0;i<n;i++)for(int j=0;i+j<=n;j++)
            if(s.substr(i,j).find('5') != string::npos) ans++;
        cout<<ans<<'\n';
        return 0;
    }
    
    

    中间两个测试点:

    这两个测试点是提示正解的。如果所有字符均为'5',则总数量是\(n*(n+1)/2\)。

    200pts:

    让我们反向考虑,不符合条件的子串有多少?
    其起止点应当都位于两个'5'的中间,所以,只需要减去这些子串即可。
    例如,54445应当有\(5*6/2 - 3*4/2 = 9\)个符合条件的子串。

    Code:

    #include<bits/stdc++.h>
    using namespace std;
    using ll = long long;
    int main()
    {
        string s;cin>>s; 
        ll n = s.length();
        vector<ll> v = {-1}; 
        for(int i=0;i<s.length();i++) if(s[i]=='5') v.push_back(i);
        ll ans = n*(n+1)/2; //记录总个数 
        v.push_back(n);
        for(int i=1;i<v.size();i++) ans-=(v[i]-v[i-1])*(v[i]-v[i-1]-1)/2; // 减去两个'5'之间的子串个数。 
        cout<<ans<<'\n';
    }
    
    
  • 1

信息

ID
1290
难度
7
分类
(无)
标签
递交数
188
已通过
32
通过率
17%
被复制
2
上传者