~K Perm Counting

题目链接：https://atcoder.jp/contests/agc005/tasks/agc005_d

题目大意：求 1-n 的全排列中，不存在 $|a_i-i|==k$ 的个数

解题思路：考虑容斥原理，定义 $f(i)$ 表示全排列中至少存在 i 个 $|a_i-i|==k$ 的数量。那么答案就是 $\sum^{n}_{i=0}(-1)^{i-1}f(i)$

我们将其看成一个二分图，左边是 1-n 的编号，右边 1-n 的值，对于这样的式子 $|a_i-i|==k$ ，相当于 i 和 i+k 连一条边，最后会得到一些链，若是链上每相邻的两个点相连，则这样的式子数量就加一，但是任意两条边只能共用一个点，问题就转化成从里面选出 k 条边，任意两条边不共用一个点的方案数。我们考虑把所有的链合成一条链，然后在上面 DP 求解，注意原来不同链上的首尾节点相连是不会有贡献的，定义 $dp[i][j][0/1]$ 表示前 i 个数中已经连了 j 条边，且表示 i-1 和 i 是否连边。那么 DP 方程如下

1 2	`dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1]; if (vis[i] && j) dp[i][j][1] = dp[i - 1][j - 1][0];//判断是不是链头`

求出 DP 后， $f(i)=(dp[2*n][i][0]+dp[2*n][i][1])*(n-i)!$ ，然后用该式 $\sum^{n}_{i=0}(-1)^{i-1}f(i)$ 求解

int n, k;
int dp[4004][2002][2];
int fac[4004];
int vis[N << 5];
void solve() {
    cin >> n >> k;
    int tot = 0;
    fac[0] = 1;
    lep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
    lep(i, 1, n) {
        lep(t, 0, 1) {
            for (int j = i; j <= n; j += k) {
                tot++;
                if (i != j) vis[tot] = 1;
            }
        }
    }
    dp[0][0][0] = 1;
    lep(i, 1, 2 * n) {
        lep(j, 0, n) {
            dp[i][j][0] = (dp[i - 1][j][0] + dp[i - 1][j][1]) % mod;
            if (vis[i] && j) dp[i][j][1] = dp[i - 1][j - 1][0];
        }
    }
    int ans = 0;
    lep(i, 0, n) {
        if (i & 1)
            ans =
                (ans -
                 (dp[2 * n][i][0] + dp[2 * n][i][1]) % mod * fac[n - i] % mod +
                 mod) %
                mod;
        else
            ans =
                (ans +
                 (dp[2 * n][i][0] + dp[2 * n][i][1]) % mod * fac[n - i] % mod +
                 mod) %
                mod;
    }
    cout << ans << endl;
}

Sugigma: The Showdown

题目链接：https://atcoder.jp/contests/agc005/tasks/agc005_e

题目大意：两个人在树上游戏，有两颗树，红树和蓝树，先手只能在红树上移动，后手只能在蓝树上移动，起点分别在 x 和 y，每次只能走一步，如果两个人走到同一个点上则游戏结束，先手想要尽可能延长游戏的时间，后手想要尽快结束游戏，问双方都采取最佳行动，能持续多少回合

解题思路：先考虑 -1 的情况，如果红树上有一条边，边上的两个端点在蓝树的距离大于 2 ，那么先手在没有被后手抓到情况下到达了这两个端点之一，那么后手永远抓不到先手。否则先手为了延长时间，肯定会选择他能走的节点中， $dis(i,x)>dis(i,y)$ 的走，同时判断这个过程中有没有走到特殊边上，否则答案就是整个过程中最大深度*2

