最近老师让我们重新开始学一本通提高篇，虽然这本书比较烂，但是由于我很菜，什么都不会，所以必须（(lhy)大佬喜欢说必须）好好学！还有就是……因为(loj)可以用了，所以以后在(loj)上做了（信息学奥赛一本通官方网站真是太(rubbish)了……）
(ps:)由于前几天已经把第一部分第一章做完了，所以从第二章开始写
二分与三分
首先……二分是一种非常精妙的算法，这个东西要用的话，必须要满足单调性，使用二分一次的时间约为(O(nlog n))
LOJ #10011. 「一本通 1.2 例 1」愤怒的牛
题意：数轴上有(n)个点，要求取出其中(m)个点，使得相邻的点的最小距离最大，输出这个距离
很明显的一道二分答案的题目，输入每个点的位置后从小到大排序，直接二分枚举答案，(check)函数比较简单，如下
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n, c;
int a[A];
bool check(int d) {
int cow = 1;
int now = a[1] + d;
for(int i = 2; i <= n; i++) {
if(a[i] < now) continue;
cow++;
now = a[i] + d;
}
return cow >= c;
}
signed main() {
n = read(), c = read();
for(int i = 1; i <= n; i++) a[i] = read();
stable_sort(a + 1, a + n + 1);
int l = 0, r = a[n] - a[1];
while(l <= r) {
int mid = (l + r) >> 1;
if(check(mid)) l = mid + 1;
else r = mid - 1;
}
cout << r << '
'; return 0;
}
LOJ #10012. 「一本通 1.2 例 2」Best Cow Fences
题意：给出(N)个数字(A_i)，求一段长度大于等于(K)的连续的子序列，其平均值最大
这道题属于实数二分，求平均值最大可以转化为每次(check)减去平均值看答案是否大于(0)即可
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ex 1e-5
using namespace std;
const int M = 10000100;
const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
double l = 100000.0, r = -10000.0, mid;
int n, L;
double a[M], sum[M];
inline bool check(double ans) {
double sum1, sum2;
sum1 = sum[L-1] - (L-1) * ans;
for(int i = L; i <= n; i++) {
sum2 = sum[i] - sum[i - L] - L * ans;
sum1 = sum1 + a[i] - ans;
sum1 = max(sum1, sum2);
if(sum1 > -ex) return true;
}
return false;
}
int main() {
n = read(), L = read();
for(int i = 1; i <= n; i++) {
scanf("%lf", &a[i]);
sum[i] = sum[i-1] + a[i];
l = min(l, a[i]), r = max(r, a[i]);
}
while(r - l > ex) {
mid = (l + r)/2;
if(check(mid)) l = mid;
else r = mid;
}
int ans = (int)(r * 1000);
return cout << ans << '
', 0;
}
LOJ #10013. 「一本通 1.2 例 3」曲线
题意：求一个函数(F(x))在([0,1000])上的最小值
这题就要用到三分了，三分是个啥?? here
由于函数(S)是开口向上的二次函数((a=0)时为一次函数)，所以它是一个先单调递减，再单调递增的下凸函数，或者是一个一次的单调函数，(F(x)=max(S(x)))也是满足单调性的，所以就可以用到三分求极值（这里是最小值）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int test, n;
double a[A], b[A], c[A];
double x, maxx=0, L, r, Lmid, rmid;
double cal(double x) {
double maxx = -0x7fffffff;
for(int i = 1; i <= n; i++) maxx = max(maxx, a[i] * x * x + b[i] * x + c[i]);
return maxx;
}
int main() {
int T = read();
for(int test = 1; test <= T; test++) {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
L=0, r=1000;
while(L + 1e-11 < r) {
Lmid = L + (r - L) / 3;
rmid = r - (r - L) / 3;
if(cal(Lmid) <= cal(rmid)) r = rmid;
else L = Lmid;
}
printf("%.4lf
", cal(L));
}
return 0;
}
LOJ #10014. 「一本通 1.2 练习 1」数列分段 II
题意：给定一个长度为(n)的正整数数列，现要将其分成(m)段，并要求每段连续，且每段和的最大值最小，求出这个最大的最小值
简单二分，在洛谷上也有 双倍经验啦
需要注意的是二分的下界(l)应为数列中的最大值，不然可能会(wa)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int ans = 0, sum = 0, maxn = -inf, n, m, a[A];
bool check(int x) {
int now = 0, res = 1;
for(int i = 1; i <= n; i++) {
if(now + a[i] <= x) {
now += a[i];
} else {
res++;
now = a[i];
}
}
return res <= m;
}
signed main() {
n = read(), m = read();
for(int i = 1; i <= n; i++) a[i] = read(), sum += a[i], maxn = max(maxn, a[i]);
int l = maxn, r = sum;
while(l <= r) {
int mid = (l + r) >> 1;
if(check(mid)) r = mid - 1;
else l = mid + 1;
}
cout << l << '
';
return 0;
}
LOJ #10015. 「一本通 1.2 练习 2」扩散
并查集+二分，有点懵逼。。先鸽着，可以看这篇博客 点我
任意两点的距离为两点间的曼哈顿距离
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 5e2 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
struct node { int x, y; } a[A];
int n, d[A][A], fa[A];
int abs(int x) { return x > 0 ? x : -x; }
int juli(node n1, node n2) {
return abs(n1.x - n2.x) + abs(n1.y - n2.y);
}
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
bool check(int x) {
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 1; i <= n; i++)
for(int j = i + 1; j <= n; j++)
if(d[i][j] <= x * 2) {
int fx = find(i), fy = find(j);
if(fx != fy) fa[fx] = fy;
}
int sum = 0;
for(int i = 1; i <= n; i++) {
if(fa[i] == i) sum++;
if(sum == 2) return false;
}
return true;
}
int main() {
n = read();
for(int i = 1; i <= n; i++) a[i].x = read(), a[i].y = read();
for(int i = 1; i <= n; i++)
for(int j = 1; j < i; j++)
d[i][j] = d[j][i] = juli(a[i], a[j]);
int l = 0, r = 999999999, ans = 0;
while(l <= r) {
int mid = (l + r) >> 1;
if(check(mid)) r = mid - 1, ans = mid;
else l = mid + 1;
}
cout << ans << '
'; return 0;
}
LOJ #10016. 「一本通 1.2 练习 3」灯泡
这个题就是要求影子的最大长度，假设在墙上的长度为(x)，我们就可以用相似得到(L)的表达式
[L=D imes dfrac {h-x}{H-x} +x
]
变形一下，就能够得到
[L= dfrac {D imes (H-h)}{x-H} + (x - H) + H + D
]
然后就发现这是一个对勾函数，说明可以进行三分，写就完了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eps 1e-5
using namespace std;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
double H, D, h;
double Get(double x) {
return D * (h - x) / (H - x) + x;
}
int main() {
int T = read();
while(T--) {
scanf("%lf%lf%lf", &H, &h, &D);
double l = -0, r = h;
while(r - l > eps) {
double qwq = (r - l) / 3, lmid = l + qwq, rmid = r - qwq;
if(Get(lmid) < Get(rmid)) l = lmid;
else r = rmid;
}
printf("%.3lf
", Get(l));
}
return 0;
}
LOJ #10017. 「一本通 1.2 练习 4」传送带
神奇的三分套三分，我觉得题解讲的不错(qwq)
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double eps = 1e-8;
double ax, ay, bx, by, cx, cy, dx, dy, p, q, r;
double dis(double x1, double y1, double x2, double y2) {
double xdis = x1 - x2, ydis = y1 - y2;
return sqrt(xdis * xdis + ydis * ydis);
}
double f(double x1, double y1, double x2, double y2) {
return dis(x1, y1, x2, y2)/r + dis(x2, y2, dx, dy)/q;
}
double calc1(double x, double y) {
double lx = cx, ly = cy, rx = dx, ry = dy;
while(dis(lx, ly, rx, ry) > eps) {
double kl = (rx - lx) / 3.0, ky = (ry - ly) / 3.0;
double lmidx = lx + kl, rmidx = rx - kl, lmidy = ly + ky, rmidy = ry - ky;
double ans1 = f(x, y, lmidx, lmidy), ans2 = f(x, y, rmidx, rmidy);
if(ans2 - ans1 > eps) rx = rmidx, ry = rmidy;
else lx = lmidx, ly = lmidy;
}
return f(x, y, lx, ly);
}
double calc() {
double lx = ax, ly = ay, rx = bx, ry = by;
while(dis(lx, ly, rx, ry) > eps) {
double kl = (rx - lx) / 3.0, ky = (ry - ly) / 3.0;
double lmidx = lx + kl, rmidx = rx - kl, lmidy = ly + ky, rmidy = ry - ky;
double ans1 = calc1(lmidx, lmidy) + dis(ax, ay, lmidx, lmidy)/p, ans2 = calc1(rmidx, rmidy) + dis(ax, ay, rmidx, rmidy)/p;
if(ans2 - ans1 > eps) rx = rmidx, ry = rmidy;
else lx = lmidx, ly = lmidy;
}
return calc1(lx, ly) + dis(ax, ay, lx, ly)/p;
}
int main() {
scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &ax, &ay, & bx, &by, &cx, &cy, &dx, &dy);
scanf("%lf%lf%lf", &p, &q, &r);
printf("%.2lf", calc());
}