前缀、差分进阶

题目链接

Weird Sum

题意

计算相同数字单元格之间的距离总和

距离=abs(x1-x2)+abs(y1-y2)

思路

暴力遍历会超时不予考虑

尝试找到答案与整体坐标的关系，最后可以推出一个公式。

两个相同颜色单元格的距离即横坐标之差加纵坐标之差，那么在颜色相同的单元格中：

任意两个单元格的距离之和 = 任意两个单元格的横坐标差之和 + 这两个单元格的纵坐标差之和。

我们可以分开计算横、纵坐标差之和。

横坐标差之和：

将横坐标升序排列，遍历所有坐标，第 i 个坐标与前面所有坐标差之和为

xi * (i-1) - (x1+x2+x3+… …+xi-1)；

例如 i == 1时，第1个坐标与前面所有坐标差之和为：x1 * 0 - 0

i == 2时为：x2 * 1 - (x1)

i == 3时为：x3 * 2 - (x1 + x2)

i == 4时为：x4 * 3 - (x1 + x2 + x3)

上述各式之和即为任意两个相同颜色单元格横坐标之和。

纵坐标同理。

代码

#include 
using namespace std;
typedef long long ll;
const int N = 100002;
vector q1[N];
vector q2[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            ll a;
            cin >> a;
            q1[a].push_back(i);
            q2[a].push_back(j);
        }
    ll k = 0;
    for (int i = 1; i <= 100000; i++)
    {
        int t = q1[i].size();
        if (t == 0)
            continue;
        sort(q1[i].begin(), q1[i].end());
        sort(q2[i].begin(), q2[i].end());
        for (int j = 0; j < t; j++)
        {
            k += q1[i][j] * (t - j - 1);
            k -= q1[i][j] * j;
            k += q2[i][j] * (t - j - 1);
            k -= q2[i][j] * j;
        }
    }
    cout << abs(k)<< endl;
    return 0;
}

题目链接

Increase Subarray Sums

题意

给一个数组 a[n] 与整数 x ,定义 k （0<=k&&k<=n) ，每次可以操作 k 个数使其加上 x ，f(k) 为当前序列 $a 中最大的连续子段和，求出每一个f(k)$

思路

定义数组 d[i] 为区间为 i 时最大的连续子段和，然后遍历 k ，更新 d[i] 的值，d[ i ] = min( i , k ) * x + d[ i ] ,

最后遍历数组d 得到最大值

代码

#include 
using namespace std;
typedef long long ll;
const int N = 100002;

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, x;
        cin >> n >> x;
        int s[n + 10] = {0};
        for (int i = 1; i <= n; i++)
        {
            cin >> s[i];
            s[i] += s[i - 1];
        }
        int f[n + 10] ;
        memset(f,-126,sizeof(f));
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j + i <= n + 1; j++)
            {
                f[i] = max(f[i], s[i + j - 1] - s[j - 1]);
            }
        }

        for (int len = 0; len <= n; len++)
        {
            int mas = 0;
            for (int i = 1; i <= n; i++)
                mas = max(mas, f[i] + min(len, i) * x);
            cout << mas<<" ";
        }
        cout<<endl;
    }
    return 0;
}

题目链接

Circular Addition

思路

我们需要把数组从0变成他给出的数组，不妨考虑把他给的数组变成全是0，因为全是0，原数组的数相等，所以差分数组最后全是0，我们要把他的差分变0，

他是一个环（因为 j 超过 n 就变成 1 ），所以差分数组的正数和等于负数和，因为我们本来需要对原数组进行+1的操作，但是我们可以转化思维对他给出的数

组进行-1的操作使他变成0，当我们对他l-r的区间进行减1的操作时差分数组就会进行一个 b[ l ]-1,b [r+1]+1 的操作，因为 l ，r 是我们任意选的，所以我们只

用操作差分的正数之和个操作就可以让原数组一样（选一个正数-1，选一个负数+1），但是当最小的值太大的时候我们把差分数组变成0之后只是让他们变成了

一样的数，还需要把操作之后的n个相同的数x操作x下减到0，根据贪心的思想我们每次操作势必会对max(a[i])操作，假设操作了o次，操作之后的数再变成0所

需要的操作数h加上o肯定还是max(a[i])，我们把max(a[i])和把差分数组变成0所进行的con次操作数做比较，取最大值：如果max(a[i])>con说明他经过con次操

作只是把原数组变成了一样的数而没有变成零，所以总共需要进行max(a[i])次操作，如果con>max(a[i])说明经过con次操作不仅原数组的数一样而且等于0。

代码

#include 
using namespace std;
typedef long long ll;
const int N = 2000000;
ll s[N];
int main()
{
    int n;
    cin >> n;
    ll ans = 0;
    cin >> s[1];
    ll mas = s[1];
    for (int i = 2; i <= n; i++)
    {
        cin >> s[i];
        if (s[i] - s[i - 1] > 0)
            ans += s[i] - s[i - 1];
        mas = max(mas, s[i]);
    }
    if (s[1] - s[n] > 0)
        ans += s[1] - s[n];
    cout << max(ans, mas);
    return 0;
}

AC谷 AC谷第二周前缀&amp差分

前缀、差分进阶

Weird Sum

Increase Subarray Sums

Circular Addition

相关

标签