251225 模拟赛

T1

有 \(n\) 个位置，初始所有位置都未被标记。有 \(k\) 个操作，第 \(i\) 个操作为：若位置 \(m_i\) 未被标记，则标记位置 \(l_i\sim r_i\)，保证 \(l_i\le m_i\le r_i\)。

判断能否为这 \(n\) 个操作确定顺序，使得所有 \(n\) 个位置都被标记。

\(\sum n,k\le 5\times 10^5\)

肯定是最终操作一个集合的操作。然后发现只要集合中的操作没有交叉就是合法的，这个限制容易使用线段树优化 dp 完成。时间复杂度 \(O(n+k\log n)\)。

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e5 + 10;

struct myPair {
    int l, r, p;
    inline bool operator<(const myPair &b) const {
        return p < b.p;
    }
} a[N];

int T, n, k;

namespace SegT {
    int mn[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    void build(int p, int l, int r) {
        mn[p] = N;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
    }
    void insert(int p, int l, int r, int q, int v) {
        mn[p] = min(mn[p], v);
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(q <= mid) insert(lc(p), l, mid, q, v);
        else insert(rc(p), mid + 1, r, q, v);
    }
    int query(int p, int l, int r, int ql, int qr) {
        if(ql > qr) return N;
        if(ql <= l && r <= qr) return mn[p];
        int mid = (l + r) >> 1, res = N;
        if(ql <= mid) res = min(res, query(lc(p), l, mid, ql, qr));
        if(mid < qr) res = min(res, query(rc(p), mid + 1, r, ql, qr));
        return res;
    }
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;
    while(T--) {
        cin >> n >> k;
        SegT::build(1, 1, n);
        for(int i = 1; i <= k; i++) cin >> a[i].l >> a[i].p >> a[i].r;
        sort(a + 1, a + 1 + k);
        for(int i = 1; i <= k; i++) {
            if(a[i].l == 1) SegT::insert(1, 1, n, a[i].r, a[i].p);
            else {
                if(SegT::query(1, 1, n, a[i].l - 1, a[i].p - 1) != N || SegT::query(1, 1, n, a[i].p, a[i].r - 1) < a[i].l) {
                    SegT::insert(1, 1, n, a[i].r, a[i].p);
                }
            }
        }
        if(SegT::query(1, 1, n, n, n) != N) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}

T2

给定一个 \(n\) 个点的竞赛图，并且 \(\forall i<j\)，有一条 \(i\to j\) 的边，否则没有。

现在断掉若干条边，使得图中恰好有 \(k\) 个点满足存在一条从节点 \(1\) 到节点 \(n\) 的路径经过了该节点。对于 \(0\sim n\) 的每个 \(k\) 求出断边的方案数，对给定的质数 \(P\) 取模。

\(n\le 5000\)

先考虑求出 \(k=n\) 的答案，发现合法的充要条件是每个点都至少有一条出边和入边，除了 \(1\) 和 \(n\)。发现只有入边或者出边的限制是好做的。于是我们令每个节点都有一条入边，然后对没有出边的节点进行容斥，容易做到 \(O(n^2)\)。

然后考虑对任意的 \(k\) 求答案。将不合法的节点分为两类：能被 \(1\) 到达的和不能被 \(1\) 到达的。发现连边的限制特别简单，可以通过两次归并 dp 完成。时间复杂度 \(O(n^2)\)。

代码

#include<iostream>
#define int long long
using namespace std;
const int N = 5010;
int MOD;

inline void add(int &a, int b) { a += b; (a >= MOD) && (a -= MOD); }

int n;
int pw2[N];
int dp[N][N], pd[N][N], f[N], g[N];

signed main() {

    cin >> n >> MOD;

    pw2[0] = 1;
    for(int i = 1; i < N; i++) pw2[i] = pw2[i - 1] * 2 % MOD;

    dp[1][0] = 1;
    for(int i = 2; i <= n; i++) {
        for(int j = 0; j <= i - 1; j++) {
            add(dp[i][j], dp[i - 1][j] * (pw2[i - 1 - j] - 1) % MOD);
            add(dp[i][j + 1], dp[i - 1][j] * (pw2[i - 1 - j] - 1) % MOD);
        }
    }
    for(int i = 2; i <= n; i++) {
        for(int j = 0; j <= i; j += 2) {
            add(f[i], dp[i - 1][j] * (pw2[i - 1 - j] - 1) % MOD);
        }
        for(int j = 1; j <= i; j += 2) {
            add(f[i], MOD - dp[i - 1][j] * (pw2[i - 1 - j] - 1) % MOD);
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= n; j++) {
            dp[i][j] = 0;
        }
    }
    dp[1][0] = 1;
    for(int i = 2; i <= n; i++) {
        for(int j = 0; j < i - 1; j++) {
            add(dp[i][j], dp[i - 1][j]);
            add(dp[i][j + 1], dp[i - 1][j] * (pw2[i - 1] - 1) % MOD);
        }
    }
    pd[1][0] = 1;
    for(int i = 2; i <= n; i++) {
        for(int j = 0; j < i - 1; j++) {
            add(pd[i][j], pd[i - 1][j]);
            add(pd[i][j + 1], pd[i - 1][j] * pw2[i - 1] % MOD);
        }
    }
    for(int i = 2; i <= n; i++) {
        int ans = 0;
        for(int j = 0; i + j <= n; j++) {
            int tmp = dp[i + j - 1][j] * f[i] % MOD;
            add(ans, tmp * pd[n - 1][n - i - j] % MOD);
        }
        if(i == 2) cout << ans << ' ' << 0 << ' ';
        cout << ans << ' ';
    }
    cout << '\n';

    return 0;
}