B
题意:
给定一个01字符串,你需要找到最长的一个子串和最长的一个子序列,分别使得其中01的个数相同。
做法:
子序列很好算 2×min(cnt0,cnt1)
子串可以考虑前缀和
将0与1的个数差前缀和 每次询问当前的前缀和x 如果之前出现前缀和为y 使得x+y=0即成立
最后取个最大值就好
void solve() {
int n; cin >> n;
string s; cin >> s;
s = " " + s;
int ans = 0, cnt = 0;
map<int,int> mp;
mp[0] = 0;
for (int i = 1; i <= n; i++) {
if (s[i] == '1') cnt++;
else cnt--;
if(mp.count(cnt)) ans = max(ans, i - mp[cnt]);
else mp[cnt] = i;
}
cout << ans << " ";
int cnt1 = 0, cnt0 = 0;
for (int i = 1; i <= n; i++) {
if (s[i] == '0') cnt0++;
else cnt1++;
}
cout << min(cnt1, cnt0) * 2 << endl;
}
很神奇的做法:
假设开始线是水平的 然后我们可以找到第一条使得过线和线上方的点大于总点数的线
然后使得这条线倾斜一丢丢就好
map<int, vector<int>>mp;
int n;
void slove() {
cin >> n;
mp.clear();
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
mp[y].push_back(x);
}
int pre = 0;
for (auto p : mp) {
sort(p.second.begin(), p.second.end());
pre += p.second.size();
if (pre >= n / 2) {
pre -= p.second.size();
for (int x : p.second) {
pre++;
if (pre == n / 2) {//找到中间点
//x y
int y = p.first;
cout << int(x + 1e8) + 1<<" " << y - 1 << " " << int(x - 1e8) <<" " << y + 1 << endl;
break;
}
}
break;
}
}
}
G
题意:
给你n个数,问你有多少个长度不小于2的连续子序列,使得其中最大元素不大于所有元素和的一半。
做法
还是用到容斥原理
int a[N], n, pre[N];
int sum(int L, int R) {
if (L > R)return 0;
return pre[R] - pre[L - 1];
}
int LL[N], RR[N];
void slove() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i];
for (int i = 1; i <= n; i++)pre[i] = pre[i - 1] + a[i];
a[0] = 1e18, a[n + 1] = 1e18;
stack<int>stk; stk.push(0);
for (int i = 1; i <= n; i++) {
while (a[stk.top()] < a[i])stk.pop();
LL[i] = stk.top();
stk.push(i);
}
while (stk.size())stk.pop();
stk.push(n + 1);
for (int i = n; i >= 1; i--) {
while (a[stk.top()] < a[i])stk.pop();
RR[i] = stk.top();
stk.push(i);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
int L_len = i - LL[i], R_len = RR[i] - i;
if (L_len <= R_len) {
int mx = a[i];
for (int j = LL[i] + 1; j <= i; j++) {
auto k = lower_bound(pre + i, pre + RR[i], 2 * mx + pre[j - 1]) - pre;
ans += (k - i);
}
}
else {
int mx = a[i];
for (int j = i; j < RR[i]; j++) {
auto k = lower_bound(pre + LL[i], pre + i, pre[j] - 2 * mx + 1) - pre;
ans += i - k;
}
}
}
cout << n * (n + 1) / 2 - ans << endl;
}
原文地址:http://www.cnblogs.com/wzxbeliever/p/16784648.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性