15011418730 LV 7 @ 2025-8-24 22:08:25

自动搬运

来自洛谷，原作者为

	TJmyf NOI2025金牌得主

搬运于2025-08-24 22:08:25，当前版本为作者最后更新于2024-01-03 13:56:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

小葱和组合数问题若干是某位大神の常态。

这类提交答案的问题就是一个 NPC 问题的改编，把原问题的某个变量设为一个定值或使得数据具有某些特点能满足一些数学性质然后转化为可做的问题，如果做不了就退火骗分。

谨记：提答看数据。

数据点 1

$n=8,k=3$ 可以暴力枚举所有情况，然后查询一下即可，时间复杂度为 $O(k^n·sim)$ ，其中 $sim$ 代表 simulator 单次运行的平均时间，code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=100;
int n,m,k,opt,x,ans,a[maxn];
int main()
{
	freopen("placement1.in","r",stdin);
	cin>>n>>m>>k>>opt;
	for(int i=1;i<=m*2+n*k+k*k;i++) cin>>x;
	for(int i=1;i<=n;i++) a[i]=1;
	while(1)
	{
		FILE *f=fopen("placement1.out","w");
		for(int i=1;i<=n;i++) fprintf(f,"%d ",a[i]);
		a[1]++;
		for(int i=1;i<n;i++) if(a[i]>k) a[i]=1,a[i+1]++;
		fclose(f);
		system("simulator.exe placement1.in placement1.out");
		FILE *g = fopen("res.txt","r");
		fscanf(g,"%d",&ans);
		fclose(g);
		if(ans<=317) return 0;
	}
	return 0;
}

然而，答案是“ 2 3 3 3 3 3 3 3 ”，一共 6561 种情况，上面那段代码需要跑 6560 次 ~~QWQ (我还以为我写挂了)~~ ，时间复杂度 $O(k^n·sim)$ ，空间复杂度 $O(nk)$ (算上 simulator )。

数据点 2

$n=9,k=7$ 我们仍然可以暴力枚举所有情况，但受限于 simulator ，实际会很慢，所以考虑假贪心优化：每个问题选尽量优的 TPU ，即对每个问题，更优的 TPU 选择的概率更大一些，code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=100;
int n,m,k,opt,x,y,ans,a[maxn],t[maxn][maxn];
int main()
{
	freopen("placement2.in","r",stdin);
	cin>>n>>m>>k>>opt;
	for(int i=1;i<=m;i++) cin>>x>>y;
	for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) cin>>t[i][j];
	for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) cin>>x;
	while(1)
	{
		FILE *f=fopen("placement2.out","w");
		for(int i=1;i<=n;i++)
		{
			priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
			for(int j=1;j<=k;j++) q.push(make_pair(t[i][j],j));
			for(int j=1;j<=k;j++)
			{
				if(rint(1,100)<=80||j==k)
				{
					fprintf(f,"%d ",q.top().second);
					break;
				}
				q.pop();
			}
		}
		fclose(f);
		system("simulator.exe placement2.in placement2.out");
		FILE *g = fopen("res.txt","r");
		fscanf(g,"%d",&ans);
		fclose(g);
		if(ans<=120) return 0;
	}
	return 0;
}

答案是“ 5 2 5 7 1 7 2 3 6 ”，没有太多重复的，跑几次就出来了，时间复杂度 $O($ 能过 $)$ ，空间复杂度 $O(nk)$ ( 算上 simulator )。

数据点 3

