2018.9.21校内测试

解题报告—9.21


$\text{T1}$ 相遇


反思

T1 考到了 LCA,之前觉得没必要学,虽然也看过些文章,但大部分都没看懂,所以一直都不会,结果今天出上了这样的一道题,真尴尬,想着写写暴力吧,发现暴力也是求 LCA,无奈,遂放弃,考完试的下午就开始学 LCA,以后有能力学的东西尽量学学,不能老想着偷懒。

解题思路

画几个图会发现 $a\rightarrow b,c\rightarrow d$ 两条路径如果能够相交的话,需要满足其中一对点的 $\text{LCA}$ 在另两个点之间的路径上。

而一个点 $x$ 在一条路径 $s\rightarrow t$ 上的充要条件是如下:

  • $depth[\text{LCA}(s,t)]\le depth[x]$
  • $\text{LCA}(x,s)=x \ ||\ \text{LCA}(x,t)=x$

然后我们就可以做 $\text{LCA}$ 进行求解,一组数据最多询问 $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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn = 2e5+3;
int n, head[maxn], cnt, depth[maxn], T, fa[maxn][32], m;
struct edge {
int to, nxt;
}ed[maxn], tmp;
struct P100 {
inline void reset() {
cnt = 0;
tmp.to = tmp.nxt = 0;
fill(ed+1, ed+1+maxn-3, tmp);
memset(head, 0, sizeof(head));
memset(depth, 0, sizeof(depth));
memset(fa, 0, sizeof(fa));
}
inline void addedge(int x, int y) {
ed[++cnt].nxt = head[x], head[x] = cnt, ed[cnt].to = y;
ed[++cnt].nxt = head[y], head[y] = cnt, ed[cnt].to = x;
}
inline void init() {
for(int j=1; 1<<j<=n; j++)
for(int i=1; i<=n; i++)
fa[i][j] = fa[fa[i][j-1]][j-1];
}
inline void dfs(int u) {
for(int i=head[u]; i; i=ed[i].nxt) {
if(ed[i].to == fa[u][0]) continue;
fa[ed[i].to][0] = u;
depth[ed[i].to] = depth[u] + 1;
dfs(ed[i].to);
}
}
inline int lca(int a, int b) {
if(depth[a] > depth[b]) swap(a, b);
int h = depth[b] - depth[a];
for(int i=0; 1<<i<=h; i++)
if((1<<i)&h) b = fa[b][i];
if(a != b) {
for(int i=(int)log2(n); i>=0; i--) {
if(fa[a][i] != fa[b][i])
a = fa[a][i], b = fa[b][i];
}
a = fa[a][0];
}
return a;
}
inline void solve() {
dfs(1);
init();
}
inline bool judge(int a, int b, int c, int d) {
int x = lca(a, b), y = lca(c, d);
if(depth[x] < depth[y]) swap(x, y), swap(a, c), swap(b, d);
if(lca(x, c) == x || lca(x, d) == x) return true;
return false;
}
}p100;
int main() {
freopen("railway.in", "r", stdin);
freopen("railway.out", "w", stdout);
scanf("%d", &T);
while (T--) {
p100.reset();
scanf("%d%d", &n, &m);
int x, y;
for(int i=1; i<n; i++) {
scanf("%d%d", &x, &y);
p100.addedge(x, y);
}
p100.solve();
int a, b, c, d;
for(int i=1; i<=m; i++) {
scanf("%d%d%d%d", &a, &b, &c, &d);
if(p100.judge(a, b, c, d)) printf("YES\n");
else printf("NO\n");
}
}
fclose(stdin);
fclose(stdout);
}

$\text{T2}$ 计数


反思

不开 long long 见祖宗,写了个 $60$ 分的暴力,因为没开 long long 所以 WA 成了 30 分,以后做题先看好数据范围,可以为了以防万一,能开 long long 就开 long long

解题思路

在考场上写了个线段树维护区间最大最小值。然后 $N^2$ 枚举,左右端点,求和。算上查询的时间是 $\log N$ 总时间复杂度为 $N^2\log N$ 可以过 60 分。

再说正解:

题目大意可以简化为求下面这个式子的值:
$$
\sum_{r=1}^{n}\sum_{l=1}^{r}max(a[x]-a[y],l\le x,y\le r)
$$
观察上面的式子,其实可以从 $1\rightarrow n$ 算出每个数对答案的影响,相加就是答案。

那么怎么算贡献呢。用单调栈维护,一个点被弹出后就将其贡献减去,被压入后,就将其贡献加上。

求作为最大值的贡献和求作为最小值的贡献其实差不多,求最小值时将数组变成负数就又变成了求最大值的问题。

所以可以用一个函数解决。

代码

60 分

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 1e5+3, inf = 2147483647;
typedef long long LL;
LL T, n, a[maxn];
struct Tree {
LL l, r, mx, mn;
}tree[400003], tmp;
LL ans_mn = inf, ans_mx;
struct P60 {
inline void init() {
tmp.l = tmp.r = tmp.mx = 0;
tmp.mn = inf;
fill(tree+1, tree+400001, tmp);
}
inline void build(int k, int ll, int rr) {
tree[k].l = ll, tree[k].r = rr;
if(ll == rr) {
scanf("%d", &tree[k].mn);
tree[k].mx = tree[k].mn;
return ;
}
int mid = (ll + rr) >> 1;
build(k << 1, ll, mid);
build((k << 1)+1, mid+1, rr);
tree[k].mx = max(tree[k<<1].mx, tree[(k<<1)+1].mx);
tree[k].mn = min(tree[k<<1].mn, tree[(k<<1)+1].mn);
}
inline void check(int k, int ll, int rr) {
if(tree[k].l >= ll && tree[k].r <= rr) {
ans_mn = min(ans_mn, tree[k].mn);
ans_mx = max(ans_mx, tree[k].mx);
return ;
}
int mid = (tree[k].l + tree[k].r) >> 1;
if(mid >= ll) check(k << 1, ll, rr);
if(mid < rr) check((k<<1)+1, ll, rr);
}
inline LL solve() {
init();
build(1, 1, n);
LL Ans = 0;
for(int i=1; i<=n; i++) {
for(int j=i; j<=n; j++) {
ans_mx = 0, ans_mn = inf;
check(1, i, j);
Ans += ans_mx - ans_mn;
}
}
return Ans;
}
}p60;
int main() {
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
cin>>T;
while (T--) {
cin>>n
cout<<p60.solve()<<endl;
}
fclose(stdin);
fclose(stdout);
}

100 分

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
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 1e5+3;
typedef long long LL;
LL s[maxn], n, a[maxn], T;
struct P100 {
inline LL solve() {
LL h = 1, t = 0, sum = 0, ans = 0;
for(int i=1; i<=n; i++) {
while (h <= t && a[i] > a[s[t]]) sum -= a[s[t]] * (s[t]-s[t-1]), t--;
s[++t] = i;
sum += a[i] * (i-s[t-1]);
ans += sum;
}
return ans;
}
}p100;
int main() {
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
cin>>T;
while (T--) {
cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
LL ans = p100.solve();
for(int i=1; i<=n; i++) a[i] = -a[i];
cout<<ans + p100.solve()<<endl;
}
fclose(stdin);
fclose(stdout);
}