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) {
    // 统计 0 <= x <= L, 0 <= y <= R 且 x + y <= 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;

    // 先统计全是 1 的区间。
    // 按样例含义：长度为 1 的 [1] 是积极的，因为 1 >= 1。
    // 所以全 1 段中，只有长度 >= 2 的区间是不积极的。
    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++) {
            // 如果乘上 val[j] 后已经大于 n，则之后所有区间一定积极
            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);

            // 不积极条件：
            // prod < base + x + y
            // 即 x + y > prod - base
            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，但这会与给出的样例不符。