Educational Codeforces Round 176 (Rated for Div. 2)¶
2025-03-17
比赛链接: https://codeforces.com/contest/2075
赛时只通过了 ABC ， D看数据才补出来。。。
写题解的水平似乎过于低下了一点，不过一般是为了给自己看的。。。但是也希望分享出来看能不能起到一点帮助或者得到大家的指点。
虽然写东西的水平一直很低，但是写史花的时间也不少的。。。
A¶
不必多说了，偶数减去偶数一直是偶数，奇数减去奇数会变成偶数。
所以只用特判刚开始 \(n\) 奇偶，然后 k-- ，直接除向上取整就好。
void ChatGptDeepSeek()
{
int n, k;
cin >> n >> k;
int ans = 0;
if (n & 1) {
n -= k;
ans++;
}
k--;
if (n)
ans += (n - 1) / k + 1;
cout<<ans<<'\n';
}
B¶
如果 \(k\) 不为 \(1\) ，那么你可以把最大的 \(k+1\) 个数字都拿到。只需要把最后一个拿的数字留中间，这样你可以最后一个再拿它。
那么只用特判 \(1\) 了，最后一个拿的只能是第一个或者最后一个数字了。
void ChatGptDeepSeek()
{
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
if (k == 1 && n > 2) {
int mx = *max_element(a.begin() + 2, a.begin() + n);
cout << max(mx + max(a[1], a[n]), a[1] + a[n]) << '\n';
return;
}
sort(a.begin() + 1, a.end(), greater<>());
ll sum = 0;
for (int i = 1; i <= k + 1; i++)
sum += a[i];
cout << sum << '\n';
// x x x x
}
赛时 WA 了两发，有点不该的。
第一发提交是没有特判 \(k\) 为 \(1\) , 这倒是没啥，一个男人都会犯的错误（）。
但是第二发 WA 是特判了，但是我特判的是中间的最大的数加上 \(max(a_1,a_n)\) 。。。显然还有 \(a1+a_n\) 也是一个可行的答案。
C¶
昨晚没想出啥好做的方法。。。于是拿线段树瞎搞过了。。。希望不要 FST 。
正常写法下午上课再看看（）。
因为对于数量为 \(x\) 的颜色，我们需要另一种颜色的数量至少为 \(n-x\) ，所以另一种颜色只要数量每比 \(n-x\) 多 \(1\) ，对答案的贡献就多 \(1\) 。
所以可以转换成每种颜色对答案的贡献的范围是 \([1,a_i]\) ， 而 \([n-x,n-1]\) 的和，就是这一种颜色给答案增加的贡献。。
所以可以用线段树写个区间加。。好像有点太唐。。
struct SegmentTree {
#define ls p << 1
#define rs p << 1 | 1
#define mid ((l + r) >> 1)
vector<ll> tr, t;
SegmentTree(int n)
{
tr = t = vector<ll>(n << 2, 0);
}
void push_down(int p, int l, int r)
{
if (t[p]) {
t[ls] += t[p];
t[rs] += t[p];
tr[ls] += t[p] * (mid - l + 1);
tr[rs] += t[p] * (r - (mid + 1) + 1);
t[p] = 0;
}
}
void upd(int p, int l, int r, int lx, int rx, int x)
{
if (l >= lx && r <= rx) {
tr[p] += (r - l + 1) * x;
t[p] += x;
return;
}
push_down(p, l, r);
if (lx <= mid)
upd(ls, l, mid, lx, rx, x);
if (rx > mid)
upd(rs, mid + 1, r, lx, rx, x);
tr[p] = tr[ls] + tr[rs];
}
ll query(int p, int l, int r, int lx, int rx)
{
if (l >= lx && r <= rx)
return tr[p];
push_down(p, l, r);
ll res = 0;
if (lx <= mid)
res += query(ls, l, mid, lx, rx);
if (rx > mid)
res += query(rs, mid + 1, r, lx, rx);
return res;
}
};
void ChatGptDeepSeek()
{
int n, m;
cin >> n >> m;
vector<int> a(m + 1);
for (int i = 1; i <= m; i++)
cin >> a[i];
//[1,a[i]]是有贡献的
ll ans = 0;
SegmentTree C(n + 1);
for (int i = 1; i <= m; i++) {
if (a[i] == n)
a[i]--;
ans += C.query(1, 1, n, n - a[i], n - 1);
C.upd(1, 1, n, 1, a[i], 1);
}
cout << ans * 2 << '\n';
}
D¶
赛时不知道自己在写鸡毛啊，我是每次写一个 dp 。。。这么没有意识到可以预处理出来呢。。。因为每次查的东西其实都是一样的。
虽然之后也是能看到 wa on test 2 的数据才想到新写的东西的问题在哪里。。。
这题啥思路呢？我们观察 \(x\) 和 \(y\) 的二进制
先看看样例 \(x=13\) \(y=37\) 的情况
那么我们能把 \(x\) 和 \(y\) 变成什么值呢？
显然只有 \(0\) 和 \(1\) ，也就是说我们只能把 \(x\) 和 \(y\) 变成它们的公共前缀，或者是 \(0\) 。那么这个问题可以转换成什么呢？第一个数字需要左移 \(a\) 位，另一个数字需要右移 \(b\) 位。我们需要让构成 \(a\) \(b\) 的数字不相同，且花费最小。
就可以转换成一个经典的背包问题了。以 \(dp_{i,j}\) 表示 \(x\) 右移 \(i\) 位，\(y\) 右移 \(j\) 位的合法的最小花费的方案。我们只用枚举合法的划分方案就行了。
假设 \(x\) 的最长公共前缀是 \(len\) ，那么我们最终必须要使得 \(x\) 和 \(y\) 的剩余部分小于等于 \(len\) 。这样才能保证相等。
枚举剩下的位数为 \(i\) ，这里 \(b1, b2\) 我存的是 \(x\) 和 \(y\) 的二进制。
但是直到 wa 了看数据我才发现，有时 dp[a][b] 的值可能并不是一个可以到达的状态。。。这主要是这两个值相等且很小的情况，只有一种构成方式。
由于只有全变成 \(0\) 的情况你可以除更大的数字，一定也是可以到达的状态的。
所以我们只能 \(dp_{b1.size,b2.size}\) 的时候，选择更大的下标。
而且只有它们数字相同且很小才会不可达到。。
其实大于等于 \(3\) 就一定至少有两种构成方式了， \(x\) 和 \(1\) + \(x-1\) 。
所以只用多一个 \(dp_{a+1,b}\) 就行，\(dp_{x,y}\) 是等于 \(dp_{y,x}\) 的。
// 好像直接全部预处理好就行。。。
// Date: 2025-03-18
// Time: 11:53:03
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<ll>> dp(60, vector<ll>(60, 1e18 + 1));
void ChatGptDeepSeek()
{
ll x, y;
cin >> x >> y;
if (x == y) {
cout << "0\n";
return;
}
vector<int> b1, b2;
ll tmp = x;
while (tmp) {
b1.push_back(tmp % 2);
tmp /= 2;
}
reverse(b1.begin(), b1.end());
tmp = y;
while (tmp) {
b2.push_back(tmp % 2);
tmp /= 2;
}
reverse(b2.begin(), b2.end());
// if(b1.size()>b2.size()) swap(b1,b2);
// while(b1.size()<b2.size()) b1.push_back()
int len = 0;
for (int i = 0; i < b1.size() && i < b2.size(); i++) {
if (b1[i] != b2[i]) {
assert(i < b1.size() && i < b2.size());
// len = i;
break;
}
len++;
}
// cerr << len << '\n';
ll ans = 1e18 + 1;
for (int i = 0; i <= len; i++) {
assert(i <= b1.size() && i <= b2.size()); // 哦 没事了 有0
// 那是哪错了呢？
// cerr << b1.size() - i << " " << b2.size() - i << " \n";
ans = min(ans, dp[b1.size() - i][b2.size() - i]);
}
// for (int i = 1; i <= 10; i++) {
// if (i + b1.size() < 60)
// ans = min(ans, dp[b1.size() + i][b2.size()]);
// if (i + b2.size() < 60)
// ans = min(ans, dp[b1.size()][b2.size() + i]);
// if (i + b2.size() < 60 && i + b1.size() < 60)
// ans = min(ans, dp[b1.size() + i][b2.size() + i]);
// }
ans = min(ans, dp[b1.size() + 1][b2.size()]);
// cerr << dp[2][2] << " " << dp[1][1] << '\n';
// 哦哦 没事了 只有有一个被除成0 才能除更多位的
// 所以如果 dp[b1.size()][b2.size()] 不行
// 那就试一下它们附近的更大一些的
cout << ans << '\n';
// 10 11
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
dp[0][0] = 0;
for (int i = 1; i < 60; i++) {
vector ndp = dp;
// for (int x = 59; x >= 0; x--)
// for (int y = 59; y >= 0; y--)
for (int x = 0; x < 60; x++)
for (int y = 0; y < 60; y++) {
// 好好好 咋说呢 就是如果到不了 那么就可以直接用更大的数字来除啊
// @@@@@@@@@@@@
// 并不行。。。
if (x >= i)
ndp[x][y] = min(ndp[x][y], dp[x - i][y] + (1LL << i));
if (y >= i)
ndp[x][y] = min(ndp[x][y], dp[x][y - i] + (1LL << i));
}
dp = ndp;
}
int T = 1;
cin >> T;
while (T--)
ChatGptDeepSeek();
return 0;
}
F¶
怎么说。。看题目比较短加上有人说不是很难，于是看了一下。
果然不会做，很正常，而且浪费了很多时间。可能还是不是很理解吧，但是也理解得差不多了。
有一个东西是比较容易想出来的，比如我们选择的最优的答案的左端点，它的左侧是不会有比它小的数字的，不然你肯定选更靠前更小的，同理右端点右边也不会有比它更大的数字。
所以我们可以选择的左端点实际上只能是前缀的最小值，右端点只能是后缀的最大值。但是如果直接这样匹配的话，可能也会是 \(O(n^2)\) 。怎么优化呢？我们先把可选的左端点的下标都放到数组 \(l\) , 右端点放 \(r\) 。
实际上是计算每一个点的贡献，比如 \(a_i\) ，我们寻找第一个比它小的 \(xl\) ，那么 \(xl\) 后面的数字肯定都会是比 \(xl\) 更小的，所以我们令 \(xr\) 为第一个大于等于 \(i\) 的下标，于是我们的左端点只能从 \([xl,xr)\) 之间进行选择。
对于右端点，我们同样找到 \(yl\) 和 \(yr\) 分别为第一个大于 \(a_i\) 的右端点，\(yr\) 为第一个小于等于 \(a_i\) 的右端点。于是右端点只能从 \([yl,yr)\) 进行选择。
于是问题可以转换成，\(a_i\) 让 \([xl,xr)\) 可以对 \([yl,yr)\) 产生 \(1\) 的贡献，我们维护一个最大值的序列，在每个地方去查询当前的最大值。可以用扫描线，线段树查询和维护最大值信息。
using ll = long long;
struct SegmentTree {
#define ls p << 1
#define rs p << 1 | 1
#define mid ((l + r) >> 1)
vector<int> tr, t;
SegmentTree(int n)
{
tr = t = vector<int>((n + 2) << 2, 0);
}
void push_down(int p, int l, int r)
{
if (t[p]) {
t[ls] += t[p];
t[rs] += t[p];
tr[ls] += t[p];
tr[rs] += t[p];
t[p] = 0;
}
}
void upd(int p, int l, int r, int lx, int rx, int x)
{
if (l >= lx && r <= rx) {
tr[p] += x;
t[p] += x;
return;
}
push_down(p, l, r);
if (lx <= mid)
upd(ls, l, mid, lx, rx, x);
if (rx > mid)
upd(rs, mid + 1, r, lx, rx, x);
tr[p] = max(tr[ls], tr[rs]);
}
int query(int p, int l, int r, int lx, int rx)
{
if (l >= lx && r <= rx)
return tr[p];
push_down(p, l, r);
int res = 0;
if (lx <= mid)
res = max(res, query(ls, l, mid, lx, rx));
if (rx > mid)
res = max(res, query(rs, mid + 1, r, lx, rx));
return res;
}
};
void ChatGptDeepSeek()
{
int n;
cin >> n;
vector<int> a(n + 1), l, r;
for (int i = 1; i <= n; i++)
cin >> a[i];
int ans = 1;
for (int i = 1; i <= n; i++) {
if (l.empty() || a[l.back()] > a[i])
l.push_back(i);
if (!l.empty() && a[l.back()] < a[i])
ans = 2;
}
if (ans == 1) {
cout << "1\n";
return;
}
for (int i = n; i >= 1; i--) {
if (r.empty() || a[r.back()] < a[i])
r.push_back(i);
}
// vector<array<int, 4>> q;
priority_queue<array<int, 4>, vector<array<int, 4>>, greater<>> q;
reverse(r.begin(), r.end());
for (int i = 1; i <= n; i++) {
int xl = upper_bound(l.begin(), l.end(), i, [&](int x, int y) {
return a[x] > a[y];
}) - l.begin(); // 找到第一个小于 a[i]的
int xr = lower_bound(l.begin(), l.end(), i) - l.begin();
int yl = upper_bound(r.begin(), r.end(), i) - r.begin();
int yr = lower_bound(r.begin(), r.end(), i, [&](int x, int y) {
return a[x] > a[y];
}) - r.begin(); // 找到第一个小于等于a[i]的
if (xl < xr && yl < yr) {
q.push({ xl, 1, yl + 1, yr });
q.push({ xr, -1, yl + 1, yr });
// q.push_back({ xl, 1, yl + 1, yr });
// q.push_back({ xr, -1, yl + 1, yr });
}
}
SegmentTree C(n);
// sort(q.begin(), q.end());
for (int i = 0; i <= n; i++) {
while (!q.empty() && q.top()[0] == i) {
auto [_, x, l, r] = q.top();
q.pop();
C.upd(1, 1, n, l, r, x);
}
ans = max(ans, 2 + C.query(1, 1, n, 1, n));
}
cout << ans << '\n';
}