2019 Multi-University Training Contest 10
補題連結：2019 Multi-University Training Contest 10
1003 Valentine's Day (HDU 6693)
題意
有 \(n\) 種禮物，第 \(i\) 種禮物能讓女朋友開心的機率為 \(P_i\)，挑一些禮物，問讓女朋友開心一次的機率最大為多少。
題解
機率 貪心
如果有機率大于等于 \(0.5\) 的禮物，輸出其中最大的。
否則，對機率從大到小。暴力枚舉選擇前 \(k\) 大的禮物的的機率，求最大值即可。
此題有原題。見 CodeForces 442B
相關證明見官方題解：Codeforces #253 editorial
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const int maxn = 100000 + 5;
double p[maxn];
int main() {
int T;
scanf("%d", &T);
while(T--) {
int n;
scanf("%d", &n);
double ans = 0, maxa = -1;
int flag = 0;
for(int i = 0; i < n; ++i) {
scanf("%lf", &p[i]);
if(p[i] >= 0.5) {
flag = 1;
if(maxa = -1) maxa = p[i];
else maxa = max(maxa, p[i]);
}
}
if(flag) {
printf("%.6lf\n", maxa);
} else {
sort(p, p + n);
double tmp1 = p[n - 1];
double tmp2 = p[n - 1] * (1 - p[n - 2]) + p[n - 2] * (1 - p[n - 1]);
ans = tmp2;
int k = 3;
while(tmp1 < tmp2 && k <= n) {
ans = tmp2;
tmp1 = tmp2;
tmp2 = 0;
for(int i = n - 1; i >= n - k; --i) {
double tmp = 1;
for(int j = n - 1; j >= n - k; --j) {
if(j == i) {
tmp *= p[j];
} else {
tmp *= 1 - p[j];
}
}
tmp2 += tmp;
}
k ++;
}
printf("%.6lf\n", max(ans, tmp2));
}
}
return 0;
}
1005 Welcome Party (HDU 6695)
\(solved\ by\ ch\)
有 \(n\) 個人，\(2\) 種節目，每個人要表演其中的一種節目，每種節目至少有一人表演。用 \(x_i\) 和 \(y_i\) 表示第 \(i\ (1\le i\le n)\) 個人表演兩種節目的能力值。現在要使表演第一種節目的人中的能力最大值與表演第二種節目的人中的能力最大值之差最小，求這個最小值。
貪心
如下圖，維護兩個集合 \(s_1\) 和 \(s_2\)。
按 \(x\) 從大到小枚舉。假設 \(x_i\) 為 \(x\) 中的最大值 (下圖中的 \(4\))，則比 \(x_i\) 大的都選擇 \(y\)，也就是取 \(s_1\) 中的最大值 (下圖中的 \(8\))。比 \(x_i\) 小的取與 \(x_i\) 最接近的 \(y\) (下圖中的 \(3\))，因為更大的 \(y\) 可以選擇 \(x\) (下圖中的 \(7\) 可以用 \(2\) 替換)。然後取兩個的較大值更新到 \(ans\) (下圖中 \(|3 - 4| < |8 - 4|\) 取 \(8 - 4\))，維護最小值 \(ans\) 即可。
比賽中隊友 (線段樹大佬) 用線段樹過的。賽後我用 \(multiset\) 寫了一下。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;
const ll inf = 2e18;
struct STU {
ll x, y;
} s[maxn];
ll maxy[maxn];
int cmp(STU s1, STU s2) {
return s1.x > s2.x;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T--) {
int n;
cin >> n;
multiset<ll> s1, s2;
for(int i = 0; i < n; ++i) {
cin >> s[i].x >> s[i].y;
s2.insert(s[i].y);
}
sort(s, s + n, cmp);
ll ans = inf;
for(int i = 0; i < n; ++i) {
s2.erase(s2.find(s[i].y)); // 一個人隻能選擇一種表演
if(!s1.empty()) {
ans = min(ans, abs(*s1.rbegin() - s[i].x));
}
if(!s2.empty()) {
multiset<ll>::iterator it = s2.lower_bound(s[i].x); // 找到第一個大于等于 s[i].x 的 y
if(it == s2.end()) {
--it;
}
ll tmp = abs(*it - s[i].x);
if(tmp < ans && (s1.empty() || *it > *s1.rbegin())) {
ans = tmp;
}
if(it != s2.begin()) { // 找到最後一個小于 s[i].x 的 y
--it;
tmp = abs(*it - s[i].x);
if(tmp < ans && (s1.empty() || *it > *s1.rbegin())) {
ans = tmp;
}
}
s1.insert(s[i].y);
}
}
cout << ans << endl;
}
return 0;
}
1007 Closest Pair of Segments (HDU 6697)
類似于計算幾何中的最近點對問題，本題求的是最近線段對。
給定 \(n\) 條線段，求出最近線段對之間的距離。
暴力 剪枝
比賽時我用了三角剖分，結果逾時了。
賽後補題時看到了這篇部落格：HDU 6697 Closest Pair of Segments（線段距離）
原來暴力加上剪枝就能過。思路是這樣的：
首先将線段的左側端點按照橫坐标為第一關鍵字，縱坐标為第二關鍵字排序。然後暴力找所有線段對，維護最小值 \(ans\)。如果目前查詢的線段對中，右側線段的左端點與左側線段的右端點的橫坐标內插補點大于 \(ans\) 時，就不用再找更右側的直線了。這樣剪枝能大大減少時間複雜度。
時限給了 20s，大概 1.3s 就能跑完。
題解看不懂
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long ll;
typedef double db;
const db eps = 1e-10;
const db pi = acos(-1.0);
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll maxn = 1e5 + 10;
inline int dcmp(db x) {
if(fabs(x) < eps) return 0;
return x > 0? 1: -1;
}
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
void input() {
scanf("%lf%lf", &x, &y);
}
bool operator<(const Point &a) const {
return (!dcmp(x - a.x))? dcmp(y - a.y) < 0: x < a.x;
}
bool operator==(const Point &a) const {
return dcmp(x - a.x) == 0 && dcmp(y - a.y) == 0;
}
db dis2(const Point a) {
return pow(x - a.x, 2) + pow(y - a.y, 2);
}
db dis(const Point a) {
return sqrt(dis2(a));
}
db dis2() {
return x * x + y * y;
}
db dis() {
return sqrt(dis2());
}
Point operator+(const Point a) {
return Point(x + a.x, y + a.y);
}
Point operator-(const Point a) {
return Point(x - a.x, y - a.y);
}
db dot(const Point a) {
return x * a.x + y * a.y;
}
db cross(const Point a) {
return x * a.y - y * a.x;
}
};
typedef Point Vector;
struct Line {
Point s, e;
Line() {}
Line(Point s, Point e) : s(s), e(e) {}
void input() {
s.input();
e.input();
}
db length() {
return s.dis(e);
}
// 點到直線的距離
db point_to_line(Point p) {
return fabs((p - s).cross(e - s) / length());
}
// 點到線段的距離
db point_to_seg(Point p) {
if(dcmp((p - s).dot((e - s))) < 0 || dcmp((p - e).dot((s - e))) < 0) {
return min(p.dis(s), p.dis(e));
}
return point_to_line(p);
}
// 線段到線段的距離
db seg_to_seg(Line l) {
return min(min(point_to_seg(l.s), point_to_seg(l.e)), min(l.point_to_seg(s), l.point_to_seg(e)));
}
};
Line l[maxn];
int cmp(Line l1, Line l2) {
return l1.s < l2.s;
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
l[i].input();
if(l[i].e < l[i].s) swap(l[i].s, l[i].e);
}
sort(l, l + n, cmp);
double ans = 1e10;
for(int i = 0; i < n; ++i) {
for(int j = i + 1; j < n; ++j) {
// 剪枝部分
if(dcmp((l[j].s.x - l[i].e.x) - ans) > 0) {
break;
}
ans = min(ans, l[i].seg_to_seg(l[j])); // 更新最小值
}
}
printf("%.12lf\n", ans);
}
return 0;
}
1009 Block Breaker (HDU 6699)
\(solved\ by\ zmz\)
隊友簽的到。
![BWT (Burrows–Wheeler_transform) 解碼分析[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)