杂题合集 II

whk 马上补上来了，开始复健 OI。

不是自己想出来的的题打了星号。

CF773E Blog Post Rating

假 *3000，真 *800 题。

考虑怎样操作使得评分最大。使用 Exchange Argument 后容易发现将 \(a_i\) 从小到大排序后依次操作就是最优方案。

具体而言，考虑一个逆序对 \((a_i, a_j)\) 满足 \(i < j, a_i > a_j\)，且当前评分为 \(x\)；那么若 \(a_i, a_j\) 对 \(x\) 的贡献同号，则交换后没有影响；如果 \(a_i, a_j\) 对 \(x\) 的贡献异号（此时 \(a_i\) 贡献必为 \(+1\)，\(a_j\) 贡献必为 \(-1\)），则交换后 \(a_j\) 的贡献有可能变为 \(0\)。如果初始时 \(a_i, a_j\) 中有贡献为 \(0\) 的元素，也是同理进行分类讨论，即可证明该结论。

因为每次操作只会使得 \(x\) 增加 \(1\) 或 \(-1\)，所以 \(x\) 的图像必然为一个 V 字形，先变小，后增大。

我们考虑找到这个 V 字形的拐点。如果 \(y\) 要成为拐点，那么必须成为第一个满足 \(-\operatorname{pre}(y) \le y\) 的元素。其中 \(\operatorname{pre}(y)\) 表示 \(\le y\) 的元素个数。

移项后发现条件变为 \(y+\operatorname{pre}(y) \ge 0\)，这个条件可以使用权值线段树维护。查询的时候直接在线段树上二分即可。

知道拐点后，剩余的部分一定单调不降，我们只需要考虑相同的 \(a_i\) 使得 \(x\) 一直卡在一个地方的情况：

如果 \(x\) 没有在 \(a_i\) 处被卡住，那么 \(a_i\) 对 \(x\) 无限制。
如果 \(x\) 在 \(a_i\) 处被卡住，那么最终的结果必然满足 \(\mathrm{ans} \le a_i + k - i\)。把含 \(i\) 的项提出来后变为 \(k + \min\{a_i - i\}\) 的形式，依然可以使用权值线段树维护区间最小值。

时间复杂度 \(O(n\log n)\)。求排名部分可以使用 pbds 的平衡树或者直接上 BIT 维护。

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc (p << 1)
#define rc ((p << 1) | 1)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
typedef tree<pi, null_type, less<pi>, rb_tree_tag, tree_order_statistics_node_update> RBT;
RBT tr_2;
int trcnt = 0;
int getrk(int x)
{
    return (tr_2.order_of_key({x + 1, 0}));
}
const int N = 1e6 + 20, PY = 5e5 + 5, inf = 0x3f3f3f3f;
struct Node{
    int l, r;
    int mn, sm, tag;
};
struct Segtree{
    Node tr[4 * N];
    void pushup(int p)
    {
        tr[p].mn = min(tr[lc].mn, tr[rc].mn);
        tr[p].sm = tr[lc].sm + tr[rc].sm;
    }
    void pushdown(int p)
    {
        if(tr[p].tag)
        {
            tr[lc].tag += tr[p].tag;
            tr[rc].tag += tr[p].tag;
            tr[lc].mn += tr[p].tag;
            tr[rc].mn += tr[p].tag;
        }
        tr[p].tag = 0;
    }
    void build(int p, int ln, int rn)
    {
        tr[p] = {ln, rn, rn, 0};
        if(ln == rn) return;
        int mid = (ln + rn) >> 1;
        build(lc, ln, mid);
        build(rc, mid + 1, rn);
        pushup(p);
    }
    void update(int p, int pos)
    {
        if(tr[p].l == pos && tr[p].r == pos)
        {
            tr[p].sm++;
            return;
        }
        pushdown(p);
        int mid = (tr[p].l + tr[p].r) >> 1;
        if(pos <= mid) update(lc, pos);
        else update(rc, pos);
        pushup(p);
    }
    void update2(int p, int ln, int rn)
    {
        if(ln <= tr[p].l && tr[p].r <= rn)
        {
            tr[p].mn--;
            tr[p].tag--;
            return;
        }
        pushdown(p);
        int mid = (tr[p].l + tr[p].r) >> 1;
        if(ln <= mid) update2(lc, ln, rn);
        if(rn >= mid + 1) update2(rc, ln, rn);
        pushup(p);
    }
    int getmn(int p, int ln, int rn)
    {
        if(ln <= tr[p].l && tr[p].r <= rn) return tr[p].mn;
        pushdown(p);
        int mid = (tr[p].l + tr[p].r) >> 1;
        if(rn <= mid) return getmn(lc, ln, rn);
        if(ln >= mid + 1) return getmn(rc, ln, rn);
        return min(getmn(lc, ln, rn), getmn(rc, ln, rn));
    }
    int binary(int p, int &pre)
    {
        int l = tr[p].l, r = tr[p].r, sm = tr[p].sm;
        if(r + pre + sm < 0)
        {
            pre += sm;
            return -inf;
        }
        if(l == r) return l;
        pushdown(p);
        int res = binary(lc, pre);
        if(res != -inf) return res;
        return binary(rc, pre);
    }
} tr_1;
int n, a[N];
void solve(int k)
{
    int tmp = 0;
    int p = tr_1.binary(1, tmp);
    if(p == -inf)
    {
        cout << -k << "\n";
        return;
    }
    int s = getrk(p - 1);
    int ans = min(k + tr_1.getmn(1, p, PY), k - 2 * s);
    cout << ans << "\n";
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    tr_1.build(1, -PY, PY);
    for(int i = 1; i <= n; i++)
    {
        tr_2.insert({a[i], ++trcnt});
        tr_1.update(1, a[i]);
        tr_1.update2(1, a[i], PY);
        solve(i);
    }
    return 0;
}