$n=50,m=0,k=3,op=2$ 暴力枚举已经不能完成了。因为有 $m=0,opt=2$ 考虑 DP ：可以将问题转化为一个 $50×3$ 的矩阵，每行每列都恰好要选 $1$ 个数，使每列的和的最大值最小。设计状态为 $f_{i,x,y,z}$ ，如果某个 $f_{i,x,y,z}$ 值为 $1$ 那么代表前 $i$ 行选完了，第 $1$ 列的和问为 $x$ ，第 $2$ 列的和问为 $y$ ，第 $3$ 列的和问为 $z$ 是可以出现的。虽然这样很好转移，但是时间和空间复杂度都是 $O(n^4t^3)$ ， ~~也就耗 157TB~~ 。把 DP 优化为 $f_{i,x,y}$ ，代表前 $i$ 行选完了，第 $1$ 列的和问为 $x$ ，第 $2$ 列的和问为 $y$ ，此时第 $3$ 列的和的最小值，每次转移也只需枚举在选择是第几列即可。同时记录一下某个值的是选择哪一列转移来的，方便输出答案， code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=55,maxk=5,sumt=110;
int n,m,k,opt,t[maxn][maxk],r[maxk][maxk];
int f[maxn][sumt][sumt],las[maxn][sumt][sumt];
int ans[maxn];
int main()
{
	freopen("placement3.in","r",stdin);
	freopen("placement3.out","w",stdout);
	cin>>n>>m>>k>>opt;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=k;j++)
			cin>>t[i][j];
	for(int i=1;i<=k;i++)
		for(int j=1;j<=k;j++)
			cin>>r[i][j];
	memset(f,0x3f,sizeof(f));
	f[0][0][0]=0;
	for(int i=0;i<n;i++)
	{
		for(int x=0;x<=106;x++)
		{
			for(int y=0;y<=106;y++)
			{
				if(x+t[i+1][1]<=106)
					if(f[i+1][x+t[i+1][1]][y]>f[i][x][y])
						las[i+1][x+t[i+1][1]][y]=1,f[i+1][x+t[i+1][1]][y]=f[i][x][y];
				if(y+t[i+1][2]<=106)
					if(f[i+1][x][y+t[i+1][2]]>f[i][x][y])
						las[i+1][x][y+t[i+1][2]]=2,f[i+1][x][y+t[i+1][2]]=f[i][x][y];
				if(f[i+1][x][y]>f[i][x][y]+t[i+1][3])
					las[i+1][x][y]=3,f[i+1][x][y]=f[i][x][y]+t[i+1][3];
			}
		}
	}
	for(int x=0;x<=106;x++)
	{
		for(int y=0;y<=106;y++)
		{
			if(f[n][x][y]<=106)
			{
				for(int i=n;i>=1;i--)
				{
					ans[i]=las[i][x][y];
					if(las[i][x][y]==1) x-=t[i][1];
					else if(las[i][x][y]==2) y-=t[i][2];
				}
				for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
				return 0;
			}
		}
	}
	return 0;
}

因为最优方案是 $106$ ，所以 $x,y$ 的上届也应是 $106$ ，时间复杂度 $O(nk·ans^2)$ ，空间复杂度 $O(n·ans^2)$ 。

数据点 4

$n=399,m=396,k=100,op=1$ 很容易观察到 $1$ 到 $133$ 、 $134$ 到 $266$ 和 $267$ 到 $399$ 是三条链而且 $opt=1$ 无需计算等待时间，所以能分开计算，计算某一条链的某一个点是，我们只需要知道这条链的上一个问题是哪个 TPU 计算的来计算数据传输的时间，考虑 DP 求答案，设计状态为 $f_{i,x}$ ，代表前 $i$ 个问题选完了，第 $i$ 个问题选的是第 $x$ 个 TPU 。同时记录一下某个值的是选择那一哪个TPU移来的，方便输出答案， code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=500;
int n,m,k,opt,x,y,t[maxn][maxn],r[maxn][maxn],f[maxn][maxn],las[maxn][maxn],ans[maxn];
void solve(int id)
{
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=k;i++) f[id*133][i]=0;
	for(int i=id*133;i<(id+1)*133;i++)
		for(int x=1;x<=k;x++)
			for(int y=1;y<=k;y++)
				if(f[i+1][y]>f[i][x]+t[i+1][y]+r[x][y])
					f[i+1][y]=f[i][x]+t[i+1][y]+r[x][y],las[i+1][y]=x;
	int sm=2e9;
	for(int x=1;x<=k;x++) sm=min(sm,f[(id+1)*133][x]);
	for(int x=1;x<=k;x++)
	{
		if(f[(id+1)*133][x]==sm)
		{
			for(int i=(id+1)*133;i>id*133;i--) ans[i]=x,x=las[i][x];
			for(int i=id*133+1;i<=(id+1)*133;i++) cout<<ans[i]<<" ";
			break;
		}
	}
}
int main()
{
	freopen("placement4.in","r",stdin);
	freopen("placement4.out","w",stdout);
	cin>>n>>m>>k>>opt;
	for(int i=1;i<=m;i++) cin>>x>>y;
	for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) cin>>t[i][j];
	for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) cin>>r[i][j];
	for(int i=0;i<3;i++) solve(i);
	return 0;
}

