【2023NOIP模拟赛09】补幺梨 做题记录

有 $n$ 个在 $[1,m]$ 中均匀随机的整数随机变量 $a_{1\sim n}$，求一个最大的 $ans$ 满足找不出：

• 一组非负整数 $y_{1\sim n}$ 满足 $ans=\sum x_iy_i$。

满足有解。

$50\le n\le 10^7$，$2\le m\le 10^8$。

设 $mn=\min\{a_i\}$，考虑以 $mn$ 为模跑同余最短路，则 $dis_i+k\times mn$ 都能被表示出来，所以答案为 $\max\{dis_i-mn\}$。

由于数据随机，所以 $mn$ 的期望为 $\frac{m}{n+1}$，同余最短路时间复杂度为 $O(\frac{m}{n+1}n\log \frac{m}{n+1})$ 但是跑不满，所以能过。

代码如下：

#include <iostream>
#include <cstdio>
#include <random>
#include <queue>

using namespace std;

const int S=10000005,MS=2000005;

int n,m,seed,a[S];
int dis[MS];
bool vis[MS];
priority_queue<pair<int,int>> q;

int main()
{
	scanf("%d%d%d",&n,&m,&seed);
	mt19937 rng(seed);
	auto get=[&]()
	{
		uniform_int_distribution<int> qwq(2,m);
		return qwq(rng);
	};
	int mn=m;
	for(int i=1;i<=n;i++) mn=min(mn,a[i]=get());
	for(int i=0;i<mn;i++) dis[i]=1e9;
	dis[0]=0;
	q.push(make_pair(0,0));
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=1;i<=n;i++)
		{
			int v=(u+a[i])%mn;
			if(dis[u]+a[i]<dis[v])
			{
				dis[v]=dis[u]+a[i];
				q.push(make_pair(-dis[v],v));
			}
		}
	}
	int ans=0;
	for(int i=0;i<mn;i++) ans=max(ans,dis[i]-mn);
	printf("%d\n",ans);
	return 0;
}