板刷2023-526互联

CF1822 G1. Magic Triples (Easy Version)

$1 \leq a_i \leq 10^6$

题解

显然关键在于$j$，我们不妨枚举$j$，显然$a[i]$是$a[j]$的约数

对于每个$a[j]$来说，枚举其约数，然后即可求出倍数$b$，那么可得到$a_k$

时间复杂度：$O(1000n)$

int n, a[N];
map<int, int> mp;

void solve()
{
    mp.clear();
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        mp[a[i]]++;
    }
    int ans = 0;
    for (auto [x, y] : mp)
    {
        // cerr << x << " " << y << endl;
        vector<int> div;
        for (int i = 1; i <= x / i; ++i)
        {
            if (x % i == 0)
            {
                div.push_back(i);
                if (i != x / i)
                    div.push_back(x / i);
            }
        }
        for (auto val : div)
        {
            // cerr << val << ", ";
            int t = x / val;
            if (mp.count(val) && mp.count(x * t))
            {
                if (x == val && y >= 3)
                    ans += y * (y - 1) * (y - 2);
                else if (x != val)
                    ans += y * mp[val] * mp[x * t];
                // cerr << val << " " << x << " " << x * t << endl;
                // cerr << "x = " << x << ", ans = " << ans << endl;
            }
        }
    }
    cout << ans << endl;
}

CF1801 B. Buying gifts

题解

我们不妨枚举每个$a[i]$作为第一个人的最大值，所以对$a[i]$降序排列

对于某个$a[i]$来说，一旦我们将其作为第一个人的最大值，那么对于每个$j,j>i$，礼物一定是卖给第二个人的，所以我们在$[i + 1, n]$中找到$b[j]$的最大值，ST表查询即可，我们设最大值为$mx$

如果$mx \geq a[i]$，那么答案一定为$mx - a[i]$

如果$mx < a[i]$，我们检查一下$b[1, i - 1]$中有没有更接近$a[i]$的值，可以用$set$维护前缀实现，然后二分即可

int n, st[N][22], lg2[N];
array<int, 2> c[N];

void build()
{
    for (int i = 1; i <= n; ++i)
        st[i][0] = c[i][1];
    for (int i = 2; i <= n; ++i)
        lg2[i] = lg2[i >> 1] + 1;
    for (int j = 1; j <= 20; ++j)
        for (int i = 1; i + (1ll << j) - 1 <= n; ++i)
            st[i][j] = max(st[i][j - 1], st[i + (1ll << (j - 1))][j - 1]);
}
int query(int l, int r)
{
    int len = lg2[r - l + 1];
    return max(st[l][len], st[r - (1ll << len) + 1][len]);
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> c[i][0] >> c[i][1];
    sort(c + 1, c + n + 1);
    build();
    multiset<int> st;
    int ans = INF;
    for (int i = 1; i <= n; ++i)
    {
        int a = c[i][0], b = c[i][1];
        if (i < n)
        {
            int mx = query(i + 1, n);
            if (mx >= a)
                ans = min(ans, abs(mx - a));
            else
            {
                ans = min(ans, abs(mx - a));
                auto l = st.upper_bound(a);
                auto r = st.lower_bound(a);
                if (st.size())
                {
                    l = prev(l);
                    ans = min(ans, abs(*l - a));
                }
                if (r != st.end())
                    ans = min(ans, abs(*r - a));
            }
        }
        else
        {
            auto l = st.upper_bound(a);
            auto r = st.lower_bound(a);
            if (st.size())
            {
                l = prev(l);
                ans = min(ans, abs(*l - a));
            }
            if (r != st.end())
                ans = min(ans, abs(*r - a));
        }
        st.insert(b);
    }
    cout << ans << endl;
}

CF1797 D. Li Hua and Tree

题解

维护每个节点的重儿子和所有儿子子树的点权和，所有儿子子树的点数和，每个节点的父节点

考虑每个节点维护$set$，$set$中存放一个$pair$对$(sz[u], u):以u为根的子树中点数和，节点u$

每次操作二，我们不仅需要更新$x$和$son_x$的信息，同时需要更新$fa_x$的信息，因为有可能$fa_x$的重儿子会改变，然后再更新3个节点之间的父子关系

细节比较多，但是思路出的很快，本题难点在于对于操作2时更新信息时考虑需要更加全面

int n, q, a[N], hson[N], sz[N], sum[N], fa[N];
vector<int> g[N];
multiset<array<int, 2>> st[N];

