CodeForces585 B tutorial 详解_算法日常[28/100]

题目链接

CodeForces585 B

题意

  • 给你一串非0的正负整数串
  • 定义[l,r]为$a_l$和$a_r$之间所有元素之积是正数还是负数
  • 求串中所有的负数pair的个数和整数pair的个数

题解

  • 记录负数对之间的元素个数cnt1,和奇数个负数个数间的元素个数cnt2
  • 然后通过当下元素的添加,只会新产生当下元素为右括号的pair,这样就可以dp叠加了
  • 具体的看代码中的详细注释吧

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/* 
大佬tutorial的代码
*/

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 200 * 1000 + 13;

int n;
int a[N];

inline void read() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
}

inline void solve() {
int pos = -1;
ll ans0 = 0;
// 题目给的是a[i]!=0,大佬还要特地考虑一下鲁棒性
for (int i = 0; i < n; i++) {
if (a[i] == 0) {
pos = i;
}
if (pos != -1) {
ans0 += pos + 1;
}
}
// bal是负数的个数,cnt1标识前面负数的对数,cnt2标识前面的正数的个数
// ansP是正产的个数,负产个数可以直接用总的pair数减去ansP得到

// cnt1其实是偶数对之前的所有元素的个数,比如-1 1 -1 `1 1 1` -1 -1 这样cnt1=3
// cnt2同理就是奇数个负数之间的个数,这些都是为了后面的计算!所以上面的例子cnt2=1
// 太精妙了!
int cnt1 = 0, cnt2 = 0;
int bal = 0;
ll ansP = 0;
for (int i = 0; i < n; i++) {
if (a[i] == 0) {
cnt1 = 0, cnt2 = 0, bal = 0;
continue;
}
if (bal % 2 == 0) {
cnt1++;
} else {
cnt2++;
}
if (a[i] < 0) {
bal++;
}
// 这里之所以可以这样加tutorial没说,其实是因为每次新加入之后
// 新产生的pair一定是以a[i]作为右endpos的!所以可以这样加!

// 到了a[i]后总负数个数是偶数,所以加所有偶数对间的cnt1值,
// 可以心想一下a[i]为正或者负的时候 bal达到偶数值时的状态就懂了
if (bal % 2 == 0) {
ansP += cnt1;
} else {
ansP += cnt2;
}
}
cout << n * 1ll * (n + 1) / 2 - ans0 - ansP << ' ' << ansP << endl;
}

int main () {
#ifdef fcspartakm
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
srand(time(NULL));
cerr << setprecision(10) << fixed;

read();
solve();

return 0;
//cerr << "TIME: " << clock() << endl;
}

故事

这场比赛B,C都是1500分,然后我当时不会做B,所以写了B的题解,记录自己不太会的,会的就不记录了

每天一句叨叨

每个人都有潜在的能量,只是很容易:被习惯所掩盖,被时间所迷离,被惰性所消磨。