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

【CF】Day50——Codeforces Round 960 (Div. 2) BCD

ds 2025/5/4 7:00:12

B. Array Craft

题目：

思路：

有点意思的构造

首先题目告诉我们 y < x，这是一个重要的条件

我们先来考虑简单情况，假如可以放0进去，那么我们只需要在 y ~ x 之间全放 1 ，其余都是 0 即可，但是现在只能放 1/-1，因此我们必须要想另一种方法

一个想法就是我们利用 -1构代替0，但是显然有一个小bug，那就是如果全是-1，那么就可能会出现最大值其实是0，那么我们换一种想法，既然要保证x y处才是最大，那我们只需要在y前和x后放上-1即可，这样后面的数一定不可能超过此时x y的和，同时为了保证-1的数量不能超过xy区间内的1的数量，我们只需要在1后交替摆放-1 1即可，如 x -1 1 -1 1 ...

代码：

#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, x, y;cin >> n >> x >> y;vector<int> a(n+1, 1);int add = -1;for (int i = y - 1; i >= 0; i--){a[i] = add;add *= -1;}add = -1;for (int i = x + 1; i <= n; i++){a[i] = add;add *= -1;}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;
}

C. Mad MAD Sum

题目：

思路：

思维？模拟！

这题我们没有思路的话可以模拟一遍看看，我们可以发现我们的数组一定是这样的

如：1 2 3 4 4 4 7 8 9 10 10 11 11

第一次 0 0 0 0 4 4 4 4 4 4 10 10 11

第二次 0 0 0 0 0 4 4 4 4 4 4 10 10

第三次 0 0 0 0 0 0 4 4 4 4 4 4 4 10

....

总之我们可以发现我们之后的数组每一次都是删掉了最后那个数，因此我们可以先模拟一遍题目的变换过程，然后再根据每个数的位置判断其奉献，可以发现奉献就是 a[i] * (n - i)

特别的，对于样例 2 1 1 2，它的变换一次后是 0 0 1 2，而下一次就是 0 0 0 0，可以看出他不符合我们的上面结论，为什么？因为他不是递增数组，我们每次变换后都能发现他是一个递增数组，所以我们可以变换两次，然后再快速计算奉献，防止一开始是非递增情况而直接计算导致错误

代码：

#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;cin >> n;vector<int> a(n);int sum = 0;for (int i = 0; i < n; i++){cin >> a[i];sum += a[i];}auto fuct = [&]() {int MAD = 0;vector<int> mp(n + 1, 0);for (int i = 0; i < n; i++){mp[a[i]]++;if (mp[a[i]] >= 2){MAD = max(MAD, a[i]);}a[i] = MAD;}     };fuct();for (int i = 0; i < n; i++){sum += a[i];}fuct();for (int i = 0; i < n; i++){sum += a[i] * (n - i);}cout << sum << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

D. Grid Puzzle

题目：

思路：

看似dp，实则贪心

我们可以发现，如果 a[i] > 4，那么肯定是用第二个操作比较好，因为第一个要用 (a[i] + 1) / 2次，显然大于等于 1 次

那么来分类讨论，这里先给出一个 last ，代表上次是否使用了操作一，以及操作一的位置

如果 a[i] = 0，直接跳过即可，此时 last = 0，即这里没使用

如果 a[i] <= 2，如果 last != 0，那么就让last = 1，代表此次让1 2列变换了，否则令 last = 0，因为上次让 1 2 列变换了，这次会受到上次的影响

如果 a[i] <= 4，如果 last = 0，那我们不如直接用操作二，因为就算下面的也是 a[i] = 4，我们也要用2次才能全搞掉，还不如用操作二，还能防 a[i] > 4 的情况；如果 last = 1，那我们就令 last = 2，因为这次我们只需要让 3 4 列变白色即可；如果 last = 2，那我们令 last = 1 即可

然后根据讨论模拟即可

代码：

#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;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++){cin >> a[i];}int res = 0;int last = 0;for (int i = 0; i < n; i++){if (a[i] == 0){last = 0;continue;}if (a[i] > 4){last = 0;res++;continue;}if (a[i] <= 2){if (last != 1){res++;last = 1;}else{last = 0;}continue;}if (a[i] <= 4){if (last == 1){last = 2;}else if(last == 2){last = 1;}res++;continue;}}cout << res << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

查看全文

http://www.xdnf.cn/news/3832.html