20230924题解

发表于 分类于 ， 阅读次数：

password

每一个数字都可以加或者不加，如果直接搜索，就有 \(2^{40}\) 的计算量，显然会 T。（其实不会）

考虑到目标状态只有一个，可以 Meet in the middle，直接写双端搜索就可以在 \(2^{20}\) 之内解决。

classroom

经典区间方差。我们知道 \(\operatorname{var}(X) = E[X^2] - (E[X])^2\)，所以只要拿一个线段树维护 \(X^2\) 的和就好了。

实际应该是 long long 不是 double。

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
struct node;
typedef node* pos;
struct node {
    pos ls, rs;
    int l, r;
    double sum, sum_pf, tag;
    node() {
        l = r = 0; sum = sum_pf = tag = 0;
        ls = rs = this;
    }
    void push_up() { sum = ls -> sum + rs -> sum; sum_pf = ls -> sum_pf + rs -> sum_pf; }
    void update_one(double x) { sum_pf += 2 * x * sum + x * x * (r - l + 1); sum += x * (r - l + 1); tag += x; }
    void push_down() { ls -> update_one(tag); rs -> update_one(tag); tag = 0; }
} buf[maxn << 1], *root = buf, *buf_pos = buf;

pos new_node(int l, int r) {
    pos p = ++buf_pos;
    p -> ls = p -> rs = buf;
    p -> l = l, p -> r = r;
    return p;
}

double a[maxn];

void build(pos p) {
    if (p -> l == p -> r) {
        p -> sum = a[p -> l];
        p -> sum_pf = a[p -> l] * a[p -> l];
        return;
    }
    int mid = (p -> l + p -> r) >> 1;
    p -> ls = new_node(p -> l, mid); build(p -> ls);
    p -> rs = new_node(mid + 1, p -> r); build(p -> rs);
    p -> push_up();
    return;
}

void update(pos p, int l, int r, double x) {
    if (l <= p -> l && p -> r <= r) {
        p -> update_one(x);
        return;
    }
    p -> push_down();
    if (l <= p -> ls -> r) update(p -> ls, l, r, x);
    if (p -> rs -> l <= r) update(p -> rs, l, r, x);
    p -> push_up();
    return;
}

void ask(pos p, int l, int r, double &sum, double &sum_pf) {
    if (l <= p -> l && p -> r <= r) {
        sum += p -> sum;
        sum_pf += p -> sum_pf;
        return;
    }
    p -> push_down();
    if (l <= p -> ls -> r) ask(p -> ls, l, r, sum, sum_pf);
    if (p -> rs -> l <= r) ask(p -> rs, l, r, sum, sum_pf);
    return;
}

traffic

这个题费尽心思地告诉你“没有交叉”“没有隧道、桥梁”就是为了告诉你这玩意是平面图。（你猜为啥要给你坐标）

有什么用呢？我们先把右岸中不可达的点全部去掉。如果一个右岸点 \(v\) 是可达的，并且 \(v+1\) 和 \(v-1\) 都可以由同一个左岸的 \(u\) 达到，那么 \(v\) 也一定可以从 \(u\) 达到。（路径没有交叉，如果 \(u\) 到不了 \(v\) 但是 \(u'\) 能到，那么 \(u'\) 到 \(v\) 的路径一定会与 \(u \to v+1\) 或 \(u \to v-1\) 交叉）

换句话说，\(u\) 可达的点是连续的。

