[Agc029C]Powers of two_贪心_树形dp

Powers of two

题目链接：https://atcoder.jp/contests/agc029/tasks/agc029_b

数据范围：略。

---

题解：

可能一点思路都没有。

但是我们发现：如果一个数选择一个比自己小的数组合的话，这个数是唯一确定的。

我们根据这个建一棵树，每个点最多只有一个父亲。

现在让求出最多数量的边，使得没有公共端点。

显然从叶子开始往根选取。

也就是从大到小，依次选取。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

#define N 200010

using namespace std;

typedef long long ll;

char *p1, *p2, buf[100000];

#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

int rd() {
    int x = 0, f = 1;
    char c = nc();
    while (c < 48) {
        if (c == '-')
            f = -1;
        c = nc();
    }
    while (c > 47) {
        x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
    }
    return x * f;
}

int b[2];

char s[N];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    ll ans = 0;
    for (int i = 1; i <= n; i ++ ) {
        int c = ((s[i] == 'B') ? 1 : 0);
        // cout << c << endl ;
        if (!c) {
            ans += b[1];
        }
        b[c] ++ ;
    }
    cout << ans << endl ;
    return 0;
}