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

cf EC 172 C（0-＞-1 的转化+区间和使用前缀和表示，化简式子）+ D（二维的信息，先对一维排序，另一维看情况分析）

news 2024/12/4 5:07:53

这道题和C 题一模一样。
添加链接描述
在这里插入图片描述
真是真是菜吧。这道题做的时候还能想到前缀和，下面那一道题赛时完全没想法。
因为有一个区间的和，所以比较自然的能想到区间和。
但是区间和化简之后的式子，不可行。
换成后缀之后，就十分可以求解了。
很神奇。

后来想了一下，下一道题没做出来。完全没有往前缀和的方向去思考。

添加链接描述
C题意：
有一个n 长度的01 串。1 是B的得分点，0是A的得分点
要求B的得分大于A的得分至少K 分。
问最少划分多少区间（区间的权值依次为 0 1 2 …m-1）（每个区间至少一个元素。）或者无法做到输出-1.
对于一个区间B和A得分的差是（cnt1-cnt0）*权值
我们可以将0->-1 ，这样 cnt1-cnt0 的大小，可以直接用加法来代替。这个处理很常见。
这样区间的和，就可以尝试用前缀和来表示。
通过化简可以退出来我划分m的数组
那么B和A的差值是 (m-1)*sum-(m-1 个前缀)。
我们这个前缀当然选择最小的使用。

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
void solve()
{int n, k;cin >> n >> k;string ss;cin >> ss;vector<int> a(n + 1);int sum = 0;for (int i = 1; i <= n; i++){a[i] = ss[i - 1] - '0';if (a[i] == 0)a[i] = -1;sum += a[i];a[i] += a[i - 1];}sort(a.begin() + 1, a.end());vector<int> s(n + 1);for (int i = 1; i <= n; i++){s[i] += s[i - 1];s[i] += a[i];}// 枚举划分的组数for (int i = 1; i <= n; i++){int t = (i - 1) * sum - s[i - 1];if (t >= k){cout << i << "\n";return;}}cout << -1 << "\n";
}
signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

D题意：
就是说 n个区间，区间端点 1-1e9。每个区间的值定义为包含我这个区间的其他所有区间都具有的额外的长度。问每个区间的值
本质上是询问我每一区间合法区间中的最近的左端点和右端点。
思路：
对于二维的信息。一般的思路都有对某一维排序，之后的做法就得依据题目来分析。

我先按照左端点(升序)排序，将所有的右端点塞进set里面。这样我这个区间所有可能的合法区间的右端点都在这个set里面。我找到比我这个区间右端点大的第一个点就行。就是我合法区间里的最近的右端点。
然后再按照右端点（倒序）排序。将所有的左端点放进set里。找到比我小的第一个数

这道题还有一个细节，就是sort 的时候，当我左/右端点相同的时候，怎么排序。
回到排序的实质，当我到了i 这个区间，我要遍历了所有可能是我i 这个区间合法的区间。
所以当按照左端点来排序的时候，当左端点相同的时候，我们右端点大的要在前面。
同理右端点排序的时候。
还有一个问题，就是当我出现两个一样的区间的时候，我这些区间的ans 都是0.
这个要额外处理一下。（因为按照我们的排序，第一次出现的那个区间不会变成0）

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
int read()
{int x = 0, f = 1;char ch = getchar();while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}return x * f;
}struct node
{int l = 0, r = 0;int index = 0;
};
bool cmp1(node &a, node &b)
{if (a.l != b.l)return a.l < b.l;elsereturn a.r > b.r;
}
bool cmp2(node &a, node &b)
{if (a.r != b.r)return a.r > b.r;elsereturn a.l < b.l;
}
void solve()
{int n;cin >> n;set<PII> vis;vector<node> a(n);vector<int> ans(n);map<PII, int> mp; // 记录下标for (int i = 0; i < n; i++){cin >> a[i].l >> a[i].r;if (vis.find({a[i].l, a[i].r}) == vis.end()){vis.insert({a[i].l, a[i].r});mp[{a[i].l, a[i].r}] = i;}else{ans[mp[{a[i].l, a[i].r}]] = -1e18;ans[i] = -1e18;}a[i].index = i;}// 左端点排序sort(a.begin(), a.end(), cmp1);set<int> se;for (int i = 0; i < n; i++){int tar = a[i].r;auto it = se.lower_bound(tar);if (it != se.end()){ans[a[i].index] += *it - a[i].r;}se.insert(a[i].r);}set<int> se1;// 右端点排序sort(a.begin(), a.end(), cmp2);for (int i = 0; i < n; i++){int tar = a[i].l;auto it = se1.upper_bound(tar);if (it == se1.begin()){se1.insert(a[i].l);continue;}it = prev(it);ans[a[i].index] += a[i].l - *it;se1.insert(a[i].l);}for (int i = 0; i < n; i++){if (ans[i] < 0)cout << 0 << "\n";elsecout << ans[i] << "\n";}
}
signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}