联合省选2021 A卷

不想写游记，没啥可写的，写写题解算了

D1T1 卡牌游戏

考虑到翻肯定翻最大最小值才能有效，那我们如果把所有值不分 $a,b$ 面升序排序就是删去一段前后缀使得剩下的极差最大

有额外限制是不能删除超过 $m$ 个数字，$a,b$ 不能一起删

直接用双指针维护删到哪就行 复杂度 $O(n\log n)$

这题适合有梦想的选手，直接输出所有数最大-最小就能过官方数据

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 2e6 + 10;
typedef long long ll;
struct Data {
    ll val;
    int id, v;
    friend bool operator<(const Data &A, const Data &B) {
        return A.val < B.val;
    }
} a[N];
int n, m;
bool used[N];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].val;
        a[i].v  = 1;
        a[i].id = i;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i + n].val;
        a[i + n].id = i;
    }
    sort(a + 1, a + 1 + 2 * n);
    ll l = 0, r = n * 2 + 1, now = 0;
    while (!used[a[l + 1].id] && now + a[l + 1].v <= m) {
        now += a[l + 1].v;
        used[a[l + 1].id] = 1;
        l++;
    }
    while (!used[a[r - 1].id] && now + a[r - 1].v <= m) {
        now += a[r - 1].v;
        used[a[r - 1].id] = 1;
        r--;
    }
    ll ans = 2e18;
    while (l >= 0) {
        ans           = min(a[r - 1].val - a[l + 1].val, ans);
        used[a[l].id] = 0;
        now -= a[l--].v;
        while (!used[a[r - 1].id] && now + a[r - 1].v <= m) {
            now += a[r - 1].v;
            used[a[r - 1].id] = 1;
            r--;
        }
    }
    cout << ans << endl;
    return 0;
}

D1T2 矩阵游戏

构造并不是很麻烦的部分，其实也不难想，主要是处理 $0 \le a_{i,j} \le 10^6$ 的限制

考虑如果把所有的条件写成一个巨大的方程组，会发现有右下最外边的一圈是自由元，那我们钦定右下一行一列就可以递推了

然后就是怎么把这个推出来的 $a_{i,j}$ 改成合适的范围

发现对一行分别 $+x,-x,+x,-x\dots$ 的操作是不变的，一列同理

那么设 $c_i$ 是第 $i$ 列的调整量 $r_i$ 是对 $i$ 行的调整量

那么他们的改边量矩阵是

$$\begin{bmatrix} \begin{array}{c} r_1+c_1 & -r_1+c_2 & r_1+c_3 & \dots \\\\ r_2-c_1 & -r_2-c_2 & r_2-c_3 & \dots \\\\ \vdots & \vdots & \vdots & \ddots \\\\ \end{array} \end{bmatrix}$$

每个位置需要满足 $ -a_{i,j} \le r_i \pm c_j\le10^6 -a_{i,j}$

虽然减法差分约束能做，但是和的形式好像不大好搞

试着类似黑白染色的取反

即

$$\begin{bmatrix} \begin{array}{c} \mathrm{+} & - & + & - \\\\ \mathrm{-} & + & - & + \\\\ \mathrm{+} & - & + & - \\\\ \mathrm{-} & + & - & + \\\\ \end{array} \end{bmatrix}$$

显然这样也是不变的

那原矩阵都会是 $x-y$ 的形式，即

$$\begin{bmatrix} \begin{array}{c} r_1-c_1 & c_2-r_1 & r_1-c_3 & \dots \\\\ c_1-r_2 & r_2-c_2 & c_3-r_2 & \dots \\\\ \vdots & \vdots & \vdots & \ddots \\\\ \end{array} \end{bmatrix}$$

就可以差分约束了

边很多，但卡不满

然而我连钦定自由元都没想到

