茶7.15-7.19

Tea7.15-7.19

Mon

输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤1e5，m 之和 ≤1e5。
每组数据输入 n(2≤n≤1e5) 和长为 n 的严格递增数组 a(0≤a[i]≤1e9)。
然后输入 m(1≤m≤1e5) 和 m 个询问，每个询问输入两个数 x 和 y，范围 [1,n] 且 x≠y。

数轴上有 n 个点，点 i 的坐标为 a[i]。
有两种移动方式：

从点 i 移动到离它最近的点，花费是 1。保证每个点只有唯一的离它最近的点。
从点 i 移动到点 j，花费是 |a[i]-a[j]|。

对于每个询问，输出从点 x 移动到点 y 的最小花费。

输入
1
5
0 8 12 15 20
5
1 4
1 5
3 4
3 2
5 1
输出
3
8
1
4
14

Sol:

Code:

void solve()
{
    int n;
    cin >> n;
    vi a(n);
    FOR(i, 0, n-1) cin >> a[i];
    vi near(n);
    near[0] = 1;
    near[n-1] = n-2;
    for(int i = 1 ; i < n - 1; i++) {
        near[i] = abs(a[i] - a[i-1])>abs(a[i]-a[i+1])? i+1:i-1;
    }
    // print(near);
    // cout << endl;
    vll suml(n),sumr(n);
    suml[0] = 0;
    for (int i = 1; i < n; i++) {
        // BUG(near[i-1]);
        // BUG(i);
        suml[i] = suml[i-1];
        suml[i] += near[i-1]==i?1:abs(a[i]-a[i-1]);
        // BUG(suml[i]);
    }
    // print(suml);
    // cout << endl;
    sumr[n-1] = 0;
    for (int i = n-2; i >= 0; i--) {
        sumr[i] = sumr[i+1];
        sumr[i] += near[i+1]==i?1:abs(a[i]-a[i+1]);
    }
    // print(sumr);
    // cout << endl;
    int q;
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        l--;r--;
        if(l < r) {
            cout << suml[r] - suml[l] << endl;
        } else {
            cout << sumr[r] - sumr[l] << endl;
        }
    }
}

Feb

Smilo and Monsters_907C

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

一开始 cnt = 0。
有两种操作，每种都可以执行任意次。
第一种：把一个大于 0 的 a[i] 减少 1，然后 cnt += 1。
第二种：把一个大于等于 cnt 的 a[i] 减少 cnt，然后 cnt = 0。

把所有 a[i] 都变成 0，最少要操作多少次？

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

Sol:

提示 1：从特殊情况入手。如果有一个数非常大，最优操作是什么样的？

如果有一个数非常大，可以把其他数都通过操作一搞定，最后把操作二用到这个数上。

这启发我们，用操作一操作小的数，用操作二操作大的数，可以让总操作次数尽量小。

也可以反过来思考：如果用操作一操作大的数，操作二操作小的数，就会因为操作二的限制，导致操作二必须执行很多次。

提示 2：把 cnt 理解为能量，操作一积累能量，操作二释放能量，但释放多少，其实可以自己决定。

设 s = sum(a)，left = ceil(s/2)。

把 a 从小到大排序。不断地把 left 减少 a[i]，直到 left < a[i] 为止。此时我们积累了足够的能量，剩余的 n-i 个数（i 从 0 开始）全部用操作二搞定。

答案为 ceil(s/2) + n-i。代码

Code:

void solve()
{
    int n;
    cin >> n;
    vi a(n);
    FOR(i, 0, n-1) cin >> a[i];
    if (n == 1) {
        cout << a[0] / 2 + a[0] % 2 + (a[0] > 1?1 : 0) << endl;
        return;
    }
    sort(a);
    vll sum(n);
    sum[0] = a[0];
    for (int i = 1; i < n; i++) {
        sum[i] = sum[i - 1] + a[i];
    }
    int right = n;
    for (int i = n - 2; i >= 0; i--) {
        if (sum[n-1] - sum[i] >= sum[n-1] / 2) {
            right = i;
            break;
        }
    }
    //BUG(mid);
    //BUG(right);
    cout << n - right - 1 + sum[n-1] / 2 + sum[n-1] % 2 << endl;
}

