2024_2_1训练赛简单题解

## A
题意:给定 $n$ 个区间，问交集是否为空

```cpp
void solve() {
    int n = read(),l = 0 ,r = 1e9;
    for(int i =1; i <= n;i ++){
        int L=read(),R=read();
        l = max(L,l);
        r = min(R,r);
    }
    if(r >= l)cout <<"YES\n";
    else cout <<"NO\n";
}
```
## B
题意:求两点与直线上一点相连的最小距离。
根据初中数学可得，可以找一个点关于河对称的点，求两点距离。
注意：cin 读入double很慢，cin不解绑和printf读入很慢。

代码：略

## C
题意:给定两个长度为 $n$ 的数组 $a$,$b$，可以选择最多一个数字 $i$ 使得 $a_i = b_i$。问去掉最大最小元素后，数组的最大的和。

本质上就是维护一个数组，并同时维护最大最小值，要求可以删除，可以添加，可以使用线段树，map，set，前缀和，贪心等一系列方法。

代码：略

## D
题意:给定一个长度为 $n$ 的数组，对于 $1-n$中每一个数字，求出有多少种方法能从数组中选出一个子序列，其子序列的 $gcd = i$。

DP
考虑设DP状态为DP[gcd为i的倍数] = 方案数
$dp[i] = 2^{i的倍数的个数} - 1$
可以发现$DP$数组多算了，多算了包含他倍数的部分，所以倒着减去多算的部分即可。

```cpp
    for (int i = 1; i <= n; i++) {
        int x = read();
        cnt[x]++;
    }
    vector<mint> dp(m + 1), p(n + 1, 1);//mint 帮忙自动取模的
    for (int i = 1; i <= n; i++)
        p[i] = p[i - 1] * 2;
    for (int i = 1; i <= m; i++) {
        mint ans = 1;
        for (int j = i; j <= m; j += i)
            ans *= p[cnt[j]];
        dp[i] = ans - 1;
    }
    for (int i = m; i; i--) {
        for (int j = i * 2; j <= m; j += i)
            dp[i] -= dp[j];
    }
    for (int i = 1; i <= m; i++)
        cout << dp[i] << " \n"[i == m];
```

## E
题意:给定一颗树，多次查询，以根到点 $u$ 、 $v$的两条链中，选出长度相同的子序列，得到权值$\sum{a_i\times b_i}$。

由于树是随机生成，所以树高为 $log$ 级别，暴力向上爬，把所有数字都拿出来，暴力跑类似编辑距离的方法。
时间复杂度$O(Qlog^2n)$

```cpp
void solve() {
    int n = read();
    vector<long long> s(n + 1);
    for (int i = 1; i <= n; i++)
        s[i] = read();
    vector<int> f(n + 1);
    for (int i = 2; i <= n; i++)
        f[i] = read();
    int q = read();
    function<vector<int>(int)> go = [&](int u) -> vector<int> {
        vector<int> ans;
        int x = u;
        while (x != 1) {
            ans.push_back(x);
            x = f[x];
        }
        ans.push_back(1);
        return ans;
    };
    while (q--) {
        vector<int> a = go(read()), b = go(read());
        vector<vector<ll>> dp(a.size() + 1, vector<ll>(b.size() + 1));
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < b.size(); j++) {
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + s[a[i]] * s[b[j]]);
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
                dp[i][j + 1] = max(dp[i][j + 1], dp[i][j]);
            }
        }
        ll ans = 0;
        for (auto& x : dp)
            for (auto& y : x)
                ans = max(ans, y);
        cout << ans << "\n";
    }
}
 
 ```
 
 ## F
 题意，给定一个区间，问区间内的点不同的点两两相消，最少剩余多少个数字。
 
 首先对于能否消完，考虑如果一个数字过多，那么最后肯定会剩余这个数字，如果不多，其他的数字一定能给他消完。
 
考虑极限情况可以发现，如果最多的数字超过区间的一半，那么其他数字哪怕全和他消，那么也无法消完，所以判断能否消完的条件为是否有一个数字超过区间的一半。

由于整个区间有一半都是该数字，所以可以使用随机的方法，很容易取到该数，重复20次至少有$99.9999%$的概率能取到，同时可以一开始将数字用桶存下来，这样在枚举数字的时候可以通过二分的方式快速数出区间内有多少个数字是该数，计算即可。

当然也可以采用稳定算法：莫队，线段树维护摩尔投票等来通过该题。

代码：略

正在渲染内容...