A. Adjusted Average（暴力枚举+二分查找）
分析
读完题目可以发现k很小，那么考虑暴力做法的时间复杂度为\(O(C_n^k)\)，对于\(k\leq3\)的其实可以直接暴力创过去，但对于\(k=4\)的情况显然不适用。那么对应\(k=4\)的情况考虑优化，可以选择将数分为两个集合，先用一个set存下其中一个集合的所有选择方案，此时枚举删除另外一个集合中的哪两个数，最后二分查找最优的匹配方案。时间复杂度\(O(n^2logn)\)。
代码实现
#include <bits/stdc++.h>
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
#define int long long
int n, k, x;
std::cin >> n >> k >> x;
std::vector<int> a(n);
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
}
int sum = std::accumulate(a.begin(), a.end(), 0LL);
double ans = abs((double)sum / n - x);
for (int num = 1; num <= k; ++num) {
std::set<int> st{(int)-1e18, (int)1E18};
for (int i = 0; i < n; ++i) {
ans = std::min(ans, abs((double)(sum - a[i]) / (n - 1) - x));
if (num == 1) continue;
for (int j = i + 1; j < n; ++j) {
ans = std::min(ans, abs((double)(sum - a[i] - a[j]) / (n - 2) - x));
if (num == 2) continue;
int sur = sum - (n - num) * x - a[i] - a[j];
auto it = st.lower_bound(sur);
ans = std::min({ans, abs((double)(sur - *it) / (n - num)), abs((double)(sur - *(--it)) / (n - num))});
}
for (int j = 0; j < i; ++j) {
st.emplace(a[i] + a[j] * (num == 4));
}
if (num == 3) st.emplace(a[i]);
}
}
std::cout << ans << '\n';
}
I - Imperfect Imperial Units（离散化）
分析
正解应该是从每个点开始搜一遍，但是写的时候偷懒，于是魔改了一下Floyd创过去了。时间复杂度\(O(n^3 + q)\)
代码实现
#include <bits/stdc++.h>
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cout << std::setprecision(12);
int n, m;
std::cin >> n >> m;
std::map<std::string, int> mp;
std::vector<std::tuple<double, int, int>> edges;
int cur = 0;
for (int i = 0; i < n; ++i) {
double a, b;
std::string x, op, y;
std::cin >> a >> x >> op >> b >> y;
if (!mp.count(x)) mp[x] = cur++;
if (!mp.count(y)) mp[y] = cur++;
int u = mp[x], v = mp[y];
edges.emplace_back(b, u, v);
edges.emplace_back(a / b, v, u);
}
std::vector g(cur, std::vector<double>(cur, 1e305));
std::vector f(cur, std::vector<int>(cur, 0)), cnt(cur, std::vector<int>(cur, 0));
for (auto [c, a, b] : edges) {
g[a][b] = c;
g[a][a] = g[b][b] = 1;
f[a][b] = f[a][a] = f[b][b] = 1;
}
for (int k = 0; k < cur; ++k) {
for (int i = 0; i < cur; ++i) {
for (int j = 0; j < cur; ++j) {
f[i][j] |= f[i][k] & f[k][j];
if (f[i][j] && !cnt[i][j]) {
cnt[i][j] += 1;
g[i][j] = std::min(g[i][k] * g[k][j], g[i][j]);
}
}
}
}
while (m--) {
double x;
std::string a, op, b;
std::cin >> x >> a >> op >> b;
if (!mp.count(a) || !mp.count(b)) {
std::cout << "impossible" << "\n";
} else {
int u = mp[a], v = mp[b];
if (f[u][v]) {
std::cout << g[u][v] * x << "\n";
} else {
std::cout << "impossible" << '\n';
}
}
}
}
J. Jagged Skyline （随机化+二分）
分析
题目只给了12000次询问，显然如果每个点问过去次数显然是不够的。这边可以做个随机化问点，每次查询当前最高值+1，如果为sky那就直接跳过，否则说明当前的位置比我最大值要大，此时更新一下最大值。期望的询问次数大概是\(O(n + ln(w) * log_2(n))\)
代码实现
#include <bits/stdc++.h>
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
#define int long long
int n, h, cur = 11999;
std::cin >> n >> h;
std::vector<int> ord(n);
std::iota(ord.begin(), ord.end(), 1);
std::shuffle(ord.begin(), ord.end(), std::default_random_engine(rng()));
auto get = [&](int w, int high) {
std::cout << "! " << w << ' ' << high << std::endl;
exit(0);
};
auto ask = [&](int W, int H) {
cur--;
std::cout << "? " << W << " " << H << std::endl;
std::string x;
std::cin >> x;
return x;
};
int max = 0, pos = 1;
for (int i = 0; i < n; ++i) {
if (ask(ord[i], max + 1) != "sky") {
if (cur == 0) get(pos, max);
if (ask(ord[i], h) == "building") get(ord[i], h);
int l = max + 1, r = h;
while (l < r) {
int mid = l + r >> 1;
if (ask(ord[i], mid) == "sky") {
r = mid;
} else {
l = mid + 1;
}
if (cur == 0) get(pos, max);
}
if (l - 1 > max) {
pos = ord[i], max = l - 1;
if (max == h) get(pos, max);
}
}
}
get(pos, max);
}
L. Lowest Latency (三维最近点对)
分析
这题不知道是水还是怎么的，贴了一个二维最近点对的代码就创过去了。
代码实现
#include <bits/stdc++.h>
using namespace std;
using DB = long double;
const DB eps = 1e-12, inf = 1e100, pi = acos(-1);
DB dcmp(DB x, DB y) { return fabs(x - y) < eps ? 0 : x < y ? -1 : 1; }
DB sgn(DB x) { return fabs(x) < 0 ? 0 : x < 0 ? -1 : 1; }
DB rand_eps() { return ((DB)rand() / RAND_MAX - 0.5) * eps; }
struct Point3 {
DB x, y, z;
Point3 () {}
Point3 (DB x, DB y, DB z) : x(x), y(y), z(z) {}
void shake() { x += rand_eps(), y += rand_eps(), z += rand_eps(); }
Point3 operator+(const Point3 &P) const { return Point3(x + P.x, y + P.y, z + P.z); }
Point3 operator-(const Point3 &P) const { return Point3(x - P.x, y - P.y, z - P.z); }
Point3 operator*(DB p) const { return Point3(x * p, y * p, z * p); }
Point3 operator/(DB p) const { return Point3(x / p, y / p, z / p); }
DB operator&(const Point3 &P) const { return x * P.x + y * P.y + z * P.z; }
Point3 operator^(const Point3 &P) const { return Point3(y * P.z - z - P.y, z * P.x - x * P.z, x * P.y - y * P.x); }
friend istream &operator>>(istream &is, Point3 &rhs) { return is >> rhs.x >> rhs.y >> rhs.z; }
friend ostream &operator<<(ostream &os, const Point3 &rhs) { return os << '(' << rhs.x << ',' << rhs.y << ',' << rhs.z << ')'; }
};
using Vector3 = Point3;
DB Len(const Vector3 &A) { return sqrt(A & A); }
DB Len2(const Vector3 &A) { return A & A; }
DB Distance(const Vector3 &A, const Vector3 &B) { return Len(A - B); }
DB Closest_pair(const vector<Point3> &p, int l, int r) { // 平面最近点对
DB dist = inf;
if (l == r) return dist;
if (l + 1 == r) return Distance(p[l], p[r]);
int mid = l + r >> 1;
DB d1 = Closest_pair(p, l, mid), d2 = Closest_pair(p, mid + 1, r);
dist = min(d1, d2);
vector<Point3> tmp;
for (int i = l; i <= r; ++i)
if (fabs(p[mid].x - p[i].x) <= dist) tmp.push_back(p[i]);
for (int i = 0; i < tmp.size(); ++i) {
for (int j = i + 1; j < tmp.size(); ++j) {
// if (fabs(tmp[j].y - tmp[i].y) >= dist || fabs(tmp[j].z - tmp[i].z) >= dist) break;
dist = min(dist, Distance(tmp[i], tmp[j]));
}
}
return dist;
}
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cout << std::fixed << std::setprecision(20) << "\n";
int n;
std::cin >> n;
std::vector<Point3> p(n);
for (int i = 0; i < n; ++i) {
std::cin >> p[i];
}
std::sort(p.begin(), p.end(),
[&](const Point3& a, const Point3& b) {
if (a.x == b.x) {
if (a.y == b.y) {
return a.z < b.z;
} else {
return a.y < b.y;
}
} else {
return a.x < b.x;
}
});
std::cout << Closest_pair(p, 0, n - 1) << "\n";
}