1003. Forgiving Matching

1004. Game on Plane

题意

给定 \(n\) 条直线,每次 Alice 选择 \(k\)​ 条直线, Bob 作一条直线。Alice 希望 Bob 作出的直线与选中的直线交点尽可能多,Bob 希望尽可能少。

分析

两条直线存在公共点当且仅当它们重合或者它们斜率不同,因此 Bob 的最优策略一定是避开斜率出现次数最多的那些直线。Alice 为了让 Bob 与尽量多的直线相交,最优策略就是最小化斜率出现次数的最大值,所以不断从每种斜率的直线中各选一种即可。

总结

斜率直接拿 double 存就行,没必要用逆元。。或者直接存 \(\Delta x, \Delta y\)

一开始选择 1e9 + 7 作为取模模数存逆元出现了斜率不同但冲突的情况。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e6 + 7;
const ll inf = 1e9 + 7;
int T = 1;
map<double, int> mp;
int f[N], g[N];
pll p1, p2;
void solve()
{
    mp.clear();
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lld %lld %lld %lld", &p1.first, &p1.second, &p2.first, &p2.second);
        if (p1.first == p2.first)
            mp[inf]++;
        else
        {
            ll dx = p1.first - p2.first;
            ll dy = p1.second - p2.second;
            double tmp = dy / dx * 1.0;
            mp[tmp]++;
        }
    }
    int tot = 0, cnt = 0, now = 0;
    for (auto &it : mp)
        g[++tot] = it.second;
    sort(g + 1, g + tot + 1);
    while (cnt < n)
    {
        for (int i = 1; i <= tot; i++)
            if (g[i])
                g[i]--, cnt++, f[cnt] = cnt - now - 1;
        now++;
    }
    for (int i = 1; i <= n; i++)
        printf("%d\n", f[i]), f[i] = 0, g[i] = 0;
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        solve();
    }
}

1007. Photoshop Layers

题意

求区间和,其中区间出现标记的位置要将之前的清零,重新计数,输入输出均为十六进制数

分析

前缀和预处理,最后根据题意要跟 255 取 min

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5 + 7;
int T = 1;
unordered_map<char, int> hx;
unordered_map<int, char> dx;
void gaohx(int x)
{
    int x1 = x / 16, x2 = x % 16;
    cout << dx[x1] << dx[x2];
}
string p[N];
ll R[N], G[N], B[N];
void solve()
{
    int n, q;
    cin >> n >> q;
    vector<int> v;
    string s;
    for (int i = 1, m; i <= n; i++)
    {
        cin >> m >> s;
        p[i] = s;
        if (m == 1)
            v.emplace_back(i);
    }
    for (int i = 1; i <= n; i++)
    {
        R[i] = R[i - 1] + hx[p[i][0]] * 16 + hx[p[i][1]];
        G[i] = G[i - 1] + hx[p[i][2]] * 16 + hx[p[i][3]];
        B[i] = B[i - 1] + hx[p[i][4]] * 16 + hx[p[i][5]];
    }
    // cout << v.size() << endl;
    while (q--)
    {
        int li, ri, l, r;
        cin >> li >> ri;
        auto it = upper_bound(v.begin(), v.end(), ri);
        if (it == v.begin())
            l = li, r = ri;
        else
            l = max(li, *(it - 1)), r = ri;
        int rr = min(255ll, R[r] - R[l - 1]);
        int gg = min(255ll, G[r] - G[l - 1]);
        int bb = min(255ll, B[r] - B[l - 1]);
        gaohx(rr), gaohx(gg), gaohx(bb);
        cout << '\n';
    }
}
int main()
{
    for (int i = 0; i < 10; i++)
        hx['0' + i] = i, dx[i] = (char)('0' + i);
    for (int i = 0; i < 6; i++)
        hx['A' + i] = 10 + i, dx[10 + i] = (char)('A' + i);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        solve();
    }
}

1009. Rise in Price

1010. Road Discount

1011. Segment Tree with Pruning

题意

给定 \(n,k\)​ 求构建 \([1,n]\) 区间的线段树中区间长度大于 \(k\) 的节点个数

分析

模拟建树过程,对区间长度记忆化,因为区间长度相同则子结点个数

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5 + 7;
int T = 1;
map<ll, ll> mp;
ll n, k;
ll build(ll n)
{
    if (mp.count(n))
        return mp[n];
    else if (n <= k)
        return mp[n] = 1;
    else
        return mp[n] = build(n / 2) + build(n - n / 2) + 1;
}
void solve()
{
    mp.clear();
    scanf("%lld%lld", &n, &k);
    printf("%lld\n", build(n));
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        solve();
    }
}

间歇性踌躇满志,持续性混吃等死