P7032 [NWRRC 2016] Boys and Girls

细节一车，调了一个下午。正赛要是出这种题我就原地爆炸了。

Sol.1 暴力构造

自己乱捣鼓出的做法，细节一车，很难写。

考虑容斥原理求出两边一男一女的人数 \(z\)，可知 \(z = x+y - n\)。

我们尝试刻画这个“两边一男一女”的结构 \(\texttt{0X1}, \texttt{1X0}\)，容易发现 \(\texttt{X}\) 无论是 \(\texttt{0}\) 还是 \(\texttt{1}\)，必然形成一个长度至少为 \(2\) 的连续段。

而对于一个长度至少为 \(2\) 的连续段而言，对 \(z\) 的贡献必然为 \(2\)（头和尾各贡献一次）。

因此必然有 \(z = 2c\) 成立。其中 \(c\) 为序列中长度至少为 \(2\) 的连续段个数。为了方便构造，我们强制把长度大于 \(2\) 的连续段，全部缩小为长度恰好为 \(2\) 的连续段。之后如果需要延长的话直接在连续段中间插入相同字符即可。

于是问题被转化为：需要构造一个 \(\texttt{01}\) 串，初始时由 \(c\) 个长度恰好为 \(2\) 的连续段构成，接下来可以进行下列操作：

在连续段中间插入一个相同字符，延长连续段。
在两个连续段之间，插入一段 \(\texttt{01}\) 交替的字符串。

最后需要满足长度为 \(n\)，且 \(\texttt{0X0}\) 的结构有 \(x - z\) 个，\(\texttt{1X1}\) 的结构有 \(y - z\) 个。

发现一种便于构造的结构：左侧是若干个颜色不同的连续段（长度至少为 \(2\)）拼在一起，而右边是一整段 \(\texttt{01}\) 交替的字符串。此时为了保证序列头尾的字符不同，需要对 \(c\) 的奇偶性进行分类讨论：

若 \(c\) 为偶数：
- 那么左侧连续段部分必然头尾颜色不同，例如 \(\texttt{001110011}\)。此时右边的交替段长度必然要为偶数，才能使得整个序列头尾颜色不同。例如 \(\texttt{001110011} + \texttt{0101}\)。
- 左侧连续段里，一个长度为 \(x\) 的连续段能贡献 \(x - 2\) 个 \(\texttt{0X0}\) 或 \(\texttt{1X1}\) 的结构。
- 右侧交替段里，一个长度为 \(2x\) 的交替段能贡献 \(x\) 个 \(\texttt{0X0}\) 和 \(x\) 个 \(\texttt{1X1}\) 结构。
- 这启示我们，可以在左侧连续段里，通过将连续段延长，把 \(x, y\) 里更大的那一个变小，直至 \(x = y\)。后面再利用交替段构造完剩下的即可。
若 \(c\) 为奇数：
- 左侧的连续段部分必然头尾颜色相同，例如 \(\texttt{001110001100}\)。此时右边的交替段长度必然要为奇数，才能使得整个序列头尾颜色不同。例如 \(\texttt{001110001100} + \texttt{10101}\)。
- 左侧连续段的贡献是同理的。
- 右侧交替段里，如果 \(\texttt{0}\) 更多，一个长度为 \(2x+1\) 的交替段能贡献 \(x+1\) 个 \(\texttt{1X1}\) 和 \(x\) 个 \(\texttt{0X0}\) 结构。而 \(\texttt{1}\) 更多时同理。
- 这启示我们，如果连续段里 \(\texttt{0}\) 的连续段更多（此时右侧交替段里 \(\texttt{1}\) 更多），可以在左侧连续段里，通过将连续段延长，把 \(x, y\) 里更大的那一个变小，直至 \(x = y + 1\)。后面再利用交替段构造完剩下的即可。

