头像

YimingLi

浙江大学 $\href{https://github.com/upupming}{My\ GitHub}$




离线:16分钟前


活动打卡代码 AcWing 279. 自然数拆分

YimingLi
26分钟前
/*
f[i][j] 表示前 i 个数,总和为 j 的方案总数
每个数可以选任意多次,属于完全背包
*/
#include <iostream>
using namespace std;
const int N = 4010;

int n;
long long f[N], P = 2147483648;
int main() {
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            f[j] = (f[j] + f[j - i]) % P;
        }
    }
    cout << f[n] - 1 << endl;
    return 0;
}



活动打卡代码 AcWing 278. 数字组合

YimingLi
52分钟前
/*
f[i][j] 表示前 i 个数,和是 j 的方案总数
0/1 背包
*/
#include <iostream>
using namespace std;
const int N = 110, M = 1e4 + 10;

int a[N], f[M], n, m;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= a[i]; j--) {
            f[j] += f[j - a[i]];
        }
    }
    cout << f[m] << endl;
    return 0;
}



活动打卡代码 AcWing 277. 饼干

YimingLi
6小时前
/*
贪心 (邻项交换): 贪婪度大的孩子应该获得更多的饼干
    g[i] < g[j], 如果 i 获得的饼干更多 (c[i] > c[j]),可以将饼干数交换,其他的孩子不变,交换之后,i 增加了 g[i] 的怒气但是 j 减少了 g[j] 的怒气,总怒气减少。
把 N 个孩子按照贪婪度从大到小排序,他们分配到的饼干数将是单调不增的

f[i][j]:
状态表示:
    集合: 前 i 个孩子,一共分配 j 块饼干时,
    属性: 这 i 个孩子的怨气总和最小值。
状态计算:
    有两种情况:
    1. 第 i+1 个孩子获得的饼干数比第 i 个孩子少,a[i+1] = i
    2. 第 i+1 个孩子获得的饼干数与第 i 个孩子相同,此时还需要知道 i 前面有几个孩子与 i 获得的饼干数也相同,才能计算出 a[i+1]

    因此需要记录: 「第 i 个孩子获得的饼干数」、「i 前面有多少个孩子与 i 获得的饼干数相同」

    为了避免额外的记录这两个信息,分别做如下的处理:

    1. 若第 i 个孩子的饼干数大于 1,每人少拿一块饼干,饼干数相对顺序不变,因此 f[i][j] 和 f[i][j-1] 是等价的
    2. 若第 i 个孩子的饼干数等于 1,枚举一下前面有多少个孩子也获得 1 块饼干就可以了
初始条件 f[0][0] = 0
终止条件 f[n][m]
还需要求一下方案,只需要按照相对顺序分配好,之后剩下的全部给最大的那个人就可以了。
*/
#include <algorithm>
#include <climits>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 40, M = 5010;
typedef long long LL;

