茶7.1-7.5

Mon.

输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤2e5。
每组数据输入 n(1≤n≤2e5) 和长为 n 的数组 a(1≤a[i]≤1e9)。

一条街道上有 n 个工厂，第 i 个工厂的位置是 a[i]。
你需要建造 3 个仓库，仓库的位置由你决定，必须是整数。
每个工厂生产的物品要运到离其最近的仓库。

定义 d(i) = 第 i 个工厂到离其最近的仓库的距离。
设 M = 所有 d(i) 的最大值。
最小化 M，也就是最小化最大的工厂到仓库的距离。

输入
5
6
1 7 7 9 9 9
6
5 4 2 1 30 60
9
14 19 37 59 1 4 4 98 73
1
2
6
3 10 1 17 15 11
输出
0
2
13
0
1
解释
样例 1：在 1,7,9 处建仓库，最远距离为 0。
样例 2：在 3,30,60 处建仓库，最远距离为 2。
样例 3：在 14,50,85 处建仓库，最远距离为 13。

Sol:

二分答案+贪心。

把 a 从小到大排序。

设答案为 m，那么第一段（第一个仓库对应的工厂）的范围是 [a[0], a[0]+2m]，

二分找 a 中第一个大于 a[0]+2m 的数 a[i]，那么第二段的范围是 [a[i], a[i]+2m]。

继续二分，找 a 中第一个大于 a[i]+2m 的数 a[j]，那么第三段的范围是 [a[j], a[j]+2m]。

如果 a[j]+2m >= a[n-1]，那么 check 是 true，否则是 false。注意 i=n 和 j=n 的情况。

二分上界：可以直接写 1e9 或者 a[n-1]-a[0]，下面讨论更精细的上界。

假设答案 x 一定成立，那么极限情况下第一段是 [a0, a0+2x]，第二段是 [a0+2x+1, a0+4x+1]，第三段是 [a0+4x+2, a0+6x+2]，所以有 a[0]+6x+2 <= a[n-1]

解得 x >= ceil((a[n-1]-a[0]-2) / 6) = floor((a[n-1]-a[0]+3) / 6)

所以（开区间的）二分上界是 floor((a[n-1]-a[0]+3) / 6)。

Code:

void solve()
{
    int n;
    cin>>n;
    vi a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a);
    int l=-1,r=(a[n-1] - a[0] + 3) / 6;
    while(r-l>1){
        int m=(l+r)>>1;
        int i=0;
        while(i+1<a.size()&&a[i+1]-a[0]<=2*m){
            ++i;
        }
        int j=n-1;
        while(j-1>=0&&a.back()-a[j-1]<=2*m){
            --j;
        }
        ++i;--j;
        if (i > j || a[j] - a[i] <= 2 * m) {
            r = m;
        } else {
            l = m;
        }
    }
    cout<<r<<endl;
}

Tue

Theofanis’ Nightmare_912C

输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤2e5。
每组数据输入 n(1≤n≤1e5) 和长为 n 的数组 a(-1e8≤a[i]≤1e8)。

你需要把 a 分割成若干非空段，假设分割成了 k 段，那么得分为：
第一段的元素和 1 + 第二段的元素和 2 + … + 第 k 段的元素和 * k

例如 [1,2,3,4] 分成两段 [1,2] 和 [3,4]，得分为
(1+2) 1 + (3+4) 2

输出最大得分。

输入
4
6
1 -3 7 -6 2 5
4
2 9 -5 -3
8
-3 -4 2 -5 1 10 17 23
1
830
输出
32
4
343
830

Sol:

等价转换。

和式可以视作 a 的若干后缀和之和。

例如 [1,2,3,4] 分成两段 [1,2] 和 [3,4]，得分为

(1+2) 1 + (3+4) 2 = (1+2+3+4) + (3+4)

所以计算 a 的所有后缀和，取其中大于 0 的后缀和相加，即为答案。注意整个数组的和一定要加进答案。

注意用 64 位整数。

Code:

void solve()
{
    int n;
    cin >> n;
    vi a(n);
    FOR(i, 0, n-1) cin >> a[i];
    ll ans = 0;
    ll s = 0;
    for(int i = n-1;i >= 0; i--) {
        s += a[i];
        if (i == 0 || s > 0) {
            ans += s;
        }
    }
    cout << ans << endl;
}

Wed

https://codeforces.com/problemset/problem/1849/D

输入 n(1≤n≤2e5) 和长为 n 的数组 a(0≤a[i]≤2)。

最初，数组的每个元素都是蓝色的。
有两种类型的操作：

支付一枚硬币，选择一个蓝色元素，将其涂成红色。
选择一个不等于 0 的红色元素和与其相邻的蓝色元素，将红色元素的数值减少 1，然后将蓝色元素涂成红色。
把每个元素都涂成红色，最少要支付多少金币？

输入
3
0 2 0
输出 1

输入
4
0 0 1 1
输出 2

输入
7
0 1 0 0 1 0 2
输出 4

Sol:

分组循环 +贪心。

内层循环寻找非 0 的段（连续子数组）。