实际 maxn 没必要开 500 ，但是开 500 不会影响时间和空间复杂度，时间复杂度 $O(nk^2)$ ，空间复杂度 $O(nk)$ 。

数据点 5

$n=500,m=1262,k=5,op=1$ 很容易观察到每个问题最多只依赖于前面 5 个问题，所以在 DP 时记录前 5 个选中的 TPU 即可， code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=505;
int n,m,k,opt,x,y,t[maxn][maxn],r[maxn][maxn],cd[maxn][5];
int f[maxn][5][5][5][5][5],las[maxn][5][5][5][5][5],ans[maxn];
int main()
{
	freopen("placement5.in","r",stdin);
	freopen("placement5.out","w",stdout);
	cin>>n>>m>>k>>opt;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		cd[y][y-x-1]=1;
	}
	for(int i=1;i<=n;i++) for(int j=0;j<k;j++) cin>>t[i][j];
	for(int i=0;i<k;i++) for(int j=0;j<k;j++) cin>>r[i][j];
	memset(f,0x3f,sizeof(f));
	f[0][0][0][0][0][0]=0;
	for(int i=0;i<n;i++)
	{
		for(int x1=0;x1<k;x1++)
		{
			for(int x2=0;x2<k;x2++)
			{
				for(int x3=0;x3<k;x3++)
				{
					for(int x4=0;x4<k;x4++)
					{
						for(int x5=0;x5<k;x5++)
						{
							for(int j=0;j<k;j++)
							{
								int sum=f[i][x1][x2][x3][x4][x5]+t[i+1][j];
								if(i>=1) sum+=cd[i+1][0]*r[x1][j];
								if(i>=2) sum+=cd[i+1][1]*r[x2][j];
								if(i>=3) sum+=cd[i+1][2]*r[x3][j];
								if(i>=4) sum+=cd[i+1][3]*r[x4][j];
								if(i>=5) sum+=cd[i+1][4]*r[x5][j];
								if(f[i+1][j][x1][x2][x3][x4]>sum)
									f[i+1][j][x1][x2][x3][x4]=sum,las[i+1][j][x1][x2][x3][x4]=x5;
							}
						}
					}
				}
			}
		}
	}
	int sm=1e9;
	for(int x1=0;x1<k;x1++)
		for(int x2=0;x2<k;x2++)
			for(int x3=0;x3<k;x3++)
				for(int x4=0;x4<k;x4++)
					for(int x5=0;x5<k;x5++)
						sm=min(sm,f[n][x1][x2][x3][x4][x5]);
	for(int x1=0;x1<k;x1++)
	{
		for(int x2=0;x2<k;x2++)
		{
			for(int x3=0;x3<k;x3++)
			{
				for(int x4=0;x4<k;x4++)
				{
					for(int x5=0;x5<k;x5++)
					{
						if(sm==f[n][x1][x2][x3][x4][x5])
						{
							for(int i=n;i>=1;i--)
							{
								ans[i]=x1;
								int new_x5=las[i][x1][x2][x3][x4][x5];
								x1=x2,x2=x3,x3=x4,x4=x5,x5=new_x5;
							}
							for(int i=1;i<=n;i++) cout<<ans[i]+1<<" ";
							return 0;
						}
					}
				}
			}
		}
	}
	return 0;
}

我用的是 cd 记录某个问题和前面5个问题的依赖关系，时间复杂度 $O(nk^6)$ ，空间复杂度 $O(nk^5)$ 。

数据点 6

$n=500,m=1262,k=5,op=1$ 可以按照 数据点 2 的方法假贪心，每个问题选耗时少的 TPU ， code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=505;
int n,m,k,opt,x,y,t[maxn][maxn],r[maxn][maxn];
int main()
{
	freopen("placement6.in","r",stdin);
	freopen("placement6.out","w",stdout);
	cin>>n>>m>>k>>opt;
	for(int i=1;i<=m;i++) cin>>x>>y;
	for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) cin>>t[i][j];
	for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) cin>>r[i][j];
	for(int i=1;i<=n;i++)
	{
		int ans=1;
		for(int j=2;j<=k;j++) if(t[i][j]<t[i][ans]) ans=j;
		cout<<ans<<" ";
	}
	return 0;
}