struct P {
    int g, idx, sum;
} p[N];
int n, m, ans[N];
LL f[N][M];
int main() {
    cin >> n >> m;
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].g;
        p[i].idx = i;
    }
    // 按照贪婪值从大到小排序,保证后续分的饼干数从大到小
    sort(p + 1, p + 1 + n, [](auto& a, auto& b) {
        return a.g > b.g;
    });
    for (int i = 1; i <= n; i++) {
        p[i].sum = p[i - 1].sum + p[i].g;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= m; j++) {
            // 每人少拿一块饼干
            f[i][j] = f[i][j - i];
            // [k+1, i] 之间的孩子也获得 1 块饼干
            for (int k = 0; k < i; k++) {
                f[i][j] = min(
                    f[i][j],
                    f[k][j - (i - k)] + k * (p[i].sum - p[k].sum));
            }
        }
    }
    cout << f[n][m] << endl;

    int i = n, j = m, h = 0;
    while (i && j) {
        if (j >= i && f[i][j] == f[i][j - i])
            j -= i, h++;
        else {
            for (int k = 0; k < i; k++) {
                if (f[i][j] == f[k][j - (i - k)] + k * (p[i].sum - p[k].sum)) {
                    for (int u = i; u > k; u--) {
                        ans[p[u].idx] = 1 + h;
                    }
                    j = j - (i - k);
                    i = k;
                    break;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    return 0;
}



活动打卡代码 AcWing 276. I-区域

YimingLi
19小时前
/*
「凸」的定义有点迷,直接按照题目的左右边界递增递减性质判断即可
状态表示:
f[i][j][l][r][x][y]:
    集合: 所有选完前 i 行,且一共选择了 j 个格子,且第 i 行选择的左边界是 l,右边界是 r,且左边界的递增/递减状态是 x,右边界的递增/递减状态是 y。
        递增递减状态是一个状态机模型,例如 x 在递减状态,合法的转换只能是变成递减状态
        对于 x: 递减只能由递减状态转移而来
        对于 y: 递增只能由递增状态转移而来
        x, y 统一规定: 1 表示递减,0 表示递增
    属性: max
状态计算:

f[i][j][l][r][1][0]:
x = 1 表示左边递减 (扩张),y = 0 表示右边递增 (扩张)
将这个集合按照上一个状态进行分情况讨论:
对于左边界而言,上一个状态只能是递减 (1)
对于右边界而言,上一个状态只能是递增 (0)
f[i-1, j-(r-l+1), p, q, 1, 0], 其中 l <= p <= q <= r
f[i-1, j-(r-l+1), p, q, 1, 0] + (w[i, l] + ... + w[i, r])

---

f[i][j][l][r][1][1]:
x = 1 表示左边递减 (扩张),y = 0 表示右边递减 (收缩)
l <= p <= r <= q (画下示意图就出来了)
        |-> 注意这里是因为上下两行必须是连通的
可由 (x, y) = (1, 1) 和 (1, 0) 转移过来
---
x = 0 左收缩, y = 0 右扩张
p <= l <= q <= r
可由 (x, y) = (0, 0) 和 (1, 0) 转移过来
---
x = 0 左收缩, y = 1 右收缩
p <= l <= r <= q
可由 (x, y) = (0, 1) 和 (0, 0) 和 (1, 0) 和 (1, 1)
转移过来

最后还需要求方案,需要记录从哪里来的
*/
#include <iostream>
using namespace std;
const int N = 16;

int n, m, k;
int w[N][N];
int f[N][N * N][N][N][2][2];

// 表示当前状态从哪个状态过来的
struct State {
    int i, j, l, r, x, y;
} g[N][N * N][N][N][2][2];

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> w[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            for (int l = 1; l <= m; l++) {
                for (int r = l; r <= m; r++) {
                    // 总共可以填的个数小于当前行的数量,是不可能的,相当于一个剪枝,避免后面的下标索引出现负数
                    if (j < r - l + 1) continue;

                    // 左扩张,右扩张 (x, y) = (1, 0)
                    {
                        auto &vf = f[i][j][l][r][1][0];
                        auto &vg = g[i][j][l][r][1][0];
                        // l <= p <= q <= r
                        for (int p = l; p <= r; p++) {
                            for (int q = p; q <= r; q++) {
                                int val = f[i - 1][j - (r - l + 1)][p][q][1][0];
                                if (vf < val) {
                                    vf = val;
                                    vg = {i - 1,
                                          j - (r - l + 1), p, q, 1, 0};
                                }
                            }
                        }
                        for (int u = l; u <= r; u++) vf += w[i][u];
                    }
                    // 左扩张,右收缩 (x, y) = (1, 1)
                    {
                        auto &vf = f[i][j][l][r][1][1];
                        auto &vg = g[i][j][l][r][1][1];
                        // l <= p <= r <= q
                        for (int p = l; p <= r; p++) {
                            for (int q = r; q <= m; q++) {
                                for (int y = 0; y <= 1; y++) {
                                    int val = f[i - 1][j - (r - l + 1)][p][q][1][y];
                                    if (vf < val) {
                                        vf = val;
                                        vg = {i - 1,
                                              j - (r - l + 1), p, q, 1, y};
                                    }
                                }
                            }
                        }
                        for (int u = l; u <= r; u++) vf += w[i][u];
                    }
                    // 左收缩,右扩张 (x, y) = (0, 0)
                    {
                        auto &vf = f[i][j][l][r][0][0];
                        auto &vg = g[i][j][l][r][0][0];
                        //p <= l <= q <= r
                        for (int p = 1; p <= l; p++) {
                            for (int q = l; q <= r; q++) {
                                for (int x = 0; x <= 1; x++) {
                                    int val = f[i - 1][j - (r - l + 1)][p][q][x][0];
                                    if (vf < val) {
                                        vf = val;
                                        vg = {i - 1,
                                              j - (r - l + 1), p, q, x, 0};
                                    }
                                }
                            }
                        }
                        for (int u = l; u <= r; u++) vf += w[i][u];
                    }
                    // 左收缩,右收缩 (x, y) = (0, 1)
                    {
                        auto &vf = f[i][j][l][r][0][1];
                        auto &vg = g[i][j][l][r][0][1];
                        // p <= l <= r <= q
                        for (int p = 1; p <= l; p++) {
                            for (int q = r; q <= m; q++) {
                                for (int x = 0; x <= 1; x++) {
                                    for (int y = 0; y <= 1; y++) {
                                        int val = f[i - 1][j - (r - l + 1)][p][q][x][y];
                                        if (vf < val) {
                                            vf = val;
                                            vg = {i - 1,
                                                  j - (r - l + 1), p, q, x, y};
                                        }
                                    }
                                }
                            }
                        }
                        for (int u = l; u <= r; u++) vf += w[i][u];
                    }
                }
            }
        }
    }

    int ans = 0;
    State state;
    for (int i = 1; i <= n; i++) {
        for (int l = 1; l <= m; l++) {
            for (int r = 1; r <= m; r++) {
                for (int x = 0; x <= 1; x++) {
                    for (int y = 0; y <= 1; y++) {
                        int val = f[i][k][l][r][x][y];
                        if (ans < val) {
                            ans = val;
                            state = {i, k, l, r, x, y};
                        }
                    }
                }
            }
        }
    }
    printf("Oil : %d\n", ans);
    while (state.j) {
        for (int i = state.l; i <= state.r; i++) printf("%d %d\n", state.i, i);
        state = g[state.i][state.j][state.l][state.r][state.x][state.y];
    }

    return 0;
}




YimingLi
22小时前
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

int target[N], arr[N], n, pos[N];
int main() {
    memset(pos, -1, sizeof pos);
    cin >>n;
    for (int i = 0; i < n; i++) cin >> target[i];
    for (int i = 0; i < n; i++) cin >> arr[i];
    int ans = 0;
        for (int i = 0; i < n; i++)
            pos[target[i]] = i;
        // a 维护 target 里面的数在 arr 里面出现的下标
        // a 的最长上升子序列长度就是 target 和 arr 两者的最长公共子序列长度
        vector<int> a;
        for (auto x : arr) {
            if (pos[x]!= -1) a.push_back(pos[x]);
        }

        int len = 0;
        vector<int> q(a.size() + 1);
        for (int i = 0; i < a.size(); i++) {
            int l = 0, r = len;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (q[mid] < a[i])
                    l = mid;
                else
                    r = mid - 1;
            }
            len = max(len, r + 1);
            q[r + 1] = a[i];
        }
        cout << len << endl;

    return 0;
}


