A

std

#include <bits/stdc++.h>
using namespace std;

int main() {

    long long n, m;
    cin >> n >> m;

    cout << (n + m + 1) / 2 << '\n';

    return 0;
}

B

思路

设相邻水果距离：

$d_i=p_{i+1}-p_i$

约束变成：

$r_i+r_{i+1}\le d_i$

我们要最大化：

$\sum r_i$

这个问题可以转化成：在相邻间隔 $(d_i)$ 中选一些边，使得每个水果都被至少一条选中的边覆盖，求选中边权之和的最小值。

对于数轴上的一条链：

• 第一个间隔 $(d_1)$ 必须选，否则第 $(1)$ 个水果无法被覆盖；
• 最后一个间隔 $(d_{n-1})$ 必须选，否则第 $(n)$ 个水果无法被覆盖；
• 不能有两个连续的间隔都不选，否则中间那个水果无法被覆盖。

所以答案等价于：

$\text{所有间隔之和} - \text{能删掉的最大间隔和}$

能删掉的间隔只能是内部间隔：

$d_2,d_3,\dots,d_{n-2}$

并且不能删掉相邻的两个间隔。

这就是经典的“不选相邻元素的最大和”DP。

---

DP

设 dp1 表示处理到当前内部间隔时，能删掉的最大和。

转移：

$dp_i=\max(dp_{i-1}, dp_{i-2}+d_i)$

最后：

$ans=\sum_{i=1}^{n-1}d_i-dp$

---

代码 C++17

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    long long prev, cur;
    cin >> prev;

    long long total = 0;

    // house robber DP on internal gaps d[2] ... d[n-2]
    long long dp_im2 = 0, dp_im1 = 0;

    for (int i = 1; i <= n - 1; i++) {
        cin >> cur;
        long long d = cur - prev;
        total += d;

        if (i >= 2 && i <= n - 2) {
            long long ndp = max(dp_im1, dp_im2 + d);
            dp_im2 = dp_im1;
            dp_im1 = ndp;
        }

        prev = cur;
    }

    cout << total - dp_im1 << '\n';

    return 0;
}

---

复杂度

$O(n)$

只用常数个变量：

$O(1)$

可以通过 $n\le 10^6$。

C

std

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
typedef vector<vector<int>> mat;
using pii = pair<int, int>;
using pdd = pair<double,double>;
using u64 = unsigned long long;
constexpr int Nn = 2e5 + 10;
constexpr int mod = 998244353;

void solve()
{
    int n,m;
    cin >> n >> m;
    vector<int> d(n+1);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin >> x >> y;
        d[x]++,d[y]++;
    }
    set<int> st;
    map<int,int> mp;
    for(int i=1;i<=n;i++)
        st.insert(d[i]),mp[d[i]]++;
    vector<int> ans;
    for(auto it : st)
        ans.push_back(it);
    int cnt=0;
    for(int i=0;i<ans.size()-1;i++)
        for(int j=i+1;j<ans.size();j++)
            cnt=(cnt+(((ans[i]^ans[j])*(ans[i]|ans[j])*(ans[i]&ans[j]))*(mp[ans[i]]*mp[ans[j]]))%mod)%mod;
    cout << cnt%mod << '\n';
}
signed main()
{
    IOS;
    int _= 1;
    //cin >> _;
    while(_--)
    {
        solve();
    }
    return 0;
}

D

样例与题面“乘积大于长度”不一致：样例按 乘积 ≥ 区间长度 才能全部对上。下面代码按样例含义实现，即积极条件为：

$\prod a_i \ge r-l+1$

思路

直接统计积极区间不方便，改为统计“不积极区间”：

$\prod a_i < \text{len}$

最后用总区间数减去不积极区间数。

关键观察：

如果一个区间内非 1 的数的乘积已经大于 $n$，那么它一定积极，因为区间长度最大也只有 $n$。

而非 1 的数最小是 2，所以需要枚举的非 1 个数最多约为：

$\log_2 n \le 19$

因此可以只压缩所有 $a_i > 1$ 的位置和值。

对于一段连续的非 1 元素 $i \sim j$，它们之间的最短区间长度为：

$base = pos_j - pos_i + 1$

左边可以扩展 $L$ 个 1，右边可以扩展 $R$ 个 1。

设左扩展 $x$，右扩展 $y$，则区间长度为：

$base + x + y$

不积极条件为：

$P < base + x + y$

也就是：

$x+y > P-base$

用一个 $O(1)$ 函数统计满足条件的 $(x,y)$ 数量即可。

C++17 代码

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll count_leq_sum(ll L, ll R, ll K) {
    if (K < 0) return 0;

    ll total = (L + 1) * (R + 1);
    if (K >= L + R) return total;

    if (L > R) swap(L, R);

    if (K <= L) {
        return (K + 1) * (K + 2) / 2;
    } else if (K <= R) {
        return (L + 1) * (K + 1) - L * (L + 1) / 2;
    } else {
        ll d = L + R - K;
        return total - d * (d + 1) / 2;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n + 1);
    vector<int> pos, val;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] > 1) {
            pos.push_back(i);
            val.push_back(a[i]);
        }
    }

    int m = pos.size();

    ll total = 1LL * n * (n + 1) / 2;
    ll bad = 0;

    int prev = 0;
    for (int i = 0; i <= m; i++) {
        int cur = (i == m ? n + 1 : pos[i]);
        ll g = cur - prev - 1;
        bad += g * (g - 1) / 2;
        prev = cur;
    }

    for (int i = 0; i < m; i++) {
        ll prod = 1;

        ll L = pos[i] - (i == 0 ? 0 : pos[i - 1]) - 1;

        for (int j = i; j < m; j++) {
            if (prod > n / val[j]) break;

            prod *= val[j];

            ll R = (j + 1 == m ? n + 1 : pos[j + 1]) - pos[j] - 1;
            ll base = pos[j] - pos[i] + 1;

            ll ways = (L + 1) * (R + 1);

            ll T = prod - base;

            if (T < 0) {
                bad += ways;
            } else if (T < L + R) {
                bad += ways - count_leq_sum(L, R, T);
            }
        }
    }

    cout << total - bad << '\n';

    return 0;
}

时间复杂度：

$O(n \log n)$

实际上内层最多约 19 次，因此可以认为接近 $O(n)$。

空间复杂度：

$O(n)$

如果评测严格按题面“乘积 > 长度”，需要把“不积极”改成 prod <= len，但这会与给出的样例不符