2019牛客暑期多校训练营(第八场) Distance
题意: 给你一个 $n* m* h$ 的空间，每次插入一个点，或者询问空间中点到这一点的最小曼哈顿距离。
题解:
1.HASH+三维BIT
三维BIT，对于这种写法，太巨了，$n * m * h < 1e5$ 特么直接用三维BIT 存一下就可以了，枚举八个方向，把绝对值去掉，然后最牛的还是hash处理，把三维压缩成一维，削常数，我特么卡常卡成这样也是少见。
这种hash将维度，枚举八个方向去绝对值，数组数组模拟空间，还是挺6的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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
const LL mod = (LL) 1e9 + 7;
const int maxn = (int) 1e6 + 5;
const LL INF = 0x7fffffff;
const LL inf = 0x3f3f3f3f;
const double eps = 1e-8;
clock_t prostart = clock();
void f() {
freopen("../data.in", "r", stdin);
}
//typedef __int128 LLL;
template<typename T>
void read(T &w) {//读入
char c;
while (!isdigit(c = getchar()));
w = c & 15;
while (isdigit(c = getchar()))
w = w * 10 + (c & 15);
}
template<typename T>
void output(T x) {
if (x < 0)
putchar('-'), x = -x;
int ss[55], sp = 0;
do
ss[++sp] = x % 10;
while (x /= 10);
while (sp)
putchar(48 + ss[sp--]);
}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
struct BIT {
int n, m, h;
int a[maxn];
void init(int n, int m, int h) {
this->n = n;
this->m = m;
this->h = h;
mem(a, -inf);
}
int get(int x, int y, int z) {
return x * h * m + y * h + z;
}
int lowbit(int &x) {
return x & (-x);
}
void add(int x, int y, int z, int t) {
for (int i = x; i <= n; i += lowbit(i))
for (int j = y; j <= m; j += lowbit(j))
for (int k = z; k <= h; k += lowbit(k)) a[get(i, j, k)] = max(a[get(i, j, k)], t);
}
int sum(int x, int y, int z) {
int res = -inf;
for (int i = x; i; i -= lowbit(i))
for (int j = y; j; j -= lowbit(j))
for (int k = z; k; k -= lowbit(k))
res = max(a[get(i, j, k)], res);
return res;
}
} b[8];
int get_pos(int x, int pos) {
return (x >> pos) & 1;
}
int main() {
f();
int n, m, h, q;
int op;
read(n);
read(m);
read(h);
read(q);
for (int i = 0; i < 8; i++) {
b[i].init(n, m, h);
}
int d[] = {n + 1, m + 1, h + 1};
int a[3], c[3];
while (q--) {
read(op);
read(a[0]);
read(a[1]);
read(a[2]);
if (op == 1) {
for (int i = 0; i < 8; i++) {
c[0] = get_pos(i, 0) ? d[0] - a[0] : a[0];
c[1] = get_pos(i, 1) ? d[1] - a[1] : a[1];
c[2] = get_pos(i, 2) ? d[2] - a[2] : a[2];
b[i].add(c[0], c[1], c[2], c[1] + c[2] + c[0]);
}
} else {
int ans = inf;
for (int i = 0; i < 8; i++) {
c[0] = get_pos(i, 0) ? d[0] - a[0] : a[0];
c[1] = get_pos(i, 1) ? d[1] - a[1] : a[1];
c[2] = get_pos(i, 2) ? d[2] - a[2] : a[2];
ans = min(ans, c[0] + c[1] + c[2] - b[i].sum(c[0], c[1], c[2]));
}
output(ans);
puts("");
}
}
cout << "运行时间:" << 1.0 * (clock() - prostart) / CLOCKS_PER_SEC << " s" << endl;
return 0;
}
2.分块+bfs
第二种写法就更骚了Orz,对于 $1e5$ 组查询，分成$\sqrt{(1e5)}$ 块，每次插入一个点，先判断有没有$\sqrt{(1e5)}$个，少于这个数量，直接暴力找，假设就算每次都是满的都是 $\sqrt{(1e5)} * 1e5$ 的复杂度，然后如果满了，直接空间中bfs,比如说你插入了两个点,0,0,1 0,0,2,直接暴力bfs,枚举6个方向,找离这个点最近的距离是多少。暴力枚举空间复杂度是$O(n * m * h)$.总复杂度就是 $q*\sqrt{q}+\sqrt{n * m * h} * q$.
这种分块更新的操作，学不来，学不来，根本学不来。
1 |
|