自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:43:19，当前版本为作者最后更新于2022-11-27 12:43:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意简述：略。

碎碎念：

kkk：传智杯要有个模拟题。
我：好

然后就出现了这么一个题。

本题是要模拟一个大富翁的过程，作为模拟题，其实没有什么算法上的难度，这个题解也就主要讲解一下细节。

1. 建议将部分操作拆入函数中，方便调试；
2. 更推荐使用 $0$ 和 $1$ 作为下标存放二人数据，这样可以直接用 id^1 的方式获得另外一个行动者的各项数据情况，当然你用 $1$ 和 $2$ 的话用 id^3 也行，不过感觉不够直观。
3. 读题上的一些细节：
   1. 在移动的过程中，行动者所经过的每一个格子应当都分为两种情况。验题人一开始读成了行动结束后的格子，而且我猜也有不少人读错了。
   2. 两人都操作完一轮回合后，圆环上的每个建筑物都会提供给拥有者资金。有的人可能忘记了在游戏结束后也要进行这一轮操作。
4. 数据规模问题。可以构造这样的一组数据：$n=2$，$d_1=d_2=10^6$，$q=10000$，莲子和梅莉在第一回合建好了建筑物，接下来每个回合都可以获得 $d_i$ 元，这样她们就能有 $10^6 \times 10^4=10^{10}$ 元，超过了 int 范围。
5. 其他的想到再补。

这个题作为一个难度在 pjT3 左右的模拟还是比较适合的，有读题细节，有一点码量，也带点坑。希望大家做的愉快。

参考代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int n,m,q,L,C[105][105],d[105],a[105],lv[105],pos[2],belong[105];

long long money[2];

const string name[2]={"Renko","Merry"};

inline void putfail(int id)
{
	cout << name[id] << endl;
	exit(0);
}

inline void forward(int id,int k)
{
	for (int i=1;i<=k;i++)
	{
		int &p=pos[id];
		p++;
		if (p>n)
			p-=n;
		if (belong[p]==id)
			money[id]+=a[p];
		else if (belong[p]==(id^1))
		{
			money[id]-=a[p];
			money[id^1]+=a[p];
		}
		if (money[id]<0)
			putfail(id);
	}
}

inline void build(int id,int k)
{
	int p=pos[id],cost=C[p][lv[p]];
	for (int i=1;(money[id]>=cost && lv[p]<L && (belong[p]==-1 || belong[p]==id) && i<=k);i++)
	{
		belong[p]=id;
		money[id]-=cost;
		a[p]+=cost;
		cost=C[p][++lv[p]];
	}
}

int main()
{
	n=read(),m=read(),q=read(),L=read();
	for (int i=1;i<=n;i++)
	{
		for (int j=0;j<L;j++)
			C[i][j]=read();
	}
	for (int i=1;i<=n;i++)
		d[i]=read();
	pos[0]=pos[1]=1;
	fill(belong+1,belong+n+1,-1);
	money[0]=money[1]=m;
	for (int i=0;i<2*q;i++)
	{
		int op=read();
		begin:
			for (int j=1;j<=n && !(i&1);j++)
			{
				if (belong[j]==0)
					money[0]+=d[j];
				else if (belong[j]==1)
					money[1]+=d[j];
			}
			int k=read();
			forward(i&1,k);
			if (i==2*q-1) {
				int op=0;
				cin >> op;
				if (op==2) {
					k=read();
					build(i&1,k);
				}
				break;
			}
			op=read();
			if (op==1)
			{
				i++;
				goto begin;
			}
			else
			{
				k=read();
				build(i&1,k);
			}
	}
	for (int j=1;j<=n;j++)
	{
		if (belong[j]==0)
			money[0]+=d[j];
		else if (belong[j]==1)
			money[1]+=d[j];
	}
	
	cout << money[0] << " " << money[1] << endl;
	return 0;
}