可以证明，其余的构造方式一定能转化为这种构造（具体我不会证明，但是我并没有找到反例）。因此上述流程如果遇到无法满足的，即为无解。

最后判掉一些特殊情况，例如 \(n = 2, x = 0, y = 0, z = 0\) 之类的 corner case 即可。时间复杂度 \(O(n)\)。为了不写更多特判，我在 \(n \le 10\) 的时候直接暴力求解方案。

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 1e5 + 10;
int n, x, y, z, a[N];
bool check()
{
    int cntx = 0, cnty = 0;
    if(n == 2)
    {
        if(a[1] == 0) cntx++;
        else cnty++;
        if(a[2] == 0) cntx++;
        else cnty++;     
        return (x == cntx && y == cnty);
    }
    for(int i = 2; i < n; i++)
    {
        if(a[i - 1] == 0 || a[i + 1] == 0) cntx++;
        if(a[i - 1] == 1 || a[i + 1] == 1) cnty++;
    }
    if(a[2] == 0 || a[n] == 0) cntx++;
    if(a[2] == 1 || a[n] == 1) cnty++;
    if(a[1] == 0 || a[n - 1] == 0) cntx++;
    if(a[1] == 1 || a[n - 1] == 1) cnty++;
    return (x == cntx && y == cnty);
}
void Construct3()
{
    for(int i = 1; i <= n; i++) a[i] = (i & 1);
    if(check())
    {
        for(int i = 1; i <= n; i++) cout << (a[i] ? 'G' : 'B');
        exit(0);
    }
    for(int i = 1; i <= n; i++) a[i] = ((i & 1) ^ 1);
    if(check())
    {
        for(int i = 1; i <= n; i++) cout << (a[i] ? 'G' : 'B');
        exit(0);
    }
    cout << "Impossible";
}
void Construct1()
{
    int cnt = 0;
    int ex_x = 0, ex_y = 0;
    if(x > y)
    {
        ex_x = x - y - 1;
        if((n - z - ex_x) & 1) ex_x++;
    }
    else if(y > x)
    {
        ex_y = y - x - 1;
        if((n - z - ex_y) & 1) ex_y++;        
    }
    a[++cnt] = 0; a[++cnt] = 0;
    while(ex_x--) a[++cnt] = 0;
    a[++cnt] = 1; a[++cnt] = 1;
    while(ex_y--) a[++cnt] = 1;
    z /= 2;
    z -= 2;
    while(1)
    {
        if(z == 0) break;
        z -= 2;
        a[++cnt] = 0; a[++cnt] = 0;
        a[++cnt] = 1; a[++cnt] = 1;
    }    
    for(int i = cnt + 1, j = 0; i <= n; i++, j ^= 1) a[i] = j;
    if(check())
    {
        for(int i = 1; i <= n; i++) cout << (a[i] ? 'G' : 'B');
        exit(0);
    }
    cout << "Impossible";
}
void Sub_Construct(int ax, int ay, int x, int y, int az)
{
    int cnt = 0;
    int ex_x = 0, ex_y = 0;
    if(x > y)
    {
        ex_x = x - y - 1;
        if((n - z - ex_x) % 2 == 0) return;
    }
    else if(y > x)
    {
        ex_y = y - x + 1;
        if((n - z - ex_y) % 2 == 0) return;
    }
    else
        ex_y++;
    az /= 2;
    if(az == 1)
    {
        if(ex_y) return;
        a[++cnt] = ax; a[++cnt] = ax;
        while(ex_x--) a[++cnt] = ax;
        az--;
    }
    else
    {
        a[++cnt] = ax; a[++cnt] = ax;
        while(ex_x--) a[++cnt] = ax;
        a[++cnt] = ay; a[++cnt] = ay;
        while(ex_y--) a[++cnt] = ay;
        az -= 2;
    }
    while(1)
    {
        if(az <= 1) break;
        az -= 2;
        a[++cnt] = ax; a[++cnt] = ax;
        a[++cnt] = ay; a[++cnt] = ay;
    }
    if(az >= 1) a[++cnt] = ax, a[++cnt] = ax;
    for(int i = cnt + 1, j = ay; i <= n; i++, j ^= 1) a[i] = j;
    if(check())
    {
        for(int i = 1; i <= n; i++) cout << (a[i] ? 'G' : 'B');
        exit(0);
    }    
}
void Construct2()
{
    Sub_Construct(0, 1, x, y, z);
    Sub_Construct(1, 0, y, x, z);
    cout << "Impossible";
}
void Brute()
{
    for(int i = 0; i < (1 << n); i++)
    {
        for(int j = 0; j < n; j++)
            a[j + 1] = ((i >> j) & 1);
        if(!check()) continue;
        for(int j = 1; j <= n; j++) cout << (a[j] ? 'G' : 'B');
        exit(0);
    }
    cout << "Impossible";
    exit(0);
}
int main()
{
    // freopen("P7032.in", "r", stdin);
    // freopen("P7032.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> x >> y;
    if(x + y < n)
    {
        cout << "Impossible";
        return 0;
    }
    if(x == 0)
    {
        for(int i = 1; i <= n; i++) a[i] = 1;
        if(!check()) cout << "Impossible";
        for(int i = 1; i <= n; i++) cout << (a[i] ? 'G' : 'B');
        return 0;
    }
    if(y == 0)
    {
        for(int i = 1; i <= n; i++) a[i] = 0;
        if(!check()) cout << "Impossible";
        for(int i = 1; i <= n; i++) cout << (a[i] ? 'G' : 'B');
        return 0;
    }
    if(n <= 10) Brute();
    z = x + y - n;
    if(z & 1)
    {
        cout << "Impossible";
        return 0;
    }
    if(z == 0) Construct3();
    else if((z / 2) % 2 == 0) Construct1();
    else Construct2();
    return 0;
}

