比赛名称：第二十三届中国计量大学校 ACM 团队赛暨《ACM 竞赛实训》期末考试 编写日期：2026-06-19
编写人：Abs1nthe
本文档已根据题面补全 A-N 题标题、题型标签、难度分层与 Codeforces 风格估分。CF 估分为主观训练参考分，并非官方难度。
本场比赛共 14 题，题号为 A 到 N。整体覆盖模拟、基础数论、构造、树形 DP、最短路、并查集、动态规划、组合博弈等知识点。
| 题号 | 题目名称 | 难度 | CF 估分 | 算法标签 | 备注 |
|---|---|---|---|---|---|
| A | 硬币分类 | 中等偏难 | 1900 | 交互、分类、决策策略 | 自适应交互题 |
| B | Agent 执行计划树 | 困难 | 2100 | 树形 DP、换根 DP、组合数学、逆元 | 统计每个根的拓扑序数量 |
| C | 鸟为什么会飞 | 签到 | 900 | 数论、gcd、质因子、枚举 | 找最小可用编号 |
| D | GTNH? | 中等 | 1600 | 最短路、Dijkstra、虚点建图 | 同色跳跃可压成颜色点 |
| E | 矩阵构造 | 困难 | 2300 | 构造、异或排列、完全映射 | 题面提示不建议考试作答 |
| F | 生命因何而沉睡 | 签到 | 800 | 模拟、相邻差、边界判断 | 扫描重点时刻 |
| G | ACMBTI String | 困难 | 2200 | 构造、子序列、状态压缩、搜索 | 控制 16 个模式的出现性 |
| H | 以此烈火,斩无不断 | 困难+ | 2400 | 组合博弈、排列计数、数学 | 先判胜负性质，再计数最优排列 |
| I | 数世往回皆空虚 | 签到 | 800 | 整除、基础输入输出 | 输出 a / b |
| J | 雪融之后 | 中等 | 1700 | 离线、并查集、网格连通 | 反向加点处理水位上升 |
| K | Taibo 相信着 LanGod 的希望灯塔并偷偷将感染和被蛇咬加入他的卡组 | 中等偏难 | 1900 | 动态规划、状态优化、博弈式决策 | n,m <= 50 |
| L | 千万次初见 | 简单 | 1200 | 前缀和、构造判定、非负数组 | 判断是否可重排 |
| M | 然后,向着明天 | 简单 | 1000 | 构造、排列、逆操作、字典序 | 分情况构造 |
| N | 命运骰子 | 签到 | 800 | 模拟、骰子状态维护 | 维护六个面 |
有 n 枚硬币，被分为 A、B、C 三类，三类质量严格递增且每类至少一枚。每次可以询问两枚硬币质量大小关系，要求在不超过 floor(3n/2) 次询问内确定所有硬币类别。本题为自适应交互题。
1 <= T <= 10^43 <= n <= 30维护若干个“相等组”，每个组内的硬币已经通过若干次 = 比较证明属于同一类，用一个代表元表示整个组。
第一阶段不断从未处理代表集合 u 中取出两个代表 x,y 比较：
x = y，则合并两个相等组，新的代表继续放回 u。x < y，则 x 所在组一定不是 C 类，只可能是 A 或 B；y 所在组一定不是 A 类，只可能是 B 或 C。于是把 x 放入低端候选集合 l，把 y 放入高端候选集合 h。x > y，同理把 y 放入 l，把 x 放入 h。第一阶段结束后，最多剩下一个未被配对出去的相等组，记为 ex。
接下来分别处理 l 和 h。由于 l 中每个代表都只可能属于 A 或 B，因此只要用 l[0] 和其余所有元素比较，就能把 l 分成较轻的一类 l1 和较重的一类 l2。如果 l2 为空，说明 l 中所有代表属于同一类。对 h 同理，将其分成较轻的 h1 和较重的 h2。其中 h 中元素只可能属于 B 或 C。
分类时分情况讨论：
l2 和 h2 都非空，则 l1=A,l2=B,h1=B,h2=C。l2 非空，则 l1=A,l2=B，而三类均非空，所以 h1=C。h2 非空，则 h1=B,h2=C，而三类均非空，所以 l1=A。ex，且前面已经确定了某个 B 类代表，则再询问一次 ex 与该 B 类代表的关系即可确定 ex。ex，且 l2,h2 都为空，则当前只有三类候选组：l1,h1,ex，并且必有 l1 < h1。此时比较 ex 与 l1,h1，即可判断 ex 是 A、B、C 中的哪一类。最后将每个代表对应的整个相等组统一赋值即可。
首先证明第一阶段的不变式。每次比较两个相等组代表时，若回答为 =，则这两个组内所有硬币均与代表同类，因此合并后仍然是一个合法相等组。若回答为 <，较轻的一组不可能是 C，因为 C 是最重类；较重的一组不可能是 A，因为 A 是最轻类。因此较轻代表只可能属于 A 或 B，可以放入 l；较重代表只可能属于 B 或 C，可以放入 h。回答为 > 时同理。所以第一阶段结束后，l 中每个代表只可能是 A/B，h 中每个代表只可能是 B/C，ex 若存在则仍是一个合法相等组。
然后证明 split2 正确。对于 l，其中所有代表只来自 A/B 两类。选定 l[0] 后，将其他代表与它比较：等于 l[0] 的必然与它同类；不等于 l[0] 的必然属于另一类。由于 l 中只有两种可能类别，所有不等于 l[0] 的元素方向必然一致。因此 split2(l) 得到的两部分若都非空，则较轻部分一定是 A，较重部分一定是 B；若第二部分为空，则说明 l 中所有代表同类。对 h 完全同理，若 split2(h) 两部分都非空，则较轻部分一定是 B，较重部分一定是 C。
接着证明分类分支正确。若 l2 和 h2 都非空，由上一段可知 l1=A,l2=B,h1=B,h2=C。若只有 l2 非空，则 l 中同时出现 A 和 B；其中 B 出现在 l 中，只可能来自某次 B 与 C 的不等比较，所以对应的 C 一定被放入了 h。又因为 h2 为空，h 中所有代表同类，因此 h1=C。若只有 h2 非空同理，h1=B,h2=C,l1=A。若存在 ex 且已经有 B 类代表，直接比较 ex 与 B：小于则为 A，等于则为 B，大于则为 C。最后一种情况中，l2,h2 均为空，说明 l1 是同一类，h1 是同一类，且由第一阶段的配对关系可知 l1<h1。因为三类均至少出现一次，剩余组 ex 必须是缺失的第三类，比较 ex 与 l1,h1 即可唯一确定三者分别为 A、B、C。故算法输出的每个硬币类别均正确。
设第一阶段产生了 s 对不等关系，即 |l|=|h|=s；产生了 r 次相等合并；最后是否存在剩余组记为 e，其中 e 为 0 或 1。每次相等比较使未处理组数量减少 1，每次不等比较使未处理组数量减少 2，因此有：
n = r + 2s + e第一阶段询问 r+s 次。两次 split2 最多各询问 s-1 次，共 2s-2 次。若 e=0，无需额外询问，总次数为：
r+s+2s-2 = r+3s-2 = n+s-2 <= floor(3n/2)若 e=1，最后最多额外询问 2 次，总次数为：
r+s+2s-2+2 = r+3s = n+s-1 <= floor(3n/2)其中 s <= floor(n/2)，当 e=1 时还有 s <= (n-1)/2。因此总询问次数一定不超过题目限制。
#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define u64 unsigned long long
#define debug(x) cout<<x<<endl;
#define endl "\n"
char ask(int x, int y)
{
cout << "? " << x << " " << y << endl;
cout.flush();
char ch;
cin >> ch;
if (!cin) exit(0);
if (ch != '<' && ch != '>' && ch != '=') exit(0);
return ch;
}
void put(const vector<int>& a, char c, vector<char>& ans, const vector<vector<int>>& g)
{
for (int id : a)
{
for (int x : g[id]) ans[x] = c;
}
}
pair<vector<int>, vector<int>> split2(const vector<int>& v)
{
if (v.empty()) return {{}, {}};
vector<int> x, y;
x.push_back(v[0]);
int dir = 0;
for (int i = 1; i < (int)v.size(); i++)
{
char ch = ask(v[0], v[i]);
if (ch == '=')
{
x.push_back(v[i]);
}
else
{
y.push_back(v[i]);
if (!dir) dir = (ch == '<' ? -1 : 1);
}
}
if (y.empty()) return {x, {}};
if (dir == -1) return {x, y};
return {y, x};
}
void sol()
{
int n;
cin >> n;
vector<vector<int>> g(n + 1);
for (int i = 1; i <= n; i++) g[i].push_back(i);
vector<int> u, l, h;
for (int i = 1; i <= n; i++) u.push_back(i);
while ((int)u.size() >= 2)
{
int x = u.back(); u.pop_back();
int y = u.back(); u.pop_back();
char ch = ask(x, y);
if (ch == '=')
{
for (int v : g[y]) g[x].push_back(v);
u.push_back(x);
}
else if (ch == '<')
{
l.push_back(x);
h.push_back(y);
}
else
{
l.push_back(y);
h.push_back(x);
}
}
int ex = -1;
if (!u.empty()) ex = u[0];
auto [l1, l2] = split2(l);
auto [h1, h2] = split2(h);
vector<char> ans(n + 1, '?');
if (ex == -1)
{
if (!l2.empty() && !h2.empty())
{
put(l1, 'A', ans, g);
put(l2, 'B', ans, g);
put(h1, 'B', ans, g);
put(h2, 'C', ans, g);
}
else if (!l2.empty())
{
put(l1, 'A', ans, g);
put(l2, 'B', ans, g);
put(h1, 'C', ans, g);
}
else
{
put(l1, 'A', ans, g);
put(h1, 'B', ans, g);
put(h2, 'C', ans, g);
}
}
else
{
if (!l2.empty() || !h2.empty())
{
int b = -1;
if (!l2.empty() && !h2.empty())
{
put(l1, 'A', ans, g);
put(l2, 'B', ans, g);
put(h1, 'B', ans, g);
put(h2, 'C', ans, g);
b = l2[0];
}
else if (!l2.empty())
{
put(l1, 'A', ans, g);
put(l2, 'B', ans, g);
put(h1, 'C', ans, g);
b = l2[0];
}
else
{
put(l1, 'A', ans, g);
put(h1, 'B', ans, g);
put(h2, 'C', ans, g);
b = h1[0];
}
char ch = ask(ex, b);
for (int v : g[ex])
{
if (ch == '<') ans[v] = 'A';
else if (ch == '=') ans[v] = 'B';
else ans[v] = 'C';
}
}
else
{
int x = l1[0], y = h1[0];
char c1 = ask(ex, x);
if (c1 == '<')
{
put(l1, 'B', ans, g);
put(h1, 'C', ans, g);
for (int v : g[ex]) ans[v] = 'A';
}
else
{
char c2 = ask(ex, y);
if (c2 == '>')
{
put(l1, 'A', ans, g);
put(h1, 'B', ans, g);
for (int v : g[ex]) ans[v] = 'C';
}
else
{
put(l1, 'A', ans, g);
put(h1, 'C', ans, g);
for (int v : g[ex]) ans[v] = 'B';
}
}
}
}
cout << "! ";
for (int i = 1; i <= n; i++)
{
cout << ans[i] << (i == n ? '\n' : ' ');
}
cout.flush();
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int _;
cin >> _;
while (_--) sol();
return 0;
}给定一棵 n 个点的树。对于每个点 r，将树以 r 为根，要求每个节点必须先于它的所有子节点执行，求合法执行序列数量，答案对 998244353 取模。
1 <= n <= 2 * 10^5对于一棵以 r 为根的树，合法执行日志要求每个节点必须在它的所有子节点之前执行。这个问题等价于统计这棵有根树的拓扑序数量。
设以 r 为根时，节点 u 的子树大小为 siz_u。有一个经典结论：
ans_r = n! / Π siz_u原因可以理解为：根节点必须最先执行；之后各个子树内部要保持各自的合法顺序，但不同子树之间可以任意交错。递归展开后，所有组合数会相互抵消，最终得到上面的形式。
先随便选 1 为根，DFS 求出每个点的子树大小 siz[u]。那么：
ans[1] = n! * inv(siz[1]) * inv(siz[2]) * ... * inv(siz[n])其中 siz[1]=n。
接下来考虑换根。假设当前根为 u，现在把根从 u 换到它的儿子 v，并且在以 1 为根的 DFS 树中 v 是 u 的儿子，令 s = siz[v]。
换根前，乘积 Π siz_x 中与这条边相关的两个子树大小为：
u 的子树大小 = n
v 的子树大小 = s换根到 v 后，只有 u 和 v 的子树大小发生变化：
v 的子树大小 = n
u 的子树大小 = n - s其他点的子树大小不变。因此：
ans[v] / ans[u] = (n * s) / (n * (n - s)) = s / (n - s)所以换根转移为：
ans[v] = ans[u] * siz[v] / (n - siz[v])在模 998244353 意义下，用逆元表示除法即可。
O(n log mod)O(n)#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define u64 unsigned long long
#define debug(x) cout<<x<<endl;
#define endl "\n"
const i64 mod = 998244353;
i64 qpow(i64 a, i64 b)
{
i64 res = 1;
while (b)
{
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void sol()
{
int n;
cin >> n;
vector<vector<int>> g(n + 1);
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<i64> fac(n + 1), inv(n + 1), siz(n + 1), ans(n + 1);
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
for (int i = 1; i <= n; i++) inv[i] = qpow(i, mod - 2);
auto dfs1 = [&](auto self, int u, int fa) -> void
{
siz[u] = 1;
for (int v : g[u])
{
if (v == fa) continue;
self(self, v, u);
siz[u] += siz[v];
}
};
dfs1(dfs1, 1, 0);
ans[1] = fac[n];
for (int i = 1; i <= n; i++)
{
ans[1] = ans[1] * inv[siz[i]] % mod;
}
auto dfs2 = [&](auto self, int u, int fa) -> void
{
for (int v : g[u])
{
if (v == fa) continue;
ans[v] = ans[u] * siz[v] % mod * inv[n - siz[v]] % mod;
self(self, v, u);
}
};
dfs2(dfs2, 1, 0);
for (int i = 1; i <= n; i++)
{
cout << ans[i] << (i == n ? '\n' : ' ');
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
sol();
return 0;
}给定 x,y，寻找最小的整数 v，满足 2 <= v <= max(x,y) 且 gcd(v,x)=gcd(v,y)=1。若不存在则输出 -1。
1 <= T <= 10^41 <= x,y <= 2 * 10^5题目要求找到最小的可用编号 v。根据冲突定义，v 与 x 不冲突等价于 gcd(v,x)=1，v 与 y 不冲突等价于 gcd(v,y)=1。
因此可以从小到大枚举 v，范围为 [2,max(x,y)]。对于每个 v，检查：
gcd(v,x)=1 且 gcd(v,y)=1第一个满足条件的 v 就是答案。若枚举完整个区间仍不存在合法编号，则输出 -1。
O(T * max(x,y) * log max(x,y))O(1)//#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define u64 unsigned long long
#define debug(x) cout<<x<<endl;
#define endl "\n"
void sol()
{
int x, y;
cin >> x >> y;
int limit = max(x, y);
int ans = -1;
for (int v = 2; v <= limit; v++)
{
if (__gcd(v, x) == 1 && __gcd(v, y) == 1)
{
ans = v;
break;
}
}
cout << ans << '\n';
}
signed main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int _=1;
cin>>_;
while(_--)sol();
return 0;
}给定带权无向图，每个点有颜色。处在某个点时，可以花费该颜色对应代价跳到任意同色点。求从 1 到 n 的最短路，不可达输出 -1。
1 <= n,m,k <= 2 * 10^5<= 10^9这题很明显是最短路，关键在于如何处理“可以跳到任意同色点”这个操作。
如果直接在所有同色点之间连边，最坏情况下边数会达到 O(n^2)，无法接受。注意到同色跳跃本质上是“从某个点进入这个颜色集合，再从这个颜色集合出来”。因此可以给每种颜色建立一个虚点。
对于颜色 j，建立虚点 n+j。若原图中的点 i 颜色为 c[i]，则连两条边：
i -> n+c[i]，边权为 a[c[i]]
n+c[i] -> i，边权为 0这样从某个颜色为 j 的点 u 出发，先花费 a[j] 走到颜色虚点，再花费 0 走到任意一个同色点 v，就等价于执行一次同色跳跃。
原来的 m 条无向边照常双向连边。建完图后，直接从 1 跑 Dijkstra，答案就是到点 n 的最短距离。
n+k2m+2nO((n+m+k) log(n+k))O(n+m+k)#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define u64 unsigned long long
#define debug(x) cout<<x<<endl;
#define endl "\n"
//很显然的最短路，但是要考虑的是如何建图
//存在集合和集合之间的关系，可以考虑在集合之间多建一条路就行
//然后跑正常的dij即可
const i64 inf = (1LL << 62);
struct node
{
int to;
i64 w;
};
void sol()
{
int n, m, k;
cin >> n >> m >> k;
vector<int> c(n + 1);
for (int i = 1; i <= n; i++) cin >> c[i];
vector<i64> a(k + 1);
for (int i = 1; i <= k; i++) cin >> a[i];
int tot = n + k;
vector<vector<node>> g(tot + 1);
for (int i = 1; i <= m; i++)
{
int u, v;
i64 w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
for (int i = 1; i <= n; i++)
{
int id = n + c[i];
g[i].push_back({id, a[c[i]]});
g[id].push_back({i, 0});
}
vector<i64> dis(tot + 1, inf);
priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> q;
dis[1] = 0;
q.push({0, 1});
while (!q.empty())
{
auto [d, u] = q.top();
q.pop();
if (d != dis[u]) continue;
for (auto [v, w] : g[u])
{
if (dis[v] > d + w)
{
dis[v] = d + w;
q.push({dis[v], v});
}
}
}
if (dis[n] == inf) cout << -1 << endl;
else cout << dis[n] << endl;
return;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _ = 1;
while (_--) sol();
return 0;
}构造一个 3 * n 矩阵，使每一行都是 0 到 n-1 的排列，并且每一列三个数的异或和为 0。若不存在输出 NO。
1 <= T <= 201 <= n <= 10^4本题解由 AI 辅助生成和整理，构造代码来自给定代码，建议赛后结合官方题解复核。
我们可以固定第一行为：
0, 1, 2, ..., n-1若第二行为一个排列 p，那么为了让每一列异或和为 0，第三行必须为：
q_i = i xor p_i因此问题转化为：构造一个排列 p，使得 q_i = i xor p_i 也是 0 到 n-1 的排列。
先看无解条件。三行分别都是 0 到 n-1 的排列，所以每一行的整体异或和都等于：
S = 0 xor 1 xor 2 xor ... xor (n-1)又因为每一列异或和为 0，所以整个矩阵所有数的异或和也应为 0。但三行整体异或起来是：
S xor S xor S = S因此必须有 S=0。而 0 xor 1 xor ... xor (n-1)=0 当且仅当 n=1 或 n 是 4 的倍数。所以只有这两类情况有解。
构造部分比较复杂。代码中的核心是构造一个长度为 n 的排列 p，并输出：
第一行：i
第二行：p_i
第三行：i xor p_i辅助函数 gao2(len) 会构造 len 个二元组 (x_i,y_i)，满足两个关键性质：
x_i,y_i 合起来，每个 0..len-1 中的数恰好出现两次。i xor x_i, i xor y_i 合起来，每个 0..len-1 中的数也恰好出现两次。这两个性质由 gao1 和 gao2 的递归构造保证。gao1 处理长度为二的幂的部分，并保证左右两个坐标各自为排列，同时把异或值分布到固定半区；gao2 每次取不超过 n 的最大二的幂 N，将 [0,N) 与剩余 [N,n) 拼接起来，递归保持“端点出现两次”和“异或值出现两次”的不变量。
当 n 是 4 的倍数时，令 len=n/4。先用 gao2(len) 得到 len 个二元组。由于每个数在端点中出现两次，可以把这些二元组看成一张每个点度数为 2 的图。代码中的 DFS 只是给每条边定向，使得：
pre[i].first 形成 0..len-1 的排列
pre[i].second 也形成 0..len-1 的排列然后每个二元组 (x,y) 扩展成四个位置：
p[4i+0] = 4x+0
p[4i+1] = 4x+2
p[4i+2] = 4y+1
p[4i+3] = 4y+3因为 x 和 y 分别都是排列，所以第二行 p 一定覆盖所有形如 4t+0,4t+1,4t+2,4t+3 的数，即第二行是排列。
再看第三行。对位置 4i+r，有：
(4i+r) xor (4z+s) = 4 * (i xor z) + (r xor s)也就是说，高位由 i xor z 决定，低两位由 r xor s 决定。由 gao2 的第二个不变量，每个高位值会出现两次。代码用 vis 检查第三行是否已经出现过同一个高位的某一组低位；如果已经出现，则把当前相邻两个位置的低两位从 {0,3} 调整为 {1,2}。这样每个高位最终都对应低两位 0,1,2,3 各一次，因此第三行也是排列。
所以当 n=1 或 4|n 时可以构造出合法矩阵，其余情况无解。
O(n log n)O(n)#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> gao1(int N,int k){
if (N<=2){
vector<pair<int,int>> ans;
for (int i=0;i<N;i++) ans.emplace_back(i,i^(N-1));
return ans;
}
int mid=N/2;
vector<pair<int,int>> ans(N);
for (int i=0;i<N;i++) ans[i].second=i^(i/2+mid);
if (k<mid){
vector<pair<int,int>> pre=gao1(mid,k);
for (int i=0;i<mid;i++){
ans[i].first=pre[i].first;
ans[i+mid].first=pre[i].second^mid;
}
}
else{
vector<pair<int,int>> pre=gao1(mid,k-mid);
for (int i=0;i<mid;i++){
ans[i].first=pre[i].second;
ans[i+mid].first=pre[i].first^mid;
}
}
return ans;
}
vector<pair<int,int>> gao2(int n){
if (n<=2){
vector<pair<int,int>> ans;
for (int i=0;i<n;i++) ans.emplace_back(i,i^(n-1));
return ans;
}
int N=1;
for (;(N<<1)<=n;) N<<=1;
int k=n-N;
vector<pair<int,int>> ans(n);
vector<pair<int,int>> pre1=gao1(N,k);
vector<pair<int,int>> pre2=gao2(k);
for (int i=0;i<k;i++) ans[i].first=pre2[i].first^N;
for (int i=k;i<N;i++) ans[i].first=pre1[i].first;
for (int i=0;i<k;i++) ans[i+N].first=pre2[i].second;
for (int i=0;i<N;i++) ans[i].second=pre1[i].second;
for (int i=0;i<k;i++) ans[i+N].second=pre1[i].first^N;
return ans;
}
vector<int> gao3(int n){
if (n==1){
return {0};
}
assert((n>0) && (n%4==0));
int len=n/4;
vector<int> ans(n);
auto pre=gao2(len);
{
vector<vector<int>> pos(len);
for (int i=0;i<len;i++){
pos[pre[i].first].push_back(i);
pos[pre[i].second].push_back(i);
}
vector<int> vis(len);
function<void(int,int)> dfs=[&](int x,int p){
if (vis[x]) return;
vis[x]=1;
if (pre[p].first!=x) swap(pre[p].first,pre[p].second);
int y=pre[p].second;
int nxtp=pos[y][0]+pos[y][1]-p;
if (!vis[y]) dfs(y,nxtp);
};
for (int i=0;i<len;i++) if (!vis[i]) dfs(i,pos[i][0]);
}
{
for (int i=0;i<len;i++){
ans[i*4+0]=pre[i].first*4+0;
ans[i*4+1]=pre[i].first*4+2;
ans[i*4+2]=pre[i].second*4+1;
ans[i*4+3]=pre[i].second*4+3;
}
vector<int> vis(n);
for (int i=0;i<n;i+=2){
if (vis[i^ans[i]]){
ans[i]+=2;
ans[i+1]-=2;
}
vis[i^ans[i]]++;
vis[(i+1)^ans[i+1]]++;
}
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int Tcase=1;
cin >> Tcase;
for (;Tcase--;){
int n;
cin >> n;
if (n==1 || (n>0 && n%4==0)){
cout << "YES" << "\n";
auto ans=gao3(n);
vector<int> v;
for (int i=0;i<n;i++) cout << i << " \n"[i==n-1];
for (int i=0;i<n;i++) {cout << ans[i] << " \n"[i==n-1];v.push_back(ans[i]^i);}
for(int i:v) cout<<i<<" ";
cout<<endl;
}
else{
cout << "NO" << "\n";
}
}
return 0;
}课程持续 T 分钟，若连续 k 分钟没有重点内容就会睡着。给出重点时刻，求最多能坚持到第几分钟，若不睡着则输出 T。
1 <= q <= 10^41 <= n <= 10^51 <= k <= T <= 10^9sum n <= 10^5维护上一次听到重点内容的时刻 now，初始为 0。
依次扫描所有重点时刻 a[i]：
a[i] - now > k，说明从 now 之后开始，连续 k 分钟内都没有新的重点，开拓者会在 now+k 时刻睡着，直接输出。now=a[i]，继续扫描。所有重点时刻扫描完后，如果最后一次重点之后还能坚持到下课，则答案是 T；否则会在 now+k 睡着。因此输出：
min(T, now+k)注意判断条件是 a[i]-now>k，不是 >=k。如果刚好第 k 分钟讲到重点，他不会睡着，会被重新唤醒。
O(n)O(n)#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define u64 unsigned long long
#define debug(x) cout<<x<<endl;
#define endl "\n"
void sol()
{
int n,t,k;cin>>n>>t>>k;
int now=0;
vector<int>a(n+1);
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=1;i<=n;++i)
{
if(a[i]-now>k)
{
cout<<now+k<<endl;
return;
}
now=a[i];
}
cout<<min(t,now+k)<<endl;
return;
}
signed main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int _=1;
cin>>_;
while(_--)sol();
return 0;
}有 16 个固定的 ACMBTI 串。给定长度为 16 的 01 串 X，构造一个大写字符串 Y，使得第 i 个 ACMBTI 串是 Y 的子序列当且仅当 X_i=1。若不存在输出 NO。
T <= 10^4100 的答案本题解由 AI 辅助生成和整理，建议赛后结合官方题解复核。
一共有 16 个目标串，每个串长度都是 4。我们可以把一个字符串 Y 对这 16 个目标串的匹配情况压成一个 16 位二进制数 mask：如果第 i 个 ACMBTI 串是 Y 的子序列，则 mask 的第 i 位为 1。
考虑对任意当前构造出的字符串 Y，维护一个状态 state：
state[i] = 第 i 个目标串目前最多已经匹配到的前缀长度因为目标串长度为 4，所以 state[i] 的取值只可能是 0..4。当我们在 Y 后面追加一个字符 ch 时，对于每个目标串，如果它当前需要匹配的下一个字符正好是 ch，就让 state[i]++。
这样，state[i]=4 就代表第 i 个 ACMBTI 串已经成为当前字符串的子序列。
由于只有 16 个目标串、8 个有效字符 EINSFTJP，可以从空串开始 BFS 枚举所有可达状态。每到达一个状态，就根据 state[i]==4 得到当前字符串对应的 mask，如果这个 mask 还没有答案，就记录当前 BFS 字符串。BFS 结束后，对于每个询问字符串 X，把它转成 16 位 mask，若预处理时有答案就输出，否则输出 NO。
空集合比较特殊：如果 X 全是 0，可以直接输出 "A"，因为 A 不会匹配任何 ACMBTI 串。
O(16)O(可达状态数 + 2^16)#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define u64 unsigned long long
#define debug(x) cout<<x<<endl;
#define endl "\n"
vector<string> pat;
vector<string> ans(1 << 16, "");
u64 encode(const array<int, 16>& a)
{
u64 res = 0;
for (int i = 15; i >= 0; i--)
{
res = res * 5 + a[i];
}
return res;
}
array<int, 16> decode(u64 x)
{
array<int, 16> a{};
for (int i = 0; i < 16; i++)
{
a[i] = x % 5;
x /= 5;
}
return a;
}
int get_mask(const array<int, 16>& a)
{
int mask = 0;
for (int i = 0; i < 16; i++)
{
if (a[i] == 4) mask |= (1 << i);
}
return mask;
}
void init()
{
string s1 = "EI";
string s2 = "NS";
string s3 = "FT";
string s4 = "JP";
for (char a : s1)
{
for (char b : s2)
{
for (char c : s3)
{
for (char d : s4)
{
string s;
s += a;
s += b;
s += c;
s += d;
pat.push_back(s);
}
}
}
}
ans[0] = "A";
string alpha = "EINSFTJP";
queue<u64> q;
unordered_map<u64, string> mp;
array<int, 16> st{};
u64 start = encode(st);
q.push(start);
mp[start] = "";
while (!q.empty())
{
u64 cur = q.front();
q.pop();
array<int, 16> a = decode(cur);
string now = mp[cur];
int mask = get_mask(a);
if (ans[mask].empty())
{
ans[mask] = now;
}
for (char ch : alpha)
{
array<int, 16> b = a;
for (int i = 0; i < 16; i++)
{
if (b[i] < 4 && pat[i][b[i]] == ch)
{
b[i]++;
}
}
u64 nxt = encode(b);
if (!mp.count(nxt))
{
mp[nxt] = now + ch;
q.push(nxt);
}
}
}
}
void sol()
{
string x;
cin >> x;
int mask = 0;
for (int i = 0; i < 16; i++)
{
if (x[i] == '1') mask |= (1 << i);
}
if (ans[mask].empty())
{
cout << "NO" << endl;
}
else
{
cout << "YES" << endl;
cout << ans[mask].size() << endl;
cout << ans[mask] << endl;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
init();
int _=1;
cin>>_;
while(_--)sol();
return 0;
}对一个排列的每个连续子区间视作一个公平组合博弈状态。每次可以选择任意个正数元素同时减一，无法操作者输。定义先手必胜区间为有效区间，求使有效区间数量达到最大值的排列个数，答案对 1e9+7 取模。
1 <= t <= 10^41 <= n <= 3 * 10^5先分析区间对应的博弈。
一个状态由若干个正整数构成。每次可以选择任意个仍然大于 0 的数，并让它们同时减 1。结论是：
当前状态为必败态，当且仅当所有数都是偶数。证明思路很简单：
1，这样所有奇数都变成偶数，原本的偶数不动，局面变成全偶数。因此先手必胜当且仅当区间中至少存在一个奇数。
于是对于一个排列 p，有效区间数量就是：
总区间数 - 全偶数区间数总区间数固定，所以要让有效区间数量最大，就要让全偶数区间数量最少。
设排列中偶数个数为：
even = n / 2奇数个数为：
odd = n - even每个偶数单独作为长度为 1 的区间时，一定是全偶数区间，所以全偶数区间至少有 even 个。若两个偶数相邻，就会额外产生长度大于 1 的全偶数区间。因此最优条件就是：任意两个偶数不能相邻。
先摆放所有奇数，它们会形成 odd+1 个空隙：
_ odd _ odd _ ... odd _为了让偶数不相邻，需要从这 odd+1 个空隙中选择 even 个放偶数，方案数为：
C(odd+1, even)选好奇偶位置后，奇数之间可以任意排列，偶数之间也可以任意排列，所以答案为：
C(odd+1, even) * odd! * even!对 1e9+7 取模即可。
O(N)O(1)O(N)#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define u64 unsigned long long
#define debug(x) cout<<x<<endl;
#define endl "\n"
const int mod = 1000000007;
const int N = 300000 + 5;
i64 fac[N], ifac[N];
i64 qpow(i64 a, i64 b)
{
i64 res = 1;
while (b)
{
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
i64 C(int n, int m)
{
if (m < 0 || m > n) return 0;
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
void init()
{
fac[0] = 1;
for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod;
ifac[N - 1] = qpow(fac[N - 1], mod - 2);
for (int i = N - 2; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
void sol()
{
int n;
cin >> n;
int even = n / 2;
int odd = n - even;
i64 ans = C(odd + 1, even);
ans = ans * fac[odd] % mod;
ans = ans * fac[even] % mod;
cout << ans << endl;
}
signed main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
init();
int _ = 1;
cin >> _;
while (_--) sol();
return 0;
}签到题，略。
1 <= a,b <= 10^9签到题，略。
给定 n*m 网格海拔和按水位非降序给出的询问。第 k 个询问判断两个格子在海拔严格大于水位的可通行格子中是否连通。
n*m <= 2 * 10^5q <= 2 * 10^5<= 10^9w_1 <= w_2 <= ... <= w_q要判断网格连通，容易想到 DFS/BFS 或并查集。由于有很多询问，如果每次询问都重新扫一遍网格，复杂度会达到 O(qnm)，无法接受。
注意到一个格子在水位为 w 时可通行，当且仅当：
h > w也就是说，水位越低，可通行的格子越多；水位越高，可通行的格子越少。这个过程具有单调性。我们可以把询问按水位 w 从大到小排序，同时把所有格子也按海拔 h 从大到小排序。
处理某个询问 w 时，将所有满足 h>w 且还没有加入过的格子加入并查集。每加入一个格子，就和上下左右已经加入的邻居合并。这样当前并查集恰好表示水位为 w 时所有可通行格子的连通关系。
最后对于询问中的两个位置：
NO。由于每个格子最多加入一次，每条邻接关系最多检查常数次，所以整体复杂度可以接受。
O(nm log(nm) + q log q)O(nm α(nm))O(nm + q)#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define u64 unsigned long long
#define debug(x) cout<<x<<endl;
#define endl "\n"
//要判联通，首先可能是dsu/dfs之类的
//但是还存在一个动态的过程，其实也不算动态
//如果是dsu，我们要知道在k天的时候有哪几个点是可以走的
//如果每次这样硬扫一遍就是qnm肯定不行，那我们要优化下找路的这个过程
//可以咋优化呢
//对于这个水流的增长，很显然是有单调性的，那我们直接从最后到前面去加点就行了
//然后这样就是nm+q,应该没啥问题
//剩下就是代码实现了，注意下w的排序和dsu实现
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
struct DSU
{
vector<int> f, sz;
void init(int n)
{
f.resize(n + 1);
sz.assign(n + 1, 1);
iota(f.begin(), f.end(), 0);
}
int find(int x)
{
if (f[x] == x) return x;
return f[x] = find(f[x]);
}
void merge(int x, int y)
{
x = find(x), y = find(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
f[y] = x;
sz[x] += sz[y];
}
};
struct node
{
int h, id;
bool operator < (const node &a) const
{
return h > a.h;
}
};
struct node1
{
int w, a, b, c, d, id;
bool operator < (const node1 &a) const
{
return w > a.w;
}
};
void sol()
{
int n,m,q;cin>>n>>m>>q;
vector<int>h(n*m+1);
vector<node>p;
p.reserve(n * m);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
int x;cin>>x;
int now=(i-1)*m+j;
h[now]=x;
p.push_back({x,now});
}
}
vector<node1>tmp(q);
for(int i=0;i<q;++i)
{
cin>>tmp[i].w>>tmp[i].a>>tmp[i].b>>tmp[i].c>>tmp[i].d;
tmp[i].id=i;
}
sort(p.begin(),p.end());
sort(tmp.begin(),tmp.end());
DSU check;
check.init(n*m);
vector<int>vis(n*m+1,0);
vector<string>ans(q);
int j=0;
for(auto &qq:tmp)
{
while(j<n*m&&p[j].h>qq.w)
{
int id=p[j].id;
vis[id]=1;
int x = (id - 1) / m + 1;
int y = (id - 1) % m + 1;
for (int k = 0; k < 4; k++)
{
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
int nid =(nx-1)*m+ny;
if (vis[nid]) check.merge(id, nid);
}
j++;
}
int u=(qq.a-1)*m+qq.b;
int v=(qq.c-1)*m+qq.d;
if (vis[u] && vis[v] && check.find(u) == check.find(v)) ans[qq.id] = "YES";
else ans[qq.id] = "NO";
}
for (int i = 0; i < q; i++) cout << ans[i] << endl;
return;
}
signed main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int _=1;
//cin>>_;
while(_--)sol();
return 0;
}有 n 张毒雾和 m 张触媒。每回合先按当前毒雾层数叠毒，再打一张未出的牌，最后触发 c+1 次中毒伤害。求通过安排出牌顺序能造成的最大总伤害。
1 <= T <= 501 <= n,m <= 50这题很难直接贪心，因为打出毒雾会增加之后每回合叠毒量，打出触媒会增加之后每回合结算次数，两者互相影响。
由于 n,m <= 50，可以直接做动态规划。
设：
dp[i][j][p]表示已经打出了 i 张毒雾、j 张触媒，且当前回合开始前敌人有 p 层中毒时，最多已经造成的伤害。
对于当前状态，回合开始时会先叠加 i 层毒，所以当前可结算的中毒层数为：
q = p + i接下来有两种选择。
如果打出一张毒雾，那么毒雾层数变成 i+1，触媒层数仍为 j。回合结束时一共触发 j+1 次中毒，所以实际触发次数为：
t = min(q, j+1)造成的伤害为：
q + (q-1) + ... + (q-t+1)
= t * (2q - t + 1) / 2剩余中毒层数为：
np = q - t于是转移：
dp[i+1][j][np] = max(dp[i+1][j][np], dp[i][j][p] + damage)如果打出一张触媒，那么触媒层数会先增加到 j+1，回合结束时总共触发 (j+1)+1 = j+2 次中毒，所以：
t = min(q, j+2)类似地转移到：
dp[i][j+1][np]当前中毒层数的上界可以粗略取：
n*m + n*(n-1)/2表示毒雾叠毒可能产生的最大累计中毒量。最后在所有 dp[n][m][p] 中取最大值即可。
O(n*m*lim)O(1)lim = n*m + n*(n-1)/2O(n*m*lim)#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define i64 long long
#define u64 unsigned long long
#define debug(x) cout << x << endl;
#define endl "\n"
// 很显然的dp，无论是哪一个的变化都无法直接贪心
// dp[i][j][p]
// 本轮攻击设为t，那tot=t(2q-t+1)/2 t=min(c+1,q)
// 如果i>1 t=min(q,j+1) nq=q-t tot=.. dp[i+1][j][np]=max(dp[i+1][j][np],dp[i][j][p]+tot)
// 如果j>1 t=min(q,j+2) dp[i][j+1][np] = max(dp[i][j+1][np], dp[i][j][p] + s);
//然后p的上界是n*m+(n-1)*n/2
void sol()
{
int n, m;
cin >> n >> m;
int lim = n * m + n * (n - 1) / 2;
const i64 inf = -(1LL << 60);
vector<vector<vector<i64>>> dp(n + 1, vector<vector<i64>>(m + 1, vector<i64>(lim + 1, inf)));
dp[0][0][0] = 0;
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
for (int p = 0; p <= lim; p++)
{
if (dp[i][j][p] == inf)
continue;
int q = p + i;
if (i < n)
{
int t = min(q, j + 1);
int np = q - t;
i64 s = 1LL * t * (2LL * q - t + 1) / 2;
dp[i + 1][j][np] = max(dp[i + 1][j][np], dp[i][j][p] + s);
}
if (j < m)
{
int t = min(q, j + 2);
int np = q - t;
i64 s = 1ll * t * (2ll * q - t + 1) / 2;
dp[i][j + 1][np] = max(dp[i][j + 1][np], dp[i][j][p] + s);
}
}
}
}
i64 ans = 0;
for (int p = 0; p <= lim; p++)
ans = max(ans, dp[n][m][p]);
cout << ans << endl;
return;
}
signed main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _ = 1;
cin >> _;
while (_--)
sol();
return 0;
}给定非负数组 a 和目标 S，可以任意重排数组。若重排后每个位置 R 都存在某个 L <= R，使得区间 [L,R] 的和为 S，则输出 YES，否则输出 NO。
1 <= T <= 10^51 <= n <= 10^50 <= S,a_i <= 10^9sum n <= 3 * 10^5由于数组元素都是非负数，区间和具有很强的限制。
若 S=0，那么一个区间和为 0 当且仅当区间内所有数都是 0。要让每个位置 R 都能作为某个和为 0 的区间右端点，所有元素都必须是 0。因此 S=0 时，判断是否所有元素都是 0 即可。
下面考虑 S>0。
如果存在一个元素 a_i 满足：
a_i != 0 且 a_i != S因为所有数非负，无论把它放在哪里，它所在位置作为右端点时，想凑出和为 S 的区间都会遇到问题：单独取它不等于 S，继续向左扩展只会让区间和变大或不变，无法保证正好得到 S。因此这样的元素不能存在。
也就是说，所有元素只能是 0 或 S。
如果至少存在一个 S，就可以把数组重排成：
S, 0, 0, ..., 0, S, 0, ...事实上只要所有元素都是 0 或 S，并且至少有一个 S，每个位置 R 都可以选择离它最近的、且不超过它的那个 S 作为左端点，中间只有若干个 0，区间和就是 S。
所以 S>0 时的充要条件是：
0 或 S。S。O(n)O(n)#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define u64 unsigned long long
#define debug(x) cout<<x<<endl;
#define endl "\n"
void sol()
{
int n;
i64 S;
cin >> n >> S;
vector<i64> a(n);
bool ok = true;
int cntS = 0, cnt0 = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
if (a[i] == S) cntS++;
if (a[i] == 0) cnt0++;
}
if (S == 0)
{
cout << (cnt0 == n ? "YES" : "NO") << endl;
return;
}
for (int i = 0; i < n; i++)
{
if (a[i] != 0 && a[i] != S)
{
ok = false;
break;
}
}
if (cntS == 0) ok = false;
cout << (ok ? "YES" : "NO") << endl;
return;
}
signed main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int _=1;
cin>>_;
while(_--)sol();
return 0;
}需要构造字典序最大的初始排列，使其经过恰好 M 次“选择一个非末尾元素并移到末尾”的操作后变为 1,2,...,N。
1 <= T <= 10^51 <= N <= 10^50 <= M <= 10^9N=1，保证 M=0sum N <= 10^5这题可以直接构造。
操作是选择一个不是最后一个位置的元素，把它移动到最后。为了让初始排列字典序尽量大，我们希望越大的数越靠前。
分情况讨论：
如果 n=1，没有操作空间，答案只能是 1。
如果 n=2，排列只有两种：
m 为偶数时，输出 1 2。m 为奇数时，输出 2 1。因为一次操作会让两个数交换位置，所以只需要看奇偶性。
下面考虑 n>=3。
如果 m < n-1，为了让字典序最大，可以把最大的 m 个数依次放在最前面：
n, n-1, ..., n-m+1剩下的数保持升序：
1, 2, ..., n-m这样前 m 个位置已经尽可能大，并且可以通过恰好 m 次操作把这些被提前的数依次移到末尾，最终恢复成升序。
如果 m >= n-1，字典序最大的排列显然是完全倒序：
n, n-1, ..., 1对于 n>=3，倒序排列可以在至少 n-1 次操作后变回升序，多余的操作可以通过循环移动元素来消耗，因此所有 m>=n-1 都可以取倒序作为答案。
O(n)O(n)#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define u64 unsigned long long
#define debug(x) cout<<x<<endl;
#define endl "\n"
void sol()
{
int n;
i64 m;
cin >> n >> m;
vector<int> ans;
if (n == 1)
{
ans.push_back(1);
}
else if (n == 2)
{
if (m % 2 == 0)
{
ans.push_back(1);
ans.push_back(2);
}
else
{
ans.push_back(2);
ans.push_back(1);
}
}
else
{
if (m < n - 1)
{
for (int x = n; x >= n - m + 1; x--)
{
ans.push_back(x);
}
for (int x = 1; x <= n - m; x++)
{
ans.push_back(x);
}
}
else
{
for (int x = n; x >= 1; x--)
{
ans.push_back(x);
}
}
}
for (int i = 0; i < n; i++)
{
if (i) cout << ' ';
cout << ans[i];
}
cout << endl;
}
signed main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
while (_--) sol();
return 0;
}标准六面骰子初始上、前、右分别为 1,2,3。给定 L/R/F/B 操作串，模拟骰子滚动，输出最终上面的点数。
1 <= n <= 2 * 10^5直接维护骰子的六个面：
top, bottom, front, back, left, right初始时：
top = 1
front = 2
right = 3
bottom = 6
back = 5
left = 4每次根据操作更新六个面的相对位置：
L：向左滚，右面变成上面。R：向右滚，左面变成上面。F：向前滚，后面变成上面。B：向后滚，前面变成上面。所有操作结束后输出 top 即可。
O(n)O(1)#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define u64 unsigned long long
#define debug(x) cout<<x<<endl;
#define endl "\n"
void sol()
{
int n;
string s;
cin >> n >> s;
int top = 1, bottom = 6;
int front = 2, back = 5;
int left = 4, right = 3;
for (char ch : s)
{
if (ch == 'L')
{
int ntop = right;
int nright = bottom;
int nbottom = left;
int nleft = top;
top = ntop;
right = nright;
bottom = nbottom;
left = nleft;
}
else if (ch == 'R')
{
int ntop = left;
int nleft = bottom;
int nbottom = right;
int nright = top;
top = ntop;
left = nleft;
bottom = nbottom;
right = nright;
}
else if (ch == 'F')
{
int ntop = back;
int nback = bottom;
int nbottom = front;
int nfront = top;
top = ntop;
back = nback;
bottom = nbottom;
front = nfront;
}
else
{
int ntop = front;
int nfront = bottom;
int nbottom = back;
int nback = top;
top = ntop;
front = nfront;
bottom = nbottom;
back = nback;
}
}
cout << top << endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int _ = 1;
while (_--) sol();
return 0;
}