Wed

Neutral Tonality_908B

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

把 b 中所有元素以任意顺序在任意位置插入 a 中，得到数组 c。
例如 a=[3,1,1]，b=[9,4,5]，插入后可以是 c=[3,1,4,1,5,9]。

你需要使 LIS(c) 最短。（LIS 是最长严格递增子序列）
输出任意符合要求的 c。

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

Sol：

构造题。

从特殊到一般，思考如下情况：

a 单调递减。

a 单调递增。

min(a) = a[0]

min(a) ≠ a[0]

构造方法：先把 b 从大到小排序。然后双指针遍历 a 和 b 合并成 c，在把 a[i] 加到 c 之前，必须把 >= a[i] 的 b[j] 都加到 c。

Code:

void solve()
{
    int n,m;
    cin >> n >> m;
    vi a(n),b(m);
    FOR(i, 0, n-1) cin >> a[i];
    FOR(i, 0, m-1) cin >> b[i];
    rsort(b);
    vi c;
    int l = 0;
    for (int i = 0; i < n; i++) {
        while(b[l] >= a[i] && l < m) {
            c.pb(b[l]);
            l++;
        }
        c.pb(a[i]);
    }
    while(l < m) {
        c.pb(b[l]);
        l++;
    }
    print(c);cout << '\n';
}

Thu

Range Deleting 65E

输入 n(1≤n≤1e6) x(1≤x≤1e6) 和长为 n 的数组 a(1≤a[i]≤x)。

定义 D(a,L,R) 为删除 a 中所有元素值在 [L,R] 中的元素后，剩余的元素组成的数组（不改变顺序）。

输出有多少对 (L,R) 满足 1<=L<=R<=x 且 D(a,L,R) 是非降数组，即相邻元素左边 <= 右边。

输入
3 3
2 3 1
输出 4

输入
7 4
1 3 1 2 2 4 3
输出 6

Sol:

本题是近期打卡题【力扣 2972. 统计移除递增子数组的数目 II】的变形题。

由于思路和代码都非常接近，推荐先把力扣那题做了。

核心思路：删除元素后，对于剩余的每个元素，考察其出现位置的区间，这些区间必须不相交。

记录每个元素首次和最后一次出现的位置。

定义 ps[v].l 表示元素 v 首次出现的位置，ps[v].r 表示元素 v 最后一次出现的位置。

用闭区间 [ps[v].l, ps[v].r] 表示元素 v。

对于剩余元素中的两个数 v 和 w，如果 v < w，那么区间 [ps[v].l, ps[v].r] 必须在区间 [ps[w].l, ps[w].r] 的左侧，即 ps[v].r < ps[w].l。

首先考虑一个简单情况：1 到 x 中的每个数都在数组 a 中。

和力扣 2972 题代码一样，双指针，把「元素值比大小」改成 ps[v].r < ps[w].l 这样的「区间左右端点比大小」即可。

本题的一个难点是，如果有元素不在 a 中，怎么算清楚这种情况，尤其是不能重复统计。

首先把 ps 中的元素值在 a 中的区间提取出来，得到数组 b。

其中 b[i].l 和 b[i].r 是第 i 个区间的左右端点，b[i].v 是第 i 个区间对应的元素值。

看上去在 b 数组上「区间左右端点比大小」就行，怎么把不在 a 中的元素值考虑进来呢？

和 2972 题灵神的题解一样，首先讨论删除后缀的情况，然后讨论一般情况。

删除后缀 b[k] 到 b[n-1]，其中 n 是 b 的长度，k <= i+1。

那么删除的范围，最小值 <= b[i+1].v，最大值 >= b[n-1].v，根据乘法原理，这一共有 b[i+1].v * (x + 1 - b[n-1].v) 个。

然后讨论删除的不是后缀的情况。