int n, x, y, flag, dep;
int f[N], dis[N];
vector<int> R[N], B[N];
void dfs_fa(int u, int fa) {
    f[u] = fa;
    for (auto v : B[u]) {
        if (v == fa) continue;
        dis[v] = dis[u] + 1;
        dfs_fa(v, u);
    }
}
void dfs(int u, int fa, int tim) {
    dep = max(dep, dis[u]);
    for (auto v : R[u]) {
        if (v == fa) continue;
        int a = f[u];
        int b = f[a];
        int c = f[v];
        int d = f[c];
        if (a == v || c == u || a == c || b == v || d == u) {
            if (dis[v] > tim) dfs(v, u, tim + 1);
        } else
            flag = 1;
    }
}
void solve() {
    cin >> n >> x >> y;
    flag = dep = 0;
    f[0] = n + 1;
    f[n + 1] = -1;
    lep(i, 2, n) {
        int u, v;
        cin >> u >> v;
        R[u].emplace_back(v);
        R[v].emplace_back(u);
    }
    lep(i, 2, n) {
        int u, v;
        cin >> u >> v;
        B[u].emplace_back(v);
        B[v].emplace_back(u);
    }
    dfs_fa(y, 0);
    dfs(x, 0, 1);
    if (flag)
        cout << -1 << endl;
    else
        cout << 2 * dep << endl;
}

Pushing Balls

题目链接：https://atcoder.jp/contests/agc007/tasks/agc007_c

题目大意：在一条直线上有 n+1 个洞，每两个洞之间有一个小球，每个小球与它相邻两个洞之间的距离组成一个序列，是一个首项为 d，公差为 x 的等差数列，每次随机选择一个没有入洞的小球，等概率的选择左右方向移动，直到入洞，求所有小球入洞后的移动总距离的期望值（每个洞只能放一个球，当洞里有球时，其他小球可以踩着它经过，直到落入某个空洞）

解题思路：可以看成有 2*n 段连续的区间，从中选择 n 个区间的期望总长度，一开始的长度序列为 d,d+x,d+2x,d+3x,…,d+2(n-1)x。选择一段区间的长度期望为 s(2n)/2n,然后序列会变成以下几种情况：

选择第一段区间，之后的区间会变成 d+2x,d+3x,d+4x,d+5x…。有1/2n 的概率
选择第二段区间，之后的区间会变成 3d+3x,d+3x,d+4x,d+5x…。有1/2n 的概率
选择第三段区间，之后的区间会变成 d,3d+6x,d+4x,d+5x…。有1/2n 的概率
选择第四段区间，之后的区间会变成 d,d+x,3d+9x,d+5x…。有1/2n 的概率
选择第四段区间，之后的区间会变成 d,d+x,d+2x,3d+2x…。有1/2n 的概率

第一段区间期望值：1/2n的概率是 d+2x，1/2n的概率是 3d+3x，(2n-2)/2n的概率是 d。总期望是 ((2n+2)d+5x)/2n

第二段区间期望值：2/2n的概率是 d+3x，1/2n的概率是 3d+6x，(2n-3)/2n的概率是 d+x。总期望是 ((2n+2)d+2nx+9x)/2n

第三段区间期望值：3/2n的概率是 d+4x，1/2n的概率是 3d+9x，(2n-4)/2n的概率是 d+2x。总期望是 ((2n+2)d+4nx+13x)/2n

以此类推，可以发现期望值也是一个等差数列，首项为（(2n+2)d+5x)/2n ，公差为（2nx+4x)/2n

那么每段的贡献就是 d+(2n-1)x/2，求 n 次即可

int n;
int main() {
    double d, x, ans = 0;
    cin >> n >> d >> x;
    while (n) {
        ans += d + (n - 0.5) * x;
        d = ((2 * n + 2) * d + 5 * x) / 2 / n;
        x = x + 2 * x / n;
        n--;
    }
    cout << setiosflags(ios::fixed) << setprecision(10);
    cout << ans << endl;
}

不条理狂诗曲

题目链接：P7482 不条理狂诗曲 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目大意：给定一个长度为 n 的序列，定义 $f(l,r)$ 表示区间 $[l,r]$ 中选择若干不相邻的数的和的最大值，求 $\sum_{l=1}^{n}\sum_{r=l}^{n} f(l,r)$

