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

【CF】Day44——Codeforces Round 908 (Div. 2) C + Codeforces Round 1020 (Div. 3) DE

backend 2025/5/9 5:13:04

C. Anonymous Informant

题目：

思路：

比这场的D难，虽然也不是很难

一个很容易想到的就是由当前状态推出初始状态，那么怎么推呢？

一个性质就是如果对于某一个 x 它可以执行左移操作的话，那么它一定会到数组最后，因此初始数组其实是唯一的，我们可以模拟一遍即可

但是 k 可是有 1e9 这么大，这样可以吗？

之前写过类似的题，面对这种k次操作的题，如果k的值很大，说明有隐藏的性质，比如循环

这题就是循环，如果我们执行了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;vector<int> b(n);for (int i = 0; i < n; i++){cin >> b[i];}k = min(k, n);int now = n - 1;for (int i = 0; i < k; i++){if (b[now] > n){no;return;}now -= b[now];if (now < 0){now += n;}}yes;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

D. Flower Boy

题目：

思路：

前后缀的应用，比较典

由于我们必须按照顺序选，也就是必须选了 i 才能选 i + 1，因此我们就要考虑什么时候用魔法比较好

一个显然的结果就是结果肯定是 b[i] 中的一个或者 0，由于只能用一次，所以我们可以枚举跳过 b[i]，对于每一个 b[i] 都枚举一遍有点满了，那么有什么方法可以快速得到一段区间的结果呢？

那就是前后缀了，我们提前用贪心算出每个位置 i 最多能选出多少个花朵，那么只要有一个位置满足前缀[i] + 后缀[i+1] == m - 1，就说明此时刚好差一朵，那么就能把它放入答案中了

注意特判 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, m;cin >> n >> m;vector<int> a(n+1), b(m+1);for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= m; i++){cin >> b[i];}vector<int> l(n+2, 0), r(n+2,0);int now = 0;for (int i = 1;i <= n; i++){if (now < m && a[i] >= b[now + 1]){now++;}l[i] = now;}now = 0;for (int i = n; i >= 1; i--){if (now < m && a[i] >= b[m - now]){now++;}r[i] = now;}if (l[n] >= m){cout << "0\n";return;}int res = INT_MAX;for (int i = 0; i <= n; i++){if (l[i] + r[i+1] == m - 1){res = min(res, b[l[i] + 1]);}}cout << (res == INT_MAX ? -1 : res) << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

E. Wolf

题目：

思路：

很有意思的题目，感觉比较简单

题目摆明了就是一道模拟二分题

我们就按照平常的操作模拟一下即可，首先记录所有的数的坐标，这样方便获取坐标

那么对于一个 k，如果我们要找到 p[k] 这个位置，那么就要看看过程中到底有几次往左和往右的操作，我们定义 l r 分别为左边界和右边界，那么操作就如下

①.获取mid

②.判断mid是大于还是小于p[k]，如果小于，说明要往右，否则就是要往左

③.更新 l 或 r，并重复上述操作

那么关键点就是判断能不能到 p[k]，我们想想要到 p[k] 要满足什么条件？显然就是要每次都能正确的左移或者右移，即 a[mid] 必须是正确的大于 k 或者小于 k

具体的，如果要往左移，那么就是要满足 a[mid] > k，反之就是 a[mid] < k

那么只要有不符合的，就说明我们就要借一个数过来，然后到最后统计一下能不能借

具体操作就是如上所示，我们定义一个 big small Big Small，前两个代表要借的数量，后两个代表能提供的数量，那么如果某个是a[mid]正确的大小关系，那就就是 Big/Small - 1，即这个数被固定了，不能借出去了，否则就借一个

特别的，我们最后的答案其实是 2 * max(small，big)，因为借一个 small 的同时要把当前的位置也去掉，而这个位置肯定是 Big，所以这个 Big 可以给另一个需要借 big 的用，反之亦然，因此最多只需要 2 * max(small，big) 个数即可

代码：

#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, q;cin >> n >> q;vector<int> a(n+1), p(n+1);for (int i = 1; i <= n; i++){cin >> a[i];p[a[i]] = i;}auto check = [&](int L, int R,int k){if (p[k] > R || p[k] < L){return -1LL;}int big = 0, small = 0;int Big = n - k, Small = k - 1;while (L <= R){int mid = L + R >> 1;if (mid == p[k]){break;}else if (mid < p[k]){if (a[mid] > k)small++;elseSmall--;L = mid + 1;}else if (mid > p[k]){if (a[mid] < k)big++;elseBig--;R = mid - 1;}}int sum = Small + Big;if (small > Small || big >  Big || 2*small > sum || 2*big > sum){return -1LL;}return 2 * max(small, big);};for (int i = 0; i < q; i++){int l, r, k;cin >> l >> r >> k;cout << check(l,r,k) << " ";}cout << 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/2260.html