T1 假期计划
题目大意
规定
d
i
s
(
x
,
y
)
dis(x, y)
d
i
s
(
x
,
y
)
表示一张图上点
x
x
x
到
y
y
y
的最短距离。
给定一张无向图（图上所有边的边权都是
1
1
1
，并且给定图上每一个点一个点权记为
v
a
l
u
e
x
value_x
v
a
l
u
e
x
），让你选定
4
4
4
个图上的点
a
,
b
,
c
,
d
a, b, c, d
a
,
b
,
c
,
d
，使得
d
i
s
(
1
,
a
)
,
d
i
s
(
a
,
b
)
,
d
i
s
(
b
,
c
)
,
d
i
s
(
c
,
d
)
dis(1, a), dis(a, b), dis(b, c), dis(c, d)
d
i
s
(
1
,
a
)
,
d
i
s
(
a
,
b
)
,
d
i
s
(
b
,
c
)
,
d
i
s
(
c
,
d
)
和
d
i
s
(
d
,
1
)
dis(d, 1)
d
i
s
(
d
,
1
)
都小于等于
k
+
1
k + 1
k
+
1
。并且要求
v
a
l
u
e
a
+
v
a
l
u
e
b
+
v
a
l
u
e
c
+
v
a
l
u
e
d
value_a + value_b + value_c + value_d
v
a
l
u
e
a
+
v
a
l
u
e
b
+
v
a
l
u
e
c
+
v
a
l
u
e
d
最小。
分析
首先发现点数比较小，甚至可以
O
(
n
2
)
O(n^2)
O
(
n
2
)
，所以我们可以直接对于每一个点
x
x
x
暴力
b
f
s
(
x
)
bfs(x)
b
f
s
(
x
)
求出
x
x
x
到其他节点的最短路径长度。
然后如果考虑暴力，那么就可以直接枚举
4
4
4
个点然后判断能否符合条件（就是
d
i
s
(
x
,
y
)
dis(x, y)
d
i
s
(
x
,
y
)
是否小于等于
k
+
1
k + 1
k
+
1
），就可以暴力统计答案了，但是这样复杂度
O
(
n
4
)
O(n^4)
O
(
n
4
)
显然爆炸，所以我们要考虑优化一下这个做法。
我们考虑只枚举
b
,
c
b, c
b
,
c
这两个点，因为我们发现
a
a
a
点对于
b
b
b
点来说和
d
d
d
点对于
c
c
c
点来说约束条件是一样的，具体来说就是：
-
对于
a,
b
a, b
a
,
b
来说，
aa
a
的约束条件是
di
s
(
1
,
a
)
≤
k
+
1
∧
d
i
s
(
a
,
b
)
≤
k
+
1
dis(1, a) \le k + 1 \land dis(a, b) \le k + 1
d
i
s
(
1
,
a
)
≤
k
+
1
∧
d
i
s
(
a
,
b
)
≤
k
+
1
-
对于
d,
c
d, c
d
,
c
来说，
dd
d
的约束条件是
di
s
(
1
,
d
)
≤
k
+
1
∧
d
i
s
(
d
,
c
)
≤
k
+
1
dis(1, d) \le k + 1 \land dis(d, c) \le k + 1
d
i
s
(
1
,
d
)
≤
k
+
1
∧
d
i
s
(
d
,
c
)
≤
k
+
1
这俩玩意儿是不是长得一模一样，所以我们考虑对于每一个点
x
x
x
预处理出另一个点
y
y
y
使得
y
y
y
满足
d
i
s
(
1
,
y
)
≤
k
+
1
∧
d
i
s
(
x
,
y
)
≤
k
+
1
dis(1, y) \le k + 1 \land dis(x, y) \le k + 1
d
i
s
(
1
,
y
)
≤
k
+
1
∧
d
i
s
(
x
,
y
)
≤
k
+
1
，且
v
a
l
u
e
y
value_y
v
a
l
u
e
y
取到最大值，这里记录这样的
y
y
y
为
f
x
f_x
f
x
。这个预处理显然是
O
(
n
2
)
O(n^2)
O
(
n
2
)
的，然后再枚举点
b
b
b
和
c
c
c
，然后直接然后直接用
v
a
l
u
e
b
+
v
a
l
u
e
c
+
v
a
l
u
e
f
b
+
v
a
l
u
e
f
c
value_b + value_c + value_{f_b} + value_{f_c}
v
a
l
u
e
b
+
v
a
l
u
e
c
+
v
a
l
u
e
f
b
+
v
a
l
u
e
f
c
作为本次的答案，每次取
max
\max
max
就好了。
但是这样做会有一个问题，可能发现我们求到的
f
b
f_{b}
f
b
和
f
c
f_c
f
c
是同一个点，这样就与题目意思不符了，所以我们还需要高出次大的点，记为
s
b
s_b
s
b
和
s
c
s_c
s
c
。
但是这样还是有一个问题，我们发现你有可能
f
b
=
c
f_b = c
f
b
=
c
且
f
c
=
b
f_c = b
f
c
=
b
并且
s
b
=
s
c
s_b = s_c
s
b
=
s
c
这样就又不行了，所以我们需要再弄出第三大值
t
b
,
t
c
t_b, t_c
t
b
,
t
c
，这样就一定是正确的了，具体的操作可以看代码。
代码
#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 3030
#define MAXM 100100
#define int long long
const int INFI = 1e18;
inline int read(){
int x = 0; char c = getchar();
while(c < '0' or c > '9') c = getchar();
while('0' <= c and c <= '9')
x = x * 10 + c - '0', c = getchar();
return x;
}
int n = 0, m = 0, k = 0;
int tot = 0;
int first[MAXN] = { 0 };
int nxt[MAXM] = { 0 };
int to[MAXM] = { 0 };
int value[MAXN] = { 0 };
inline void add(int x, int y){
nxt[++tot] = first[x];
first[x] = tot, to[tot] = y;
}
int dis[MAXN][MAXN] = { 0 };
queue<int> q;
void bfs(int st){
while(!q.empty()) q.pop();
for(int i = 1; i <= n; i++) dis[st][i] = INFI;
q.push(st); dis[st][st] = 0;
while(!q.empty()){
int x = q.front(); q.pop();
for(int e = first[x]; e; e = nxt[e]){
int y = to[e];
if(dis[st][y] == INFI) dis[st][y] = dis[st][x] + 1, q.push(y);
}
}
}
int f[MAXN] = { 0 }; // 最大值
int s[MAXN] = { 0 }; // 次大值
int t[MAXN] = { 0 }; // 第三大值
void prework(){ // 对于每一个 c 选出最大的 d
for(int c = 2; c <= n; c++)
for(int d = 2; d <= n; d++){
if(c == d) continue;
if(dis[1][d] <= k and dis[d][c] <= k){
if(value[d] > value[f[c]]) t[c] = s[c], s[c] = f[c], f[c] = d;
else{
if(value[d] > value[s[c]]) t[c] = s[c], s[c] = d;
else if(value[d] > value[t[c]]) t[c] = d;
}
}
}
}
inline bool can(int a, int b, int c, int d) { return a != d and a != c and d != b and a and d; }
void solve(){
int ans = 0;
for(int b = 2; b <= n; b++)
for(int c = b + 1, a, d; c <= n; c++){
if(dis[b][c] > k) continue;
/* 这里懒得分类讨论，所以直接每都看可不可行然后取 max 作为答案 */
a = f[b], d = f[c];
if(can(a, b, c, d)) ans = max(ans, value[a] + value[b] + value[c] + value[d]);
a = f[b], d = s[c];
if(can(a, b, c, d)) ans = max(ans, value[a] + value[b] + value[c] + value[d]);
a = f[b], d = t[c];
if(can(a, b, c, d)) ans = max(ans, value[a] + value[b] + value[c] + value[d]);
a = s[b], d = f[c];
if(can(a, b, c, d)) ans = max(ans, value[a] + value[b] + value[c] + value[d]);
a = s[b], d = s[c];
if(can(a, b, c, d)) ans = max(ans, value[a] + value[b] + value[c] + value[d]);
a = s[b], d = t[c];
if(can(a, b, c, d)) ans = max(ans, value[a] + value[b] + value[c] + value[d]);
a = t[b], d = f[c];
if(can(a, b, c, d)) ans = max(ans, value[a] + value[b] + value[c] + value[d]);
a = t[b], d = s[c];
if(can(a, b, c, d)) ans = max(ans, value[a] + value[b] + value[c] + value[d]);
a = t[b], d = t[c];
if(can(a, b, c, d)) ans = max(ans, value[a] + value[b] + value[c] + value[d]);
}
cout << ans << '\n';
}
signed main(){
// freopen("a.in", "r", stdin);
n = in, m = in, k = in; k++;
for(int i = 2; i <= n; i++) value[i] = in;
for(int i = 1; i <= m; i++){
int x = in, y = in;
add(x, y), add(y, x);
}
for(int i = 1; i <= n; i++) bfs(i);
prework(); solve();
return 0;
}
T2
题目大意
给定两个数组
a
a
a
和
b
b
b
，长度分别为
n
,
m
n, m
n
,
m
，现在有
q
q
q
个询问，每次询问给出
l
1
,
r
1
,
l
2
,
r
2
l_1, r_1, l_2, r_2
l
1
,
r
1
,
l
2
,
r
2
，每次询问假定有两个人在进行博弈，甲需要在
a
[
l
1
∼
r
1
]
a[l_1 \sim r_1]
a
[
l
1
∼
r
1
]
中选出一个数字
x
x
x
，乙需要在
b
[
l
2
∼
r
2
]
b[l_2\sim r_2]
b
[
l
2
∼
r
2
]
中选出一个数字
y
y
y
，最终得分就是
x
y
xy
x
y
，甲的目的是让最终得分尽量大，乙则希望他尽量小，并且甲乙两个人都足够聪明，每次询问输出最后应该得出的答案。
分析
粗略想一下应该是区间最值（线段树就好了），但是又有正负值之分，如果甲选了区间最大，并且最大是正值，乙选了区间最小，并且最小是负值，这样显然对甲不利，所以甲应该要选一个负数？再想想应该也不太对，因为如果甲选择负数的话乙就可以选一个最大的正数让答案最小。
思考到这里发现好像分正负值分类讨论有一点困难，所以我们考虑分
16
16
1
6
种情况把所有的可能性都列举出来，具体来说也就是：
-
aa
a
中非负数的最小值
和
bb
b
中非负数的最小值
的乘积 -
aa
a
中非负数的最小值
和
bb
b
中非负数的最大值
的乘积 -
aa
a
中非负数的最小值
和
bb
b
中非正数的最小值
的乘积 -
aa
a
中非负数的最小值
和
bb
b
中非正数的最大值
的乘积 -
aa
a
中非负数的最大值
和
bb
b
中非负数的最小值
的乘积 -
aa
a
中非负数的最大值
和
bb
b
中非负数的最大值
的乘积 -
aa
a
中非负数的最大值
和
bb
b
中非正数的最小值
的乘积 -
aa
a
中非负数的最大值
和
bb
b
中非正数的最大值
的乘积 -
aa
a
中非正数的最小值
和
bb
b
中非负数的最小值
的乘积 -
aa
a
中非正数的最小值
和
bb
b
中非负数的最大值
的乘积 -
aa
a
中非正数的最小值
和
bb
b
中非正数的最小值
的乘积 -
aa
a
中非正数的最小值
和
bb
b
中非正数的最大值
的乘积 -
aa
a
中非正数的最大值
和
bb
b
中非负数的最小值
的乘积 -
aa
a
中非正数的最大值
和
bb
b
中非负数的最大值
的乘积 -
aa
a
中非正数的最大值
和
bb
b
中非正数的最小值
的乘积 -
aa
a
中非正数的最大值
和
bb
b
中非正数的最大值
的乘积
这样就可以把所有的情况都考虑进去了。然后只需要在最后选出满足条件的答案就好了。
现在问题又来了，怎么选出满足条件的答案呢？现在我们把这些情况先列出来一下看看（下面的
a
p
m
i
n
apmin
a
p
m
i
n
就表示
a
a
a
中非负数的最小值，
b
n
m
a
x
bnmax
b
n
m
a
x
就表示
b
b
b
中非正数的最大值）：
|
apmin = x 1 x_1 x 1 |
apmax = x 2 x_2 x 2 |
anmin = x 3 x_3 x 3 |
anmax = x 4 x_4 x 4 |
|
|---|---|---|---|---|
|
bpmin = y 1 y_1 y 1 |
x 1 y 1 x_1y_1 x 1 y 1 |
x 2 y 1 x_2y_1 x 2 y 1 |
x 3 y 1 x_3y_1 x 3 y 1 |
x 4 y 1 x_4y_1 x 4 y 1 |
|
bpmax = y 2 y_2 y 2 |
x 1 y 2 x_1y_2 x 1 y 2 |
x 2 y 2 x_2y_2 x 2 y 2 |
x 3 y 2 x_3y_2 x 3 y 2 |
x 4 y 2 x_4y_2 x 4 y 2 |
|
bnmin = y 3 y_3 y 3 |
x 1 y 3 x_1y_3 x 1 y 3 |
x 2 y 3 x_2y_3 x 2 y 3 |
x 3 y 3 x_3y_3 x 3 y 3 |
x 4 y 3 x_4y_3 x 4 y 3 |
|
bnmax = y 4 y_4 y 4 |
x 1 y 4 x_1y_4 x 1 y 4 |
x 2 y 4 x_2y_4 x 2 y 4 |
x 3 y 4 x_3y_4 x 3 y 4 |
x 4 y 4 x_4y_4 x 4 y 4 |
我们先观察一列，发现这里的
x
x
x
都是一样的，所以我们只需要取出这一列中
x
y
i
xy_i
x
y
i
的最小值作为这一列的答案，再把这四列的答案取最大值得到最后的答案即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
#define in read()
#define MAXN 100100
const int INFI = 1e18;
inline int read() {
int x = 0, f = 0; char c = getchar();
while(c < '0' or c > '9') {
if(c == '-') f = 1; c = getchar();}
while('0' <= c and c <= '9')
x = x * 10 + c - '0', c = getchar();
return f ? -x : x;
}
int a[MAXN] = { 0 };
int b[MAXN] = { 0 };
int n = 0, m = 0, q = 0;
struct SegmentTreemin{
struct Tnode { int l, r, dat; };
int arr[MAXN];
Tnode t[MAXN << 2];
inline void up(int p) { t[p].dat = min(t[ls(p)].dat, t[rs(p)].dat); }
void build(int p, int l, int r){
t[p].l = l, t[p].r = r;
if(l == r) { t[p].dat = arr[l]; return; }
int mid = l + r >> 1;
build(ls(p), l, mid); build(rs(p), mid + 1, r);
up(p);
}
int query(int p, int l, int r){
if(l <= t[p].l and t[p].r <= r) return t[p].dat;
int mid = t[p].l + t[p].r >> 1, ans = INFI;
if(l <= mid) ans = min(ans, query(ls(p), l, r));
if(r > mid) ans = min(ans, query(rs(p), l, r));
return ans;
}
}Tapmin, Tanmin, Tbpmin, Tbnmin;
struct SegmentTreemax{
struct Tnode { int l, r, dat; };
int arr[MAXN];
Tnode t[MAXN << 2];
inline void up(int p) { t[p].dat = max(t[ls(p)].dat, t[rs(p)].dat); }
void build(int p, int l, int r){
t[p].l = l, t[p].r = r;
if(l == r) { t[p].dat = arr[l]; return; }
int mid = l + r >> 1;
build(ls(p), l, mid); build(rs(p), mid + 1, r);
up(p);
}
int query(int p, int l, int r){
if(l <= t[p].l and t[p].r <= r) return t[p].dat;
int mid = t[p].l + t[p].r >> 1, ans = -INFI;
if(l <= mid) ans = max(ans, query(ls(p), l, r));
if(r > mid) ans = max(ans, query(rs(p), l, r));
return ans;
}
}Tapmax, Tanmax, Tbpmax, Tbnmax;
void init(){
for(int i = 1; i <= max(n, m); i++)
Tapmin.arr[i] = Tanmin.arr[i] = Tbpmin.arr[i] = Tbnmin.arr[i] = INFI;
for(int i = 1; i <= max(n, m); i++)
Tapmax.arr[i] = Tanmax.arr[i] = Tbpmax.arr[i] = Tbnmax.arr[i] = -INFI;
for(int i = 1; i <= n; i++){
if(a[i] >= 0) Tapmin.arr[i] = Tapmax.arr[i] = a[i]; // 非负数
if(a[i] <= 0) Tanmin.arr[i] = Tanmax.arr[i] = a[i]; // 非正数
}
for(int i = 1; i <= m; i++){
if(b[i] >= 0) Tbpmin.arr[i] = Tbpmax.arr[i] = b[i]; // 非负数
if(b[i] <= 0) Tbnmin.arr[i] = Tbnmax.arr[i] = b[i]; // 非正数
}
Tapmin.build(1, 1, n), Tapmax.build(1, 1, n), Tanmin.build(1, 1, n), Tanmax.build(1, 1, n);
Tbpmin.build(1, 1, m), Tbpmax.build(1, 1, m), Tbnmin.build(1, 1, m), Tbnmax.build(1, 1, m);
}
int solve(int x, int l2, int r2){
int y = INFI;
int t1 = Tbpmin.query(1, l2, r2); // b+min
int t2 = Tbpmax.query(1, l2, r2); // b+max
int t3 = Tbnmin.query(1, l2, r2); // b-min
int t4 = Tbnmax.query(1, l2, r2); // b-max
if(abs(t1) != INFI) y = min(y, x * t1);
if(abs(t2) != INFI) y = min(y, x * t2);
if(abs(t3) != INFI) y = min(y, x * t3);
if(abs(t4) != INFI) y = min(y, x * t4);
return y;
}
int solve(int l1, int r1, int l2, int r2){
int x = 0, y = INFI, ans = -INFI;
x = Tapmin.query(1, l1, r1);
if(abs(x) != INFI) ans = max(ans, solve(x, l2, r2));
x = Tapmax.query(1, l1, r1);
if(abs(x) != INFI) ans = max(ans, solve(x, l2, r2));
x = Tanmin.query(1, l1, r1);
if(abs(x) != INFI) ans = max(ans, solve(x, l2, r2));
x = Tanmax.query(1, l1, r1);
if(abs(x) != INFI) ans = max(ans, solve(x, l2, r2));
return ans;
}
signed main(){
n = in, m = in, q = in;
for(int i = 1; i <= n; i++) a[i] = in;
for(int i = 1; i <= m; i++) b[i] = in;
init();
while(q--){
int l1 = in, r1 = in, l2 = in, r2 = in;
cout << solve(l1, r1, l2, r2) << '\n';
}
return 0;
}
T3
T4