void dfs(int u, int par)
{
    sz[u] = 1;
    sum[u] = a[u];
    hson[u] = -1;
    fa[u] = par;
    for (auto v : g[u])
    {
        if (v == par)
            continue;
        dfs(v, u);
        if (hson[u] == -1 || sz[hson[u]] < sz[v])
            hson[u] = v;
        else if (hson[u] != -1 && sz[hson[u]] == sz[v])
        {
            if (v < hson[u])
                hson[u] = v;
        }
        st[u].insert({sz[v], -v});
        sz[u] += sz[v];
        sum[u] += sum[v];
    }
}

void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1, u, v; i < n; ++i)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    while (q--)
    {
        int op, u;
        cin >> op >> u;
        if (op == 1)
            cout << sum[u] << endl;
        else
        {
            if (hson[u] == -1)
                continue;
            int v = hson[u];
            st[u].erase(st[u].find({sz[v], -v}));
            st[fa[u]].erase(st[fa[u]].find({sz[u], -u}));
            sum[u] -= sum[v];
            sz[u] -= sz[v];
            if (st[u].size())
                hson[u] = -(*prev(st[u].end()))[1];
            else
                hson[u] = -1;

            sz[v] += sz[u];
            sum[v] += sum[u];
            st[v].insert({sz[u], -u});
            st[fa[u]].insert({sz[v], -v});
            if (st[v].size())
                hson[v] = -(*prev(st[v].end()))[1];
            else
                hson[v] = -1;

            if (st[fa[u]].size())
                hson[fa[u]] = -(*prev(st[fa[u]].end()))[1];
            else
                hson[fa[u]] = -1;

            fa[v] = fa[u], fa[u] = v;
        }
    }
}

CF1796 D. Maximum Subarray

题解

显然最大子段和问题可以通过线段树来解决

我们贪心的考虑，如果$x > 0$，那么我们一定是给一段连续的位置$ + x$，其余位置$-x$，所以我们不妨滑动窗口枚举给哪些连续位置$+x$，那么每次枚举只需要单点修改两个位置即可

对于$x < 0$的情况，和上面的情况反过来后滑动窗口枚举即可

int n, k, x, a[N];

struct info
{
    int ans, pre, suf, sum;
    info(int a = 0, int b = 0, int c = 0, int d = 0) : ans(a), pre(b), suf(c), sum(d) {}
    friend info operator+(const info &a, const info &b)
    {
        info c;
        c.ans = max({a.ans, b.ans, a.suf + b.pre});
        c.pre = max(a.pre, a.sum + b.pre);
        c.suf = max(b.suf, a.suf + b.sum);
        c.sum = a.sum + b.sum;
        return c;
    }
};
struct SEG
{
    info val;
} seg[N << 2];

void up(int id) { seg[id].val = seg[lson].val + seg[rson].val; }
void build(int id, int l, int r)
{
    if (l == r)
    {
        seg[id].val = info(a[l], a[l], a[l], a[l]);
        return;
    }
    int mid = l + r >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    up(id);
}
void change(int id, int l, int r, int x, int val)
{
    if (l == r)
    {
        seg[id].val.ans += val;
        seg[id].val.pre += val;
        seg[id].val.suf += val;
        seg[id].val.sum += val;
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid)
        change(lson, l, mid, x, val);
    else
        change(rson, mid + 1, r, x, val);
    up(id);
}

void solve()
{
    cin >> n >> k >> x;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    build(1, 1, n);
    if (x == 0)
    {
        cout << max(0ll, seg[1].val.ans) << endl;
        return;
    }
    if (x > 0)
    {
        for (int i = 1; i <= k; ++i)
            change(1, 1, n, i, x);
        for (int i = k + 1; i <= n; ++i)
            change(1, 1, n, i, -x);
        int ans = seg[1].val.ans;
        for (int i = k + 1; i <= n; ++i)
        {
            change(1, 1, n, i - k, -2 * x);
            change(1, 1, n, i, 2 * x);
            ans = max(ans, seg[1].val.ans);
        }
        cout << max(0ll, ans) << endl;
    }
    else
    {
        x = -x;
        for (int i = 1; i <= n - k; ++i)
            change(1, 1, n, i, x);
        for (int i = n - k + 1; i <= n; ++i)
            change(1, 1, n, i, -x);
        int ans = seg[1].val.ans;
        for (int i = n - k + 1; i <= n; ++i)
        {
            change(1, 1, n, i - n + k, -2 * x);
            change(1, 1, n, i, 2 * x);
            ans = max(ans, seg[1].val.ans);
        }
        cout << max(0ll, ans) << endl;
    }
}

