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

【CF】⭐Day96——2025武汉ICPC（AILF）

ops 2025/7/13 5:54:35

Problem A. 出题

题目：

思路：

签到，模拟即可

很简单的模拟，我们直接判断一下一个值的左右区间，然后尽量取最小值即可

同时题目可能多次约束一个值，因此还要时刻取最大L和最小R

代码：

#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>
#include <complex>
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);vector<int> L(n,0), R(n,1e9);vector<int> lim(n,0);for (int i = 0; i < n; i++){cin >> a[i];}for (int i = 0; i < q; i++){int p, l, r;cin >> p >> l >> r;p--;lim[p] = 1;L[p] = max(L[p], l);R[p] = min(R[p], r);}int ans = 0;for (int i = 0; i < n; i++){if (!lim[i]) continue;if (L[i] > R[i]){cout << "-1\n";return;}if(a[i] < L[i] || a[i] > R[i])ans += min(abs(a[i] - L[i]), abs(a[i] - R[i]));}cout << ans << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

Problem I. Bingo 3

题目：

思路：

构造 + 思维

显然如果 k 过小，即 k < n 时我们肯定不可以构造出来，那么上界呢？

纸上写两下我们可以发现是 n*n - (n-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>
#include <complex>
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> vis(n * n + 1, 0);vector<vector<int>> ans(n, vector<int>(n, 0));if (k < n || k >n*n - (n-1)){no;return;}yes;int nowk = k;for (int i = 0; i < n; i++){ans[i][i] = nowk;vis[nowk] = 1;nowk++;}int now = 1;for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (ans[i][j] != 0){cout << ans[i][j] << " ";continue;}while (vis[now]){now++;}cout << now << " ";vis[now] = 1;now++;}cout << endl;}
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

Problem L. 子序列

题目：

思路：

暴力枚举 + 二分 + 思维

首先看到 n 的限制我们直接就能想到暴力 n² 的枚举，那我们枚举什么呢？

这里我们选择枚举最小值和中位数，那么最大值就是 2*mid - mi

随后我们二分最后一个为最大值的位置，因为我们肯定是选的越多越好，随后考虑如何选择

如果我们选择奇数个，那么首先中间值肯定要选，那么左右两边的数的数量就要一样，也就是说我们最多只能选 min(j - i, posr - j) * 2 + 1 个

如果我们选择偶数个，那么中间的数就包括在左半部分，此时要我们右半部分的数量要等于左半部分的数量，那么就有 min(j - i + 1, posr - j) * 2

代码：

#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>
#include <complex>
using namespace std;
#define yes cout << "Yes\n"
#define no cout << "No\n"void solve()
{int n;cin >> n;vector<int> a(n+1,1e9+5);for (int i = 0; i < n; i++){cin >> a[i];}sort(a.begin(), a.end());int len = 0;//枚举最小值for (int i = 0; i < n; i++){//枚举中位数for (int j = i; j < n; j++){int r = 2 * a[j] - a[i];int lidx = lower_bound(a.begin(), a.end(), r) - a.begin();if (lidx == n || a[lidx] != r){continue;}int ridx = lower_bound(a.begin(), a.end(), r + 1) - a.begin() - 1;int posr = ridx;//如果选奇数个len = max(len, min(j - i, posr - j) * 2 + 1);//如果选偶数个len = max(len, min(j - i + 1, posr - j) * 2);}}cout << len << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

Problem F. 背包

题目：

思路：

贪心地模拟，但是模拟过程很细节

显然贪心地想，我们肯定是先把大的数分配完较好，同时由于都是 2 的 b 次幂，所以上一次剩下来的空间一定能填单个的数（我们降序排列）

这样的话我们就可以先计算上次剩下来的空间能不能完全装下这次的东西，如果装不下，那么所有的包都要更新大小，于是剩下来的空间也要更新大小，以此类推

注意：由于 b 的范围很大，我们如果直接暴力计算显然不行，以此我们需要优化（提前跳出）

具体实现看代码

代码：

#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>
#include <complex>
using namespace std;
#define int long long
#define yes cout << "Yes\n"
#define no cout << "No\n"
const int mod = 998244353;
int qpow(int a, int b)
{int ans = 1;for (; b; b >>= 1){if (b & 1)ans = ans * a % mod;a = a * a % mod;}return ans;
}
int solve()
{int n, m;cin >> n >> m;//first 代表大小 second 代表数量map<int, int> f;for (int i = 1; i <= n; i++){int a, b;cin >> a >> b;f[b] += a;}vector<pair<int, int>> a;for (auto p : f)a.push_back({ p.first, p.second });//按照大小降序排列（贪心）reverse(a.begin(), a.end());//res代表剩余的幂次，ans代表容量int res = 0, ans = 0;auto add = [&](int& x, int y) -> void{x += y;if (x >= mod)x -= mod;};for (int i = 0; i < a.size(); i++){auto x = a[i].first;//当前大小auto c = a[i].second;//当前数量int d = (i == 0) ? 1 : a[i - 1].first - a[i].first;//相差的数量级//既然这个数都相差很大，那么后面的数就相差更多了//极端情况下就是后面的 n 个数 ai 全为 1e9，且相差都为 d//那么最坏的情况下我们后面所有物品的重量就为 2e5 * 1e9 * 2的x次方//我们假设上一个是数量级是 y,那么也就是有下面式子// res * 2的y次方 > 2e5*10e9*2的 x 次方（由于 2的50次方恰好大于 1e15，下面进行变换）// 即 res > 2的 50次方*2的(x - y) 次方// 即 res > 2的 (50 - d) 次方//如果有剩余，且 d > 50，此时右边小于 1，而 res 有剩余则大于等于 1，故此时能直接走if (res && d > 50)return ans;//否则我们计算一下看看到底能不能直接结束if (res && res > (1ll << (50 - d)))return ans;//将上一个幂拆成现在的幂，如上一个幂是 10，剩了一个，当前的幂是9//那么全变为 9 就能容下 res <<= (10 - 9) 即 res = 1 << 1 = 2 个 res <<= d;//如果转化为相同的幂次还不够，那么容量就要提升了if (res < c){//计算用完了现在 res 个，每个包最少要新增的 容纳的 2 的 x 次幂 的个数int last = (c - res + m - 1) / m;//计算容量，新的容量就是原来的基础上加上每个包最少需要添加的 2 的 x 次幂的个数//即 ans += last * 2的x次幂add(ans, last % mod * qpow(2LL, x) % mod);//也就是说容量新增了 last * m 个可使用的空间，下面再把 c减去即可res += last * m;}//记得减去res -= c;}return ans;
}
signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){cout << solve() << endl;}return 0;
}

查看全文

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