然后发现输出和答案正好一样， get10 分 $(*^▽^*)$ 。

数据点 7

$n=500,m=0,k=600,op=2$ 发现所有的计算时间都不小于 $1000$ 但是答案是 $1014$ ，所以每个 TPU 至多会跑一个问题，而且跑的时间不能超过 $1014$ ，那么我们可以把不超过 $1014$ 的时间当作边，建图跑匈牙利算法或网络流，显然成功匹配数量或流量 $=n$ ，此时的匹配或流就是方案了， code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=605,inf=1e8;
int n,m,k,opt,x,ans[maxn],s,t,cnt,fir[maxn*4];
struct node
{
	int u,v,w,op,next;
}e[maxn*maxn*4];
void add_edge(int u,int v,int w)
{
	cnt++,e[cnt].u=u,e[cnt].v=v,e[cnt].w=w,e[cnt].next=fir[u],fir[u]=cnt;
	cnt++,e[cnt].u=v,e[cnt].v=u,e[cnt].w=0,e[cnt].next=fir[v],fir[v]=cnt;
	e[fir[u]].op=fir[v],e[fir[v]].op=fir[u];
}
queue<int> q;
int dep[maxn*4];
bool bfs()
{
	memset(dep,0,sizeof(dep));
	q.push(s);
	dep[s]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=fir[x];i;i=e[i].next)
			if(e[i].w>0&&dep[e[i].v]==0)
				dep[e[i].v]=dep[x]+1,q.push(e[i].v);
	}
	return dep[t]; 
}
int dfs(int now,int flow)
{
	if(now==t) return flow;
	int res=0;
	for(int i=fir[now];i&&flow;i=e[i].next)
	{
		if(e[i].w>0&&dep[e[i].v]==dep[now]+1)
		{
			int tmp=dfs(e[i].v,min(flow,e[i].w));
			flow-=tmp,res+=tmp,e[i].w-=tmp,e[e[i].op].w+=tmp; 
		}
	}
	return res;
}
int dinic()
{
	int res=0;
	while(bfs()) res+=dfs(s,inf);
	return res; 
}
int main()
{
	freopen("placement7.in","r",stdin);
	freopen("placement7.out","w",stdout);
	cin>>n>>m>>k>>opt;
	s=n+k+1,t=s+1;
	for(int i=1;i<=n;i++) add_edge(s,i,1);
	for(int i=1;i<=k;i++) add_edge(i+n,t,1);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
		{
			cin>>x;
			if(x<=1014) add_edge(i,j+n,1);
		}	
	}
	for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) cin>>x;
	int FLOW=dinic();//FLOW没用，只是跑一下方案
	for(int i=1;i<=cnt;i++) if(e[i].u<=n&&n<e[i].v&&e[i].v<=n+k&&e[i].w==0) ans[e[i].u]=e[i].v-n;
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	return 0;
}

时间复杂度 $O(n^2E)$ ，空间复杂度 $O(n)$ 。根据输入数据， $E$ 是 $O(n)$ 量级的。

数据点 8