活动打卡代码 AcWing 3499. 序列最大收益

/*
最长上升子序列问题
状态表示:
f[i][j]:
    集合: 只考虑前 i 个数,共删除了 j 个数且保留了第 i 个数的所有方案的集合
    属性: 最大收益
状态计算:
    倒数第 2 个数是第 u 个数,中间一共删除了 [u+1, i-1],那么剩下的最优方案就是 f[u][j-(i-u-1)],需要再加上 w[a_u][a_i]
利用反证法可证明第 1 个数和最后一个数一定会保留,可以省去边界判断
*/
#include <cstring>
#include <iostream>
using namespace std;
const int N = 210;

int a[N], w[N][N], f[N][N], n, m, k;
int main() {
    cin >> n >> k >> m;
    for (int i = 1; i <= m; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> w[i][j];
        }
    }
    memset(f, -1, sizeof f);
    f[1][0] = 0;
    for (int i = 2; i <= m; i++) {
        for (int j = 0; j <= k && j <= i; j++) {
            for (int u = 0; u <= i - 1; u++) {
                if (j - (i - u - 1) >= 0)
                    f[i][j] = max(
                        f[i][j],
                        f[u][j - (i - u - 1)] + w[a[u]][a[i]]);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= k; i++) ans = max(ans, f[m][i]);
    cout << ans << endl;
    return 0;
}



活动打卡代码 AcWing 3493. 最大的和

/*
枚举所有可能的区间 [l, l+k-1],将这个区间内所有的元素都置为可选
*/
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;

int a[N], n, k, st[N], lft[N], rht[N];
LL sum[N], st_sum[N];
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> st[i];
        st_sum[i] = st_sum[i - 1] + st[i] * a[i];
    }
    LL ans = 0;
    for (int l = 1; l + k - 1 <= n; l++) {
        int r = l + k - 1;
        ans = max(ans,
                  // [l, r]
                  sum[r] - sum[l - 1] +
                      //   [1, l-1]
                      st_sum[l - 1] +
                      //   [r+1, n]
                      st_sum[n] - st_sum[r]);
    }
    cout << ans << endl;
    return 0;
}




