C 逆序对大师cwb - 题解

题目大意

给定一个长度为 $n$ 的正整数数组 $a[1..n]$ ，定义一个“逆序对”为一对下标 $(i,j)$ ，满足 $i < j$ 且 $a_i > a_j$ 。对于每一个逆序对 $(i,j)$ ，计算其对应的表达式 $(a_i + a_j)^2$ 。任务是求出所有逆序对对应表达式之和，并将结果对 $10^9 + 7$ 取模后输出。

解题思路

暴力解法（不可行）

最直观的方法是枚举所有可能的下标对 $(i, j)$ （ $1 \leq i < j \leq n$ ），检查是否满足 $a_i > a_j$ 。如果满足，则累加 $(a_i + a_j)^2$ 。此方法的时间复杂度为 $O(n^2)$ ，对于 $n \leq 10^5$ 的数据规模显然不可行。

优化解法：归并排序思想

我们可以利用归并排序（Merge Sort）来高效地找到所有逆序对。归并排序的核心思想是分治：将数组递归地分成两半，分别排序，然后合并两个有序子数组。在合并过程中，我们可以方便地统计跨越左右两部分的逆序对。

关键观察

在归并排序的合并步骤中，我们有两个已经排序好的子数组 $L$ 和 $R$ （ $L$ 在左， $R$ 在右）。假设 $L$ 中当前考虑的元素是 $L[i]$ ， $R$ 中当前考虑的元素是 $R[j]$ 。

如果 $L[i] \leq R[j]$ ，那么 $L[i]$ 不会与 $R[j]$ 及其右边的任何元素形成逆序对。
如果 $L[i] > R[j]$ ，那么 $L[i]$ 会与 $R[j]$ 以及 $R$ 中 $j$ 右边的所有元素形成逆序对。设 $R$ 的长度为 $|R|$ ，当前处理到 $R[j]$ ，则 $L[i]$ 会与 $|R| - j$ 个 $R$ 中的元素构成逆序对。

计算平方和

当我们发现 $L[i]$ 与 $R[j]$ 构成逆序对时，我们需要计算 $(L[i] + R[j])^2 = L[i]^2 + 2 \cdot L[i] \cdot R[j] + R[j]^2$ 。为了高效计算跨越 $L$ 和 $R$ 的所有逆序对的 $(a_i + a_j)^2$ 之和，我们可以利用前缀和。

设 $L$ 的长度为 $len_L$ ， $R$ 的长度为 $len_R$ 。当处理 $L$ 中的 $L[i]$ 且 $L[i] > R[j]$ 时， $L[i]$ 会与 $R$ 中从 $R[j]$ 到末尾的所有元素 $R[k]$ （ $j \leq k < len_R$ ）形成逆序对。

对于这些逆序对，其 $(a_i + a_j)^2$ 之和可以表示为：

\begin{align} \sum_{k=j}^{len_R-1} (L[i] + R[k])^2 &= \sum_{k=j}^{len_R-1} (L[i]^2 + 2 \cdot L[i] \cdot R[k] + R[k]^2) \\ &= \sum_{k=j}^{len_R-1} L[i]^2 + 2 \cdot L[i] \cdot \sum_{k=j}^{len_R-1} R[k] + \sum_{k=j}^{len_R-1} R[k]^2 \\ &= (len_R - j) \cdot L[i]^2 + 2 \cdot L[i] \cdot \sum_{k=j}^{len_R-1} R[k] + \sum_{k=j}^{len_R-1} R[k]^2 \end{align}

为了快速计算 $\sum_{k=j}^{len_R-1} R[k]$ 和 $\sum_{k=j}^{len_R-1} R[k]^2$ ，我们可以在归并前预处理出 $R$ 数组的后缀和（Suffix Sum）和后缀平方和（Suffix Square Sum）。

算法步骤

递归处理：在归并排序的递归函数入口，如果子数组长度大于 1，就递归处理左右两半。
预处理：对左右两半分别排序后，合并前，预处理右半部分的后缀和 suffix_sum 和后缀平方和 suffix_squares。
合并与统计：使用双指针 $i$ (指向左半) 和 $j$ (指向右半) 进行合并。
- 如果 $L[i] \leq R[j]$ ，将 $L[i]$ 放入临时数组， $i$ ++。
- 如果 $L[i] > R[j]$ ，说明 $L[i]$ 与 $R$ 中从 $j$ 开始到末尾的所有元素都能形成逆序对。
  - 计算当前 $L[i]$ 贡献的平方和部分： $(len\_R - j) \cdot L[i]^2$
  - 计算交叉项部分： $2 \cdot L[i] \cdot suffix\_sum[j]$
  - 计算 $R$ 部分的平方和： $suffix\_squares[j]$
  - 将这三部分加到全局答案中（记得对 $10^9 + 7$ 取模）。
  - 将 $L[i]$ 放入临时数组， $i$ ++。
完成合并：合并完成后，将临时数组内容复制回原数组对应位置。