#include <cstring>
#include <deque>
#include <iostream>
using namespace std;
const int N   = 605;
const int MAX = 1e6;
int T;
int b[N][N];
int a[N][N];
int n, m;
struct Edge {
    int v;
    int w, nxt;
} edge[N * N * 2];
int head[N * N * 2], ecnt;
void init() {
    memset(a, 0, sizeof(a));
    memset(head, 0, sizeof(head));
    ecnt = 0;
}
void add(int u, int v, int w) {
    edge[++ecnt].v = v;
    edge[ecnt].w   = w;
    edge[ecnt].nxt = head[u];
    head[u]        = ecnt;
}
long long dis[N * 2];
int cnt[N * 2];
bool vis[N * 2];
bool spfa() {
    deque<int> q;
    memset(cnt, 0, sizeof(cnt));
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x7f, sizeof(dis));
    dis[1] = 0;
    q.push_back(1);
    while (!q.empty()) {
        int x = q.front();
        q.pop_front();
        ++cnt[x];
        vis[x] = 0;
        if (cnt[x] > n + m) {
            return false;
        }
        for (int i = head[x]; i; i = edge[i].nxt) {
            int v = edge[i].v;
            if (dis[v] > dis[x] + edge[i].w) {
                dis[v] = dis[x] + edge[i].w;
                if (!vis[v]) {
                    if (!q.empty() && dis[v] < dis[q.front()]) {
                        q.push_front(v);
                    } else {
                        q.push_back(v);
                    }
                    vis[v] = 1;
                }
            }
        }
    }
    return true;
}
int main() {
    cin >> T;
    while (T--) {
        init();
        cin >> n >> m;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                cin >> b[i][j];
            }
        }
        for (int i = n; i >= 1; i--) {
            for (int j = m; j >= 1; j--) {
                a[i][j] = b[i][j] - a[i + 1][j] - a[i + 1][j + 1] - a[i][j + 1];
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if ((i + j) & 1) {
                    add(i, j + n, MAX - a[i][j]);
                    add(j + n, i, a[i][j]);
                } else {
                    add(i, j + n, a[i][j]);
                    add(j + n, i, MAX - a[i][j]);
                }
            }
        }
        if (!spfa()) {
            cout << "NO" << endl;
            continue;
        } else {
            cout << "YES" << endl;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if ((i + j) & 1) {
                        a[i][j] -= dis[i];
                        a[i][j] += dis[j + n];
                    } else {
                        a[i][j] += dis[i];
                        a[i][j] -= dis[j + n];
                    }
                    cout << a[i][j] << " ";
                }
                cout << endl;
            }
        }
    }
    return 0;
}

D1T3 图函数

$f(i,G)$ 就是 $[1,i]$ 这段点里满足 $i \rightarrow x$ 联通且 $x \rightarrow i$ 联通的 $x$ 的个数

发现其实条件就是 存在有 $i \rightarrow x$ 和 $x \rightarrow i$ 的路径不经过 $[1,x)$ 中的点

证明只要口胡下就行，如果存在 $i\rightarrow y \rightarrow x \ (y \in [1,x)$ 的路径且 $i,x$ 双向联通那 $y$ 就被删了

设 $[i,x]$ 代表满足 $i,x$ 双向联通

那么我们要求的就是当前的 $G$ 的 $\sum\limits_{u,v \in G}[u,v]$

删边不太好做，反向加边

随着边增加满足条件的点对必然增大，仅需求出增量然后前缀和就行，也就是找到每个点对最早满足条件的时间

这种转移直接 Floyd 即可

复杂度 $O(n^3+m)$，虽然看起来稳 T 但是能过…

不知道有没有复杂度靠谱的算法

#include <iostream>
using namespace std;
const int N = 1005;
int G[N][N];
int tim[N * N];
int n, m, ans[N * N];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        G[u][v] = i;
    }
    for (int k = n; k >= 1; k--) {
        for (int i = k + 1; i <= n; i++) {
            tim[min(G[k][i], G[i][k])]++;
        }
        for (int i = 1; i <= n; i++) {
            if (!G[i][k]) {
                continue;
            }
            int nowid = G[i][k];
            if (i > k) {
                for (int j = 1; j < k; j++) {
                    G[i][j] = max(G[i][j], min(nowid, G[k][j]));
                }
            } else {
                for (int j = 1; j <= n; j++) {
                    G[i][j] = max(G[i][j], min(nowid, G[k][j]));
                }
            }
        }
    }
    ans[m + 1] = n;
    for (int i = m; i >= 1; i--) {
        ans[i] = ans[i + 1] + tim[i];
    }
    for (int i = 1; i <= m + 1; i++) {
        cout << ans[i] << " ";
    }
    return 0;
}

D2T1 宝石

概括下题意就是找到 $ u \rightarrow v$ 路径上最长的连续子序列，只需要按照给出个排列 $p$ 编号即可