解题思路：如果只求一段区间的话，就是 DP 了， $f[i]=max(f[i-1],f[i-2]+a[i])$ 。考虑分而治之，对于区间 $[l,r]$ ，如果子区间在 $[l,mid]$ 或 $[mid+1,r]$ 之间，则递归求解。如果横跨中间节点，需要额外处理

定义 $fl(i)$ 表示区间 $[i,mid]$ 选取 $a_{mid}$ 的最大值， $fr(i)$ 表示区间 $[mid,i]$ 选取 $a_{mid}$ 的最大值， $gl(i)$ 表示区间 $[i,mid]$ 不选取 $a_{mid}$ 的最大值， $gr(i)$ 表示区间 $[mid,i]$ 不选取 $a_{mid}$ 的最大值，那么 $f(l,r)=max(fl_l+gr_r,fr_r+gl_l,gl_l+gr_r)$ ，化简一下就是 $f(l,r)=max(max(fl_l,gl_l)+gr_r,gl_l+fr_r)$ ，假设 $gl_l+fr_r>max(fl_l,gl_l)+gr_r$ ，那么 $fr_r-gr_r>max(fl_l-gl_l,0)$ ，因此对于区间 $[l,mid]$ ，求出 $max(fl_i-gl_l,0)$ 的前缀和 t ，排序，然后根据 t 求出 $max(fl_l,gl_l)$ 的前缀和 sml 以及 $gl_l$ 的前缀和 sgl，然后枚举 $[mid+1,r]$ 的每一个点 i ，二分 t 找到小于 $fr_i-gr_i$ 的个数 k ，那么区间 $[l,mid]$ 的贡献就是 $sgl_k+k*fr_r+(mid-k)*gr_r+sml_mid-sml_k$

时间复杂度为 $O(nlog_n^{2})$

int n, ans; 
int a[N], fl[N], gl[N], fr[N], gr[N], sml[N], sgl[N];
PII t[N];
void work(int l, int r) {
    if (l == r) {
        ans = (ans + a[l]) % mod;
        return;
    }
    int mid = (l + r) / 2;
    work(l, mid);
    work(mid + 1, r);
    rep(i, mid, l) {
        if (i == mid) {
            fl[i] = a[i];
            gl[i] = 0;
        } else if (i == mid - 1) {
            gl[i] = a[i];
            fl[i] = max(fl[i + 1], a[i]);
        } else {
            fl[i] = max(fl[i + 1], fl[i + 2] + a[i]);
            gl[i] = max(gl[i + 1], gl[i + 2] + a[i]);
        }
        t[i] = {max(fl[i] - gl[i], 0ll), i};
    }
    sort(t + l, t + mid + 1);
    sml[l - 1] = sgl[l - 1] = 0;
    lep(i, l, mid) {
        sml[i] = (sml[i - 1] + max(fl[t[i].se], gl[t[i].se])) % mod;
        sgl[i] = (sgl[i - 1] + gl[t[i].se]) % mod;
    }
    lep(i, mid + 1, r) {
        if (i == mid + 1) {
            fr[i] = a[i];
            gr[i] = 0;
        } else if (i == mid + 2) {
            gr[i] = a[i];
            fr[i] = max(fr[i - 1], a[i]);
        } else {
            fr[i] = max(fr[i - 1], fr[i - 2] + a[i]);
            gr[i] = max(gr[i - 1], gr[i - 2] + a[i]);
        }
        int k = lower_bound(t + l, t + mid + 1, (PII){fr[i] - gr[i], 0}) - t;
        ans = (ans + (sml[mid] - sml[k - 1]) % mod +
               (mid - k + 1) * (gr[i] % mod) % mod + (sgl[k - 1] % mod) +
               (k - l) * (fr[i] % mod) % mod) %
              mod;
    }
}
void solve() {
    cin >> n;
    lep(i, 1, n) cin >> a[i];
    work(1, n);
    cout << ans << endl;
}

Algorithm Solution

Algorithm

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

October 2022 Algorithm Solution 上一篇

August 2022 Algorithm Solution 下一篇

September 2022 Algorithm Solution

~K Perm Counting

Sugigma: The Showdown

Pushing Balls

不条理狂诗曲