删除 b[k] 到 b[j-1]，保留 b[j] 到 b[n-1]，那么删除的范围，最小值 <= b[i+1].v，最大值在左闭右开区间 [b[j-1].v, b[j].v) 中，根据乘法原理，这一共有 b[i+1].v * (b[j].v - b[j-1].v) 个。

Code:

void solve()
{
    ll n, x, y;
    cin >> n >> x;
    node *ps = new node[x + 1];
    for (int i = 0; i < n; i++) {
        cin >> y;
        if (ps[y].l == INT_MAX) {
            ps[y].l = i;
            ps[y].v = y;
        }
        ps[y].r = i;
    }
    vector<node> b;
    for(int i = 1; i <= x; i ++){
        if(ps[i].r >= 0){
            b.emplace_back(ps[i]);
        }
    }
    n = b.size();
    int i = 0, j = n - 1;
    while(i < n - 1 && b[i].r < b[i + 1].l) i ++;
    if(i == n - 1){
        cout << x * (x + 1) / 2 << endl;
        return;
    }
    long long ans = b[i + 1].v * (x + 1 - b[n - 1].v);
    while(j >= 0 && (j == n - 1 || b[j].r < b[j + 1].l)){
        while(i >= 0 && b[i].r >= b[j].l) i --;
        ans += b[i + 1].v * (b[j].v - b[j - 1].v);
        j --;
    }
    cout << ans << endl;
    delete[] ps;
}

Fri

Playlist for Polycarp_568G

输入 n(1≤n≤50) 和 T(1≤T≤2500)。有 n 首歌。
然后输入 n 行，每行两个数 t(1≤t≤50) 和 g(1≤g≤3)，表示第 i 首歌的时长和类型。

你需要从这 n 首歌中选出若干首歌，组成一个播放列表，满足：

总时长为 T。
没有重复歌曲。
相邻歌曲的类型不同。注意这个列表只播放一次，所以不考虑首尾。

有多少种方案？注意歌曲的顺序不同，也算不同的方案。
答案模 1e9+7。

输入
3 3
1 1
1 2
1 3
输出 6

输入
3 3
1 1
1 1
1 3
输出 2

输入
4 10
5 3
2 1
3 2
5 1
输出 10

Sol:

初步分析：

原问题可以拆分成如下两个问题：

不考虑总时长（以及歌曲的排列），计算从这 n 首歌中选出 i 个类型 1，j 个类型 2，k 个类型 3，且相邻歌曲类型不同的方案数。
不考虑相邻歌曲类型不同（以及歌曲的排列），计算从这 n 首歌中选出 i 个类型 1，j 个类型 2，k 个类型 3，且总时长为 t 的方案数。

两个方案数相乘，再乘上排列数 i!j!k!，就可以得到从这 n 首歌中选出 i 个类型 1，j 个类型 2，k 个类型 3，总时长为 t 且相邻歌曲类型不同的方案数。

另一种理解方式：相当于有若干个格子和三种颜色，问题 1 负责涂色（保证相邻格子颜色不同），问题 2（乘上 i!j!k*!）负责给每个格子放上具体的歌曲（颜色要匹配）。

枚举所有的i，j，k，累加方案数，即为答案。

问题1:

不考虑总时长（以及歌曲的排列），计算从这n首歌中选出i个类型1，j个类型2，k个类型3，且相邻歌曲类型不同的方案数。

用状态机DP解决。

定义$c_{i,j,k,x}$表示从这n首歌中选出i个类型1，j个类型2，k个类型3，且最后一首歌的类型为x且响铃歌曲类型不同的方案书。

枚举上一首歌的类型，那么有

$c_{i+1,j,k,1} = c_{i,j,k,2} + c_{i,j,k,3}\\ c_{i+1,j,k,2} = c_{i,j,k,1} + c_{i,j,k,3}\\ c_{i+1,j,k,3} = c_{i,j,k,1} + c_{i,j,k,2}$

这里用刷表法转移

初始值$c{1,0,0,1}=c{0,1,0,2}=c_{0,0,1,3} = 1$

问题2

