E
76与61
https://ac.nowcoder.com/acm/contest/83181/E
E
先看数据10^5
排除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;
}