所以对于一个左岸的点，我们只要求出来最高可以到右岸哪里，以及最低可以到右岸哪里。在反图上分别从右岸开始从上往下和从下往上搜一遍就行了。

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
void dfs(int u) {
    vis[u] = true;
    for (int v : graph[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
}

void dfs_inv(int u, int id, int from) {
    ans[id][u] = from;
    for (int v : graph_inv[u]) {
        if (!ans[id][v]) {
            dfs_inv(v, id, from);
        }
    }
}

vector<pair<int, int> > s, t;

int main() {
    //...
    for (auto x : s) {
        if (!vis[x.second]) dfs(x.second);
    }
    vector<pair<int, int> > tt;
    t.swap(tt);
    for (auto x : tt) {
        if (vis[x.second]) t.emplace_back(x);
    }

    sort(t.begin(), t.end());
    for (int i = 0; i < t.size(); i++) {
        dfs_inv(t[i].second, 0, i + 1);
    }
    for (int i = t.size() - 1; i >= 0; i--) {
        dfs_inv(t[i].second, 1, i + 1);
    }

    sort(s.begin(), s.end());
    for (auto x : s) {
        write(ans[1][x.second] ? ans[1][x.second] - ans[0][x.second] + 1 : 0);
    }
    return 0;
}

earthworm

这玩意的证明不是很好懂。。。

  1. 既然其他人都长，那就相当于被砍的变短。
  2. 在 1 的定义之下被砍的蚯蚓序列长度一定是递减的。
  3. 在 2 的前提下砍完生成的序列也是递减的。

还是别人的题解严谨：Link

所以将原数组排序之后，将每次砍的结果分别放在两个队列里，则这两个队列都是有序的。每次最大值就是原数组和两个队列中的第一个里面选。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
sort(a + 1, a + n + 1);
reverse(a + 1, a + n + 1);
ta = n;
for (int i = 1; i <= m; i++) {
    long long now;
    if (a[ha] > b[hb] && a[ha] > c[hc]) now = a[ha++];
    else if (b[hb] > c[hc]) now = b[hb++];
    else now = c[hc++];
    now += (i - 1) * q;
    if (i % t == 0) printf("%lld ", now);
    b[++tb] = now * u / v - i * q;
    c[++tc] = now - now * u / v - i * q;
}
putchar('\n');
merge(a + ha, a + ta + 1, b + hb, b + tb + 1, d + 1, greater<int>());
merge(c + hc, c + tc + 1, d + 1, d + (tb - hb + 1) + (ta - ha + 1) + 1, b + 1, greater<int>());
for (int i = t; i <= n + m; i += t) {
    printf("%lld ", b[i] + m * q);
}

cow-libi

显然易得同理，既然真正的罪犯可以按顺序走完所有抓握，那么只要一头（或者说一只）犯罪嫌疑牛能够走到时间上最近的两个抓握处，他就可能是罪犯；反之亦然。

所以对抓握按照时间排序，然后二分判断相邻两个即可。

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;

struct node {
    long long x, y, t;
    bool operator < (const node &x) const {
        return t < x.t;
    }
} g[maxn];

long long n, m, ans;

long long dis(long long x1, long long y1, long long x2, long long y2) {
    return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld %lld %lld", &g[i].x, &g[i].y, &g[i].t);
    }
    sort(g + 1, g + n + 1);
    for (int i = 1; i <= m; i++) {
        node x;
        scanf("%lld %lld %lld", &x.x, &x.y, &x.t);
        auto p = lower_bound(g + 1, g + n + 1, x);
        bool flag = false;
        if (p != g + n + 1 && dis(p -> x, p -> y, x.x, x.y) > (p -> t - x.t) * (p -> t - x.t)) flag = true;
        if (p != g + 1 && dis((p - 1) -> x, (p - 1) -> y, x.x, x.y) > (x.t - (p - 1) -> t) * (x.t - (p - 1) -> t)) flag = true;
        if (flag) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

subarray

考虑区间对某个点的贡献：如果两个区间的区间和之差为 \(w\)，那么 \(w\) 可以是两个区间的非重合部分的答案。

为啥是非重合部分呢？首先肯定不是非覆盖部分。如果非覆盖部分变化 \(w\)，这两个区间不可能有变化。

如果是重合部分变化 \(w\)，那么两个区间都变化，无效。

所以只能是非重合部分：一个变化一个不变，那么将这些点的答案对 \(w\) 取 \(\min\)。

并不需要枚举所有的区间对，只要按照区间和大小从小到大排序，只用相邻的两个区间就好。

然后你用一个线段树之类的维护区间最小值，就可以做到 \(O(n^2 \log n)\)。

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e2 + 5;

struct node {
    int l, r;
    node() {}
    node(int _l, int _r) {
        l = _l, r = _r;
    }
};

vector<node> b;

long long a[maxn];

bool compare(const node &x, const node &y) {
    return a[x.r] - a[x.l - 1] < a[y.r] - a[y.l - 1];
}

int n;
bool book[maxn];
long long ans[maxn];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", a + i);
        a[i] += a[i - 1];
        for (int j = 1; j <= i; j++) {
            b.emplace_back(j, i);
        }
        ans[i] = LLONG_MAX;
    }
    sort(b.begin(), b.end(), compare);
    for (int i = 0; i < b.size() - 1; i++) {
        int l1 = b[i].l, r1 = b[i].r, l2 = b[i + 1].l, r2 = b[i + 1].r;
        long long w = abs(a[r1] - a[l1 - 1] - a[r2] + a[l2 - 1]);
        for (int i = l1; i <= r1; i++) book[i] ^= 1;
        for (int i = l2; i <= r2; i++) book[i] ^= 1;
        for (int i = 1; i <= n; i++) if (book[i]) ans[i] = min(ans[i], w), book[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}