云服务器网站建设,郴州有什么好玩的地方,lnmp wordpress 登陆,中通顺昌建设有限公司网站原题链接#xff1a;
PTA | 程序设计类实验辅助教学平台 题面#xff1a; 在某个直播间里#xff0c;观众常常会发送类似这样的弹幕#xff1a; 鱼越大#xff0c;鱼刺越大#xff1b;鱼刺越大#xff0c;肉越少#xff1b;肉越少#xff0c;鱼越小#xff1b;所以鱼…原题链接
PTA | 程序设计类实验辅助教学平台 题面 在某个直播间里观众常常会发送类似这样的弹幕 鱼越大鱼刺越大鱼刺越大肉越少肉越少鱼越小所以鱼越大鱼越小这样通过一连串推导得出一个搞笑的结论的弹幕发送者被称为“相对论大师”。 现在给定一系列已有的推论请你从给定的推论中挑选一些组成一条类似于上面的弹幕成为一名“相对论大师”。 输入格式: 输入第一行是一个正整数 N (1≤N≤1000表示总共有多少条推论。 接下来的 N 行每行有两对四个元素形如下 A 0 B 1 每对元素表示一个论点第一个是一个长度不大于 5 的、只包含大小写字母的字符串称为论点的核心第二个数字固定为 0 或者 1代表论点核心的方向属性。为简单理解你可以将 0 理解为正面方向1 理解为负面方向。例如 YuCi 0 Rou 1 就可以理解为鱼刺大肉少 。 于是一行中的两个论点就形成一条推论表示第一个核心某个方向的属性能推出第二个核心的某个方向的属性即鱼刺越大肉越少。 输出格式: 按照弹幕格式输出一行例如 Yu 0 YuCi 0 YuCi 0 Rou 1 Rou 1 Yu 1 Yu 0 Yu 1具体格式要求为在一行中输出从起始论点到最终论点的所有推论论点格式与输入相同论点间以1个空格分隔。随后输出等号等号前后均有1个空格最后是相互矛盾的起始和终止论点。 如果有多种方案选择使用推论最少的推论条数相同的输出任意一种方案均可。 在方案中每条推论仅可使用一次。保证有解且给定的推论中没有相同的推论。 输入样例: 5
Yu 0 Yuci 0
Rou 1 Yu 1
Yuci 0 Rou 1
Yuci 0 Gutou 0
Gutou 0 Rou 0 输出样例: Yu 0 Yuci 0 Yuci 0 Rou 1 Rou 1 Yu 1 Yu 0 Yu 1提示: 本题返回结果若为格式错误均可视为答案错误。 解题思路
BFS搜索需要对每个论据用map转换为整数x以方便建图对于一个论据的相反论据我们将其编码为x10000。对于每个点我们都要作为起点跑一次bfs 代码CPP
#include bits/stdc.h
using namespace std;
#define endl \n
typedef long long ll;
typedef unsigned long long ull;
const int maxn 1e4 2010;
const int INF 0x3fffffff;
const int mod 1000000007;
setstring core; // 论点核心
mappairstring, int, int mp; // 把论点映射成整数方便建图
mapint, pairstring, int mmp; // 逆映射
vectorint G[maxn];
bool vis[maxn];
int pre[maxn]; // 记录最短路径节点前驱
vectorint path; // 路径
vectorint ans; // 答案
int n;int encode(string s, int x) { // 将每个论据映射为整数用于建图int u;if (core.count(s)) {if (mp.count({s, x})) {return mp[{s, x}];}u mp[{s, !x}] 10000; // 反论点mp[{s, x}] u;mmp[u] {s, x};} else {core.insert(s);u mp.size() 1;mp[{s, x}] u;mmp[u] {s, x};}return u;
}void dfs(int u) { // 回溯记录bfs的最短路径if (u pre[u]) {path.push_back(u);return;}dfs(pre[u]);path.push_back(u);
}void bfs(int start) {memset(vis, 0, sizeof vis);path.clear();queueint q;q.push(start);vis[start] true;pre[start] start;while (!q.empty()) {int u q.front();q.pop();if (abs(u - start) 10000) { // 判断是否已经找到了逻辑悖论dfs(u);if (ans.empty() || path.size() ans.size()) {ans path;}return;}for (int i 0; i G[u].size(); i) {int v G[u][i];if (!vis[v]) {vis[v] true;pre[v] u;q.push(v);}}}
}void solve() {cin n;for (int i 1; i n; i) {string sa;int a;string sb;int b;cin sa a sb b;int u encode(sa, a);int v encode(sb, b);G[u].push_back(v);}for (auto ele : mp) {bfs(ele.second);}cout mmp[ans[0]].first mmp[ans[0]].second ;cout mmp[ans[1]].first mmp[ans[1]].second ;for (int i 2; i ans.size(); i) {cout mmp[ans[i - 1]].first mmp[ans[i - 1]].second ;cout mmp[ans[i]].first mmp[ans[i]].second ;}cout mmp[ans[0]].first mmp[ans[0]].second mmp[ans[ans.size() - 1]].first mmp[ans[ans.size() - 1]].second;
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout fixed;cout.precision(18);solve();return 0;
}