Google KickStart 2021 Round B

比 A 轮还是难一点,只拿了 37 分,思维和代码熟练度都欠缺,再接再厉。

  • Score: 37
  • Rank: 1946

A. Increasing Substring

算法 —— 线性扫描

  • 从前到后扫描整个字符串,dp[i] 表示以 i 为结尾的最长单调子串的长度
  • 转移方程为:

    • dp[i] = dp[i]+1, s[i] > s[i-1]
    • dp[i] = 1, s[i] <= s[i-1]
  • 由于状态计算只需要使用上一个下标 dp[i-1] 的值,所以将数组可以优化成一个变量,滚动更新。

时间复杂度

  • 扫描一遍字符串: O(n)

C++ 代码

#include <iostream>
using namespace std;

int t, n, k;
string s;

void solve() {
    int dp = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] > s[i - 1])
            dp += 1;
        else
            dp = 1;
        cout << dp << " ";
    }
    cout << endl;
}

int main() {
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cin >> n >> s;
        s = ' ' + s;
        printf("Case #%d: ", i);
        solve();
    }
    return 0;
}

B. Longest Progression

比较复杂的一个分类讨论,当时没有梳理清楚逻辑关系,直接在 2020 RoundE Problem A 的基础上写的暴力(暴力枚举差分改变的地方,然后运行原来的朴素算法),O(N^2) 的所以会在 Test 2 上 TLE。

算法 —— 差分+贪心

  • 计算最长等差数列和 2020 RoundE Problem A 一样,是首先计算差分数组,然后统计差分数组里面最长的具有相同数的子串的长度 len,答案就是 len+1
    • 例如: 原数组 A=[1,3,4,7,9,11],差分数组 D=[2,1,3,2,2](其中 D[i] = A[i+1]-A[i], i = 1,...n-1),最长相同数子串 [2,2],长度为 2,对应最长等差数列为 [7,9,11],长度为 3
  • 现在可以在原来的基础上修改一个数,修改一个数等价于修改两个差分值
    • 不妨设你将 A[i] 增加 x,那么修改之后 D[i-1] 会增加 xD[i] 会减少 x,两者的总和保持不变。这个修改对最终的差分数组的影响需要分情况讨论
    • 可以先将差分数组分成若干段,每一段都是一个包含全部一样数 d 的子串,不妨设起始下标为 D[i],长度为 k
    • 我们一定是修改下个子串的第一个差分值让其等于当前子串的差分值,这样能使答案优于不改变任何数的时候的答案
    • 改变了子串的第一个差分值 D[i+k] 之后,会对紧接着的差分值 D[i+k+1] 产生影响,需要分情况考虑
    • 例子 1 (D[i+k] + D[i+k+1] != 2d): D=[1,1],[3],[0,0],考虑第 1 个子串,修改第 2 个子串的第一个数之后就是: D=[1,1],[1],[2,0],最终的 len=3
    • 例子 2 (D[i+k] + D[i+k+1] == 2d, D[i+k+2] != d): D=[1,1],[2],[0,0],考虑第 1 个子串,修改第 2 个子串的第一个数之后就是: D=[1,1],[1],[1,0],最终的 len=4
    • 例子 3 (D[i+k] + D[i+k+1] == 2d, D[i+k+2] == d): D=[2],[1],[3],[2,2],考虑第 1 个子串,修改第 2 个子串的第一个数之后就是: D=[2],[2],[2],[2,2],最终的 len=5

时间复杂度

  • 预处理差分数组、按照相等值分段: O(N)
  • 依次考虑每块,并且对于每一块,考虑上面 3 种情况: O(N)

C++ 代码

  • 实际实现时,没有必要存储每个子串的长度 k,可以通过 upper_bound 实现,用 set 只会增加一个 log 的时间复杂度
  • 对于例子 A=[1,0,1,1], D=[-1,1,0],最优解是修改第 1 和第 2 个差分值,为了避免特殊判断,将 D 反转重新算一遍取最大即可
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;

