Educational Codeforces Round 129 (Rated for Div. 2)

A. Game with Cards.

题目链接

题目大意：

Alice和Bob玩卡牌。Alice有n张，Bob有m张。第一轮选手出一张数字卡牌。第二轮另一个选手要选择一张比他大的，依此类推。谁没有牌可出则输。问Alice和Bob分别先手时，谁赢？输出两行，代表赢的人。

思路：

博弈：

如果Alice拥有的牌上面的数字的最大值 大于Bob拥有的牌上面的数字的最大值,无论谁先手都是Alice赢，因为Alice打出最大的那一张牌时Bob接不下去，若Bob只有一张牌，且Bob先手，那么他打出这一张牌之后Alice可以拿最大的牌压住，同样的，如果Alice拥有的牌上面的数字的最大值 小于Bob拥有的牌上面的数字的最大值,那么总是Bob赢，若最大值相同，谁先手谁赢.

参考代码：

void solve() {int n, m;std::cin >> n;std::vector<int> a(n);for (int i = 0; i < n; i++)std::cin >> a[i];std::cin >> m;std::vector<int> b(m);for (int i = 0; i < m; i++)std::cin >> b[i];int maxa = *max_element(a.begin(), a.end());int maxb = *max_element(b.begin(), b.end());if (maxa > maxb)std::cout << "Alice\nAlice\n";else if (maxa < maxb)std::cout << "Bob\nBob\n";elsestd::cout << "Alice\nBob\n";
}

B. Card Trick

题目链接

题目大意：

有一个队列a，以及m次操作第i次操作将a中前b[i]个数从队列中取出，放到队尾。问m次操作后队头数字是多少？

思路：

计算游标在环上到哪个位置即可。答案a[bsum % n] .每调换n张牌相当于没变化.

参考代码：

void solve() {int n, m;std::cin >> n;std::vector<int> a(n);for (int i = 0; i < n; i++)std::cin >> a[i];std::cin >> m;std::vector<int> b(m);for (int i = 0; i < m; i++)std::cin >> b[i];int pos = accumulate(b.begin(), b.end(), 0ll) % n;std::cout << a[pos] << '\n';
}

C. Double Sort

题目链接

题意：

题意：给定两个数组 a,b ，问能否进行以下操作，使得两个数组均有序(不降)。

• 选择位置 i,j，交换 ai,aj ；交换 bi,bj。

数组长度是 100 ，交换次数不能超过 10000 。如果可以，输出一种方案。

分析：先进行交换使得 a 有序。交换次数不会超过 10000 。如果这个限制缩小的话，可以使用选择排序。

然后再对 a 进行排序，这里需要注意：不能破坏 a 的有序性，即若希望交换 bi,bj ，必须有 ai=aj 。

参考代码：

void solve() {int n;std::cin >> n;std::vector<int> a(n + 1), b(n + 1);for (int i = 1; i <= n; i++)std::cin >> a[i];for (int i = 1; i <= n; i++)std::cin >> b[i];std::vector<std::array<int, 2>> v;// v数组存每次交换的下标for (int i = 1; i <= n; i++) { // 先排a数组for (int j = i + 1; j <= n; j++) {if (a[i] > a[j]) {std::swap(a[i], a[j]);std::swap(b[i], b[j]);v.push_back({i, j});}}}for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= n; j++) {if (b[i] > b[j]) {if (a[i] == a[j]) {std::swap(a[i], a[j]);std::swap(b[i], b[j]);v.push_back({i, j});}else {std::cout << "-1\n";// 无法在不影响a的有序性的情况下使得b数组有序return;}}}}std::cout << v.size() << '\n';for (auto [x, y] : v) {std::cout << y << " " << x << '\n';}
}

思路二：

按pair顺序排一下序，记录位置，检查b是否有序，如果无序，则无解。有序则按位置安排一下。比较简单的办法是用插入排序或者冒泡，比较好写。

也可以不用，直接用sort记录位置，可以应对n = 10^6的情形。

 

参考代码：

void solve() {int n;std::cin >> n;std::vector<int> a(n), b(n), id(n), pos(n), originalPos(n);for (int i = 0; i < n; i++)std::cin >> a[i];for (int i = 0; i < n; i++)std::cin >> b[i];std::iota(id.begin(), id.end(), 0);std::iota(pos.begin(), pos.end(), 0);std::iota(originalPos.begin(), originalPos.end(), 0);// copy(id.begin(), id.end(), pos.begin());std::sort(id.begin(), id.end(), [&](const int i, const int j){if (a[i] < a[j]) return true;if (a[i] == a[j] && b[i] < b[j]) return true;return false; });for (int i = 1; i < n; i++) {if (b[id[i]] < b[id[i - 1]]) {std::cout << "-1\n";return;}}// id: 排在第i的，原先在哪个位置// pos: 原来位置i，现在在哪// originalPos = pos的逆，当前第i个位置，原先是哪个位置std::vector<std::array<int, 2>> ans;for (int i = 0; i < n; i++){int j = pos[id[i]];if (i == j)continue;ans.push_back({i + 1, j + 1});std::swap(pos[originalPos[i]], pos[originalPos[j]]);std::swap(originalPos[i], originalPos[j]);}std::cout << ans.size() << "\n";for (std::array<int, 2> &a : ans) {std::cout << a[0] << " " << a[1] << "\n";}
}