先考虑链上的做法，发现可以倍增处理

因为对当前有贡献的只能是下一个数，所以按后继倍增，正反跑就行

而树上的做法先套路成 $u\rightarrow lca$ $lca \rightarrow v$

$u \rightarrow lca$ 仍然可以倍增处理，而下行段考虑记录前驱倍增，如果倍增到当前前驱深度大于 $lca$ 就是一个可行解

然后发现答案是满足单调性的，于是可以二分

复杂度 $O(n \log^2n)$

题很不错，就是人菜

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
int n, m, c;
const int N = 2e5 + 10;
int p[N], id[N], w[N];
struct Edge {
    int v;
    int nxt;
} edge[N * 2];
int head[N], ecnt;
int lca[N];
void add(int u, int v) {
    edge[++ecnt].v = v;
    edge[ecnt].nxt = head[u];
    head[u]        = ecnt;
}
int fa[N][21], dep[N];
void pre(int x,int f) {
    fa[x][0] = f;
    dep[x]   = dep[f] + 1;
    for (int i = 1; i <= 19; i++) {
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    }
    for (int i = head[x]; i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (v == f) {
            continue;
        }
        pre(v, x);
    }
}
int getLCA(int u, int v) {
    if (dep[u] < dep[v]) {
        swap(u, v);
    }
    for (int i = 19; i >= 0; i--) {
        if (dep[fa[u][i]] >= dep[v]) {
            u = fa[u][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = 19; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}
vector<int> up[N], down[N];
int updep[N][21], ans[N];
int last[N];
void qup(int x) {
    int p            = last[w[x]];
    last[w[x]]       = dep[x];
    updep[dep[x]][0] = last[w[x] + 1];
    for (int i = 1; i <= 19; i++) {
        updep[dep[x]][i] = updep[updep[dep[x]][i - 1]][i - 1];
    }
    for (auto d : up[x]) {
        int x = last[1];
        if (x < dep[lca[d]]) {
            continue;
        }
        ++ans[d];
        for (int i = 19; i >= 0; i--) {
            if (updep[x][i] >= dep[lca[d]]) {
                ans[d] += (1 << i);
                x = updep[x][i];
            }
        }
    }
    for (int i = head[x]; i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (v != fa[x][0]) {
            qup(v);
        }
    }
    last[w[x]] = p;
}
void qdown(int x) {
    int p            = last[w[x]];
    last[w[x]]       = dep[x];
    updep[dep[x]][0] = last[w[x] - 1];
    for (int i = 1; i <= 19; i++) {
        updep[dep[x]][i] = updep[updep[dep[x]][i - 1]][i - 1];
    }
    for (auto d : down[x]) {
        int l = ans[d] + 1, r = c, res = ans[d];
        while (l <= r) {
            int mid = (l + r) / 2;
            int x = last[mid], cnt = mid - ans[d] - 1;
            for (int i = 19; i >= 0; i--) {
                if ((1 << i) & cnt) {
                    x = updep[x][i];
                }
            }
            if (x > dep[lca[d]]) {
                res = mid;
                l   = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        ans[d] = res;
    }
    for (int i = head[x]; i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (v != fa[x][0]) {
            qdown(v);
        }
    }
    last[w[x]] = p;
}
int main() {
    cin >> n >> m >> c;
    for (int i = 1; i <= c; i++) {
        cin >> p[i];
        id[p[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        w[i] = id[w[i]];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dep[1] = 1;
    pre(1, 0);
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int u, v;
        cin >> u >> v;
        lca[i] = getLCA(u, v);
        up[u].push_back(i);
        down[v].push_back(i);
    }
    memset(updep, 0, sizeof(updep));
    qup(1);
    qdown(1);
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

D2T2 滚榜

数据范围就把状压拍脸上了

考虑对一个排列 $\pi$ ，贪心的分配使得 $b_i$ 尽可能小即可

具体来说若 $\pi_i>\pi_{i-1}$ 那因为 $b_i$ 不降就取 $b_{i-1}$ 否则取 $b_i=b_{i-1}+\pi_{i-1}-\pi_i$ （还需要考虑下分数相同标号小的放前面）

dp 是 $f[S][i][j]$ 表示状态为 $S$ 上一个人是 $i$ 当前用掉了 $j=\sum b_i$

可以发现 $\sum b_i=\sum\max(\pi_{i-1}-\pi_i,0)(n-i+1)$

枚举状态时枚举下一个人

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 13, M = 500;
int n, m, S, a[N + 1], id[1 << N | 1];
long long dp[(1 << N) + 1][N + 1][M + 1];
int lowbit(int x) {
    return x & (-x);
}
int mmax = -1, maxid;
int main() {
    cin >> n >> m;
    S = (1 << n) - 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] > mmax) {
            mmax  = a[i];
            maxid = i;
        }
        id[1 << (i - 1)] = i;
    }
    for (int i = 1; i <= n; i++) {
        int v = n * (mmax - a[i] + (maxid < i));
        if (v <= m) {
            dp[1 << (i - 1)][i][v] = 1;
        }
    }
    for (int i = 1; i < S; i++) {
        int cnt = __builtin_popcount(i);
        for (int t = i; t; t -= lowbit(t)) {
            for (int sum = 0; sum <= m; sum++) {
                int pos = id[lowbit(t)];
                for (int j = 1; j <= n; ++j) {
                    if ((i & (1 << (j - 1)))) {
                        continue;
                    } else {
                        int v =
                            sum + (n - cnt) * max(0, (pos < j) + a[pos] - a[j]);
                        if (v <= m) {
                            dp[i | (1 << (j - 1))][j][v] += dp[i][pos][sum];
                        }
                    }
                }
            }
        }
    }
    long long ans = 0;
    for (int i = 0; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            ans += dp[S][j][i];
        }
    }
    cout << ans;
    return 0;
}

D2T3 支配

显然支配关系会构成一个树，假如我们通过奥妙重重的方法拿到了这个树

考虑加入边 $(u,v)$ 的影响，可以发现若 $x$ 的受支配集变化当且仅当 $fa_x$ 的受支配集变化或者 $fa_x$ 不支配 $x$

直接枚举点判断，从根节点向下找虽然也行，不过按 $bfs$ 序更好写

建树可以用 $O(n^2)$ 的算法，也就是枚举每个点删除后 $1$ 到其他点的连通性即可

总复杂度 $O(n^2+qn)$

虽然用优秀的 $O(n)$ 支配树建法可以不动脑子的过本题…?

#include <iostream>
#include <queue>
using namespace std;
const int N = 3005;
struct Graph {
    struct Edge {
        int v;
        int nxt;
    } edge[N * 2];
    int head[N], ecnt;
    void add(int u, int v) {
        edge[++ecnt].v = v;
        edge[ecnt].nxt = head[u];
        head[u]        = ecnt;
    }
} G, rG;
int n, m, q;
bool dom[N][N], qaq[N][N];
int in[N], fa[N], id[N];
void build() {
    for (int i = 1; i <= n; i++) {
        dom[1][i] = 1;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= n; j++) {
            dom[i][j] = 1;
        }
        queue<int> q;
        q.push(1);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (int _i = G.head[x]; _i; _i = G.edge[_i].nxt) {
                int v = G.edge[_i].v;
                if (dom[i][v] && (i != v)) {
                    dom[i][v] = 0;
                    q.push(v);
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            in[j] += dom[i][j];
        }
    }
    queue<int> q;
    q.push(1);
    static int que[N], head;
    que[++head] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (dom[x][i]) {
                --in[i];
                if (in[i] == 1) {
                    fa[i] = x;
                    q.push(i);
                    que[++head] = i;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        id[i] = que[i];
    }
    for (int i = 2; i <= n; i++) {
        queue<int> q;
        q.push(i);
        qaq[i][i] = 1;
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (int j = rG.head[x]; j; j = rG.edge[j].nxt) {
                int v = rG.edge[j].v;
                if (!qaq[i][v] && (v != fa[i])) {
                    qaq[i][v] = 1;
                    q.push(v);
                }
            }
        }
    }
}
int main() {
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G.add(u, v);
        rG.add(v, u);
    }
    build();
    while (q--) {
        static bool vis[N];
        int a, b;
        scanf("%d%d", &a, &b);
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            vis[id[i]] =
                ((!dom[fa[id[i]]][a] && qaq[id[i]][b]) || (vis[fa[id[i]]]));
            ans += vis[id[i]];
        }
        cout << ans << endl;
    }
    return 0;
}

额外内容

当然是HE下午的特色FJOI2021加试，然而除了T3啥也不会