CF1779 D. Boris and His Amazing Haircut

题解

显然贪心的考虑，我们会从大到小的进行取$min$

一个显然的结论：如果存在$b[i] > a[i]$，那么$a$一定不可能变成$b$

所以我们不妨将每个$b[i]$离散化后，对每个$b[i]$开个$Vector$，里面存放所有$b[i] < a[i]$的位置

对于任意两个位置$i, j$来说，如果$[i , j]$之间出现$x > b[i]$，那么修改次数一定会 $+ 1$，所以利用$st$表查询最大值即可

然后对于每个$b[i]$，检查修改次数是否小于给定的修改次数即可

int n, q, a[N], b[N], st[N][22], lg2[N];
map<int, int> mp;
vector<int> vec[N];

void build()
{
    for (int i = 1; i <= n; ++i)
        st[i][0] = b[i];
    for (int i = 2; i <= n; ++i)
        lg2[i] = lg2[i >> 1] + 1;
    for (int j = 1; j <= 20; ++j)
        for (int i = 1; i + (1ll << j) - 1 <= n; ++i)
            st[i][j] = max(st[i][j - 1], st[i + (1ll << (j - 1))][j - 1]);
}
int query(int l, int r)
{
    int len = lg2[r - l + 1];
    return max(st[l][len], st[r - (1ll << len) + 1][len]);
}

void solve()
{
    mp.clear();
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    vector<int> nums;
    bool ok = true;
    for (int i = 1; i <= n; ++i)
    {
        cin >> b[i];
        if (b[i] > a[i])
            ok = false;
        nums.push_back(b[i]);
    }
    cin >> q;
    for (int i = 1; i <= q; ++i)
    {
        int x;
        cin >> x;
        mp[x]++;
    }
    if (!ok)
    {
        cout << "NO" << endl;
        return;
    }
    sort(all(nums));
    nums.erase(unique(all(nums)), nums.end());
    for (int i = 1; i <= n; ++i)
        b[i] = lower_bound(all(nums), b[i]) - nums.begin() + 1;
    build();
    int m = (int)nums.size();
    for (int i = 1; i <= m; ++i)
        vec[i].clear();
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] > nums[b[i] - 1])
            vec[b[i]].push_back(i);
    }
    for (int i = 1; i <= m; ++i)
    {
        // cerr << i << endl;
        if (vec[i].empty())
            continue;
        int cnt = 0;
        for (int j = 0; j < (int)vec[i].size() - 1; ++j)
        {
            int l = vec[i][j], r = vec[i][j + 1];
            // cerr << l << " " << r << " " << nums[i - 1] << endl;
            if (query(l, r) > i)
                cnt++;
        }
        cnt++;
        if (!mp.count(nums[i - 1]) || mp[nums[i - 1]] < cnt)
        {
            cout << "NO" << endl;
            // cerr << "cnt = " << cnt << endl;
            return;
        }
    }
    cout << "YES" << endl;
}

CF1748 C. Zero-Sum Prefixes

题解

我们定义$pre[i] = a[1] + a[2] + ... + a[i]$

显然对于$i,j,i < j, a[i] = 0, a[j] = 0$来说，我们在$a[i]$位置上$+x$对$pre[i]$的影响，可以在$a[j]$处$-x$抵消掉，所以我们贪心的考虑每一段由$0$分开的区间之间，出现次数最多的$pre[i]$就是我们可以使其变为$0$的前缀，利用$map$记录次数即可

int n, a[N], pre[N];

void solve()
{
    cin >> n;
    a[n + 1] = 0;
    vector<int> vec;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        if (a[i] == 0)
            vec.push_back(i);
    }
    vec.push_back(n + 1);
    for (int i = 1; i <= n; ++i)
        pre[i] = pre[i - 1] + a[i];
    int ans = 0;
    for (int i = 1; i < vec.front(); ++i)
        if (pre[i] == 0)
            ans++;
    for (int i = 0; i < (int)vec.size() - 1; ++i)
    {
        int l = vec[i], r = vec[i + 1];
        map<int, int> mp;
        int mx = 0;
        for (int j = l; j < r; ++j)
        {
            mp[pre[j]]++;
            mx = max(mx, mp[pre[j]]);
        }
        // cerr << l << " " << r << endl;
        ans += mx;
    }
    cout << ans << endl;
}