时间复杂度分析

归并排序本身的时间复杂度是 $O(n \log n)$ 。
在每个合并步骤中，预处理后缀和、后缀平方和是 $O(|R|)$ ，计算贡献是 $O(1)$ 每次（利用预处理的后缀和）。总共有 $O(\log n)$ 层递归，每层处理 $n$ 个元素。
总体时间复杂度为 $O(n \log n)$ 。

空间复杂度分析

归并排序需要 $O(n)$ 的临时数组空间。
预处理后缀和、后缀平方和需要 $O(|R|)$ 的额外空间，但它们可以在合并完成后释放，所以最大空间占用仍然是 $O(n)$ 。

代码

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define endl "\n"
#define int long long
#define x first
#define y second
using namespace std;
const int mod = 1e9 + 7;
void solve()
{
    int n;
    cin >> n;
    vector<int>a(n + 1, 0);
    for (int i = 1; i <= n; i++)cin >> a[i];
    int ans = 0;
    function<vector<int>(int, int)>merge_sort = [&](int l, int r)->vector<int>
    {
        if (l > r)return {};
        if (l == r)return {a[l]};
        int mid = l + r >> 1;
        auto la = merge_sort(l, mid);
        auto ra = merge_sort(mid + 1, r);
        int i = 0, j = 0;
        vector<int>t, sa(la.size() + 1, 0), sb(la.size() + 1, 0);
        for (int o = 1; o <= la.size(); o++)
        {
            sa[o] = (sa[o - 1] + la[o - 1]) % mod;
            sb[o] = (sb[o - 1] + 1LL * la[o - 1] * la[o - 1] % mod) % mod;
        }
        while (i < la.size() && j < ra.size())
        {
            if (la[i] <= ra[j])t.push_back(la[i++]);
            else
            {
                ans = (ans + 1LL * (la.size() - i) % mod * ra[j] % mod * ra[j] % mod) % mod;
                ans = (ans + 2LL * ra[j] % mod * ((sa.back() - sa[i] + mod) % mod)) % mod;
                ans = (ans + 1LL * (sb.back() - sb[i] + mod) % mod) % mod;
                t.push_back(ra[j++]);
            }
        }
        while (i < la.size())t.push_back(la[i++]);
        while (j < ra.size())t.push_back(ra[j++]);
        return t;
    };
    merge_sort(1, n);
    cout << ans << endl;
}

signed main()
{
    IOS
    int T = 1;
    //cin >> T;
    while (T--) solve();
    return 0;
}

其它解法-树状数组

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define endl "\n"
#define int long long
#define x first
#define y second
using namespace std;
const int mod = 1e9 + 7;

typedef struct FenwickTree
{
    vector<int>tr;
    int n;
    FenwickTree() {}
    FenwickTree(int n): n(n) {tr.resize(n + 1, 0);}
    FenwickTree(vector<int>tr, int n)
    {
        this->n = n;
        this->tr = tr;
    }
    int lowbit(int x)
    {
        return x & (-x);
    }
    void add(int x, int c)
    {
        for (int i = x; i <= n; i += lowbit(i))tr[i] = (tr[i] + c) % mod;
    }
    int sum(int x)
    {
        int ans = 0;
        for (int i = x; i; i -= lowbit(i))ans = (ans + tr[i]) % mod;
        return ans;
    }
} FT;

typedef struct Discretization
{
    int n;
    vector<int> alls;
    Discretization() {}
    Discretization(vector<int>all)
    {
        for (auto x : all)alls.push_back(x);
        sort(alls.begin(), alls.end());
        alls.erase(unique(alls.begin(), alls.end()), alls.end());
        n = alls.size();
    }
    void init()
    {
        sort(alls.begin(), alls.end());
        alls.erase(unique(alls.begin(), alls.end()), alls.end());
        n = alls.size();
    }
    int find(int x)
    {
        return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
    }
} DS;

void solve()
{
    int n;
    cin >> n;
    vector<int>a(n + 1, 0);
    DS ds;
    for (int i = 1; i <= n; i++)cin >> a[i], ds.alls.push_back(a[i]);
    ds.init();
    FT ft1(ds.n), ft2(ds.n), ft3(ds.n);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int w = ds.find(a[i]);
        ft1.add(w, 1);
        ft2.add(w, a[i]);
        ft3.add(w, a[i] * a[i] % mod);
        ans = (ans + (i - ft1.sum(w)) % mod * a[i] % mod * a[i] % mod) % mod;
        ans = (ans + 2 * a[i] % mod * (ft2.sum(ds.n) - ft2.sum(w) + mod) % mod) % mod;
        ans = (ans + (ft3.sum(ds.n) - ft3.sum(w) + mod) % mod) % mod;
    }
    cout << ans << endl;
}

signed main()
{
    IOS
    int T = 1;
    //cin >> T;
    while (T--) solve();
    return 0;
}

H-tjh学长爱玩剧本杀

题目大意

给定 $N$ 张卡牌，每张卡牌可以选择：

