牛客 周赛109 20250924

牛客 周赛109 20250924

https://ac.nowcoder.com/acm/contest/116945

A：
题目大意：

给定两个坐标，判断和原点一起能否构成一个直角三角形

void solve(){double x, y, u, v;cin >> x >> y >> u >> v;double L[] = {sqrt(x * x + y * y), sqrt(u * u + v * v), sqrt((x - u) * (x - u) + (y - v) * (y - v))};sort(L, L + 3);if (L[0] + L[1] <= L[2]) cout << "No";else cout << "Yes";
}

签到

B：
题目大意：

void solve(){int n;cin >> n;vector<double> x(n), y(n);for (int i = 0; i < n; i ++)cin >> x[i] >> y[i];auto check = [&](int i, int j){double dx = x[i] - x[j], dy = y[i] - y[j];return abs(sqrt(dx * dx + dy * dy) - 1) < 0.000001;};int cnt = 0;for (int i = 0; i < n; i ++){for (int j = i + 1; j < n; j ++){if (check(i, j)) cnt ++; }}cout << cnt ;
}

\(O(n^2)\) 的暴力

C：
题目大意：

void solve(){pair<int, int> p1, p2, p3;cin >> p1.first >> p1.second >> p2.first >> p2.second;if (p1.first == p2.first || p1.second == p2.second){if (p1.first == p2.first){p3.second = min(p1.second, p2.second);p3.first = p1.first - 2;}else{p3.first = min(p1.first, p2.first);p3.second = p1.second - 2;}cout << p3.first << ' ' << p3.second; return ;}if (p1.second < p2.second) swap(p1, p2);p3.first = p1.first;p3.second = p2.second;int dx = p2.first - p3.first;int dy = p1.second - p2.second;if (dx & 1 && dy & 1) p3.first -= dx;cout << p3.first << ' ' << p3.second; }

先构造出以 \(AB\) 为斜边的一个直角三角形，然后判断两条直角边是否都为奇数

如果全为奇数，那么面积存在小数，所以令任意一条直角边变为原来的两倍，构造满足题意

D：
题目大意：

int dx[] = {1, 2, -1, -2};
int dy[] = {2, -2 , 1, -1};void solve(){int n;cin >> n;vector<pair<int, int>> p(n);for (int i = 0; i < n; i ++)cin >> p[i].first >> p[i].second;sort(p.begin(), p.end());map<pair<int, int>, int> mp;for (int i = 0; i < n; i ++){int x = p[i].first, y = p[i].second;for (int u = 0; u < 4 ; u ++){for (int v = 0; v < 4; v ++){if (abs(dx[u]) == abs(dy[v])) continue;int tx = x + dx[u], ty = y + dy[v];if (tx <= 0 || ty <= 0) continue;mp[{tx, ty}] ++;}}}pair<int, int> ans = {0, 0};int mx = 0;for (auto [k ,v] : mp){if (mx < v && lower_bound(p.begin(), p.end(), k) != p.end()){mx = v;ans = k;}}cout << ans.first << ' ' << ans.second;
}

考虑用 map 记录所有可以威胁到兵的位置，至多存在 \(8n = 1.6e6\) 个，存入空间复杂度可以接受

最后枚举所有记录的位置，得到最大值答案

E：
题目大意：

void solve(){int n;cin >> n;vector<pair<int, int>> p(n);for (int i = 0; i < n; i ++)cin >> p[i].first >> p[i].second;sort(p.begin(), p.end());map<int, set<int>> mp;for (int i = 0; i < n; i ++)mp[p[i].first].insert(p[i].second);int ans = 0;for (auto it = mp.begin(); next(it, 1) != mp.end(); it ++){auto st1 = (*it).second, st2 = (*next(it, 1)).second;if ((*it).first != (*next(it, 1)).first - 1) continue;int cnt = 0;for (auto i : st1){if (st2.count(i)) cnt ++;}ans += cnt * (cnt - 1) / 2;}mp.clear();for (int i = 0; i < n; i ++)mp[p[i].second].insert(p[i].first);for (auto it = mp.begin(); next(it, 1) != mp.end(); it ++){auto st1 = (*it).second, st2 = (*next(it, 1)).second;if ((*it).first != (*next(it, 1)).first - 1) continue;int cnt = 0;for (auto i : st1){if (st2.count(i)){cnt ++;if (st1.count(i - 1) && st2.count(i - 1)) ans --;}}ans += cnt * (cnt - 1) / 2;}cout << ans ;
}

对点进行两次排序，第一次按照横坐标从小到大排序，把点按照横坐标存进不同的 set 中，然后枚举 map 中的 set

暴力计算相邻的横坐标相差一的 set 中相同的纵坐标数量，排列组合计算在横坐标相差一下可以构造的矩形数量

同样的对纵坐标排序后相似计算，注意还需要减去长宽都为 \(1\) 的矩形重复的贡献

for (auto i : st1){if (st2.count(i)){cnt ++;if (st1.count(i - 1) && st2.count(i - 1)) ans --;}
}

F：
题目大意：

const int N = 2e5 + 10;struct Q{int k1, k2, idx;
};int s[N];int lowbit(int x){return x&-x;
}void change(int x, int k){while (x < N){s[x] += k;x += lowbit(x);}
}int query(int x){int res = 0;while (x){res += s[x];x -= lowbit(x);}return res;
}void solve(){int n, m;cin >> n >> m;vector<pair<int, int>> p(n);for (int i = 0; i < n; i ++)cin >> p[i].first >> p[i].second;	vector<Q> q(m);for (int i = 0; i < m; i ++){cin >> q[i].k1 >> q[i].k2;q[i].idx = i;}set<int> st;map<int, int> mp;int idx = 0;for (int i = 0; i < n; i ++){int x = p[i].first, y = p[i].second;p[i].first = x - y;p[i].second = x + y;st.insert(p[i].second);}for (int i = 0; i < m; i ++){q[i].k1 *= -1;st.insert(q[i].k2);}for (auto i : st) mp[i] = ++ idx;for (int i = 0; i < n; i ++){p[i].second = mp[p[i].second];change(p[i].second, 1);}for (int i = 0; i < m; i ++) q[i].k2 = mp[q[i].k2];auto cmp = [&](Q x, Q y){return x.k1 < y.k1;};sort(p.begin(), p.end());sort(q.begin(), q.end(), cmp);int i = 0, j = 0;vector<int> ans(m);while (i < m){while (j < n && p[j].first <= q[i].k1){change(p[j].second, -1);j ++;}ans[q[i].idx] = query(q[i].k2 - 1);i ++;}for (auto i : ans) cout << i << '\n';}

给定的点需要满足下面的约束：

\[y - x < k_1\\ y + x < k_2 \]

换算到切比雪夫坐标下，令 \(X = x -y,Y=x + y\) ，约束为 \(X > -k_1,Y<k_2\)

对询问和点集按照 \(X\) 从小到大排序后，离散化后树状数组查询对应 \(Y\) 满足的点的数量

while (i < m){//枚举询问while (j < n && p[j].first <= q[i].k1){//删去点集中不合法的点change(p[j].second, -1);j ++;}ans[q[i].idx] = query(q[i].k2 - 1);//处理询问i ++;
}

时间复杂度为 \(O(n\log n)\)