$n=502,m=22600,k=600,op=2$ 发现这个问题其实是一块一块的， $1$ 和 $502$ 各独自是一块，中间每 $50$ 个问题是一块，要计算下一块的任何问题，必须计算完上一块的所有问题，在块内，和 数据点 7 一样，但是没有了时间限制，但显然时间限制是单调的，我们可以二分。观察到传输数据的时间都为 $0$ 或 $1$ ，而且显然是要传输数据的，所以块间耗时就是 $1$ ，这是定值，不用考虑， code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=605,inf=1e8;
int n,m,k,opt,x,y,a[maxn][maxn],r[maxn][maxn],ans[maxn];
int s,t,cnt,fir[maxn*4];
struct node
{
	int u,v,w,op,next;
}e[maxn*maxn*4];
void add_edge(int u,int v,int w)
{
	cnt++,e[cnt].u=u,e[cnt].v=v,e[cnt].w=w,e[cnt].next=fir[u],fir[u]=cnt;
	cnt++,e[cnt].u=v,e[cnt].v=u,e[cnt].w=0,e[cnt].next=fir[v],fir[v]=cnt;
	e[fir[u]].op=fir[v],e[fir[v]].op=fir[u];
}
queue<int> q;
int dep[maxn*4];
bool bfs()
{
	memset(dep,0,sizeof(dep));
	q.push(s);
	dep[s]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=fir[x];i;i=e[i].next)
			if(e[i].w>0&&dep[e[i].v]==0)
				dep[e[i].v]=dep[x]+1,q.push(e[i].v);
	}
	return dep[t]; 
}
int dfs(int now,int flow)
{
	if(now==t) return flow;
	int res=0;
	for(int i=fir[now];i&&flow;i=e[i].next)
	{
		if(e[i].w>0&&dep[e[i].v]==dep[now]+1)
		{
			int tmp=dfs(e[i].v,min(flow,e[i].w));
			flow-=tmp,res+=tmp,e[i].w-=tmp,e[e[i].op].w+=tmp; 
		}
	}
	return res;
}
int dinic()
{
	int res=0;
	while(bfs()) res+=dfs(s,inf);
	return res; 
}
bool check(int x,int loc)
{
	memset(fir,0,sizeof(fir));
	cnt=0,s=50+k+1,t=s+1;
	for(int i=1;i<=50;i++) add_edge(s,i,1);
	for(int i=1;i<=k;i++) add_edge(i+50,t,1);
	for(int i=loc;i<=loc+50;i++)
		for(int j=1;j<=k;j++)
			if(a[i][j]<=x)
				add_edge(i-loc+1,j+50,1);
	return dinic()==50;
}
int main()
{
	freopen("placement8.in","r",stdin);
	freopen("placement8.out","w",stdout);
	cin>>n>>m>>k>>opt;
	for(int i=1;i<=m;i++) cin>>x>>y;
	for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) cin>>a[i][j];
	for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) cin>>r[i][j];
	ans[1]=ans[n]=1; 
	for(int i=2;i<=k;i++) if(a[1][i]<a[1][ans[1]]) ans[1]=i;
	for(int i=2;i<=k;i++) if(a[n][i]<a[n][ans[n]]) ans[n]=i;
	for(int i=2;i+50<=n;i+=50)
	{
		int l=1,r=10000;
		while(l+1!=r)//(l,r]
		{
			int mid=(l+r)>>1;
			if(check(mid,i)) r=mid;
			else l=mid;
		}
		bool tag=check(r,i);//tag没用，只是跑一下上界为r时的方案
		for(int j=1;j<=cnt;j++) if(e[j].u<=50&&50<e[j].v&&e[j].v<=50+k&&e[j].w==0) ans[e[j].u+i-1]=e[j].v-50;
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	return 0;
}

时间和空间复杂度很难计算但都能接受，在本地跑不到 1s 和 256MB （也可能是 i9 芯片比较猛）。

数据点 9,10

现在没有正确的办法了，所以考虑退火算法，随机生成初始方案和变化即可。每次调用程序太慢了，所以把 simulator 写到程序里常数优化， code:

