摘要
Title: Nowcoder G. 分割
Tag: 数学、规律
Memory Limit: 64 MB
Time Limit: 1000 ms

Nowcoder G. 分割

题意

在一个二维平面，
有n条平行于y轴的直线, 他们的x坐标是x[i]，
m条平行于x轴的直线y[i]，他们的y坐标是y[i].
求出这些直线所有可能形成矩形的总面积对1000000007取模的值。
保证所有直线不完全重叠。
思路

题目是要任取两条横线,两条竖线,将所有可能的方案组成的矩形面积相加.

容易发现横线的选择和竖线的选择是相互独立的,
因此我们只需要计算出选择两条横线能组成的所有矩形边长的和,
同时计算出选择两条竖线能组成的所有矩形变成的和,
两者相乘就是答案.

现在问题变为如何计算所有能组成的边长的和.

对于x[i]
对答案的贡献为x[i]-x[0],x[i]-x[1],...x[i]-x[i-1],这些数的和.
合并一下就是x[i]*i-sum(x[0]+x[1]...x[i-1]),
维护一个前缀sum就可以O(n)计算了.

代码

ps: 一定要注意，当vector下标从1开始时，就不能直接从a.begin()开始了，得+1

#include <bits/stdc++.h>
#define int long long
#define ALL(X) (X).begin(), (X).end()
using namespace std;

const int MOD = 1000000007;
signed main()
{
    int n, m;
    cin >> n >> m;
    vector<int> x(n);
    for (int i = 0; i < n; ++i)
        cin >> x[i];

    vector<int> y(m);
    for (int i = 0; i < m; ++i)
        cin >> y[i];

    sort(ALL(x));
    sort(ALL(y));

    int ansx = 0, ansy = 0, sum = 0;
    for (int i = 0; i < n; ++i)
    {
        ansx = (ansx + i * x[i] - sum) % MOD;
        sum = (sum + x[i]) % MOD;
    }
    sum = 0;
    for (int i = 0; i < m; ++i)
    {
        ansy = (ansy + i * y[i] - sum) % MOD;
        sum = (sum + y[i]) % MOD;
    }
    cout << ansx * ansy % MOD;

    return 0;
}

Nowcoder G. 分割

题意

思路

代码