Kalorona

P1122:最大子树和题解

思路

设一个F[n+1]为树形DP的数组。在点i上，对于每一个子节点j，都有F[j] = dis[i] + max(0, F[j])。其中dis是美丽指数。

代码

// P1122.cpp
#include <iostream>
#include <algorithm>

using namespace std;
// the tree;
const int maxn = 160010;
int n;
int dis[maxn];
int to[maxn];
int next[maxn];
int point[maxn];
int current = 0;
int F[maxn];
int ans = 0;

void add_edge(int src, int dst)
{
    next[current] = point[src];
    to[current] = dst;
    point[src] = current;
    current++;
}
// core code: search subtrees and add them up to F[curt],
// in the meanwhile, get the ans;
void DFS(int curt, int fat)
{
    F[curt] = dis[curt];
    for (int i = point[curt]; i != -1; i = next[i])
    {
        int dst = to[i];
        if (dst == fat)
            continue;
        DFS(dst, curt);
        F[curt] += max(0, F[dst]);
    }
    ans = max(ans, F[curt]);
}
// initialize;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> dis[i];
    fill(point, point + n + 1, -1);
    fill(next, next + n + 1, -1);
    fill(F, F + n + 1, 0);
    int a, b;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a >> b;
        add_edge(a, b), add_edge(b, a);
    }
    DFS(1, 0);
    cout << ans;
    return 0;
}

P2678:跳石头题解 & 二分答案原理

暑假和小学神仙们集训的时候发过这道题，一直不知道如何去解决。一个月前crazydave大佬给我简述过二分答案的原理，而蒟蒻我今天才搞定这些。

我们先来看例题：洛谷P2678

这是一道NOIP提高组的简单题（我太菜了），主要是通过枚举答案，在每次枚举时检测能不能符合要求即可。先看代码：

// P2678.cpp
#include <iostream>

using namespace std;

const int maxn = 500020;
int L, N, M;
int D[maxn];

bool check(int num)
{
    int last = 0;
    int cnt = 0;
    for (int i = 0; i <= N; i++)
        if (D[i] - last < num)
            cnt++;
        else
            last = D[i];
    if (cnt > M)
        return false;
    return true;
}

void solve()
{
    int left = 0;
    int right = L;
    int ans = 0;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (check(mid))
            left = mid + 1, ans = mid;
        else
            right = mid - 1;
    }
    cout << ans;
}

int main()
{
    cin >> L >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> D[i];
    D[N] = L;
    solve();
    return 0;
}

check函数就是验证答案num（也就是我们枚举出来的答案）是否符合要求，在这里便是检测当最小距离为num时，移走的石子会不会超过限制。如果超过了，返回false，二分便会把区间调为[left,mid-1]，以降低最大值来试探限制；没有超过，则返回true，二分把区间调整为[mid+1,right]，以追求更大的最大值。

抽象化分析结果

准备枚举一道题答案之前，请考虑二分答案。如果可以二分答案，那么时间复杂度会极度降低，从O(n^2)转变为O(n log n)。二分答案的结构就是二分代码和检验答案正确性代码。如果能通过正确性检查，那么追求更大（小）的答案并重新枚举；如果无法通过，则把区间调整，在较小（大）区间内追求更大（小）的答案。亦复如此。