int t, n, a[N], d[N];

int solve() {
    for (int i = 1; i <= n - 1; i++) {
        d[i] = a[i + 1] - a[i];
    }
    // 每一个子串的起始下标
    set<int> startPos;
    for (int i = 1; i <= n - 1; i++) {
        if (i == 1 || d[i] != d[i - 1]) {
            // i 是一个新的分段的起点
            startPos.insert(i);
        }
    }
    // 哨兵
    startPos.insert(n);

    // 枚举所有的子串,尝试修改后面的子串的第 1 个值
    int m = startPos.size(), ans = 0;
    for (auto it = startPos.begin(); it != startPos.end(); it++) {
        int i = *it, val = d[i];
        if (i > n - 1) break;
        auto it2 = it;
        it2++;

        // j 是下一个子串的开头
        int j = *it2;
        // 区间 [i, j)
        int tmp = j - i;
        // 区间 [i, j]
        if (j <= n - 1) tmp++;
        // 区间 [i, j+1]
        if (j + 1 <= n - 1 && d[j] + d[j + 1] == 2 * val) {
            tmp++;

            if (j + 2 <= n - 1 && d[j + 2] == val) {
                int k = *startPos.upper_bound(j + 2);
                // 区间 [i, k)
                assert(k <= n && d[k - 1] == val);
                tmp = k - i;
            }
        }
        ans = max(ans, tmp);
    }
    return ans + 1;
}

int main() {
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        int ans1 = solve();
        reverse(a + 1, a + 1 + n);
        int ans2 = solve();
        printf("Case #%d: %d\n", i, max(ans1, ans2));
    }
    return 0;
}

C. Consecutive Primes

比赛的时候想到了先用线性筛计算 [1, sqrt(Z)] 范围内的素数,然后二分小因子的算法,总时间复杂度为 O(sqrt{Z} + log cnt),其中 cnt 表示[1, sqrt(Z)] 范围内的素数总个数。显然无法过 Test 3。主要瓶颈在线性筛算法上。

注:根据 lucifer1004 的解释,用线性筛也是可以过的,但是要将线性筛外提,所有的测试用例只运行一次线性筛。不过这是因为 KickStart 评测机的时间限制比较宽裕,我们赛后还是要追求最好的解法。

算法 —— 素数判断

  • 官方给的解析反倒更加简单,不需要用素数筛,只需要用素数判定算法即可,比第 2 题更加好实现,关键在于利用了条件「两个素数因子是相邻的」
  • 假设最终的答案是 N (N <= Z),那么最终两个相邻素数因子一定是 3 种情况:
    • sqrt(Z) 左侧最大、sqrt(Z) 右侧最小,这两个素数之积如果小于 Z,那么一定是答案
    • 否则,sqrt(Z) 左侧最近的两个素数,这两个素数之积一定小于 Z
  • 根据素数的数学性质,可以知道 Z=1e18, sqrt(Z)=1e9 时,临近的质数之差的绝对值不会超过 282,直接暴力的枚举即可
  • 这样看来,第三题比第二题是线上还简单很多,主要是有需要一个思维上的转变

时间复杂度

  • 枚举三个数: O(282 * 3)
    • 判断是否是质数: fourth_root(z)z 的四次方根)
  • 总时间复杂度: O(282 * 3 * fourth_root(z))

C++ 代码

#include <iostream>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;

int t;
LL z;

