Link

Sol

其实我觉得这题就很适合作为联赛题。就是那种典型的水平、积累到了一定层次就会做,有区分度的题目。

首先我们来考虑一下,怎么样才能问出一个被子地下的奇偶性。加入我们问了一段区间$[l,r]$的奇偶性,又问一次$[l,r+1]$的奇偶性,那么$[r,r+1]$这段的有没有球就确定了。原因:假如这两段区间的奇偶性是一奇一偶,说明两个右端点组成的区间必是因为有球才导致的奇偶性不同。

那么我们来形式化地描述这种已经知道$[r,r+1]$的奇偶性的状态:从$[r,r+1]$连一条边。那么,知道$[l,r]$的奇偶性就是从$l$到$r$有一条边(对刚才的性质进行换元就可以了)。我们把按照这种方法建一张图,最终我们就只要选出一些边使这张图联通。最小生成树即可。

我觉得这道题改改可以出道交互题。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 2e3 + 5;

int n, m, num;
int fa[SIZE];

struct node {
    int from, to, v;

    bool operator< (const node &a) const {
        return v < a.v;
    }
} edge[SIZE * SIZE];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

void addEdge(int u, int v, int d) {
    edge[++ num].from = u, edge[num].to = v, edge[num].v = d;
}

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

signed main() {
    // freopen("code.in", "r", stdin);
    n = read();
    for (int i = 1; i <= n; ++ i) {
        for (int j = i, w; j <= n; ++ j) {
            w = read();
            addEdge(i - 1, j, w);
        }
    }
    std::sort(edge + 1, edge + num + 1);
    for (int i = 1; i <= n; ++ i) fa[i] = i;
    int tot = 0, cnt = 0;
    for (int i = 1, fx, fy; i <= num; ++ i) {
        fx = find(edge[i].from), fy = find(edge[i].to);
        if (fx != fy) {
            fa[fx] = fy, ++ cnt, tot += edge[i].v;
        }
        // if (cnt == n - 1) break;
    }
    printf("%lld\n", tot);
    return 0;
}
最后修改:2021 年 08 月 20 日
如果觉得我的文章对你有用,请随意赞赏