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

全部评论

相关推荐

11-28 17:58
门头沟学院 Java
美团 JAVA开发 n×15.5
牛客786276759号:百度现在晋升很难的 而且云这块的业务没美团好 你看百度股价都跌成啥样了
点赞 评论 收藏
分享
10-30 10:16
南京大学 Java
永远的鹅孝子:给南大✌️跪了
点赞 评论 收藏
分享
头像
11-06 10:58
已编辑
门头沟学院 嵌入式工程师
双非25想找富婆不想打工:哦,这该死的伦敦腔,我敢打赌,你简直是个天才,如果我有offer的话,我一定用offer狠狠的打在你的脸上
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务