不考虑相邻歌曲类型不同（以及歌曲的排列），计算从这n首歌中选出i个类型1，j个类型2，k个类型3，且总时长为t的方案数。

用多维0-1背包解决。

优化前

定义$f_{p,i,j,k,t}$表示从前p首歌中选出i个类型1，j个类型2，k个类型3，且总时长为t的方案数。需要O(n⁴T)的时间和空间。

优化

考虑继续拆分问题：

计算从这n首歌中选出i个类型1，且总时长为t的方案数。记为$f_{i,t}$。
计算从这n首歌中选出j个类型2，k个类型3，且总时长为T-t的总方案数。记为$g_{j,k,T-t}$。

两个方案数相乘，就是问题2的方案数。

汇总

枚举i,j,k。

从这n首歌中选出i个类型1，j个类型2，k个类型3，总时长为t且相邻歌曲类型不同的方案数为

$w_{i,j,k} = i!j!k!*(c_{i,j,k,1}+c_{i,j,k,2}+c_{i,j,k,3})*\sum_{t=0}^T{f_{i,t}g_{j,k,T-t}}$

答案为

$\sum_{i=0}^{cnt_1}\sum_{j=0}^{cnt_2}\sum_{k=0}^{cnt_3}w_{i,j,k}$

其中cnt_x为输入的n首歌中的类型为x的歌曲个数。

代码实现时，类型改成0，1，2。

Code:

void solve()
{
    int n, tot, w, tp;
    cin >> n >> tot;
    vector<vector<int> > f(n + 2, vector<int>(tot + 1, 0));
    f[0][0] = 1;

    vector<vector<vector<int> > > g(n + 2, vector<vector<int> >(n + 2, vector<int>(tot + 1, 0)));
    g[0][0][0] = 1;

    vector<int> cnt(3, 0);

    for (int i = 0; i < n; i++) {
        cin >> w >> tp;
        tp--;
        if (tp == 0) {
            for (int j = cnt[0]; j >= 0; j--) {
                for (int t = tot; t >= w; t--) {
                    add(f[j + 1][t], f[j][t - w]);
                }
            }
        } else {
            vector<int> is(3, 0);
            is[tp] = 1;
            for (int j = cnt[1]; j >= 0; j--) {
                for (int k = cnt[2]; k >= 0; k--) {
                    for (int t = tot; t >= w; t--) {
                        add(g[j + is[1]][k + is[2]][t], g[j][k][t - w]);
                    }
                }
            }
        }
        cnt[tp]++;
    }
    vector<int> fac(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }

    int ans = 0;
    vector<vector<vector<vector<int> > > > c(cnt[0] + 2, vector<vector<vector<int> > >(cnt[1] + 2, vector<vector<int> >(cnt[2] + 2, vector<int>(3, 0))));
    c[1][0][0][0] = 1;
    c[0][1][0][1] = 1;
    c[0][0][1][2] = 1;
    for (int i = 0; i <= cnt[0]; i++) {
        for (int j = 0; j <= cnt[1]; j++) {
            for (int k = 0; k <= cnt[2]; k++) {
                int sum = 0;
                for (int t = 0; t <= tot; t++) {
                    sum = (sum + f[i][t] * g[j][k][tot - t]) % mod;
                }
                add(ans, fac[i] * fac[j] % mod * fac[k] % mod * (c[i][j][k][0] + c[i][j][k][1] + c[i][j][k][2]) % mod * sum);
                add(c[i + 1][j][k][0], c[i][j][k][1] + c[i][j][k][2]);
                add(c[i][j + 1][k][1], c[i][j][k][0] + c[i][j][k][2]);
                add(c[i][j][k + 1][2], c[i][j][k][0] + c[i][j][k][1]);
            }
        }
    }

    cout << ans << endl;
}

codeforces

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

茶7.15-7.19

https://www.polarishaw.top/2024/07/15/茶7.15-7.19/

作者

Polaris

发布于

2024年7月15日

许可协议

why kafka so fast? 上一篇

why using mq? 下一篇