Codeforces Round 881 (Div. 3)

~~A：ABC~~

A. Sasha and Array Coloring

题意：求最大的着色成本（着色成本是指同一个颜色的最大值-最小值）

思路：肯定不能是相同的，直接最大-最小就行

#include <bits/stdc++.h>

using namespace std;
int a[60];

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);\
    int mi = 0, ma = 0;
    for (int i = 0; i < (n + 1) / 2; i++) {
        ma += a[n - i - 1];
        mi += a[i];
    }
    cout << ma - mi << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B. Long Long

题意：操作：a[i]=-a[i];目标：把所有负数搞正所需的最小次数

思路：连在一起的算一次反转就行

#include <bits/stdc++.h>

using namespace std;
const int MAX = 2e5 + 10;
int a[MAX];
#define int long long

void solve() {
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += abs(a[i]);
    }
    int res = 0;
    a[n] = 1;
    for (int i = 0; i < n; i++) {
        if (a[i] < 0 && a[i + 1] == 0) a[i + 1] = -1;
        else if (a[i] < 0 && a[i + 1] > 0) {
            res++;
        }
    }
    cout << sum << " " << res << "\n";
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C. Sum in Binary Tree

题意：给一个二叉树，求1到n的顶点数之和

思路：二叉树直接/2就行

#include <bits/stdc++.h>

using namespace std;
#define int unsigned long long

void solve() {
    int n;
    cin >> n;
    int sum = 0;
    while (n >= 1) {
        sum += n;
        n /= 2;
    }
    cout << sum << "\n";
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D. Apple Tree

~~能看出是树型dp，写不来一点~~

题意：两棵树儿子的个数相乘

思路：树形dp+dfs(找儿子个数)

这个点的数要取2*MAX（是以操作来存点）（坑死人！！！）

#include <bits/stdc++.h>

using namespace std;
const int MAX = 4e5 + 10;
int head[MAX], tail[MAX], edge[MAX];//描述一个节点所需的三个参数
int dp[MAX], num[MAX];//num位于同一颗树上的点的数量
int idx = 0;

void add(int a, int b) {
    edge[++idx] = b;
    tail[idx] = head[a];
    head[a] = idx;
}

void dfs(int u, int fa) {
    if (num[u] == 1) {
        dp[u] = 1;
    }
    for (int i = head[u]; i; i = tail[i]) {
        int x = edge[i];
        if (x == fa) continue;
        dfs(x, u);
        dp[u] += dp[x];
    }
}

void solve() {
    int n;
    cin >> n;
    idx = 0;
    for (int i = 1; i <= n; i++) {
        head[i] = 0;
        dp[i] = 0;
        num[i] = 0;
    }//畜生化
    num[1] = 1;
    for (int i = 1; i < n ; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
        num[a]++;
        num[b]++;
    }
    dfs(1, 0);
    int m;
    cin >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        long long int res = 1ll * dp[a] * dp[b];
        cout << res << endl;
    }
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E. Tracking Segments

题意：区间是美丽：区间上1的数量严格大于0的数量

操作：a[x]=1

目标：至少有一个完美区间

思路：二分+前缀和(用在check上)

#include <bits/stdc++.h>

using namespace std;
const int MAX = 1e5 + 10;
pair<int, int> se[MAX];
int qu[MAX];
int m, n;

bool check(int mid) {
    vector<int> a(n + 1), sum(n + 1);
    for (int i = 1; i <= mid; i++) a[qu[i]]++;
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
    for (int i = 1; i <= m; i++) {
        int cnt = sum[se[i].second] - sum[se[i].first - 1];
        if (cnt >= (se[i].second - se[i].first + 1) / 2 + 1) return true;
    }
    return false;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> se[i].first >> se[i].second;
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> qu[i];
    }
    int l = 1, r = q;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    if (check(l)) cout << l << "\n";
    else cout << -1 << "\n";

}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F不是很懂题目回头再说