对于非 0 的段（下标从 i 到 j），把端点 i 或者 j 涂成红色后，最终整个段都会变成红色。如果段中没有 2，那么 i-1 或者 j+1 会变成红色，取决于一开始涂的是哪个端点。

贪心来说，优先把左边的变成红色，即如果 i>0 且 i-1 不是红色，那么把 i-1 变成红色，否则把 j+1 变成红色。

如果段中有 2，那么把 2 涂成红色，最终 i-1 和 j+1 都会变成红色。

答案为段的个数，加上最后剩下的蓝色 0 的个数。

Code：

void solve()
{
    int n;
    cin >> n;
    vi a(n);
    FOR(i, 0, n-1) cin >> a[i];
    int ans = 0;
    for (int i = 0; i < n; ) {
        if (a[i] == 0) {
            ans++;
            i++;
            continue;
        }
        int st = i;
        bool h2 = false;
        for(; i < n && a[i]>0; i++) {
            if(a[i]==2) {
                h2=true;
            }
        }
        ans++;
        if (st>0 && a[st-1]==0) {
            ans--;
            if (!h2) {
                continue;
            }
        }
        if(i < n) {
            a[i] = 1;
            i++;
        }
    }
    cout << ans << endl;
}

Thu

Civilization_260C

输入 n m(0≤m<n≤3e5) 和 q(1≤q≤3e5)。
然后输入一个森林的 m 条边。注：森林由多棵树组成。
然后输入 q 个询问，格式如下：
“1 x”：输出节点 x 所在的树的直径。
“2 x y”：如果节点 x 和节点 y 在同一棵树，什么也不做；否则在这两棵树之间连一条边，要求连边后，得到的新树的直径最小。
所有输入的节点编号均从 1 开始。

输入
6 0 6
2 1 2
2 3 4
2 5 6
2 3 2
2 5 3
1 1
输出
4

Sol:

在周赛第四题的基础上，套一个带权并查集。

初始化：跑树形 DP 的同时，把树上的每个节点 x 和根节点 i 合并。在根节点 i 处记录直径信息 d[i]。

合并：按照周赛第四题的做法更新直径，如果要把 y 合并到 x 上，那么更新 d[x] = max(d[x], d[y], (d[x]+1)/2+(d[y]+1)/2+1)

const long long inf = numeric_limits<long long>::max();
struct dsu
{
    vector<int> fa, siz;
    dsu(int n)
    {
        init(n);
    }
    void init(int n)
    {
        fa.resize(n);
        siz.resize(n, 1);
        for (int i = 0; i < n; i++)
        {
            fa[i] = i;
        }
    }
    int find(int x)
    {
        int t = x;
        while (fa[x] != x)
        {
            x = fa[x];
        }
        while (t != x)
        {
            int p = t;
            fa[p] = x;
            t = fa[t];
        }
        return fa[x];
    }
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }

    void merge(int x, int y)
    {
        int root1 = find(x);
        int root2 = find(y);
        if (root1 != root2)
        {
            if (root1 < root2)
            {
                fa[root2] = root1;
                siz[root2] += siz[root1];
            }
            else
            {
                fa[root1] = root2;
                siz[root1] += siz[root2];
            }
        }
    }
    int size(int x)
    {
        int root = find(x);
        return siz[root];
    }
};
void solve()
{
    int n, m, q;
    cin >> n >> m >> q;
    dsu dsu(n+1);
    vector<vector<int> > g(n + 1);
    while (m--) {
        int a,b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
        dsu.merge(a, b);
    }
    vector<array<int, 2> > st(n + 1);
    vector<int> dis(n + 1);
    for (int i = 1; i <= n; i++)
    {
        dis[i] = 0;
    }
    auto bfs = [&](int x) -> int
    {
        queue<pair<int, int>> pq;
        st[x][0] = 1;
        pq.push(make_pair(x, 0));
        pair<ll, ll> tag = make_pair(-inf, -1);
        while (!pq.empty())
        {
            auto t = pq.front();
            pq.pop();
            int a = t.first, dis = t.second;
            if (dis > tag.first)
            {
                tag.first = dis;
                tag.second = a;
            }
            for (auto b : g[a])
            {
                if (st[b][0] == 0)
                {
                    st[b][0] = 1;
                    pq.push(make_pair(b, dis + 1));
                }
            }
        }
        ll ans = -inf;
        st[tag.second][1] = 1;
        pq.push(make_pair(tag.second, 0));
        while (!pq.empty())
        {
            auto t = pq.front();
            pq.pop();
            ll a = t.first, dis = t.second;
            ans = max(ans, dis);
            for (auto b : g[a])
            {
                if (st[b][1] == 0)
                {
                    st[b][1] = 1;
                    pq.push(make_pair(b, dis + 1));
                }
            }
        }
        return ans;
    };
    for (int i = 1; i <= n; i++)
    {
        if (st[i][0] == 0)
        {
            dis[i] = bfs(i);
        }
    }
    // for (int i = 1; i <= n; i++)
    // {
    //     cout << i << " this dis " << dis[i] << endl;
    // }
    while (q--)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int x;
            cin >> x;
            cout << dis[dsu.find(x)] << endl;
        }
        else
        {
            int x, y;
            cin >> x >> y;
            if (!dsu.same(x, y))
            {
                
                int fa1 = dsu.find(x);
                int fa2 = dsu.find(y);
                int d1 = dis[fa1];
                int d2 = dis[fa2];
                dsu.merge(x, y);
                int d = max({d1, d2, (d1 + 1) / 2 + (d2 + 1) / 2 + 1});
                if (fa1 < fa2)
                {
                    dis[fa1] = d;
                }
                else
                {
                    dis[fa2] = d;
                }
            }
        }
    } 
}

