题解：「GLR-R3」雨水

题目链接

前言

先吐槽一下，这个英文是真的坑。

const int MAXN = 712; // Set a right value according to your solution.

为啥不能直接把数组下标设为最大值呢，还要挖个坑考考英文。

然后这个随机数据卡不掉 $O(n^2)$ 做法啊，感觉大为震撼。

正文

更简化的题意

给定一个序列 $A$，从中选取下标单调递增的一些数，相邻的两两交换，但仅局限于下标为奇数的和它右边的数这样交换，再放回原序列，使得新得到的序列字典序尽可能小。

解题

一道很不错的贪心，对于字典序最小，假设我们只能换一次，那肯定将整个序列里面最小的那个数换到最前面。推广到多次操作，再交换的数肯定只能从最小的那个数右边去找，否则不符合操作规则。

对于如果有多个最小的数，我们应该交换哪一个呢？因为字典序尽可能小，同样可以推出大的应该尽可能往后放，因此在寻找最小的数时，要找下标更大的。

由此我们可以倒序跑一遍记录下对于每一个数它的右侧的最小值，再正着跑一遍进行交换操作，这样的总时间复杂度就是 $O(n)$。

答案自然溢出即可。

Code

#include<bits/stdc++.h>
#define ull unsigned long long
#define MAX 10000002
#define INF 999999999
using namespace std;

int n,a[MAX];

namespace Generator
{
	ull k1,k2;
	int thres;
	inline ull xorShift128Plus()
	{
		ull 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;
	}
}

unsigned int key[MAX],pos[MAX];
ull ans;
inline void work()
{
	key[n+1]=INF;
	for(int i=n;i>=2;i--)
	{
		key[i]=key[i+1],pos[i]=pos[i+1];
		if(a[i]<key[i]) key[i]=a[i],pos[i]=i;
	}
	int mink,minp;
	for(int i=1;i<n;i++)
	{
		mink=key[i+1],minp=pos[i+1];
		if(mink<a[i]) swap(a[i],a[minp]),i=minp;
	}
	return;
}

int main()
{
	scanf("%d",&n);
	scanf("%llu %llu %d",&Generator::k1,&Generator::k2,&Generator::thres);
	Generator::generate();
	work();
	for(int i=1;i<=n;i++)
		ans+=(unsigned long long)a[i]*i;
	cout<<ans;
	return (0-0);
}