当前位置：首页 > news >正文

【CF】Day9——Codeforces Round 953 (Div. 2) BCD

news 来源：原创 2025/8/13 1:01:59

B. New Bakery

题目：

思路：

被标签害了，用什么二分（

很简单的思维题，首先如果a >= b，那么全选a就行了，还搞啥活动

否则就选 b - a 天来搞活动，为什么？

首先如果我们要搞活动，而且要最大利益，那么肯定要满足 b - k >= a，即每一天的利润都不能小于a，不然的话我搞啥活动

所以变换一下就是 b - a >= k，可知最大k是 b - a ，然后再写出理论公式即可（自己写X）

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"int n, a, b;void solve()
{cin >> n >> a >> b;int k = min(n, b - a), ans = 0;if (a >= b)ans = n * a;else {k = min(n, b - a);ans += (2 * b + 1 - k) * k / 2 + (n - k) * a;}cout << ans << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

C. Manhattan Permutations

题目：

思路：

这是一道比较直觉的思维题目

首先题目说要构造出一个排列使得其曼哈顿值为所需的k，那首先我们肯定要判断能不能构造出

显然，使得排列为 n n-1 n-2 ... 3 2 1这种形式存在最大曼哈顿值，同时还能观察到，如果要构造只能构造出偶数曼哈顿值，为什么呢？其实自己举例证明就能发现（我就是这样发现的）

那么现在就考虑如何构造出这个排列呢？

我们对于任意一个x和y，如果交换其位置，那么奉献肯定是 2 * |x - y|，也就是说可以构造出任何偶数，那我们考虑直接模拟，双指针来选择合适的x y，如果小于k，那么就加，否则就往内缩小，由于每次的奉献其实是对称的，所以维护一边的指针即可，特别的，这一题肯定是要从大到小枚举

（注意数据，因为数据不是特别大，所以O(n)的做法可以接受，我一开始就是想太难，在考虑如何优化，纯属是杞人忧天了）

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"void solve()
{int n, k;cin >> n >> k;int maxn = 0;vector<int> a(n+1,0);for (int i = 1; i <= n; i++){maxn += abs((n - i + 1) - i);a[i] = i;}if (k % 2 || k > maxn){no;return;}yes;int L = 1, R = n;while (k && L <= R){while (2ll * (a[R] - a[L]) > k)R--;k -= 2ll * (a[R] - a[L]);swap(a[L], a[R]);L++, R--;}for (int i = 1; i <= n; i++){cout << a[i] << " ";}cout << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

D. Elections

题目：

思路：

考验直觉和眼力的思维题

首先我们要看清楚！这个人数是分给下标最小的，也就是下标最前的，那么显然

只要第一个人不去除，别的票都会给第一个！

也就是说对于第 i 个人，如果不将前 i - 1 个人删去的话，那么第 i 个人的票数是不会增加的

到此，关键点就没了，接下来就是模拟了

首先我们要确定一开始谁都不删除的情况下谁是最大的，这样就知道谁是不需要删除的了，也就是比较 a[0] + c 和 max(a1 ~ an)，那么特判就到此结束了，接下来乖乖模拟即可

我们可以用sum来储存有多少人可以投给第i人，如果a[i] + sum >= maxn（其中maxn是整个数列的最大值），那么就输出 i 个人即可，因为我们最少都要删掉 i 个人，如果还是小于最大值的话，我们只需要多删去那个最大值就行了，也就是要删 i + 1 个，同时我们根本不需要考虑最大值相等的情况，因为对于第 i 个，前面的都删完了，就算有相等的，他也是第一个

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"void solve()
{int n, c;cin >> n >> c;vector<int> a(n);for (int i = 0; i < n; i++){cin >> a[i];}if (n == 1){cout << "0\n";return;}int maxn = *max_element(a.begin(), a.end());int maxN = max(maxn, a[0] + c);int first = (maxN == a[0] + c) ? 0 : (find(a.begin(),a.end(),maxn) - a.begin());int sumc = c;for (int i = 0; i < n;i++){int ans = 0;if (i == first){ans = 0;}else if(sumc + a[i] >= maxn){ans = i;}else{ans = i + 1;}cout << ans << " ";sumc += a[i];}cout << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

B. New Bakery

题目：

思路：

代码：

C. Manhattan Permutations

题目：

思路：

代码：

D. Elections

题目：

思路：

代码：

相关文章：