bool is_prime(LL x) {
    if (x <= 1) return false;
    for (LL i = 2; i <= x / i; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

LL solve() {
    LL x = sqrt(z), a, b, c;

    LL t = x;
    for (; !is_prime(t); t--) {
        ;
    }
    b = t--;

    // Z = 6 时,特殊情况,不存在第二小的质因子 a
    if (t < 2) {
        a = z;
    } else {
        for (; !is_prime(t); t--) {
            ;
        }
        a = t;
    }

    t = x + 1;
    for (; !is_prime(t); t++) {
        ;
    }
    c = t;

    if (b * c <= z) return b * c;
    if (a * b <= z) return a * b;
    assert(false);
    return -1;
}

int main() {
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cin >> z;
        printf("Case #%d: %lld\n", i, solve());
    }
    return 0;
}

D. Truck Delivery

暴力解法

暴力解法只能过 Test 1

算法 —— DFS + 暴力

  • DFS 一遍,计算每个点的到 1 的简单路径,记录 pre 数组,这里使用常用的遍历无向树的套路:dfs 参数 x 表示正在遍历的节点, father 记录从哪个方向来的,下一个节点不是 father 的时候往下遍历
  • 初始化答案 ans=0,对于每一个查询,枚举路径上所有的点,依次比较每条边 l 值和当前查询的 w,看是否要更新答案 ans = gcd(ans, a)

时间复杂度

  • DFS: O(N)
  • 遍历所有询问: O(Q)
    • 每个询问需要访问路径上所有的边,最坏情况下最长边为 N-1: O(N)
      • 最多每条边计算一次 gcd
    • 计算 N 个数的 gcd 的总时间复杂度为 O(N + log(max{A})),注意不是 O(N * log(max{A})),证明先略去
  • 总时间复杂度: O(Q(N + log(max{A})))

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10, Q = 1e5 + 10;
typedef long long LL;

int t, n, q, pre[N];
vector<int> e[N];
unordered_map<int, unordered_map<int, LL>> L, A;

LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

void dfs(int x, int fa) {
    pre[x] = fa;
    for (auto &y : e[x]) {
        if (y != fa) {
            dfs(y, x);
        }
    }
}

void solve() {
    memset(pre, -1, sizeof pre);
    dfs(1, -1);
    while (q--) {
        int c, w;
        cin >> c >> w;
        LL ans = 0;
        while (c != 1) {
            LL l = L[c][pre[c]], a = A[c][pre[c]];
            if (w >= l) {
                ans = gcd(ans, a);
            }
            c = pre[c];
        }
        cout << ans << " ";
    }
    cout << endl;
}

int main() {
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cin >> n >> q;
        for (int i = 1; i <= n; i++) e[i].clear();
        L.clear(), A.clear();
        for (int i = 0; i < n - 1; i++) {
            LL x, y, l, a;
            cin >> x >> y >> l >> a;
            e[x].push_back(y);
            e[y].push_back(x);
            L[x][y] = L[y][x] = l;
            A[x][y] = A[y][x] = a;
        }
        printf("Case #%d: ", i);
        solve();
    }
    return 0;
}

优化解法

算法 —— DFS + 线段树

  • 基于离线查询进行优化,按照特定顺序填充答案,降低时间复杂度
  • 在 DFS 的过程中维护一个表示当前路径的线段树
    • 线段树的 key 为每条边的 load l
      • 这里有一个很重要的点,是说,所有的 l 是不同的(启发我们题目的数据范围一定要要仔细看),这就避免出现一个 key 有多个 value 的情况发生
    • 线段树的 value 为每条边的 amount a,初始值为 0 表示不存在
      • 删除的时候也是直接将 value 置为 0
    • 线段树的 merge 方式为 gcd()
  • 在 DFS 搜索到 x 的时候,如果查询中存在当前节点 x,且负重为 w,只需要在线段数中查询所有 <=w 区间范围内的 l 的所有 a 值的 gcd()

时间复杂度

  • DFS: O(N + Q)
    • 同时维护线段树:
      • 维护的时间复杂度为 log(max{L})
      • 最多只需要计算 log(max{L}) 个数的 gcd: O(log(max{L}) + log(max{A}))
  • 总时间复杂度: O[(N + Q)(log(max{L}) + log(max{A}))]

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10, Q = 1e5 + 10, LMax = 2e5 + 10;
typedef long long LL;

int t, n, q;
vector<int> e[N];
// 节点 x 的所有询问: pair<w, index>
vector<pair<int, int>> query[N];
unordered_map<int, unordered_map<int, int>> L;
unordered_map<int, unordered_map<int, LL>> A;
LL ans[Q];

LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

struct SegmentTree {
    int l, r;
    LL dat;
} tree[LMax * 4];

// 线段树的建树,时间复杂度:O(N)
// p 表示节点编号,[l, r] 表示节点所代表的区间
void build(int p, int l, int r) {
    tree[p].l = l, tree[p].r = r;
    // 叶节点,表示单个元素
    if (l == r) {
        tree[p].dat = 0;
        return;
    }
    int mid = (l + r) >> 1;
    // 左子节点:编号为 2*p,代表区间 [l, mid]
    build(2 * p, l, mid);
    // 右子节点:编号为 2*p+1,代表区间 [mid+1, r]
    build(2 * p + 1, mid + 1, r);
    // 从下往上合并更新信息
    tree[p].dat = gcd(tree[2 * p].dat, tree[2 * p + 1].dat);
}

