AtCoder Beginner Contest 478A - Grapes题意有N个人编号为1到N现在要把M颗葡萄分给他们。每次按照1, 2, …, N的顺序每人分一颗分到第N个人以后再从第1个人开始直到所有葡萄分完。最后输出每个人分到了多少颗葡萄。思路这个题直接按照题意模拟就可以了。我们用数组记录每个人分到的葡萄数量每分出去一颗就移动到下一个人。到达最后一个人以后又需要回到第一个人所以可以使用取模来实现循环。代码中数组下标从0开始i表示已经分出了多少颗葡萄那么下一颗就分给下标为i % n的人。例如N3、M5时下标依次是0, 1, 2, 0, 1所以最后每个人得到的数量是2, 2, 1。注意输出时每个人的数量各占一行。因为M最多只有10000逐颗模拟完全可以通过。时间复杂度为O(M N)空间复杂度为O(N)。#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorint ans(n 1, 0); int i 0; while (m) { ans[i % n]; i; m--; } for (int i 0; i n; i) cout ans[i] endl; return 0; }B - Topping题意拉面店有N种配料第i种配料的价格是i快乐值是W[i]。我们需要选择恰好三种不同的配料并且总价格不能超过V问我们能够得到的最大快乐值是多少。题目保证至少存在一种合法的选择。思路最开始看到“价格不能超过V还要让快乐值最大”可能会想到背包但是这个题只需要选三种配料而且N最多是100所以直接枚举这三种配料就足够了。我们用三重循环枚举编号i、j、k并让它们满足i j k。这样既保证选择的是三种不同的配料又不会把同一组配料按照不同顺序重复枚举。对于每组选择如果i j k v就用w[i] w[j] w[k]更新答案。注意这里价格是配料编号数组w存的是快乐值所以判断预算时比较的是编号之和不是快乐值之和。N100时只会枚举161700种组合时间复杂度为O(N^3)空间复杂度为O(N)。#include bits/stdc.h using namespace std; int main() { int n, v; cin n v; vectorint w(n 1); for (int i 1; i n; i) cin w[i]; int ans 0; for (int i 1; i n; i) { for (int j i 1; j n; j) { for (int k j 1; k n; k) { if (i j k v) ans max(ans, w[i] w[j] w[k]); } } } cout ans endl; return 0; }C - Sort Subarray题意给我们一个长度为N的整数数组A以及一个整数K。我们必须进行恰好一次操作选择一个长度为K的连续区间把这个区间中的元素按升序排序。问能不能通过这一次操作让整个数组都变成升序也就是满足A[i] A[i1]。数组中可能有重复元素。思路这个题最开始可以想到暴力枚举区间。我们尝试每一个起点复制数组、排序对应的K个元素再检查整个数组是否有序。但是这样会重复排序很多次最坏时间复杂度达到O(N^2 log N)而N可以达到2 × 10^5显然不能这样做。第一步先想清楚我们最后到底要得到什么数组虽然可以选择不同的区间但如果操作后整个数组有序那么最终的数组是确定的它一定等于把原数组完整排序后的结果。所以我们先复制一份数组B然后把B完整排序。接下来不急着枚举区间而是比较A和B看看哪些位置还没有到它们应该在的状态。例如位置12345原数组A14325目标数组B12345这里第2、4个位置不同因此这两个位置必须被修改。第二步哪些位置必须包含在操作区间内一次排序只能改变我们选中的区间区间外的元素完全不会动。因此如果某个位置满足a[i] ! b[i]这个位置就必须在操作区间里否则它永远无法变成目标值。我们记录第一个不同的位置L以及最后一个不同的位置R。操作区间是连续的所以必须包含整个[L, R]即使中间有些位置本来就是正确的也不能跳过去。因此如果R - L 1 K就说明长度为K的区间放不下所有需要修改的位置答案一定是No。第三步跨度不超过K为什么就一定可以如果R - L 1 K我们可以把[L, R]向两边适当扩展选出一个长度恰好为K、并且包含它的合法区间。靠近数组边界时向另一边补足即可。这个区间外没有错位位置所以A和B在区间外已经完全相同。又因为B本来就是A排序得到的两者整体包含的元素以及每个元素出现的次数都相同。扣除区间外相同的部分区间内的元素及其次数也必然相同。而B的这个区间已经有序所以把A的这个区间排序以后一定会得到B中对应的部分。这样区间内外就都和B一致整个数组也就有序了。所以首尾错位位置的跨度不超过K就是能够完成操作的条件。这个结论对重复元素也成立。在上面的例子中L2、R4跨度为3。K3时排序第2到第4个元素即可K2时无论选哪个区间都无法同时修改第2和第4个位置。第四步注意原数组已经有序的情况。如果A和B完全相同答案直接是Yes。虽然题目要求恰好操作一次但已经有序的数组中任意一个长度为K的区间也都有序再排序一次不会改变数组。你下面的代码把mn初始化为1e8mx初始化为0。如果没有不同位置它们就不会更新算出的cnt是负数因此会进入cnt k并输出Yes。这个结果是正确的不过这里的负数只是初始值未更新造成的不能把它理解成真实的区间长度。最后把流程串起来就是复制A得到B并排序 → 找到首尾不同的位置 → 判断这两个位置的跨度是否不超过K如果没有不同位置则本来就已经有序。时间复杂度主要来自对B的排序为O(N log N)需要保存两个数组空间复杂度为O(N)。#include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorint a(n 1), b(n 1); for (int i 1; i n; i) { cin a[i]; b[i] a[i]; } sort(b.begin() 1, b.end()); int mn 1e8, mx 0; for (int i 1; i n; i) { if (a[i] ! b[i]) { mn min(mn, i); mx max(mx, i); } } // cout mx mn endl; int cnt mx - mn 1; if (cnt k) cout Yes endl; else cout No endl; return 0; }D - Range Set Insertion Query题意起初我们有N个空SetS1,S2,…,SNS_1, S_2, \ldots, S_NS1,S2,…,SN接下来我们要对这N个set进行Q次操作每次操作往LiL_iLi和RiR_iRi范围内的SSSset添加XiX_iXi这个数问我们经历过若干次操作后我们每个Set中都有多少个数字。思路读完题模拟了一下数据我们很容易想到差分因为最后统计的是我们每个Set中会有多少个数字因此每次操作可以当成在LiL_iLi和RiR_iRi范围内的SSSset 1最后我们做一次前缀和就可以得到我们最后的结果了吗NO本题最麻烦的一个地方就是我们的XiX_iXi是可以能重复的也就是我们可能会在某个区间的范围内加入若干次我们相同的某个数字。那么既然这样直接做是不对的那我们该如何去处理我们的这个插入呀。既然我们可能会在部分区间添加多次我们的XiX_iXi那我们是不是可以提前处理一下我们的区间让可能会造成重复添加的区间不在重复添加也就是合并我们添加相同XiX_iXi的区间这样我们就不会再出现一个区间添加两次XiX_iXi了这里我要强烈推荐一下我的区间合并模板真的好用。区间合并模板vectorpairint, int b; //处理输入输出 sort(b.begin(), b.end()); vectorpairint, int tmp; //合并后的新区间数组 for (auto c : b) { if (tmp.empty() || c.first tmp.back().second) tmp.push_back({c.first, c.second}); else tmp.back().second max(tmp.back().second, c.second); }完整代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, q; cin n q; vectorint ans(n 1, 0); mapint, vectorpairint, int cnt; for (int i 0; i q; i) { int l, r, x; cin l r x; cnt[x].push_back({l, r}); } for (auto [a, b] : cnt) { sort(b.begin(), b.end()); vectorpairint, int tmp; for (auto c : b) { if (tmp.empty() || c.first tmp.back().second) tmp.push_back({c.first, c.second}); else tmp.back().second max(tmp.back().second, c.second); } for (int i 0; i tmp.size(); i) { ans[tmp[i].first]; if (tmp[i].second 1 n) ans[tmp[i].second 1]--; } } for (int i 1; i n; i) ans[i] ans[i - 1]; for (int i 1; i n; i) cout ans[i] ; return 0; }