题目描述
麻将猜牌类型的模拟题。(写给自己的题解)
这个题目初看很复杂,其实正确的解题思路所生成的逻辑并不复杂。
思路:
1. 抓取题目中的关键信息,尤其黑体部分,转化为自己的理解方式
- 麻将一共27张,分 W, T, B三类,各九张,每张麻将的牌型可以直接看到
- 玩法:两名玩家,采用不同的策略轮流进行猜牌,每个人初始有一定数量的牌,之后从公共牌堆摸牌(公共牌堆有牌的时候),当一个人的牌被全部猜出游戏结束。
- 一些规则:每个人的牌从小到大排序(即对方可以知道左小右大之类的);时刻知道自己的牌;先摸牌再猜牌,猜测错误需要翻开摸到的牌;
- 策略:晨晨使用 小大小的策略猜对手的牌,(叫小大小是为好记否则容易忘记),表示优先猜排序中最小的那张牌,对于这张牌的可能范围从大到小进行猜测。小路使用 大小大 的策略。
- 黑体强调:对方不会猜测已经摸过的牌;不知道互相的猜测策略;第二点好理解,主要是第一点主语是对方,可以理解为这个是一个隐性规则(因为这样做对自己没有直接好处,虽然可能可以恶心别人),这样带来的后果就是,一旦对方猜过这张牌,并且没有摸到同牌型的牌(牌型是可以直接看到的),可以认为该牌一定不在对方牌堆中,后续可以不用猜测。
2.信息有点多先捋一捋,主要是游戏规则和玩家策略
- 游戏规则:3 * 9 = 27牌,牌型透明,两个玩家,轮流摸牌,猜牌,排序插入(自己的牌堆)
- 玩家策略:利用相同方式得到的信息,分别用小大小,大小大进行猜测
- 可以计算未知牌范围的信息来源:对方的已知牌,自己的牌,对方猜过的牌,对方的未知牌自己设定的范围(仅考虑该牌的左右即可)
3.伪代码思想
- 结构体设计:麻将,玩家(麻将比较特殊所以单独使用一个结构体,玩家信息较多)
- 3.1 game_init 游戏初始化,读取各自牌堆和公共牌堆
- 3.2 game_turn 轮流执行回合
- 3.3 check_game_end 检查游戏是否结束
- 3.4 game_output 进行游戏结果输出
其中 3.2 需要设计中展开
- 3.2.1 pub_get_maj 尝试从公共牌堆中获取麻将,直接插入自己牌堆
- 3.2.2 get_next_guessed_id 获取本次需要猜测的麻将
- 3.2.3 update_maj_scope 猜测前更新对方每张麻将的范围
- 3.2.4 guess 进行猜测
- 3.2.5 猜测成功且插入新牌时,对方需要对该类牌型记录的已猜测值进行重置(因为可能摸到之前猜的),猜测失败需要展示这张牌,并根据猜牌策略缩小该牌的范围。
注意:仅仅在使用猜牌策略时,双发存在差异,其他情况下操作均应当一致,很大程度降低思考复杂度。注意在两个地方,一个是获取待猜测的麻将不同,一个是使用比较的范围端点值,和失败后的端点范围缩小不同。
其中3.2.4是存在一定算法思想的部分,但不复杂
如何更新每张未知麻将的范围,显然每张麻将有上界和下界,且上下界随着游戏的进行越来越紧缩,即均单调变化。以上界范围缩减为例,根据对方新被展开的牌,自己新摸的牌,对方猜测的牌可以进行范围缩减。且每个人的牌堆均是单调有序的(表面下一个一定在上一个的界限上 +-1),且不能和已经确定不可能的牌相同)
注意,上界和下界中可能夹杂一些不可能的值(此点未论证),但无影响,该题猜测策略也是单调的
反思:
1. 上来就动笔写代码是大忌,一旦思路不对就浪费很多时间,且思路没有形成记录,还有之后回忆,且极其容易让人疲惫。
2. 模拟题建议增加适当的debug功能方便调试
3. 非常感谢 CYMario 大佬,有一个答案在这里的好处就是,你调试的时候不需要一步步的看,可以直接对比各阶段的debug信息。
4. 关于清晰的代码,我认为在于看上去你确定下一步你大概也这样写(理解了含义之后),感觉自己的写的像坨。,当然算法应该适当简单快速(模拟题的定位有点尴尬,我大型项目感觉写的也比较烂,如果大家有什么学习途径其他推荐,十分感谢分享)。
一些闲言碎语:
1.模拟题一个很关键的因素在于大方向要明确且正确(说实话,这很难,问题一上来很复杂,感觉基本上不能一下找到正确的解题思路。 ————基于对错误的解题思路分析和整理
2.复杂模拟题的代码如何编写,元素结构体,总感觉写着写着网络之前的内容,记忆力确实有所下降,但感觉还是没有找到适合自己的方法
3.不是很能耐得住性子反复做这种题目,生活中杂事,各类欲望,惰性心理,都大大拉长这题的时间,一天近3个小时,4天才完成整个题目的粗略复盘,中间的很多细节都没有记录,时间拉长导致更容易忘记了。。
样例
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cassert>
using namespace std;
#define cc_role 0
#define xl_role 1
string pub_str;
int pub_read = 0;
typedef struct StPlayer Player;
typedef struct StMajh {
bool isOpen;
bool inUse;
int mi; // 该麻将可能的最小值
int mx; // 该麻将可能的最大值
} Majh;
typedef struct StPlayer {
char name;
int mj_num;
int open_count;
int read_id; // 当前猜测值
int read_trait; // 0,1,2表示wan tiao bing
Majh mjdp[3][12];
bool guessed_maj[3][12]; // 标记对应牌是否被该角色猜过
Player *oppo;
void player_role_init(char player_name)
{
name = player_name;
memset(mjdp, 0, sizeof mjdp);
memset(guessed_maj, 0, sizeof guessed_maj);
mj_num = 0;
open_count = 0;
}
void maj_insert(int trait, int id)
{
mjdp[trait][id].inUse = true;
mjdp[trait][id].isOpen = false;
mjdp[trait][id].mi = 1;
mjdp[trait][id].mx = 9;
mj_num++;
}
void set_maj_open(int trait, int id)
{
mjdp[trait][id].isOpen = true;
mjdp[trait][id].mi = id;
mjdp[trait][id].mx = id;
open_count ++;
}
void open_oppo_maj()
{
oppo->set_maj_open(oppo->read_trait, oppo->read_id);
}
void update_min_next_guessed_maj()
{
for (int j = 1; j <= 9; j++)
for (int k = 0; k < 3; k++)
if (mjdp[k][j].inUse && !mjdp[k][j].isOpen) {
read_id = j;
read_trait = k;
return;
}
}
void update_max_next_guessed_maj()
{
for (int j = 9; j > 0; j--)
for (int k = 2; k >= 0; k--)
if (mjdp[k][j].inUse && !mjdp[k][j].isOpen) {
read_id = j;
read_trait = k;
return;
}
}
int get_cur_guessed_val()
{
if (name == 'c') return mjdp[read_trait][read_id].mi;
return mjdp[read_trait][read_id].mx;
}
void update_cur_guessed_val()
{
if (name == 'c') mjdp[read_trait][read_id].mi ++;
else mjdp[read_trait][read_id].mx --;
}
bool check_val_equal()
{
if (name == 'c') return mjdp[read_trait][read_id].mi == read_id;
else return mjdp[read_trait][read_id].mx == read_id;
}
int get_cur_mx(int rrt, int rri)
{
int j = rrt + 1;
for (int k = rri; k < 10; k++) {
for (; j < 3; j++)
if (mjdp[j][k].inUse) {
int t = mjdp[j][k].mx;
if (rrt < j) return t;
else return t - 1;
}
j = 0;
}
return 9;
}
int get_cur_mi(int trait, int id)
{
int j = trait - 1;
for (int k = id; k > 0; k--)
{
for (; j >= 0; j--)
{
if (mjdp[j][k].inUse)
{
int t = mjdp[j][k].mi;
if (trait > j) return t;
else return t + 1;
}
}
j = 2;
}
return 1;
}
void reset_guessed_maj(int trait, int id) // 成功猜对后,新的插入可以迷惑对手,重置一定范围的值
{
// 失效的范围,在上一个值的mi, 到下一个值的mx
int start = get_cur_mi(trait, id);
int end = get_cur_mx(trait, id);
for (int k = start; k <= end; k++) guessed_maj[trait][k] = false;
}
void set_guessed_maj(int id)
{
guessed_maj[oppo->read_trait][id] = true;
}
bool is_winner()
{
return oppo->open_count == oppo->mj_num;
}
int get_closed_maj()
{
return mj_num - open_count;
}
void update_maj_scope() // 提供给对手调用
{
Player *pp = this; // 相当于对手
Player *op = oppo; // 所以这里的op相当于是自己
// 更新上界
// 策略为逆序遍历每个麻将,更新上界为他们当前可能的最大值
// 可利用的信息有,已open状态的对方麻将提供了严格顺序,自己的麻将提供了该值是否允许被猜测,以及逆序dp的前置信息即 last_id 和 last_trait
int last_id = 9;
int last_trait = 3;
int ff[3][12]; // 用来标记该值是否可能被猜测(被自己拥有或者对方猜过时,不能被猜测)
memset(ff, 0, sizeof ff);
for (int k = 9; k > 0; k--)
{
assert(last_id >= k);
for (int j = 2; j >= 0; j--)
{
if (pp->mjdp[j][k].inUse)
{ // 可能需要更新状态
if (pp->mjdp[j][k].isOpen)
{
assert(last_id >= k);
last_id = k;
last_trait = j;
ff[j][k] = 1;
}
else
{
// try update last_num to now num
if (last_id > pp->mjdp[j][k].mx)
{
last_id = pp->mjdp[j][k].mx;
if (ff[j][last_id]) while (ff[j][--last_id]);
}
else
{
if (last_trait > j)
{
if (ff[j][last_id]) while (ff[j][--last_id]);
}
else while (ff[j][--last_id]);
}
last_trait = j;
pp->mjdp[j][k].mx = last_id;
ff[j][last_id] = 1;
}
}
else if (op->mjdp[j][k].inUse || pp->guessed_maj[j][k]) ff[j][k] = 1;
}
}
last_id = 1;
last_trait = -1;
memset(ff, 0, sizeof ff);
// 更新下界,同上
for (int k = 1; k < 10; k++)
{
assert(last_id <= k);
for (int j = 0; j < 3; j++)
{
if (pp->mjdp[j][k].inUse)
{
if (pp->mjdp[j][k].isOpen)
{
assert(last_id <= k);
last_id = k;
last_trait = j;
ff[j][k] = 1;
}
else
{
// try update last_num to now num
if (last_id < pp->mjdp[j][k].mi)
{
last_id = pp->mjdp[j][k].mi;
if (ff[j][last_id]) while (ff[j][++last_id]);
}
else
{
if (last_trait < j)
{
if (ff[j][last_id]) while (ff[j][++last_id]);
}
else while (ff[j][++last_id]);
}
last_trait = j;
pp->mjdp[j][k].mi = last_id;
ff[j][last_id] = 1;
}
}
else if (op->mjdp[j][k].inUse || pp->guessed_maj[j][k]) ff[j][k] = 1;
}
}
}
void guess_log(int num, bool ret)
{
// const char *s1 = name == 'c' ? "xl" : "cc";
// const char *s2 = name == 'c' ? "cc" : "xl";
// char c = 'W';
// if (read_trait == 1) c = 'T';
// else if (read_trait == 2) c = 'B';
// if (ret) printf("%s guess %s %d%c succeed\n", s1, s2, num, c);
// else printf("%s guess %s %d%c failed, really %d%c\n", s1, s2, num, c, read_id, c);
}
} Player;
Player player[2];
#define cc_player player[0]
#define xl_player player[1]
void pub_get_maj(int* rt, int* ri)
{
if (pub_read >= (int)pub_str.length() - 1) return;
*ri = pub_str[pub_read] - '0';
if (pub_str[pub_read + 1] == 'W') *rt = 0;
else if (pub_str[pub_read + 1] == 'T') *rt = 1;
else if (pub_str[pub_read + 1] == 'B') *rt = 2;
pub_read += 2;
}
void game_turn(int role)
{
Player* pp = role == cc_role ? &cc_player : &xl_player;
int trait = 0, id = 0;
pub_get_maj(&trait, &id);
if (id != 0) pp->maj_insert(trait, id); // 先插入后,之后决定是否翻开
if (pp->oppo->name == 'c') pp->oppo->update_max_next_guessed_maj(); // cc 被从最大值开始猜
else pp->oppo->update_min_next_guessed_maj();
pp->oppo->update_maj_scope(); // 更新一下对方的各个maj的scope
int guess_id = pp->oppo->get_cur_guessed_val(); // 当前猜测值
pp->set_guessed_maj(guess_id); // 设置自己猜过的值
bool result = pp->oppo->check_val_equal();
if (result) pp->open_oppo_maj(); // 打开对方当前被猜测id
else pp->oppo->update_cur_guessed_val();
pp->oppo->guess_log(guess_id, result);
if (!result && id != 0) {
pp->set_maj_open(trait, id); // 猜测失败会展示此次的牌
} else if (result && id != 0) {
pp->reset_guessed_maj(trait, id); // 猜测成功可能插入新的牌(可能是之前猜测过的,需要重置一些猜测过的牌)
}
}
void game_role_init(int role) // 这个初始化有点抽象,但是也不知道咋改好一点
{
Player* pp = role == cc_role ? &cc_player : &xl_player;
char name = role == cc_role ? 'c' : 'l';
pp->player_role_init(name);
string s;
cin >> s;
pp->oppo = role == cc_role ? &xl_player : &cc_player;
for (int i = 0; i < (int)s.length() - 1; i += 2)
{
int num = s[i] - '0';
int trait = 0;
if (s[i + 1] == 'T') trait = 1;
else if (s[i + 1] == 'B') trait = 2;
pp->maj_insert(trait, num);
}
}
void game_init()
{
game_role_init(cc_role);
game_role_init(xl_role);
cin >> pub_str;
}
void game_output()
{
if (cc_player.is_winner()) {
printf("C\n%d", cc_player.get_closed_maj());
} else if (xl_player.is_winner()) {
printf("L\n%d", xl_player.get_closed_maj());
} else {
printf("dead circulate");
}
}
bool game_end()
{
return cc_player.is_winner() || xl_player.is_winner();
}
int main() {
game_init();
int turn_role = 0;
int i = 0;
do {
// printf("i: %d\n", i);
game_turn(turn_role);
turn_role = !turn_role;
i++;
if (i > 30) break; // for debug
} while(!game_end());
game_output();
return 0;
}