// 线段树的单点修改,时间复杂度:O(log N)
// 将 a[x] 的值修改为 v
void change(int p, int x, LL v) {
    // 找到叶节点
    if (tree[p].l == tree[p].r) {
        tree[p].dat = v;
        return;
    }
    int mid = (tree[p].l + tree[p].r) >> 1;
    // x 属于左半区间
    if (x <= mid) change(2 * p, x, v);
    // x 属于右半区间
    else
        change(2 * p + 1, x, v);
    // 从下往上合并更新信息
    tree[p].dat = gcd(tree[2 * p].dat, tree[2 * p + 1].dat);
}

// 线段树的区间查询,时间复杂度:O(log N)
// 查询序列 a 在区间 [l, r] 上的 gcd
LL ask(int p, int l, int r) {
    // 查询区间 [l, r] 完全包含节点 p 所代表的的区间
    if (l <= tree[p].l && r >= tree[p].r) return tree[p].dat;
    int mid = (tree[p].l + tree[p].r) >> 1;

    LL val = 0;
    // 左子节点 [tree[p].l, mid] 与查询 [l, r] 有重合
    if (l <= mid) val = gcd(val, ask(2 * p, l, r));
    // 右子节点 [mid+1, tree[p].r] 与查询 [l, r] 有重合
    if (r >= mid + 1) val = gcd(val, ask(2 * p + 1, l, r));
    return val;
}

void dfs(int x, int fa) {
    // assert 之前没有插入过 l,对应题目没有重复 l 的条件「All L_i are distinct.」
    assert(ask(1, L[x][fa], L[x][fa]) == 0);
    change(1, L[x][fa], A[x][fa]);
    // 回答所有对 x 的查询
    for (auto &[w, idx] : query[x]) {
        ans[idx] = ask(1, 0, w);
    }
    for (auto &y : e[x]) {
        if (y != fa) {
            dfs(y, x);
        }
    }
    change(1, L[x][fa], 0);
}

void solve() {
    memset(tree, 0, sizeof tree);
    memset(ans, 0, sizeof ans);
    build(1, 0, LMax);
    for (int i = 1; i <= n; i++) query[i].clear();
    for (int i = 1; i <= q; i++) {
        int c, w;
        cin >> c >> w;
        query[c].push_back(make_pair(w, i));
    }
    dfs(1, -1);
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
}

int main() {
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cin >> n >> q;
        for (int i = 1; i <= n; i++) e[i].clear();
        L.clear(), A.clear();
        for (int i = 0; i < n - 1; i++) {
            int x, y, l;
            LL a;
            cin >> x >> y >> l >> a;
            e[x].push_back(y);
            e[y].push_back(x);
            L[x][y] = L[y][x] = l;
            A[x][y] = A[y][x] = a;
        }
        printf("Case #%d: ", i);
        solve();
    }
    return 0;
}

总结

  1. 思路比较乱的时候,先不要实现,不然徒劳无功。真不行了,可以先实现朴素算法,再做改进。
  2. 没有明确思路的时候,先把所有的题目看完,可能出现后面的题目更简单的情况。(这次都没有留下时间仔细想最后一题)
  3. 数据范围还是需要仔细看。

开源代码

代码已经放在 GitHub: https://github.com/upupming/algorithm/tree/master/kick-start/2021/RoundB ,大家多多 clone,也可以随手 star 一下~




YimingLi
13天前
#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
    string replaceDigits(string s) {
        for (int i = 0; i < s.length(); i++) {
            if (i % 2) {
                s[i] = s[i - 1] + (s[i] - '0');
            }
        }
        return s;
    }
};




YimingLi
13天前
#include <bits/stdc++.h>
using namespace std;
class SeatManager {
    set<int> s;

   public:
    SeatManager(int n) {
        for (int i = 1; i <= n; i++) {
            s.insert(i);
        }
    }

    int reserve() {
        int ans = *s.begin();
        s.erase(s.begin());
        return ans;
    }

    void unreserve(int seatNumber) {
        s.insert(seatNumber);
    }
};

/**
 * Your SeatManager object will be instantiated and called as such:
 * SeatManager* obj = new SeatManager(n);
 * int param_1 = obj->reserve();
 * obj->unreserve(seatNumber);
 */