#P9319. [EGOI 2022] Social Engineering / 社会工程
[EGOI 2022] Social Engineering / 社会工程
题目背景
Day 1 Problem C.
题面译自 EGOI2022 socialengineering。
本题是一道 Grader 交互题。
本题只支持 C++ 提交,提交时不需要包含 socialengineering.h
头文件,但需要在代码中包含 GetMove
和 MakeMove
函数的声明(见【交互方式】部分)。
请使用 C++14、C++17 等语言,而不是 C++14 (GCC 9),因为一些未知原因这个语言下 SPJ 会 CE。
感谢
题目描述
一个社交网络是一个 点 边的无向连通图组成,其中每个点代表一个人,如果两个人之间有边相连,他们就是朋友。
玛丽亚是这个社交网络的成员。她喜欢以各种事情挑战她的朋友。这意味着,她首先执行一些简单的任务,然后挑战她的一个朋友做同样的事情。这个朋友随后会挑战他的一个朋友,而被挑战的朋友会接着挑战他的另一个朋友,以此类推。同一个人可能会被挑战多次,但每一个无序朋友对最多进行一次挑战。(一旦 A 挑战了 B,那么 A 和 B 都不能再次挑战对方。)换句话说,挑战可以看作图中的一条路径,其中一条边至多经过一次。
如果轮到一个人,而他又不能挑战任何朋友,那么这个人就输了。挑战总是由玛丽亚开始,她很少输。现在其他 人决定合作,以使玛丽亚输掉下一次挑战,请你帮助他们完成目标。
交互方式
你必须实现一个函数:
void SocialEngineering(int n, int m, vector<pair<int,int>> edges);
这个函数在 点 边的图上玩该游戏。这个函数会被交互库调用恰好一次。列表 edges
包含恰好 对整数 ,表示有一条连接点 和点 的边。节点编号从 到 。玛丽亚永远是节点 。你的函数可以调用以下函数:
int GetMove();
这个函数应当在玛丽亚的回合被调用,例如游戏的最开始。如果你在不是玛丽亚的回合调用这个函数,你会 WA。这个函数可以返回以下值之一:
- 一个整数 ,其中 。这意味着玛丽亚挑战编号为 的人。保证这一步一定合法。
- ,如果玛丽亚认输。当玛丽亚没有合法操作时,她就会认输。当这发生时,你的程序应当使
SocialEngineering
函数返回,然后你会 AC。
void MakeMove(int v);
这个函数应当在不是玛丽亚的回合被调用。这意味着当前回合的人挑战第 个人。如果这一步不合法,或者在玛丽亚的回合调用这个函数,你会 WA。如果在游戏开始时,玛丽亚有必胜策略,你的程序应当在第一次调用 GetMove()
前使 SocialEngineering
函数返回,然后你会 AC。
输入格式
见【交互方式】部分。
输出格式
见【交互方式】部分。
提示
样例交互过程
你的操作 | 交互库的操作 | 解释说明 |
---|---|---|
SocialEngineering(5, 6, {{1,4}, {1,5}, {2,4}, {2,5}, {2,3}, {3,5}}) |
SocialEngineering 被调用,参数为一个 点 边的图。 |
|
GetMove() |
返回 | 玛丽亚挑战第 个人。 |
MakeMove(2) |
第 个人挑战第 个人。 | |
MakeMove(5) |
第 个人挑战第 个人。 | |
MakeMove(1) |
第 个人挑战玛丽亚。 | |
GetMove() |
返回 | 玛丽亚没有合法操作,所以她认输。 |
返回 | 你赢了游戏,应当使 SocialEngineering 函数返回。 |
样例交互过程
你的操作 | 交互库的操作 | 解释说明 |
---|---|---|
SocialEngineering(5, 1, {{1,2}}) |
SocialEngineering 被调用,参数为一个 点 边的图。 |
|
返回 | 玛丽亚有必胜策略,你的程序应当在未调用 GetMove() 前使 SocialEngineering 函数返回以认输。 |
数据范围
对于全部数据,,。保证图连通,每对无序点对至多作为边出现一次,每条边连接两个不同节点。
当玛丽亚有必胜策略时,她会完美地执行必胜策略。如果她没有必胜策略,她会试图以各种聪明的手段引诱你的程序犯错误。除子任务三外,只有当玛丽亚没有合法操作时,她才会认输。
- 子任务一( 分):。
- 子任务二( 分):除玛丽亚外,每个人至多有 个朋友。
- 子任务三( 分):除非玛丽亚有必胜策略,否则她会立即认输。
- 子任务四( 分):。
- 子任务五( 分):无特殊限制。
感谢