不调查：耗时 0 ，得分 0；
普通表面调查：耗时 t1，得分v；
深入调查：耗时t1 + t2，得分2v；

问：在时间T内使用最优解所获得的价值能否超过给定价值V

解题思路

通过以上观察可发现该情况是动态规划中典型的01背包问题。
每一张卡牌可以看做两个物品：
- 第一个物品：占用空间t1，价值v
- 第二个物品：占用空间t1+t2，价值2v
现在问题就可以转换为在背包总容量为T的情况下，如何装这些物品是总价值达到最大。
如果对背包问题还不太熟悉或者没有了解过的请移步->[https://www.cnblogs.com/dx123/p/17301748.html]

时间复杂度分析

该题为01背包模板题，时间复杂度即01背包问题时间复杂度：O(N*T)

代码(普通版)

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // For INT_MIN

using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int N, T, V;
    cin >> N >> T >> V;

    vector<int> t1(N + 1), t2(N + 1), v(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> t1[i] >> t2[i] >> v[i];
    }

    // dp[i][j]: 考虑前i张卡牌，在时间j内能获得的最大价值
    // 初始化为一个极小值，因为可能有些状态无法达到
    vector<vector<long long>> dp(N + 1, vector<long long>(T + 1, LLONG_MIN));

    // 初始状态：不考虑任何卡牌，时间0，价值0
    for (int j = 0; j <= T; j++) {
        dp[0][j] = 0;
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= T; j++) {
            // 选择1: 不调查第i张卡牌
            dp[i][j] = dp[i - 1][j];

            // 选择2: 表面调查第i张卡牌
            if (j >= t1[i] && dp[i - 1][j - t1[i]] != LLONG_MIN) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - t1[i]] + v[i]);
            }

            // 选择3: 深入调查第i张卡牌
            if (j >= t1[i] + t2[i] && dp[i - 1][j - t1[i] - t2[i]] != LLONG_MIN) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - t1[i] - t2[i]] + 2LL * v[i]);
            }
        }
    }

    bool possible = false;
    for (int j = 0; j <= T; j++) {
        if (dp[N][j] >= V) {
            possible = true;
            break;
        }
    }

    if (possible) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

代码(优化空间版)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int main() {
    int N, T, V;
    cin >> N >> T >> V;
    
    vector<int> t1(N), t2(N), v(N);
    for (int i = 0; i < N; i++) {
        cin >> t1[i] >> t2[i] >> v[i];
    }
    
    // 创建DP数组，dp[j]表示使用j小时能获得的最大价值
    vector<int> dp(T + 1, 0);
    
    // 动态规划过程
    for (int i = 0; i < N; i++) {
        // 逆序遍历时间，确保每个线索只被考虑一次
        for (int j = T; j >= 0; j--) {
            // 选择表面调查当前线索
            if (j >= t1[i]) {
                dp[j] = max(dp[j], dp[j - t1[i]] + v[i]);
            }
            
            // 选择深入调查当前线索（需要先完成表面调查）
            if (j >= t1[i] + t2[i]) {
                dp[j] = max(dp[j], dp[j - t1[i] - t2[i]] + 2 * v[i]);
            }
        }
    }
    
    // 检查是否能在时间限制内达到目标价值
    int max_value = 0;
    for (int j = 0; j <= T; j++) {
        max_value = max(max_value, dp[j]);
    }
    
    // 输出结果
    if (max_value >= V) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    
    return 0;
}

L-找平年

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

const int mod = 1e9 + 7;
int solve(string s) {
    vector<vector<int> > dp(5, vector<int>(400, 0)) ;
     dp[0][0] = 1;
     for (auto c : s) {
         int num = c - '0';
        for (int i = 4; i >= 1; i--) {
            for (int j = 0; j < 400; j++) {
               dp[i][(j * 10 + num) % 400] = (dp[i - 1][j] + dp[i][(j * 10 + num) % 400]) %mod;
             }
       }
    }
    int res = 0;
    for (int i = 1; i < 400; i++) {
         if(i%4 || i%100==0)res = (res + dp[4][i]) % mod;
    }
    return res % mod;
}
signed main() {
    // 禁用同步以加速I/O
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);


    string s;
    getline(cin, s);
    //cout<<s<<endl;
    int result = solve(s);

    cout << result << endl;

    return 0;
}

总体思路

我们设s是给出的字符串，我们需要从中找到子序列t满足是平年，设置dp数组储存结果 dp[位数][mod 400的结果]
当s[i]中出现了符合条件的t[j]符合条件的,

C H L

C 逆序对大师cwb - 题解

题目大意

解题思路

暴力解法（不可行）

优化解法：归并排序思想

关键观察

计算平方和

算法步骤

时间复杂度分析

空间复杂度分析

代码

其它解法-树状数组

H-tjh学长爱玩剧本杀

题目大意

解题思路

时间复杂度分析

代码(普通版)

代码(优化空间版)

L-找平年

总体思路