P8475

__vector__ · 2022-08-16 16:04:50 · 个人记录

做法

做法很显然，就是贪心的使低位尽量小。

对于每一位，都尽量选择在它后面的，且最小的元素与之交换。

如果后面有多个最小的，那怎么做呢？

因为要使字典序尽可能小，而交换的时候必然有一位变大，所以使变大的这一位尽量靠后。

所以，做法就是，对于每一位，将其与在它后面的，最小且最远的元素交换。

另外要注意，由题目性质可以得出，两个元素交换之后，它们之间的元素（包括自己）就不能进行交换操作了，要进行判断。

Code

#include <bits/stdc++.h> // scanf
using namespace std;
const int MAXN = 1e7+5; // Set a right value according to your solution.
int n, a[MAXN];

namespace Generator {

    unsigned long long k1, k2;
    int thres;

    inline unsigned long long xorShift128Plus() {
        unsigned long long k3 = k1, k4 = k2;
        k1 = k4, k3 ^= (k3 << 23), k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
        return k2 + k4;
    }

    inline void generate() {
        for (int i = 1; i <= n; ++i) {
            a[i] = xorShift128Plus() % thres;
        }
    }

} // namespace Generator.
int imin[MAXN];
int pos[MAXN];
int main() {
    scanf("%d", &n);
    scanf("%llu %llu %d", &Generator::k1, &Generator::k2, &Generator::thres);
    Generator::generate();
    // Now array a[1..n] represents the sequence A in the statement.
    imin[n]=a[n];
    pos[n]=n;
    for(register int i=n-1;i>=1;i--)
    {
        if(a[i]<imin[i+1])
        {
            imin[i]=a[i];
            pos[i]=i;
        }
        else
        {
            imin[i]=imin[i+1];
            pos[i]=pos[i+1];
        }
    }
    register int _pos;
    for(register int i=1;i<=n;i++)
    {
        if(imin[i]==a[i])continue;
        _pos=pos[i];
        swap(a[i],a[pos[i]]);
        i=_pos;
    }
    unsigned long long ans=0;
    for(register int i=1;i<=n;i++)
    {
        ans=(ans+(unsigned long long)i*(unsigned long long)a[i]);
    }
    printf("%llu",ans);
    return 0;
}