牛客-F.牛牛的Link Power I - TT3E
牛客-F.牛牛的Link Power I
题目链接:[https://ac.nowcoder.com/acm/contest/3004/F]
第一种做法
统计每个位置产生的贡献，不只是1，包括0的位置，如下
0的位置上的贡献等于前面位置上的贡献+前面1的个数，这样，我们如果遇到了1，我们就累加到答案中。这样的好处是我们不需要再开一个变量，记录1和1之间隔了多少个位置，然后再统计这个位置上的贡献等于前面的贡献加上这个变量乘以前面1的个数。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
const long long mod = 1e9 + 7;
char s[MAXN];
int n;
long long sum, cnt, ans;
int main()
{
scanf("%d", &n);
scanf("%s", s + 1);
for (int i = 1; i <= n; ++i)
{
sum = (sum + cnt) % mod;
if (s[i] == \'1\')
{
ans = (ans + sum) % mod;
++cnt;
}
}
printf("%lld\n", ans);
return 0;
}
另一种做法，记录1和1之间的距离
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
const int N = 100005;
char str[N];
int p[N];
int sum[N];
int main()
{
int n;
scanf("%d", &n);
scanf("%s", str + 1);
//前面1的个数，当前1和之前的距离
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; ++i)
{
sum[i] = sum[i - 1];
if (str[i] == \'0\')
{
++cnt2;
p[i] = p[i - 1];
}
else
{
++cnt2;
p[i] = (p[i - 1] + cnt1 * cnt2) % mod;
sum[i] = (sum[i] + p[i]) % mod;
cnt2 = 0;
++cnt1;
}
}
cout << sum[n] << endl;
return 0;
}
版权声明：本文为pixel-Teee原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。