Kalorona

「Codeforces 566C」Logistical Questions – 题解

主要思路

这个题很神仙啊。首先考虑这个函数是一个单峰函数，且最后多个点所构成的代价函数一定形如 \(y = ax^{\frac{3}{2}} + b\)，显然这个函数也是单峰的。所以，当树的形态为一条链时，我们可以尝试二分。如果进化成一颗树，我们可以考虑进行点分治，考虑当前与根连接的子树里，只有一个以下的子树是更优的。

Continue reading →

Codeforces 434E:Furukawa Nagisa’s Tree – 题解

主要思路

这个题还蛮神仙的。主要的思路就是算三元组 \( (p_1, p_2, p_3) \)，满足 \( G(S(p_1, p_2)) = G(S(p_2, p_3)) = G(S(p_1, p_3)) = x \)。我们先考虑 \(G(S(p_1, p_2)) = x\) 的 \((p_1, p_2)\)。假设我们能把这些路径全部求出来，并把这个仅包含有向边 \( S(p_1, p_2) \) 的有向图的入度、出度算出来。如果能算出这种东西的话，发现直接乘法原理可以算出非法的三元组（合法的三元组是没法搞的，因为你还得算 \( (p_1, p_3) \) 的东西才能搞）。如果规定时间内能搞定这个入度出度之后，我们直接 \(\Theta(n)\) 算掉乘法原理那个。搞入度出度可以直接上点分治。

Continue reading →

「USACO 2018.01 Platinum」解题报告

A – Lifeguards

先可以想到把所有的包含的区间给去掉，然后来关注如何进行 DP。我们可以考虑设置 \(dp[i][j]\) 为前 \(i\) 个区间里删掉了 \(j\) 个区间的最优答案。正常我们做「选择 \(j\) 个区间」的问题会比较简单，然而 \(k \leq 200\) 就很麻烦。

Continue reading →

「Fortuna OJ」Jul 11th – Group B 解题报告

A – 照片

这道题是一道很考察思维的题目，我在这里介绍 DP 的做法。

我们考虑 DP。大概的方程可以写成：

\[ dp[i] = max\{ dp[j], j \in S_i \} + 1 \]

其中，\(dp[i]\)代表\([1, i]\)之间最多的斑点奶牛数量，然后\(S_i\)就是我们可以转移来的区间。我们可以提前处理好每一个点对应的\(lft_{S_i}, rig_{S_i}\)，也就是每一个点集合的左右端点。这个区间满足一个根本的条件：这个区间是点\(i\)左边最近的、不包含\(i\)的集合。我们肯定可以从这一段区间搞出最大的答案。预处理的时候先默认\(rgt[i] = i – 1\)，最后做个小 DP 更新数据即可。

Continue reading →

POJ1741:Tree 题解

主要思路

这道题应该算是点分治的一道经典题目。点分治的精髓就在于找到重心、对子树进行计算并且合并答案，之后删除中心变成子树内的小问题，分治思想非常的巧妙。

我们首先写好找根函数：

// root finding functions;
void dfs1(int u, int fa, int siz)
{
    son[u] = 1;
    int res = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        if (edges[i].to == fa || done[edges[i].to])
            continue;
        dfs1(edges[i].to, u, siz);
        son[u] += son[edges[i].to];
        res = max(res, son[edges[i].to] - 1);
    }
    res = max(res, siz - son[u]);
    if (res < rootKey)
        root = u, rootKey = res;
}
void findRoot(int src, int siz)
{
    root = src, rootKey = siz;
    dfs1(src, 0, siz);
}

遍历子树：我们设定一个\(dist[]\)数组，算出距离的答案，并且无视曾经被当作根的节点，并向cnt[from[u]]进行自增操作，维护子树的大小，并把本身编号加入vec供之后进行排序用途。

// the calc one;
void dfs(int u, int fa)
{
    vec.push_back(u);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa && !done[edges[i].to])
        {
            cnt[from[u]]++;
            dist[edges[i].to] = dist[u] + edges[i].weight;
            from[edges[i].to] = from[u];
            dfs(edges[i].to, u);
        }
}

点分治：我们在计算完子树答案之后，合并的方法是主要的问题。我们可以考虑将vec进行排序，然后通过递增的性质设置首尾指针，并且去除掉当前子树内的错误答案（因为子树内部的路径不经过根，所以要去掉，之后的分治子问题中会处理这些内部路径）。