#include<bits/stdc++.h>
#define ll long long
#define wjin "placement?.in"//?填9或10
#define wjout "placement?.out"//?填9或10
using namespace std;
const int maxn=1010;
namespace simulator
{
	int n,m,k,en,op,r[maxn][maxn],t[maxn][maxn],w[maxn],in[maxn];
	bool running[maxn];
	struct edge
	{
		int e;
		edge *next;
	}*v[maxn],ed[maxn*maxn];
	void add_edge(int s,int e)
	{
		en++;
		ed[en].next=v[s];v[s]=ed+en;v[s]->e=e;
	}
	struct rec
	{
		int v,p;
		rec(){}
		rec(int a){v=a;p=a;}
		rec(int a,int b){v=a;p=b;}
	};
	bool operator<(const rec &a,const rec &b)
	{
		if (a.v != b.v) {
			return a.v>b.v;
		} else if ((a.p & 1) != (b.p & 1)) {
			return (a.p & 1) < (b.p & 1);
		} else {
			return a.p > b.p;
		}
	}
	priority_queue<rec> q[maxn],event;
	void init()
	{
		if (n) return;
		freopen(wjin,"r",stdin);
		scanf("%d%d%d%d",&n,&m,&k,&op);
		for (int a=1;a<=m;a++)
		{
			int p1,p2;
			scanf("%d%d",&p1,&p2);
			add_edge(p1,p2);
		}
		for (int a=1;a<=n;a++)
			for (int b=1;b<=k;b++)
				scanf("%d",&t[a][b]);
		for (int a=1;a<=k;a++)
			for (int b=1;b<=k;b++)
				scanf("%d",&r[a][b]);
	}
	int work(int *w)
	{
		init();
		for (int i=1;i<=n;i++)
			for (edge *e=v[i];e;e=e->next)
				in[e->e]++;
		int totalt=0,maxt=0;
		for (int a=1;a<=n;a++)
			if (!in[a]) 
			{
				q[w[a]].push(a);
				totalt += t[a][w[a]];
			}
		for (int a=1;a<=k;a++)
			if (q[a].size() > 0)
			{
				running[a] = true;
				rec top = q[a].top();
				q[a].pop();
				event.push(rec(t[top.p][a],top.p<<1));
			}

		int solved = 0;
		while (event.size() > 0)
		{
			int nowt=event.top().v;
			maxt=max(maxt,nowt);
			while (event.size()>0 && event.top().v == nowt)
			{
				rec top = event.top();
				event.pop();
				int id=top.p>>1;
				int op=top.p&1;
				if (op == 0)
				{
					for (edge *e=v[id];e;e=e->next)
					{
						event.push(rec(nowt+r[w[id]][w[e->e]],e->e<<1|1));
						totalt += r[w[id]][w[e->e]];
					}
					solved += 1;
					running[w[id]] = false;
				}
				else
				{
					in[id]--;
					if (!in[id])
					{
						totalt += t[id][w[id]];
						q[w[id]].push(rec(id));
					}
				}
			}
			for (int a=1;a<=k;a++)
				if (!running[a] && q[a].size()>0)
				{
					rec now = q[a].top();
					q[a].pop();
					event.push(rec(nowt+t[now.p][a],now.p<<1));
					running[a]=true;
				}
		}
		if (op == 1) return totalt;
		else return maxt;
	}
};
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
ll rint(ll l,ll r){return uniform_int_distribution<ll>(l,r)(rnd);}
int n,m,k,opt;
int times=10,turn=1000;
double start_T=1e4,end_T=1e-4,los_T=0.98;
int a[maxn],b[maxn],ans=1e9;
void tuihuo(int id)
{
	for(int i=1;i<=n;i++) a[i]=rint(1,k);
	int val=simulator::work(a); 
	for(double T=start_T;T>=end_T;T*=los_T)
	{
		for(int i=1;i<=turn;i++)
		{
			int loc=rint(1,n),tmp=rint(1,k);
			int od=a[loc];
			a[loc]=tmp;
			int nval=simulator::work(a);
			if(nval<val||exp((val-nval)/T)>=rint(1,100000000)/1e8) val=nval;
			else a[loc]=od;
			if(val<ans)
			{
				ans=val;
				for(int j=1;j<=n;j++) b[j]=a[j];
				FILE *f=fopen(wjout,"w");
				for(int i=1;i<=n;i++) fprintf(f,"%d ",b[i]);
				fclose(f);
			}
			cerr<<"Round"<<id<<"  :  Tmperature="<<T<<"  ,  Val="<<val<<"  ,  Ans="<<ans<<endl;
		}
	}
}
int main()
{
	freopen(wjin,"r",stdin);
	cin>>n>>m>>k>>opt;
	for(int i=1;i<=times;i++) tuihuo(i);
	return 0;
}

数据点 9 计算出过 18258 ，小于最小评测标准；数据点 10 计算出过 5142063 ，等于最小评测标准。

ID

4191

时间

1000ms

内存

125MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

小葱和组合数问题若干是某位大神の常态。

谨记：提答看数据。

数据点 1

数据点 2

数据点 3

数据点 4

数据点 5

数据点 6

数据点 7

数据点 8

数据点 9,10

[CTSC2018] 组合数问题

信息

1 条题解

自动搬运

以下是正文

小葱和组合数问题若干是某位大神の常态。

谨记：提答看数据。

数据点 1

数据点 2

数据点 3

数据点 4

数据点 5

数据点 6

数据点 7

数据点 8

数据点 9,10

[CTSC2018] 组合数问题

信息

还没有账户？

登录