牛客周赛 Round 109 题解（简）

A 小红的直角三角形

两个点分别落在 轴和 轴上即可。

void solve() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    if (x1 == 0 && y1 != 0 && x2 != 0 && y2 == 0 || x1 != 0 && y1 == 0 && x2 == 0 && y2 != 0) cout << "Yes" << "\n";
    else cout << "No" << "\n";
}

B 小红的好点对

一看只有100个点，直接暴力枚举即可。

void solve() {
    int n;
    cin >> n;
    vector<PII> p(n);
    for (int i = 0; i < n; ++i) cin >> p[i].fi >> p[i].se;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int dx = p[i].fi - p[j].fi, dy = p[i].se - p[j].se;
            if (dx * dx + dy * dy == 1) ans++;
        }
    }
    cout << ans << "\n";
}

C 小红的整数三角形

分两类讨论：

• 1.两点 或 坐标相同上，即 ，显然可以取一个与连线距离为 的点，此时面积为 或 ，为整数。
• 2.两点坐标不同，我们可以用 铅锤高 水平宽 来计算面积，也就是把三角形拆成两个直角三角形。根据已有的两点构造出直角三角形（即取 或 ），此时面积为 ，若已经为整数了，输出即可，否则再添上一个 或 即可。

void solve() {
    int x1, x2, y1, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int dx = x1 - x2, dy = y1 - y2;
    if (dx != 0 && dy != 0) {
        if (dx * dy & 1) {
            cout << x1 + 1 << " " << y2 << "\n";
        } else {
            cout << x1 << " " << y2 << " ";
        }
    } else {
        if (dx == 0) {
            cout << x1 + 2 << " " << y1 << "\n";
        } else {
            cout << x1 << " " << y1 + 2 << "\n";
        }
    }
}

D 小红的马

对于每一个兵，标记可达它的周围8个点，最后找出标记次数最多的即为答案。

int dx[] = { -1, 1, -2, -2, -1, 1, 2, 2}, dy[] = {2, 2, 1, -1, -2, -2, 1, -1};
 
void solve() {
    const ll len = 2e5;
    int n;
    cin >> n;
    auto encode = [&](ll x, ll y) {
        return x * len + y;
    };
 
    map<ll, int> mp;
    for (int i = 0; i < n; ++i) {
        ll x, y;
        cin >> x >> y;
        for (int j = 0; j < 8; ++j) {
            if (x + dx[j] >= 1 && x + dx[j] <= len && y + dy[j] >= 1 && y + dy[j] <= len) mp[encode(x + dx[j], y + dy[j])]++;
        }
    }
    ll mx = 0, loc;
    for (auto [u, v] : mp) {
        if (v > mx) {
            mx = v;
            loc = u;
        }
    }
    cout << loc / len << " " << loc % len << "\n";
}

E 小红的好矩形

考虑容斥，答案即为

因为坐标范围给的很大，所以先要进行离散化（用map标记即可）。

void solve() {
    int n;
    cin >> n;
    vector<PII> p(n);
    map<int, map<int, int>> mp;
    map<int, vector<int>> X, Y;
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        p[i] = {x, y};
        mp[x][y] = 1;
        X[x].pb(y);
        Y[y].pb(x);
    }
    map<int, int> cnt1, cnt2;
    for (auto [u, v] : X) {
        for (auto vv : v) {
            if (mp[u + 1][vv]) cnt1[u]++;
        }
    }
    for (auto [u, v] : Y) {
        for (auto vv : v) {
            if (mp[vv][u + 1]) cnt2[u]++;
        }
    }
    ll ans = 0;
    for (auto [_, v] : cnt1) {
        ans += v * (v - 1) / 2;
    }
    for (auto [_, v] : cnt2) {
        ans += v * (v - 1) / 2;
    }
    sort(all(p));
    for (auto [x, y] : p) {
        if (mp[x + 1][y] && mp[x][y + 1] && mp[x + 1][y + 1]) ans--;
    }
    cout << ans << "\n";
}

F 小红的线下查询

先化公式，移一下项，得到。

先取出 的部分，再在其中找 有多少个即可。

离线实现，借助了 的平衡树实现，需要注意 的 不能处理重复元素，所以需要用 打上重复标记。

void solve() {
    int n, q;
    cin >> n >> q;
    vector<PII> p(n);
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        p[i] = {y - x, y + x};
    }
    sort(all(p));
    vector<array<int, 3>> qs;
    for (int i = 0; i < q; ++i) {
        int k1, k2;
        cin >> k1 >> k2;
        qs.pb({k1, k2, i});
    }
    sort(all(qs));

    vector<int> ans(q);
    int ptr = 0;
    unordered_map<int, int> cnt;
    Tree tr;
    for (auto [k1, k2, i] : qs) {
        while (ptr < n && p[ptr].fi < k1) {
            tr.insert({p[ptr].se, cnt[p[ptr].se]});
            cnt[p[ptr].se]++;
            ++ptr;
        }
        ans[i] = tr.order_of_key({k2, 0});
    }
    for (auto v : ans) cout << v << "\n";
}

头文件参考

//Another
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef tuple<ll, ll, ll> TLLL;
typedef __gnu_pbds::tree<PLL, __gnu_pbds::null_type, less<PLL>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;
// typedef __gnu_pbds::tree<ll, __gnu_pbds::null_type, less<ll>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;

constexpr int inf = (ll)1e9 + 7;
// constexpr ll INF = (ll)2e18 + 9;
constexpr ll INF = (ll)4e18;
// constexpr ll MOD = 1e9 + 7;
constexpr ll MOD = 998244353;
constexpr ld PI = acos(-1.0);
constexpr ld eps = 1e-10;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull randint(ull l, ull r) {uniform_int_distribution<unsigned long long> dist(l, r); return dist(rng);}

void init() {

}

void solve() {
    
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    init();

    int t = 1;
    // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    return 0;
}