传智杯 2022 初赛 F 题解

· · 题解

题意简述：略。

碎碎念：

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;
}