Sol.2 图论转化

其他题解的做法，大概是把 \(\texttt{AXB}\) 的结构里，连边 \(A\leftrightarrow B\)，表示两者之间可以产生贡献。若 \(n\) 为奇数，那么连边后形成了一个环；否则形成两个点集不交的环。最后对两个环分别构造即可。

* AT_abc361_g [ABC361G] Go Territory

whk 学傻了，简单图论题都不会做了/ll。

如果 \(X, Y \le 10^3\)，那么直接从 \((-1, -1)\) 开始 BFS 就可以了。但是如果 \(X, Y\) 扩展到 \(2\times 10^5\)，就必须要根据网格图或者点数的特殊性质来简化建图。

具体而言，我们可以对每一行考虑，这一行上的若干个石子把整行分成了若干个连续段，而每个连续段内部是连通的，我们只需要对这些连续段进行 BFS 即可。

因为点数很小，只有 \(2\times 10^5\)，所以连续段也是 \(O(n)\) 量级的，可以进行 BFS。

最后只需要快速找到一个连续段可以到达的点即可，这个可以使用 set 维护，时间复杂度 \(O(n\log n)\)。

如果使用双指针将相邻两行连边，再 BFS / DSU 也可以做。要是题目保证了点是以有序的方式给出的，这种方式甚至可以做到线性。

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
using pii = pair<pi, int>;
const int N = 2e5 + 5;
set<pi> s[N];
vector<int> blk[N];
ll n, ans, cnt;
bool intersec(int al, int ar, int bl, int br)
{
    if(ar < bl || br < al) return 0;
    return 1;
}
int main()
{
    //freopen("sample.in", "r", stdin);
    //freopen("sample.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for(int i = 0; i < N; i++)
    {
        blk[i].push_back(-2);
        blk[i].push_back(N - 1);
    }
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        blk[y].push_back(x);
    }
    for(int i = 0; i < N; i++)
    {
        sort(blk[i].begin(), blk[i].end());
        for(int j = 1; j < blk[i].size(); j++)
        {
            int l = blk[i][j - 1] + 1, r = blk[i][j] - 1;
            if(l > r) continue;
            s[i].insert({r, l});
            ans += r - l + 1;
        }
    }
    queue<pii> q;
    q.push({{-1, N - 2}, -1});
    while(!q.empty())
    {
        pii u = q.front();
        q.pop();
        int y = u.se, xl = u.fi.fi, xr = u.fi.se;
        if(y + 1 < N)
        {
            auto it = s[y + 1].lower_bound({xl, -2});
            while(it != s[y + 1].end())
            {
                int vl = (*it).se, vr = (*it).fi;
                if(!intersec(xl, xr, vl, vr)) break;
                q.push({{vl, vr}, y + 1});
                ans -= vr - vl + 1;
                auto tmp = it;
                ++it;
                s[y + 1].erase(tmp);
            }
        }
        if(y - 1 >= 0)
        {
            auto it = s[y - 1].lower_bound({xl, -2});
            while(it != s[y - 1].end())
            {
                int vl = (*it).se, vr = (*it).fi;
                if(!intersec(xl, xr, vl, vr)) break;
                q.push({{vl, vr}, y - 1});
                ans -= vr - vl + 1;
                auto tmp = it;
                ++it;
                s[y - 1].erase(tmp);
            }
        }
    }
    cout << ans;
    return 0;
}

