[传智杯 #5 初赛] F-二人的大富翁游戏

GitHub 跳转原题关系图返回列表

按操作顺序直接模拟移动、过路结算、建造升级和轮末收益，维护建筑拥有者、等级与价值即可。

OJ: luogu

题目 ID: P8874

难度:普及/提高-

标签:模拟思维

日期: 2026-06-19 01:38

题意

有两个玩家在一个环形地图上移动。

每次行动会：

按骰子点数走若干步；
路过自己的建筑就收钱，路过对方的建筑就付钱；
停下后，可能在当前位置建造或升级自己的建筑；
每轮两个人都行动完后，所有建筑还会再给拥有者一笔固定收益。

如果某个人在自己行动过程中资金变成负数，这个人立刻输掉游戏。

给出整个操作序列，问谁会输；如果一直没人输，就输出最后两人的资金。

思路

先看一个可以直接验证想法的朴素解：

严格按题意把整场游戏一步一步模拟出来，维护：

两人的当前位置
两人的资金
每个格子是否有建筑
建筑属于谁、等级是多少、当前价值 a_i 是多少

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154// brute.cpp：按题目规则直接模拟整场游戏。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAXL = 105;
const int RENKO = 0;
const int MERRY = 1;

struct Op {
    int type;
    int val;
};

int n, q, L;
long long m;
int c[MAXN][MAXL];
int d[MAXN];
vector<Op> ops;

int pos_[2];
long long money[2];
int owner[MAXN];
int level_[MAXN];
long long value_[MAXN];

void give_round_income() {
    for (int i = 1; i <= n; i++) {
        if (owner[i] != -1) {
            money[owner[i]] += d[i];
        }
    }
}

bool move_player(int who, int step) {
    int other = who ^ 1;

    for (int i = 1; i <= step; i++) {
        pos_[who]++;
        if (pos_[who] > n) {
            pos_[who] = 1;
        }

        int p = pos_[who];
        if (owner[p] == who) {
            money[who] += value_[p];
        }
        else if (owner[p] == other) {
            money[who] -= value_[p];
            money[other] += value_[p];
            if (money[who] < 0) {
                return false;
            }
        }
    }

    return true;
}

void build_or_upgrade(int who, int times) {
    int p = pos_[who];

    if (owner[p] != -1 && owner[p] != who) {
        return;
    }

    if (owner[p] == -1) {
        if (times >= 1 && money[who] >= c[p][0]) {
            money[who] -= c[p][0];
            owner[p] = who;
            level_[p] = 1;
            value_[p] = c[p][0];
            times--;
        }
        else {
            return;
        }
    }

    for (int t = 1; t <= times; t++) {
        if (level_[p] >= L) {
            break;
        }
        if (money[who] < c[p][level_[p]]) {
            break;
        }
        money[who] -= c[p][level_[p]];
        value_[p] += c[p][level_[p]];
        level_[p]++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q >> L;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= L - 1; j++) {
            cin >> c[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
    }

    while (true) {
        Op op;
        if (!(cin >> op.type >> op.val)) {
            break;
        }
        ops.push_back(op);
    }

    for (int i = 1; i <= n; i++) {
        owner[i] = -1;
    }
    pos_[RENKO] = 1;
    pos_[MERRY] = 1;
    money[RENKO] = m;
    money[MERRY] = m;

    int move_cnt = 0;
    for (int i = 0; i < (int)ops.size(); i++) {
        if (ops[i].type != 1) {
            continue;
        }

        int who = move_cnt % 2;
        if (!move_player(who, ops[i].val)) {
            if (who == RENKO) {
                cout << "Renko\n";
            }
            else {
                cout << "Merry\n";
            }
            return 0;
        }

        if (i + 1 < (int)ops.size() && ops[i + 1].type == 2) {
            build_or_upgrade(who, ops[i + 1].val);
            i++;
        }

        move_cnt++;
        if (move_cnt % 2 == 0) {
            give_round_income();
        }
    }

    cout << money[RENKO] << ' ' << money[MERRY] << '\n';

    return 0;
}

这题本质上没有隐藏算法，重点是把规则实现完整、顺序实现正确。

真正容易出错的地方主要有四个：

1 k 操作才会切换行动者，2 k 不会切换；
每个 1 k 后面至多跟一个 2 k，所以要按顺序读操作；
路过格子时，终点格子也算“经过”；
每两次 1 k 操作结束后，才统一结算一轮建筑收益。

因此正式做法依然就是模拟，只是把几个动作拆清楚：

处理 1 k：逐步移动，并在经过每个格子时结算建筑效果；
如果后面紧跟 2 k：尝试建造/升级；
每完成两次 1 k：遍历所有建筑，给拥有者发一轮固定收益；
过程中一旦当前行动者资金变成负数，就立即输出输家。

因为题目规模只有 n,L <= 100，q <= 10^4，直接模拟完全足够。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAXL = 105;
const int RENKO = 0;
const int MERRY = 1;

struct Op {
    int type;
    int val;
};

int n, q, L;
long long m;
int c[MAXN][MAXL];
int d[MAXN];
vector<Op> ops;

int pos_[2];
long long money[2];
int owner[MAXN];         // -1 表示无建筑，0 表示莲子，1 表示梅莉
int level_[MAXN];        // 建筑当前等级
long long value_[MAXN];  // 当前建筑的 a_i

void give_round_income() {
    for (int i = 1; i <= n; i++) {
        if (owner[i] != -1) {
            money[owner[i]] += d[i];
        }
    }
}

bool move_player(int who, int step) {
    int other = who ^ 1;

    for (int i = 1; i <= step; i++) {
        pos_[who]++;
        if (pos_[who] > n) {
            pos_[who] = 1;
        }

        int p = pos_[who];
        if (owner[p] == who) {
            money[who] += value_[p];
        }
        else if (owner[p] == other) {
            money[who] -= value_[p];
            money[other] += value_[p];
            if (money[who] < 0) {
                return false;
            }
        }
    }

    return true;
}

void build_or_upgrade(int who, int times) {
    int p = pos_[who];

    if (owner[p] != -1 && owner[p] != who) {
        return;
    }

    if (owner[p] == -1) {
        if (times >= 1 && money[who] >= c[p][0]) {
            money[who] -= c[p][0];
            owner[p] = who;
            level_[p] = 1;
            value_[p] = c[p][0];
            times--;
        }
        else {
            return;
        }
    }

    while (times > 0) {
        if (level_[p] >= L) {
            break;
        }
        if (money[who] < c[p][level_[p]]) {
            break;
        }
        money[who] -= c[p][level_[p]];
        value_[p] += c[p][level_[p]];
        level_[p]++;
        times--;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q >> L;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= L - 1; j++) {
            cin >> c[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
    }

    while (true) {
        Op op;
        if (!(cin >> op.type >> op.val)) {
            break;
        }
        ops.push_back(op);
    }

    for (int i = 1; i <= n; i++) {
        owner[i] = -1;
    }
    pos_[RENKO] = 1;
    pos_[MERRY] = 1;
    money[RENKO] = m;
    money[MERRY] = m;

    int move_cnt = 0;
    for (int i = 0; i < (int)ops.size(); i++) {
        if (ops[i].type != 1) {
            continue;
        }

        int who = move_cnt % 2;
        if (!move_player(who, ops[i].val)) {
            if (who == RENKO) {
                cout << "Renko\n";
            }
            else {
                cout << "Merry\n";
            }
            return 0;
        }

        if (i + 1 < (int)ops.size() && ops[i + 1].type == 2) {
            build_or_upgrade(who, ops[i + 1].val);
            i++;
        }

        move_cnt++;
        if (move_cnt % 2 == 0) {
            give_round_income();
        }
    }

    cout << money[RENKO] << ' ' << money[MERRY] << '\n';

    return 0;
}

复杂度

设一共读到 2q 次移动操作，总移动步数之和为 S。

时间复杂度是 $O(S + nq)$ ，空间复杂度是 $O(nL)$ 。

总结

这题的关键不是优化，而是规则实现的顺序必须绝对准确。

只要把“移动结算、建造升级、轮末收益、输家判定”这几个时机分开写清楚，代码就会很稳。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P8874 [传智杯 #5 初赛] F-二人的大富翁游戏

题目背景

作为大学生，莲子和梅莉有着比高中时更为闲暇的课余时光。在没有课的时候，她们喜欢玩大富翁这一游戏，在游玩过程中交流自己的喜怒哀乐。

如图所示，是一个 $n=10$ 的大富翁地图。玩家在圆格子上行动。而方格子则可以建造建筑物。每个圆格子唯一对应一个方格子。

（友情提示：赌博是不对的）

题目描述

莲子和梅莉在玩大富翁游戏。这个大富翁游戏是由传智播客定制的，与一般的大富翁游戏在玩法上有略微区别，因此也被称为传智大富翁。

大富翁游戏是由 $n$ 个格子组成，编号逆时针地从 $1,2,\dots,n$ ，构成了一个环。莲子和梅莉起始在编号为 $1$ 的格子。莲子和梅莉最开始都有 $m$ 元资金。每一个回合，莲子先投掷骰子，再是梅莉投掷骰子。每一方行动时，设骰子最上面的数字为 $k$ ，则行动方逆时针移动 $k$ 步。在移动的过程中，行动者所经过的每一个格子应当都分为两种情况：

如果当前格子（假设编号为 $i$ ）上有建筑物，而且建筑物是自己的，则行动方可以获得额外的 $a_i$ 元资金。
如果当前格子上有建筑物，但是建筑物是对方的，则行动方要将自己的 $a_i$ 元资金转移给对方。

在行动结束后亦有两种情况：

如果当前格子（设编号为 $i$ ）上没有建筑物，则行动方可以选择花费 $C_{i,0}$ 元资金（前提要求行动者当前的资金大于等于 $C_{i,0}$ ）搭建建筑物，此时 $a_i$ 被初始化为 $C_{i,0}$ 。
如果当前格子的建筑物是行动方的，假设当前是一座 $j$ 等级的建筑物，那么行动方可以选择用 $C_{i,j}$ 元为建筑物升级，功效是使得 $a_i \gets a_i+C_{i,j}$ 。这里， $C_{i,j}$ 表示将第 $i$ 个格子上的第 $j$ 等级的建筑物升级到第 $j+1$ 等级的建筑物所需花费的资金。同一回合内可以多次升级建筑。特别地，建筑物的等级上限为 $L$ 。如果当前建筑物等级已经到达上限则无法升级。
在所有建筑操作结束后，操作权转移给另一方。

两人都操作完一轮回合后，圆环上的每个建筑物都会提供给拥有者资金，具体来说，第 $i$ 格上的建筑物会给其拥有者提供 $d_i$ 的资金。游戏结束当且仅当存在一个人在它行动过程中或者结束时的资金为负数。此时这个人成为输家（换而言之，允许中途过程资金为 $0$ ）。

给定莲子和梅莉的 $q$ 个回合的每次操作，请问谁会是输家呢？

输入格式

第一行输入四个正整数 $n,m,q,L$ ，表示格子数、初始资金、回合次数和建筑物等级上限。

第二行开始，往下 $n$ 行，每行输入 $L$ 个正整数，表示 $C_{i,j}$ ，其中 $j$ 是从 $0$ 到 $L-1$ 。

第 $(n+2)$ 行输入 $n$ 个正整数表示 $d_i$ 。

第 $(n+3)$ 行开始，往下若干行，每行只会有两种可能的情况：

$\texttt{1 k}$ ，表示当前行动方投掷了骰子，最上面的点数是 $k$ 。之后行动者会逆时针移动 $k$ 步。
$\texttt{2 k}$ ，表示当前行动方在当前位置建造或者升级了建筑物共 $k$ 次。
- 在此过程中，当前位置已经有了对方建筑物则忽略此操作；
- 如果资金不够升级 $k$ 次，则只升级到资金允许范围内的最高等级；
- 在此过程中，如果进行下一次升级，建筑物等级超过 $L$ ，则后续的所有升级忽略处理。

特别地，规定除了第一次外，每次 $\texttt{1 k}$ 操作出现时意味着行动者的切换。也就是说，第一次输入 $\texttt{1 k}$ 操作时，行动方是莲子，第二次是梅莉，第三次是莲子……以此类推。值得注意的是， $\texttt{2 k}$ 操作出现并不会切换行动者。

此外，保证每个 $\bm 1$ 操作后面最多跟随 $\bm 1$ 个 $\bm 2$ 操作。

输出格式

如果已经分出了输赢，则输出谁是输家（如果莲子输，则输出 $\texttt{Renko}$ ；如果梅莉输，则输出 $\texttt{Merry}$ ）；

如果没有分出输赢，则按照先莲子，后梅莉的顺序输出她们现在有的资金数。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
266 40 5 3
10 20 30
15 25 35
6 8 12
6 12 18
8 16 24
8 12 40
1 2 3 4 5 6
1 4
2 3
1 2
2 5
1 3
1 2
2 1
1 5
2 3
1 3
2 4
1 4
1 6
2 2
1 3
2 1
1 3
2 1

输出 #1

text

1Merry

输入输出样例 #2

输入 #2

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
266 9961 5 3
10 20 30
15 25 35
6 8 12
6 12 18
8 16 24
8 12 40
1 2 3 4 5 6
1 4
2 3
1 2
2 5
1 3
1 2
2 1
1 5
2 3
1 3
2 4
1 4
1 6
2 2
1 3
2 1
1 3
2 1

输出 #2

text

110099 9946

说明/提示

【样例解释 1】

第一回合，莲子首先走 $4$ 步，到达编号为 $5$ 的格子，同时尝试建造与升级 $3$ 次第五个格子的建筑物，但是 $C_{5,0}+C_{5,1}+C_{5,2}=48$ ，所以只能把建筑物造到 $2$ 级。此时莲子手上还有 $16$ 元。
接着梅莉走了两步，到达编号为 $3$ 的格子，同时尝试建造与升级 $5$ 次第三个格子的建筑物， $C_{3,0}+C_{3,1}+C_{3,2}=26$ ，而造五次会超过等级上限 $L$ ，因此只能升到 $3$ 次，此时梅莉手上还有 $14$ 元。
回合结束后每个建筑物都会提供给拥有者 $d_i$ 的资金，也就是说莲子此时手上有 $21$ 元，梅莉手上有 $17$ 元。
第二回合，莲子首先走 $3$ 步，到达编号为 $2$ 的格子。梅莉接着走 $2$ 步，到达编号为 $5$ 的格子，收取 $a_i$ 元。而 $a_i=24$ ，因此梅莉的资金被扣成了负数，从而输出 $\texttt{Merry}$ 。

【样例解释 2】

仅在初始资金与第一组样例有一定变化，因此在这些回合中无法决出胜负，因此输出两人手上现有的资金。

【数据范围】

对于所有数据，保证 $1 \leq n,L\leq 100$ ， $1 \leq q \leq 10^4$ ， $1 \leq m,C_{i,j},d_i \leq 10^6$ ， $1 \leq k \leq 10^3$ （你可以不必在意怎么获得一个 $k$ 面的骰子）。数据保证 $1$ 操作次数恰好为 $2\times q$ 。

[传智杯 #5 初赛] F-二人的大富翁游戏

目录

题意

思路

代码

复杂度

总结

一图流解析