临颖网站建设,桂林象鼻山作文400字,传媒公司怎么注册,大连金豆网站建设A. Game with Cards.
题目链接
题目大意#xff1a; Alice和Bob玩卡牌。Alice有n张#xff0c;Bob有m张。第一轮选手出一张数字卡牌。第二轮另一个选手要选择一张比他大的#xff0c;依此类推。谁没有牌可出则输。问Alice和Bob分别先手时#xff0c;谁赢#xff1f;输出…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::vectorint a(n);for (int i 0; i n; i)std::cin a[i];std::cin m;std::vectorint 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::vectorint a(n);for (int i 0; i n; i)std::cin a[i];std::cin m;std::vectorint 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 必须有 aiaj 。 参考代码
void solve() {int n;std::cin n;std::vectorint 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::vectorstd::arrayint, 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::vectorint 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::vectorstd::arrayint, 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::arrayint, 2 a : ans) {std::cout a[0] a[1] \n;}
}