void pdq(int curt, int siz)
{
    memset(son, 0, sizeof(son));
    memset(cnt, 0, sizeof(cnt));
    findRoot(curt, siz);
    dist[root] = 0, done[root] = true;
    vec.clear(), vec.push_back(root), from[root] = root;
    cnt[root]++;
    for (int i = head[root]; i != -1; i = edges[i].nxt)
        if (!done[edges[i].to])
        {
            from[edges[i].to] = edges[i].to, cnt[edges[i].to]++;
            dist[edges[i].to] = edges[i].weight;
            dfs(edges[i].to, root);
        }
    sort(vec.begin(), vec.end(), compare);
    cnt[from[vec[0]]]--;
    int l = 0, r = vec.size() - 1;
    while (l < r)
    {
        while (dist[vec[l]] + dist[vec[r]] > k)
            cnt[from[vec[r--]]]--;
        answer += r - l - cnt[from[vec[l]]];
        cnt[from[vec[++l]]]--;
    }
    int pos = root;
    for (int i = head[pos]; i != -1; i = edges[i].nxt)
        if (!done[edges[i].to])
            pdq(edges[i].to, son[edges[i].to]);
}

嗯，写完了。具体代码如下：

代码

// POJ1741.cpp
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 10100, INF = 0x3f3f3f3f;
int head[MAX_N], current, k, n, tmpx, tmpy, tmpz, root, rootKey, son[MAX_N];
int from[MAX_N], dist[MAX_N], cnt[MAX_N];
bool done[MAX_N];
long long answer = 0;
vector<int> vec;
struct edge
{
    int to, nxt, weight;
} edges[MAX_N << 1];
bool compare(int a, int b) { return dist[a] < dist[b]; }
void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}
// root finding functions;
void dfs1(int u, int fa, int siz)
{
    son[u] = 1;
    int res = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        if (edges[i].to == fa || done[edges[i].to])
            continue;
        dfs1(edges[i].to, u, siz);
        son[u] += son[edges[i].to];
        res = max(res, son[edges[i].to] - 1);
    }
    res = max(res, siz - son[u]);
    if (res < rootKey)
        root = u, rootKey = res;
}
void findRoot(int src, int siz)
{
    root = src, rootKey = siz;
    dfs1(src, 0, siz);
}
// the calc one;
void dfs(int u, int fa)
{
    vec.push_back(u);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa && !done[edges[i].to])
        {
            cnt[from[u]]++;
            dist[edges[i].to] = dist[u] + edges[i].weight;
            from[edges[i].to] = from[u];
            dfs(edges[i].to, u);
        }
}
void pdq(int curt, int siz)
{
    memset(son, 0, sizeof(son));
    memset(cnt, 0, sizeof(cnt));
    findRoot(curt, siz);
    dist[root] = 0, done[root] = true;
    vec.clear(), vec.push_back(root), from[root] = root;
    cnt[root]++;
    for (int i = head[root]; i != -1; i = edges[i].nxt)
        if (!done[edges[i].to])
        {
            from[edges[i].to] = edges[i].to, cnt[edges[i].to]++;
            dist[edges[i].to] = edges[i].weight;
            dfs(edges[i].to, root);
        }
    sort(vec.begin(), vec.end(), compare);
    cnt[from[vec[0]]]--;
    int l = 0, r = vec.size() - 1;
    while (l < r)
    {
        while (dist[vec[l]] + dist[vec[r]] > k)
            cnt[from[vec[r--]]]--;
        answer += r - l - cnt[from[vec[l]]];
        cnt[from[vec[++l]]]--;
    }
    int pos = root;
    for (int i = head[pos]; i != -1; i = edges[i].nxt)
        if (!done[edges[i].to])
            pdq(edges[i].to, son[edges[i].to]);
}
int main()
{
    while (scanf("%d%d", &n, &k) && n != 0)
    {
        answer = 0;
        memset(head, -1, sizeof(head)), current = 0;
        for (int i = 1; i <= n - 1; i++)
            scanf("%d%d%d", &tmpx, &tmpy, &tmpz), addpath(tmpx, tmpy, tmpz), addpath(tmpy, tmpx, tmpz);
        memset(done, false, sizeof(done));
        pdq(1, n);
        printf("%lld\n", answer);
    }
    return 0;
}

 

P4149:「IOI2011」Race 题解

思路

这道题我们直接进行点分治即可。我们需要实现一下的几个操作：

  • FIND-ROOT()：找出重心
  • GET-META()：更新最小边数答案
  • UPDATE(u, sz)：更新边数数组
  • CLEAR()：清除边数数组
  • DIVIDE()：点分治

我们一段一段来讲。

代码段

