来源：https://mp.weixin.qq.com/s/jqp4YIQLaaFu0c2M915Hkw
米小游有一个长度为 n 的数组，其中第 i 个元素为
现在米小游想要任选数组中的某两个相邻的元素进行交换（你必须使用这次交换机会），他想知道最大可以将数组的价值更改为多少？
输入描述
第一行输入一个整数
输出描述
在一行上输出一个整数表示答案。
输入样例
4
1 2 10 8
输出样例
80
说明
如果交换 2 和 10，则数组的价值会减少。但是由于必须使用交换机会，所以可以交换 1 和 2，这样数组的价值仍为 80。
思路与代码
模拟题，直接按照题目要求模拟即可。
- 计算出在不交换情况的最大值是多少，虽然题目说了无论如何一定得交换，但是原本序列的最大值也一定就可以存在，例如[a,b,c]原本是[a,b]相乘是最大的，那么我们完全可以选择交换a,b，那么结论一样成立。
- 枚举所有可能的交换位置，计算出所有可能的结果，更新即可。其中，假设交换A[i]和A[i+1]，那么此时产生的新的答案就有可能是
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
int main() {
int n;
cin >> n;
vector<LL> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
LL ans = nums[0] * nums[1];
for (int i = 1; i < n - 1; i++) {
swap(nums[i], nums[i + 1]);
ans = max(ans, nums[i - 1] * nums[i]);
ans = max(ans, nums[i] * nums[i + 1]);
swap(nums[i], nums[i + 1]);
}
cout << ans;
return 0;
}商店里有 n 个商品，分别编号为 1～n，每个商品的价值为
米小游认为有些东西一起购买会带来灾难，比如可莉的角色立牌和蹦蹦炸弹的小手办，所以他设定了 k 组互斥关系，每组关系给定两个数字 a、b，表示编号为 a 的商品和编号为 b 的商品不能同时购买。
米小游希望装下的物品的价值之和最大，请你帮帮他求出最大价值。
输入描述
第一行输入三个整数 n，m，k(
接下来 n 行，每行输入两个整数
接下来 k行，每行输入两个整数
输出描述
在一行上输出一个整数表示答案。
输入样例
3 100 2
15 19
20 30
15 19
1 2
2 3
输出样例
38
说明
根据两组互斥关系，买了 2 就不能买 1 和 3，所以我们可以购买物品 1 和物品 3，这样达到最大价值。
思路与代码
暴力枚举+哈希表。
首先观察题目中的 n 只有15，因此可以直接使用回溯来解（也可以使用二进制来枚举）。回溯的思路如下：
- 每个物品有2种选择：选或者不选。无论什么情况下都可以不选择。关键是何时可以选择呢？
- 必须保证当前的背包容量是足够的，并且已经选择的物品并不会与当前物品出现互斥关系，这个可以使用哈希来进行快速判断。
- 不断更新所有可能的答案即可。
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
int n, m, k;
vector<int> w, v;
vector<vector<bool>> table;
unordered_set<int> visited;
int ans = 0;
void dfs(int current, int sum_v, int sum_w) {
if (current > n) {
ans = max(ans, sum_v);
return ;
}
bool canTake = true;
for (const auto &item : visited) {
if (table[item][current]) {
canTake = false;
break;
}
}
if (canTake && sum_w + w[current] <= m) {
visited.insert(current);
dfs(current + 1, sum_v + v[current], sum_w + w[current]);
visited.erase(current);
}
dfs(current + 1, sum_v, sum_w);
}
int main() {
cin >> n >> m >> k;
w.resize(n + 1);
v.resize(n + 1);
table.resize(n + 1, vector<bool>(n + 1));
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i];
}
for (int i = 1; i <= k; i++) {
int a, b;
cin >> a >> b;
table[a][b] = true;
}
dfs(1, 0, 0);
cout << ans;
return 0;
}米小游和派蒙在进行一场游戏。游戏在一个基环树（点数与边数相等的无向简单连通图）上进行，定义图中一个点的度数为与其相连的边数，二人轮流进行以下操作：
- 选择图中一个度数为 1 的点，删除这个点以及与这个点相连的边。
图中有一个特殊的点 x ，删除了点 x 的玩家即获得胜利。
现在，由米小游先进行操作。在双方都采取最优策略的情况下，胜者是谁？
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数
第一行输入两个整数
此后 n 行，第 i 行输入两个整数
除此之外，保证给定的边构成一个基环树，所有的 n 之和不超过
输出描述
对于每一组测试数据，在一行上输出胜者的名字（Xiaoyo 或 Pyrmont ）。特别地，若点 x 不可能被删除，请输出 Draw 。
输入样例
3
4 2
1 2
1 3
1 4
3 4
5 2
1 2
1 3
1 4
3 4
2 5
3 1
1 2
1 3
2 3
输出样例
Xiaoyo
Pyrmont
Draw
思路与代码
拓扑排序+GTO博弈论。
所谓的基环树指的是：在一棵树的基础上加上一个环。
以后大家看到这种：每个人都会按照最优策略进行选择，最后判断谁会获胜。这种字眼的时候，基本就可以确定是一个GTO（博弈论）的题目。基本的做题思路就是找到一个规律可以直接得出结论的。
对于这道题，有一个显而易见的结论，如果 x 在环中，那么无论如何删点都不可能删的掉，因此必然是Draw。
如果点不在环中呢？
我们可以考虑在删除x点之前（包括x），有多少个节点是可以删除的？假设这个值是 cnt。
如果 cnt 是偶数的话，那么 Xiaoyo 作为先选取的一方，一定是无法删除这个点的。因为双方的操作是对称的。
反之，则是Pyrmont获胜。
因此大题思路与拓扑排序类似，不断地将度数为1的节点加入队列，记录在删除x节点之前最多可以访问的节点数（包括x节点）。最后判断x的奇偶性即可。
需要注意的是
- 如果x节点是在环中的，那么我们永远无法遍历到这个节点，此时必然是Draw。
- 如果x节点的度数初始值就是1，那么此时Xiaoyo获胜。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void solve() {
int n, x;
cin >> n >> x;
vector<vector<int>> graph(n + 1);
vector<int> indegree(n + 1, 0);
for (int i = 0; i < n; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
indegree[u]++;
indegree[v]++;
}
queue<int> q;
for (int i = 1; i <= n; i++) {
if (indegree[i] == 1) {
if (i == x) {
cout << "Xiaoyo" << endl;
return ;
}
q.push(i);
}
}
int cnt = 0;
bool find_x = false;
while (q.size()) {
int node = q.front();
q.pop();
cnt++;
if (node == x) {
// 不能删除 x
find_x = true;
continue;
}
for (const auto &next : graph[node]) {
indegree[next]--;
if (indegree[next] == 1) {
q.push(next);
}
}
}
if (!find_x) {
cout << "Draw" << endl;
} else if (cnt % 2) {
cout << "Xiaoyo" << endl;
} else {
cout << "Pyrmont" << endl;
}
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
}