这能评蓝？
我们需要查询原数组里面有多少对数满足无法进位，首先把不到 7 位的数高位全部补上 0，假设这个数的第 k 位为 ai,k，那么满足条件的数 j 就必须满足所有的 k 都 aj,k≤9−ai,k。于是这题就转化成了一个前缀和问题，但是有 7 维。
这里我选择了无脑写一个树状数组解决，时间复杂度 O(n×log710)，发现 atcoder 神机 4 秒轻轻松松就能过。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
struct fenwick
{
int bit[11][11][11][11][11][11][11];
void init() {
memset(bit, 0, sizeof(bit));
}
int lowbit(int x) {
return x & (-x);
}
void update(vector<int> v, int k) {
for (int i1 = v[0] + 1; i1 < 11; i1 += lowbit(i1)) {
for (int i2 = v[1] + 1; i2 < 11; i2 += lowbit(i2)) {
for (int i3 = v[2] + 1; i3 < 11; i3 += lowbit(i3)) {
for (int i4 = v[3] + 1; i4 < 11; i4 += lowbit(i4)) {
for (int i5 = v[4] + 1; i5 < 11; i5 += lowbit(i5)) {
for (int i6 = v[5] + 1; i6 < 11; i6 += lowbit(i6)) {
for (int i7 = v[6] + 1; i7 < 11; i7 += lowbit(i7)) {
bit[i1][i2][i3][i4][i5][i6][i7] += k;
}
}
}
}
}
}
}
}
int query(vector<int> v) {
int res = 0;
for (int i1 = v[0] + 1; i1 > 0; i1 -= lowbit(i1)) {
for (int i2 = v[1] + 1; i2 > 0; i2 -= lowbit(i2)) {
for (int i3 = v[2] + 1; i3 > 0; i3 -= lowbit(i3)) {
for (int i4 = v[3] + 1; i4 > 0; i4 -= lowbit(i4)) {
for (int i5 = v[4] + 1; i5 > 0; i5 -= lowbit(i5)) {
for (int i6 = v[5] + 1; i6 > 0; i6 -= lowbit(i6)) {
for (int i7 = v[6] + 1; i7 > 0; i7 -= lowbit(i7)) {
res += bit[i1][i2][i3][i4][i5][i6][i7];
}
}
}
}
}
}
}
return res;
}
};
signed main()
{
int n;
cin >> n;
int ans = 0;
fenwick bit;
bit.init();
for (int i = 0; i < n; i++) {
int x;
cin >> x;
vector<int> v;
int tp = x;
for (int j = 0; j < 7; j++) {
v.push_back(tp % 10);
tp /= 10;
}
ans += bit.query({9 - v[0], 9 - v[1], 9 - v[2], 9 - v[3], 9 - v[4], 9 - v[5], 9 - v[6]});
bit.update(v, 1);
}
cout << ans;
return 0;
}
|
