Codeforces Round #585 (Div. 2)

B. The Number of Products 递推:ne[i]表示以ai结尾的负区间个数,po[i]表示以ai结尾的负区间个数 ``` /**/ #include #include #include #include #include #include #include #include #include #include #include #include

typedef long long LL;
typedef unsigned long long ULL;
using namespace std;

bool Sqrt(LL n) { return (LL)sqrt(n) * sqrt(n) == n; }
const double PI = acos(-1.0), ESP = 1e-10;
const LL INF = 99999999999999;
const int inf = 999999999, N = 2e5 + 24;
int n;
LL a[N], po[N], ne[N];

int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
while(scanf("%d", &n) == 1) {
for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
memset(po, 0, sizeof po);
memset(ne, 0, sizeof ne);
if(a[0] < 0) ne[0] = 1;
else po[0] = 1;
for(int i = 1; i < n; i++) {
if(a[i] < 0) {
po[i] = ne[i - 1];
ne[i] = po[i - 1] + 1;
}
else {
po[i] = po[i - 1] + 1;
ne[i] = ne[i - 1];
}
}
for(int i = 0; i < n; i++) {
po[n] += po[i];
ne[n] += ne[i];
}
printf("%lld %lld ", ne[n], po[n]);
}

return 0;

}
/*
input:
output:
modeling:
methods:
complexity:
summary:
*/

原文地址:https://www.cnblogs.com/000what/p/12229358.html