P7986 [USACO21DEC] HILO P

比较有趣的题。

Sol.1 排列 DP

\(O(n^2)\) 的做法是平凡的，我们先研究有效询问的性质。

容易发现，一个询问是有效询问，当且仅当它缩小了上界或者下界。而上界必然 \(> x\)，下界必然 \(\le x\)，这启示我们对上界、下界分别进行研究。

继续观察，发现所有出现过的上界组成了一个单调下降的序列。同理，所有出现过的下界也组成了一个单调上升的序列。

由于这是个排列，我们可以使用排列 DP 的经典套路：插入法。具体而言，定义 \(dp_{i, j, 0/1}\) 表示排列中已经出现了 \(i\) 个 \(> x\) 的元素，\(j\) 个 \(\le x\) 的元素，且上一次有效询问缩小的是上界还是下界。

在转移的过程中，我们先枚举它是大于 \(x\) 还是小于等于 \(x\)，然后再确定它在 \(> x\) 或 \(\le x\) 中已插入元素的相对排名。如果相对排名最大 / 最小，则根据题目要求进行特殊转移即可。

转移的过程中需要分别记录方案数与计数总和。

时间复杂度 \(O(n^2)\)。

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
const int N = 5e3 + 10;
const ll mod = 1e9 + 7;
ll n, x;
inline void add(ll &a, ll b)
{
    a += b;
    if(a >= mod) a -= mod;
}
inline void upd(pl &a, pl b, int typ)
{
    add(a.fi, b.fi);
    if(typ == 2) add(b.se, b.fi);
    add(a.se, b.se);
}
pl mul(pl a, ll b)
{
    return {(a.fi * b) % mod, (a.se * b) % mod};
}
pl dp[N][N][2];
int main()
{
    //freopen("sample.in", "r", stdin);
    //freopen("sample.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> x;
    dp[0][0][0] = {1, 0};
    for(int i = 0; i <= n - x; i++)
    {
        for(int j = 0; j <= x; j++)
        {
            upd(dp[i + 1][j][1], dp[i][j][0], 1);
            upd(dp[i][j + 1][0], dp[i][j][0], 1);

            upd(dp[i + 1][j][1], dp[i][j][1], 1);
            upd(dp[i][j + 1][0], dp[i][j][1], 2);

            upd(dp[i + 1][j][0], mul(dp[i][j][0], i), 1);
            upd(dp[i][j + 1][0], mul(dp[i][j][0], j), 1);

            upd(dp[i + 1][j][1], mul(dp[i][j][1], i), 1);
            upd(dp[i][j + 1][1], mul(dp[i][j][1], j), 1);            
        }
    }
    cout << (dp[n - x][x][0].se + dp[n - x][x][1].se) % mod;
    return 0;
}

Sol.2 贡献法

暂时没有理解题解里 \(A_{n}^{n - j+\max\{i-1, 0\}}\) 的系数是怎么来的，到时候再来补。

posted @ 2026-03-22 00:50 KS_Fszha 阅读(8) 评论(0) 收藏举报

刷新页面返回顶部

Kruskal4668