Fri

The Chocolate Spree

输入 n(2≤n≤1e5) 和长为 n 的数组 a(1≤a[i]≤1e9)，表示每个节点的点权。
然后输入一棵树的 n-1 条边，节点编号从 1 开始。

你需要从这棵树中，选出两条不相交的路径，也就是没有节点会同时出现在两条路径中。
输出这两条路径的节点点权之和的最大值。

输入
9
1 2 3 4 5 6 7 8 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
输出 25

输入
2
20 10
1 2
输出 30

Sol:

如果只有一条路径，做法类似求树的直径，把路径分解成左右两条链，dfs 返回从叶子到当前节点的最长链。

方法一：两次 DFS（换根 DP）

提示：枚举边，删除这条边，把这棵树一分为二，每部分只需要计算一条最大路径和。

分类讨论：

如果两条路径分别在两棵不相交子树中，那么做法和求直径是一样的，设当前节点为 v，维护前面遍历的 v 的儿子子树的最大路径和，加上当前儿子子树的最大路径和。

dfs 除了返回最长链，还要返回子树最大路径和。

如果两条路径分别在两棵相交子树中，考虑换根 DP，一条路径在子树 w 中，另一条路径从 v 开始的以下三条链中选两条：

v - w1 子树中的最长链（其中 w1 != w）

v - w2 子树中的最长链（其中 w2 != w）

v - 从父节点过来的最长链（在换根的过程中计算）

代码一

方法二：一次 DFS

如右图所示，下文把：从叶子往上到 v 的路径称作「链」。

dfs

由两条链拼成的路径叫做「路」。

由链 + 路组成的复合结构叫做「链路」。

注意链路中的链和路不一定在一起，可能间隔很远。

分类讨论，遍历 v 的子树列表时，假设当前遍历到子树 w，得到其「w 链」「w 路」「w 链路」，同时维护遍历过的子树的「最大链」「含 v 最大路」「不含 v 最大路」「最大链路」。其中「最大链」「最大链路」已经把 a[v] 算进去了。

如图，答案是以下三种情况的最大值： dfs

max(含 v 最大路, 不含 v 最大路) + w 路

最大链 + w 链路

最大链路 + w 链

其中「最大链路」是以下三种情况的最大值：

w 链路 + a[v]

不含 v 最大路 + w 链 + a[v]

最大链 + w 路

注意链路这一复合结构，一定是链在上，路在下，不然无法往上加点。不能是【含 v 最大路 + w 链】。

这也是为什么我们要区分这两种最大路。

含 v 最大路的计算方式同直径，取最大链 + w 链的最大值。

而最大链又是 w 链 + a[v] 的最大值。注意变量更新的顺序。

不含 v 最大路是 w 路的最大值。

代码二

int n, ans = 0;
vector<int> a;
vector<vector<int> > g;
tuple<int, int, int> dfs(int v, int fa) {
    int val = a[v];
    int maxChain = val;
    int maxPathV = val;
    int maxPathW = 0;
    int maxChainPath = val;

    for (int w : g[v]) {
        if (w == fa) continue;
        auto [chainW, pathW, chainPathW] = dfs(w, v);
        ans = max({ans, maxPathV + pathW, maxPathW + pathW, maxChain + chainPathW, maxChainPath + chainW});
        maxChainPath = max({maxChainPath, chainPathW + val, maxPathW + chainW + val, maxChain + pathW});
        maxPathV = max(maxPathV, maxChain + chainW);
        maxPathW = max(maxPathW, pathW);
        maxChain = max(maxChain, chainW + val);
    }

    return {maxChain, max(maxPathV, maxPathW), maxChainPath};
}
void solve()
{
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    g.resize(n);
    for (int i = 1; i < n; ++i) {
        int v, w;
        cin >> v >> w;
        --v; --w;
        g[v].push_back(w);
        g[w].push_back(v);
    }

    dfs(0, -1);
    cout << ans << endl;

}

codeforces

#数据结构 #图论 #贪心算法 #二分查找 #DFS（深度优先搜索） #树形DP #并查集 #最短路径 #动态规划 #分治法

茶7.1-7.5

https://www.polarishaw.top/2024/07/01/茶7.1-7.5/

作者

Polaris

发布于

2024年7月1日

许可协议

CMU15445-lecture8 上一篇

CMU15445-lecture7 下一篇