20211006题解

发表于 2022-07-13 分类于信奥，题解阅读次数：

T1 奶牛排序

题面描述

FJ 想按照奶牛产奶的能力给她们排序。现在已知有 \(N\) 头奶牛，编号依次为 \(1 ... N\) 。FJ 通过比较，已经知道了 \(M\) 对相对关系。每一对关系表示为 \(X\) \(Y\) ，意指 \(X\) 的产奶能力强于 \(Y\) 。现在FJ想要知道，最差的时候他至少还要调查多少对关系才能完成整个排序。

思路分析

把奶牛抽象成点，关系抽象成边，则整个问题就变成了一个 \(DAG\) 。

一个奶牛序列想要进行排序，最好知道每两个点之间的关系，也就是 \(N(N-1)/2\) 条关系。

但实际上，最好情况下，只要 \(N-1\) 条关系就可以排序。这两者之间有什么关系呢？

小学生都知道，如果 \(a > b,b > c\) ,那么 \(a > c\) ，这是一个类似于 \(Floyd\) 闭包传递的过程，如果对于最好情况的图跑一边 \(Floyd\) ，他就会转化为有 \(N(N-1)/2\) 的连通图。

所以，我们可以对于题目给出的图跑一边 \(Floyd\) ，然后看看它和连通图差了多少。时间复杂度 \(\Theta (n^3)\)

代码如下：（来自CmsMartin，码风不一样 ~~（实际上一模一样）~~）

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

int N , M , ToT;

bool Dis[1010][1010];

int main() {
    ios::sync_with_stdio(false);

    cin >> N >> M;
    for(int i = 1 ,x ,y; i <= M; i++) {
        cin >> x >> y;
        Dis[x][y] = true;
    }
    
    for(int k = 1; k <= N; k++) {
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                Dis[i][j] |= Dis[i][k] & Dis[k][j];
            }
        }
    }

    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            if(Dis[i][j] == true) ToT++;
        }
    }

    cout << N * (N - 1) / 2 - ToT << endl;
    
    return 0;
}

由于数据太水了，一秒钟就能过，但是仁慈的管理员把时间调到了 \(0.02\) 秒。

怎么优化呢？

在 \(Floyd\) 中，有很多的枚举其实是用来求最短路的，并不是判连通的，而且用邻接矩阵显然太慢了（题目给的是稀疏图）

所以我们可以用邻接表存图，然后对每一点跑一次 \(BFS\) 用来判断连通，这样时间复杂度就是 \(\Theta (n(n + m))\) 。

AC代码

code

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

#define uns unsigned
#define ll long long
#define use_cin_cout do {ios::sync_with_stdio(false); /*cin.tie();*/} while(false)
#define endl '\n'

const ll inf_ll = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
const int maxn = 1e3 + 5, maxm = 1e4 + 5;

struct edge {
    int u, v;
};

vector<int> graph[maxn]; //这里用的是vector存图
int n, m, cnt;
queue<int> bfs_q;
bool bfs_b[maxn];

void bfs(int root) {
    while (!bfs_q.empty()) bfs_q.pop();
    memset(bfs_b, 0, sizeof(bfs_b));

    bfs_q.push(root);
    bfs_b[root] = true;
    while (!bfs_q.empty()) {
        int top = bfs_q.front();
        bfs_q.pop();

        for (int i = 0; i < graph[top].size(); i++) {
            int to = graph[top][i];
            if (bfs_b[to]) continue;

            bfs_b[to] = true;
            cnt++;
            bfs_q.push(to);
        }
    }
}

int main() {
    use_cin_cout;
    // freopen("ranking.in", "r", stdin);
    // freopen("ranking.out", "w", stdout);

    for (int i = 1; i <= n; i++) {
        graph[i][i] = true;
    }

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }

    for (int r = 1; r <= n; r++) {
        bfs(r);
    }

    /*
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (arrive[i][j]) {
                cout << i << ' ' << j << endl;
            }
        }
    }
    */
    
    cout << n * (n - 1) / 2 - cnt << endl;

    return 0;
}

T4

题目描述

小 L 非常喜欢树。最近，他发现了一棵有趣的树。这棵树有 \(n\) 个节点( \(1\) 到 \(n\) 编号)，节点 \(i\) 有一个初始的权值 \(A_i\) 。这棵树的根是节点 \(1\) 。这棵树有一个特殊的性质：当你给节点 \(i\) 的权值加 \(val\) 的时候，节点 \(i\) 的所有儿子的权值都会加 \(-val\) 。注意当你给节点 \(i\) 的儿子的权值加 \(-val\) 时，节点 \(i\) 的这个儿子的所有儿子的权值都会加 \(-(-val)\) ，以此类推。

有 \(2\) 种操作：

操作(a) 1 x val 表示给节点 \(x\) 的权值加 \(val\) 。
操作(b) 2 x 输出节点 \(x\) 当前的权值。

为了帮助小 L 更好地理解这棵树，你必须处理 \(m\) 个操作。

思路分析

很明显，这是一道区间修改，单点查询的题，很容易可以想到线段树。在这之前跑一便 \(dfs\) ，获得每个点的深度，就很好修改了。

~~是不是写的太简单了~~

在dfs中，我们先记录下每个点是1还是-1，然后记录下以这个点为根的子树对应的树状数组开始节点和结束节点，记为 \(dfn \_ in\) 和 \(dfn \_ out\) ，树状数组中我们存储每一个点的增加的绝对值，然后在查询的时候，查询 \(dfn \_ in\) 就可以了。

AC代码

code

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

#define uns unsigned
#define ll long long
#define use_cin_cout do {ios::sync_with_stdio(false); /*cin.tie();*/} while(false)
#define endl '\n'

const ll inf_ll = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
const int maxn = 1e5 + 5;

vector<int> tree[maxn];
int val[maxn], t[maxn], f[maxn], dfn_in[maxn], dfn_out[maxn];
int n, m, dfn;

void dfs(int x, int fa) {
    dfn_in[x] = ++dfn;
    f[x] = -f[fa];
    for (int i = 0; i < tree[x].size(); i++) {
        dfs(tree[x][i], x);
    }
    dfn_out[x] = dfn;
}

int query(int x) {
    int result = 0;
    for (int i = x; i; i -= (i & -i)) result += t[i];
	// cout << "ok" << endl;
    return result;
}

void update(int x, int data) {
    for (int i = x; i <= n; i += (i & -i)) t[i] += data;
}

int main() {
    use_cin_cout;
    // freopen("tree.in", "r", stdin);
    // freopen("tree.out", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
    }

    f[0] = -1;
    dfs(1, 0);

    int mode;
    for (int i = 1; i <= m; i++) {
        cin >> mode;

        if (mode == 1) {
            int node, v;
            cin >> node >> v;
            update(dfn_in[node], f[node] * v);
            update(dfn_out[node] + 1, -f[node] * v);
        }

        else {
            int node;
            cin >> node;
            cout << val[node] + query(dfn_in[node]) * f[node] << endl;
        }
    }

    return 0;
}