E

76与61

https://ac.nowcoder.com/acm/contest/83181/E

E

先看数据10^5

alt

排除O(n^2)和O(n^3),想一想如何遍历一遍得出答案? 761只有3位数,我们先考虑中间的6。 用map先存一下6的下标,用前缀和记录7和1。 然后遍历一遍map,得出答案。

using namespace std;
const int N = 1e5 + 10;
int ans;
string s;
unordered_map<int, int>arr6;
int sum1[N];
int sum7[N];

int main(void)
{
    getline(cin, s);

    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '6')
            arr6[i + 1] = 1;
        if (s[i] == '1')
            sum1[i + 1] = sum1[i] + 1;
        else sum1[i + 1] = sum1[i];
         if (s[i] == '7')
            sum7[i + 1] = sum7[i] + 1;
        else sum7[i + 1] = sum7[i];
    }

    long long ans = 0;
    for (auto u : arr6)
    {
       ans+=(sum7[u.first]-sum7[0])*(sum1[s.size()]-sum1[u.first]);
    }
    cout << ans;
}

全部评论

相关推荐

点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务