网站构建工具,wordpress 主题授权,惠州专业做网站,安徽建设项目建设工程在线A.jagged Swaps
题意#xff1a;
给出一个包含 n n n个数字的序列#xff0c;每次可以选择一个同时大于左右两边相邻的数字#xff0c;将这个数字与它右边的数字交换#xff0c;问能否在经过若干次操作后使序列变为升序。
分析#xff1a;
由于交换只能向后进行#…A.jagged Swaps
题意
给出一个包含 n n n个数字的序列每次可以选择一个同时大于左右两边相邻的数字将这个数字与它右边的数字交换问能否在经过若干次操作后使序列变为升序。
分析
由于交换只能向后进行且第一个元素无法向后交换不存在左边的数字而其他大的数字均可以通过交换到达自己的位置因此只需要考虑开始时序列的第一个数字是否为1如果是1就是YES否则就是NO。
hint包含 n n n个数字的序列恰好包含 1 ∼ n 1 \sim n 1∼n中每一个数字。
代码
#include bits/stdc.h
using namespace std;int a[15];void solve() {int n;cin n;for (int i 1; i n; i) {cin a[i];}if (a[1] ! 1) {cout NO endl;} else {cout YES endl;}
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}
B.AB Flipping
题意
给出一个长度为 n n n且仅包含AB两种字符的字符串每次可以选择一个下标 i i i,当字符串中第 i i i个字符为A且第 i 1 i 1 i1个字符为B那么可以让第 i i i个字符和第 i 1 i 1 i1个字符交换。
要求每个下标 i i i均只能选择一次问最多可以进行多少次交换。
分析
当出现连续的B前面有一个A时这段连续区间上的B均可以向前交换一次交换次数为这段连续的B的长度而经过一次交换之后由于每个下标只能被选择一次那么仅有第一个B还能向前交换可以认为这段连续的B交换完成后就只剩下开头这一个B了。使用变量维护还能向前交换的B的个数从后往前遍历模拟即可。
代码
#include bits/stdc.h
using namespace std;string s;void solve() {int n;cin n s;int cnt 0, ans 0;for (int i n - 1; i 0; i--) {if (s[i] B) {cnt;} else {ans cnt;cnt min(cnt, 1);//如果当前没有遇到过B就让cnt保持在0}}cout ans endl;
}int main() {solve();return 0;
}C.Matching Arrays
题意
给出两个包含 n n n个数字的数组 a a a和 b b b这两个数组的美丽值为满足 a i b i a_i b_i aibi的下标 i i i的个数。
题目会给出一个数字 x x x问能否对 b b b重新排列使得这两个数组的美丽值等于 x x x。
分析
虽然题目要求只能对 b b b重排但为了便于处理两个数组都需要排序同时为了记录数组 a a a原本的数字位置需使用结构体存储数据。
贪心将 a a a中最大的 x x x个元素与 b b b中最小的 x x x个元素按大小次序进行比较如果这部分元素无法构成 x x x的美丽值由于 a a a中剩余元素更小 b b b中剩余元素更大那么无论怎么交换元素都无法使美丽值增加此时本题无解。
检查比较完 a a a中最大的 x x x个元素与 b b b中最小的 x x x个元素后还需要考虑剩余的元素是否还会产生美丽值同样采用按大小次序依次比较如果产生美丽值那么同样表示本题无解。
输出如果可以构造那么需要根据记录的 a a a中每个数字排序前的位置将对应的 b b b数组元素输出。
代码
#include bits/stdc.h
using namespace std;struct Node{int val, id;bool operator (const Node o) const {return val o.val;}
}a[200005], b[200005];int ans[200005];void solve() {int n, x;cin n x;for (int i 1; i n; i) {cin a[i].val;a[i].id i;}sort(a 1, a 1 n);for (int i 1; i n; i) {cin b[i].val;b[i].id i;}sort(b 1, b 1 n);for (int i 1; i x; i) {if (a[i n - x].val b[i].val) {//a中最大的x个与b中最小的x个对位比较cout NO endl;return;}ans[a[i n - x].id] b[i].val;//将当前b中元素放入对应的a中元素原本所在下标对应的位置上}for (int i 1; i n - x; i) {if (a[i].val b[i x].val) {//剩余的n-x个元素对位比较cout NO endl;return;}ans[a[i].id] b[i x].val;}cout YES endl;for (int i 1; i n; i) {cout ans[i] ;}cout endl;
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}D.Ones and Twos
题意
给出一个仅包含 1 , 2 1,2 1,2的数组。
有 q q q个询问询问分以下两种情况 1 s询问数组中能否找出一个子段和为 s s s 2 i v将数组中第 i i i个数字修改为 v v v
分析
通过分析样例可以发现以下规律如果子段的左右端点数字均为1那么可以组成任意值在 1 ∼ 1 \sim 1∼子段数字之和以内的数字。
根据以上规律想要组成尽可能多的数字那么选择的一定是最左和最右的两个 1 1 1中间的子段包含端点。
然后需要根据以下情况进行分类讨论 数组中存在 1 1 1这两个 1 1 1之间的子段总和为 s u m sum sum x ≤ s u m x \le sum x≤sum,则可以组成 x s u m x \gt sum xsum分成以下两种情况 x x x与 s u m sum sum奇偶性相同为了尽可能使总和最大一定会选择将选择的子段向左右扩散且此时左右元素一定均为2只要整个数组的数字总和可以达到 x x x那么就能组成 x x x。 奇偶性不同时可以删去子段一侧的 1 1 1再加上另一侧的 2 2 2看组成的子段数字总和能否到达 x x x。 数组中不存在 1 1 1那么能组成的只有偶数且能组成的偶数 x x x的值要在数组中数字总和的范围内。
hint可以通过 s e t set set对所有 1 1 1所在的位置下标进行维护通过 ∗ ( b e g i n ( ) ) *(begin()) ∗(begin())和 ∗ ( − − e n d ( ) ) *(--end()) ∗(−−end())end()函数返回的是最后一个元素的下一个迭代器需要通过前自减得到最后一个元素的迭代器来获得集合中最小和最大的元素。
代码
#include bits/stdc.husing namespace std;
int n, q, a[100005], cnt;setint S;bool check(int x) {if (S.empty()) {//数组中没有1if (x % 2 1) return false;if (n * 2 x) return false;return true;}int first *S.begin(), last *(--S.end());//获得最前和最后的1所在的下标int sum (last - first 1) * 2 - S.size();//将区间内所有的数视为2计算出总和减去1的数量就是该子段的数字总和if (sum x) return true;//被1包围的子段已经能组成x了if (x % 2 sum % 2) {int add n - (last - first 1);//计算出未被加上的2的数量if (sum add * 2 x) return true;} else {int add max(n - last, first - 1);//计算左右两边最多有多少个2if (sum - 1 add * 2 x) return true;}return false;
}void solve() {S.clear();cin n q;for (int i 1; i n; i) {cin a[i];if (a[i] 1) {S.insert(i);cnt;}}while (q--) {int op;cin op;if (op 1) {int x;cin x;if (check(x)) {cout YES endl;} else {cout NO endl;}} else {int i, v;cin i v;if (a[i] 1) S.erase(i);a[i] v;if (a[i] 1) S.insert(i);}}
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}E.Permutation Sorting
更新中…
以下学习交流QQ群群号 546235402大家可以加群一起交流做题思路分享做题技巧欢迎大家的加入。
