B.Crazy Binary String
给01串,问最长的01数量相等的子串和子序列长度。
#include <bits/stdc++.h>
using namespace std;
map<int, int> M;
int n;
char s[100005];
int main() {
scanf("%d%s", &n, s + 1);
int cnt0 = 0, cnt1 = 0, mx = 0;
for (int i = 1; i <= n; ++i) {
if (s[i] == '1') ++cnt1;
else ++cnt0;
if (cnt0 == cnt1) mx = i;
if (M[cnt0 - cnt1] != 0) mx = max(mx, i - M[cnt0 - cnt1]);
if (M[cnt0 - cnt1] == 0) M[cnt0 - cnt1] = i;
}
printf("%d %d\n", mx, min(cnt0, cnt1) << 1);
return 0;
}
H.Magic Line
给n个平面上的点,求一条直线把平面分成两半,一半N/2个点(不能过给定的点)。
找一个左上角的点,比如(-1e5-1,1e5+3),二分一下倾斜角即可。为了方便直接二分了点,然后稍微偏移一下。
#include <bits/stdc++.h>
using namespace std;
struct pt {
double x, y;
pt(const pt &rhs) : x(rhs.x), y(rhs.y) {}
pt(double x = 0, double y = 0) : x(x), y(y) {}
pt operator -(const pt &rhs) { return pt(x - rhs.x, y - rhs.y); }
pt operator +(const pt &rhs) { return pt(x + rhs.x, y + rhs.y); }
template<typename T> pt operator *(const T &rhs) { return pt(x * rhs, y * rhs); }
};
double cross(const pt &a, const pt &b) { return a.x * b.y - a.y * b.x; }
pt a[1005];
int n;
int calc(pt s, pt e) {
int cnt = 0;
for (int i = 1; i <= n; ++i)
cnt += cross(e - s, a[i] - s) > 0;
return cnt;
}
int main() {
int T; scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%lf%lf", &a[i].x, &a[i].y);
pt s(-1e5 - 73, 1e5 + 11);
sort(a + 1, a + n + 1, [&](pt &a, pt &b){ return cross(b - s, a - s) > 0; });
int l = 0, r = n;
while (l < r) {
int mid = l + 1 + r >> 1;
pt e((a[mid] - s) * 8753 + s);
e.y -= 1;
if (calc(s, e) <= n >> 1) l = mid;
else r = mid - 1;
}
pt e((a[l] - s) * 8753 + s);
e.y -= 1;
assert(calc(s, e) == n >> 1 && abs(e.x) <= 1e9 && abs(e.y) <= 1e9);
printf("%.0lf %.0lf %.0lf %.0lf\n", s.x, s.y, e.x, e.y);
}
return 0;
}
标签:const,pt,int,rhs,mid,return,2022.10
From: https://www.cnblogs.com/herald/p/16747452.html