void predfs(int u, int fa)
{
    siz[u] = 1, son[u] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to, w = edges[i].weight;
        if (to == fa || vis[to])
            continue;
        predfs(to, u);
        siz[u] += siz[to], son[u] = max(siz[to], son[u]);
    }
    son[u] = max(son[u], capacity - siz[u]);
    if (son[u] < son[root])
        root = u;
}

这一段是找重心的代码，很简单我就不解释了。

void getMeta(int u, int fa, int cnt, int dist)
{
    if (dist > k)
        return;
    ans = min(ans, sides[k - dist] + cnt);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (to == fa || vis[to])
            continue;
        getMeta(to, u, cnt + 1, dist + edges[i].weight);
    }
}

这段比较重要。点分治出来之后就进行子树上的答案统计，答案的计算为\(ans=min\{sides[k – dist] + cnt\}\)，其中 sides 数组代表长度为 dist 的最小段数。统计的时候不用担心边重复的问题，因为我们之后 update 操作之后才会让 sides 数组生效。

void update(int u, int fa, int cnt, int dist)
{
    if (dist > k)
        return;
    sides[dist] = min(sides[dist], cnt);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (to == fa || vis[to])
            continue;
        update(to, u, cnt + 1, dist + edges[i].weight);
    }
}

用 DFS 进行更新。

void clear(int u, int fa, int dis)
{
    if (dis >= k)
        return;
    sides[dis] = 1e9;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to] || fa == to)
            continue;
        clear(to, u, dis + edges[i].weight);
    }
}

设置为极大值来覆盖子树恢复答案。

void divide(int u, int sz)
{
    vis[u] = true, sides[0] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to])
            continue;
        getMeta(to, u, 1, edges[i].weight);
        update(to, u, 1, edges[i].weight);
    }
    clear(u, 0, 0);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to])
            continue;
        son[0] = capacity = (siz[to] > siz[u]) ? (sz - siz[u]) : (siz[to]);
        root = 0;
        predfs(to, 0);
        divide(root, capacity);
    }
}

点分治是在重心上运行的。在重心上更新子树的信息，然后进行换根保证正确性。

总代码

// P4149.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200200;
struct edge
{
    int to, nxt, weight;
} edges[MAX_N << 1];
int head[MAX_N], n, k, current, tmpx, tmpy, tmpz, siz[MAX_N], capacity;
int ans = 1e9, sides[1002000], son[MAX_N], root;
bool vis[MAX_N];
inline int read()
{
    int re = 0, flag = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0')
    {
        if (ch == '-')
            flag = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        re = (re << 1) + (re << 3) + ch - '0', ch = getchar();
    return re * flag;
}
void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}
void predfs(int u, int fa)
{
    siz[u] = 1, son[u] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to, w = edges[i].weight;
        if (to == fa || vis[to])
            continue;
        predfs(to, u);
        siz[u] += siz[to], son[u] = max(siz[to], son[u]);
    }
    son[u] = max(son[u], capacity - siz[u]);
    if (son[u] < son[root])
        root = u;
}
void getMeta(int u, int fa, int cnt, int dist)
{
    if (dist > k)
        return;
    ans = min(ans, sides[k - dist] + cnt);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (to == fa || vis[to])
            continue;
        getMeta(to, u, cnt + 1, dist + edges[i].weight);
    }
}
void update(int u, int fa, int cnt, int dist)
{
    if (dist > k)
        return;
    sides[dist] = min(sides[dist], cnt);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (to == fa || vis[to])
            continue;
        update(to, u, cnt + 1, dist + edges[i].weight);
    }
}
void clear(int u, int fa, int dis)
{
    if (dis >= k)
        return;
    sides[dis] = 1e9;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to] || fa == to)
            continue;
        clear(to, u, dis + edges[i].weight);
    }
}
void divide(int u, int sz)
{
    vis[u] = true, sides[0] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to])
            continue;
        getMeta(to, u, 1, edges[i].weight);
        update(to, u, 1, edges[i].weight);
    }
    clear(u, 0, 0);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to])
            continue;
        son[0] = capacity = (siz[to] > siz[u]) ? (sz - siz[u]) : (siz[to]);
        root = 0;
        predfs(to, 0);
        divide(root, capacity);
    }
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n - 1; i++)
    {
        scanf("%d%d%d", &tmpx, &tmpy, &tmpz);
        addpath(tmpx + 1, tmpy + 1, tmpz), addpath(tmpy + 1, tmpx + 1, tmpz);
    }
    capacity = n;
    son[0] = n, root = 0;
    for (int i = 0; i <= k; i++)
        sides[i] = 1e9;
    predfs(1, 0);
    divide(root, n);
    if (ans != 1e9)
        printf("%d", ans);
    else
        printf("-1");
    return 0;
}