D. Shift and Flip

给定两个 \(01\) 串 \(A\) 和 \(B\)，每次操作可以将 \(A\) 循环左移或右移一位，或选择一个 \(B_i = 1\) 的位置将 \(A_i\) 取反，求使 \(A\) 和 \(B\) 相等至少要进行几次操作。

\(n \leq 2 \times 10^3\)。

显然，无解当且仅当 \(B\) 中不存在 \(1\)，且 \(A\) 中存在 \(1\)。

结合数据范围，容易想到先枚举最终 \(A\) 和 \(B\) 的对齐方式，这时操作 \(3\) 的次数是固定的，也就是 \(A\) 和 \(B\) 不同的位置个数。现在我们要最小化前两个操作的次数和。

对每个 \(i\)，我们求出 \(p_i\) 表示使得 \(b_{i – j} = 1\) 的 \(j\) 的值，\(q_i\) 表示使得 \(b_{i+j} = 1\) 的 \(j\) 的值（下标运算默认在 \(\text{mod} \ n\) 意义下进行）。利用调整法容易说明如下事实：设 \(L\) 为左移长度，\(R\) 为过原点后右移长度，那么最优方案中 \(A\) 的移动一定是分为两段：向左移动 \(L\)，回到原点，向右移 \(R\)（或者相反），然后和 \(B\) 对齐。并且，\(L\) 一定恰等于某个 \(p_i\)，\(R\) 一定恰等于某个 \(q_i\)。

考虑每次枚举对齐方式后如何求出 \(L,R\)：我们将所有没有匹配上的位置找出来，那么 \(L,R\) 合法当且仅当对于每一个失配点 \(i\) 都有 \(L \geq p_i\) 或 \(R \geq q_i\)。将二元组 \((p_i,q_i)\) 以 \(q_i\) 为关键字从小到大排序，设 \(f_i\) 为 \(p_i\) 的后缀最大值，那么所有可能最优的合法解即为 \(L_i =f_{i+1},R_i = q_i\)，枚举即可。

由于 \(\forall i,q_i < n\)，使用基数排序，时间复杂度 \(O(n^2)\)。

code 
/*
挥拂去蒙尘半生的晦暗
用这嶙峋双臂迎接 振翅吧 我的蝴蝶
最后一支 赤诚赞歌盘旋
潮起潮落翻覆昼夜 澎湃在生命刻度之前
此刻色彩挣脱谎言 献予你 赤红纸花遍野
*/
#include <bits/stdc++.h>
#define mem(x, v) memset(x, v, sizeof(x))
using namespace std;
const int N = 2e3 + 5, inf = 0x3f3f3f3f;

int n, m, ans, L[N], R[N], buk[N], vr[N], suf[N], tmp[N];
char s[N]; bool a[N], b[N], sa, sb;

int main() {
    scanf("%s", s), n = strlen(s);
    for (int i = 0; i < n; i++) a[i] = s[i] - '0';
    scanf("%s", s);
    for (int i = 0; i < n; i++) b[i] = s[i] - '0';
    mem(L, inf), mem(R, inf);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) if (b[j])
            L[i] = min(L[i], (i - j + n) % n), R[i] = min(R[i], (j - i + n) % n);
    for (int i = 0; i < n; i++) sa |= a[i], sb |= b[i];
    if (!sb) return puts(sa ? "-1" : "0"), 0;
    ans = inf;
    for (int i = 0; i < n; i++) {
        m = 0;
        for (int j = 0, k = i; j < n; j++, k++, k %= n) if (a[k] != b[j]) vr[++m] = k;
        for (int i = 0; i <= n; i++) buk[i] = 0;
        for (int i = 1; i <= m; i++) buk[R[vr[i]]]++;
        for (int i = 1; i <= n; i++) buk[i] += buk[i - 1];
        for (int i = m; i >= 1; i--) tmp[buk[R[vr[i]]]--] = vr[i];
        for (int i = 1; i <= m; i++) vr[i] = tmp[i];
        suf[m + 1] = 0;
        for (int j = m; j >= 1; j--) suf[j] = max(suf[j + 1], L[vr[j]]);
        ans = min(ans, max(i, suf[1]) * 2 - i + m);
        ans = min(ans, (suf[1] + (n - i) % n) * 2 - (n - i) % n + m);
        for (int j = 1; j <= m; j++) {
            ans = min(ans, (R[vr[j]] + max(i, suf[j + 1])) * 2 - i + m);
            ans = min(ans, (suf[j + 1] + max((n - i) % n, R[vr[j]])) * 2 - (n - i) % n + m);
        }
    }   
    cout << ans << endl;
    return 0;
}

E. Shuffle and Swap

给定两个长度为 \(n\) 的 \(01\) 串 \(A\) 和 \(B\)，两个串均有 \(k\) 个 \(1\)。

令 \(a_{1\sim k}\) 和 \(b_{1\sim k}\) 分别表示 \(A\) 和 \(B\) 中所有 \(1\) 出现的位置。现将 \(a\) 和 \(b\) 等概率随机排列，按 \(1\sim k\) 的顺序交换 \(A_{a_i}\) 和 \(A_{b_i}\)，求有多少种不同的排列方式使得操作结束后 \(A\) 和 \(B\) 相等。答案对 \(998244353\) 取模。

\(n \leq 10^4\)，时限 \(\text{2.0s}\)。

不妨先分析一下操作的结构：

我们将所有点分成三类：\(A_i = 0\) 且 \(B_i = 1\)，\(A_i = 1\) 且 \(B_i = 0\)，以及 \(A_i = B_i = 1\)。

我们的目标是，将所有 \(1\) 类点的 \(0\) 传出去，其中可能经过一些 \(3\) 类点，然后到达一个 \(2\) 类点。换句话说，我们需要将所有 \(1\) 类点和 \(2\) 类点匹配。

为了更精确地刻画这个过程，我们建立这样一张图：如果操作了 \(a_i,b_i\) 就连边 \(b_i \to a_i\)，那么此时 \(1\) 类点出度为 \(1\)，\(2\) 类点入度为 \(1\)，\(3\) 类点入度和出度均为 \(1\)。也就是说，这张图一定由若干链和环组成，其中链的条数是确定的，也就是 \(1\) 类点的数量。

不妨考虑有多少 \(3\) 类点在链上，我们枚举这个值，设 \(1\) 类点有 \(p\) 个，\(3\) 类点有 \(q\) 个，\(f_{i,j}\) 为有 \(i\) 个 \(3\) 类点，组成 \(j\) 条链的排列数，那么答案即为

\[\sum_{k=0}^q \binom{q}{k} \binom{p+q}{k} \cdot (k!)^2 \cdot f_{p,q-k} \]

其组合意义显然，\((k!)^2\) 是因为剩下的 \(3\) 类点可以随便匹配。现在的问题变成了如何求 \(f\)。考虑转移：

  • 在序列末尾新建一条链，这需要选择一个 \(1\) 类点和一个 \(2\) 类点，因此 \(f_{i,j} \gets f_{i-1,j} \cdot i^2\)。

  • 在某条链的末尾插入一个 \(3\) 类点，这需要选择一条链以及一个 \(3\) 类点，因此 \(f_{i,j} \gets f_{i,j – 1} \cdot i \cdot j\)。

综上可得 \(f_{i,j} = f_{i-1,j} \cdot i^2 + f_{i,j-1} \cdot i \cdot j\)，由于我们每次只在末尾插入，因此不会算重。直接算就行了，时间复杂度 \(O(n^2)\)。

code 
/*
挥拂去蒙尘半生的晦暗
用这嶙峋双臂迎接 振翅吧 我的蝴蝶
最后一支 赤诚赞歌盘旋
潮起潮落翻覆昼夜 澎湃在生命刻度之前
此刻色彩挣脱谎言 献予你 赤红纸花遍野
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5, mod = 998244353;

int qpow(int a, int b = mod - 2, int ret = 1) {
    while (b) {
        if (b & 1) ret = 1ll * ret * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return ret;
}

int n, p, q, ans, f[N][N], fac[N], inv[N]; 
char a[N], b[N];

int main() {    
    scanf("%s %s", a + 1, b + 1), n = strlen(a + 1);
    for (int i = 1; i <= n; i++) p += (a[i] == '1' && b[i] == '0'), q += (a[i] == '1' && b[i] == '1');
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[n] = qpow(fac[n]);
    for (int i = n; i >= 1; i--) inv[i - 1] = 1ll * inv[i] * i % mod; 
    for (int i = 0; i <= p; i++) f[i][0] = 1ll * fac[i] * fac[i] % mod;
    for (int i = 1; i <= p; i++)
        for (int j = 1; j <= q; j++)
            f[i][j] = 1ll * (1ll * f[i - 1][j] * i % mod + 1ll * f[i][j - 1] * j % mod) % mod * i % mod;
    for (int i = 0; i <= q; i++)
        ans = (ans + 1ll * fac[q] * fac[p + q] % mod * ifac[q - i] % mod * ifac[p + q - i] % mod * f[p][q - i] % mod) % mod;
    cout << ans << endl;
    return 0;
}

F. Yes or No

有 \(n+m\) 个问题，其中有 \(n\) 个问题的答案是 Yes，\(m\) 个问题的答案是 No。当你回答一个问题之后，会知道这个问题的答案，求最优策略下期望对多少。答案对 \(998244353\) 取模。

\(n,m \leq 10^5\)。

感性理解一下，我们的最优策略是：假设此时已知 Yes 有 \(n\) 个而 No 有 \(m\) 个，若 \(n > m\) 则回答 Yes，若 \(n < m\) 回答 No，否则回答 Yes 或 No 均可。

把这个问题放到数轴上考虑，点 \((n,m)\) 表示当前 Yes 有 \(n\) 个而 No 有 \(m\) 个，那么一道题答案为 Yes 相当于往左走一步，答案为 No 相当于往下走一步。那么我们回答的过程相当于是一条 \((n,m) \to (0,0)\) 的路径。

我们画一条直线 \(y=x\)，如果不考虑直线上的点，那么答案显然是 \(\max(n,m)\)。考虑这条直线对答案的影响：位于 \(y=x\) 上的点表示剩下的问题中，答案为 Yes 和 No 的一样多，这时我们猜对的概率为 \(\frac{1}{2}\)。于是只需要计算每个 \(y=x\) 上的点被经过多少次即可算出直线的额外贡献。

经过点 \((i,i)\) 的方案数为 \(\binom{2i}{i} \times \binom{n+m -2\times i}{n-i}\)，而总路径数为 \(\binom{n+m}{m}\)，所以一个点 \((i,i)\) 的贡献就是 \(\dfrac{1}{2} \times \dfrac{\binom{2i}{i} \times \binom{n+m -2\times i}{n-i}}{\binom{n+m}{m}}\)。据此容易计算总贡献，时间复杂度 \(O(n)\)。

code 
/*
挥拂去蒙尘半生的晦暗
用这嶙峋双臂迎接 振翅吧 我的蝴蝶
最后一支 赤诚赞歌盘旋
潮起潮落翻覆昼夜 澎湃在生命刻度之前
此刻色彩挣脱谎言 献予你 赤红纸花遍野
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, mod = 998244353;

int qpow(int a, int b = mod - 2, int ret = 1) {
    while (b) {
        if (b & 1) ret = 1ll * ret * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return ret;
}

int n, m, fac[N], inv[N];
void add(int &x, int y) { x = (x + y >= mod) ? (x + y - mod) : (x + y); }
int C(int n, int m) { 
    return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod; 
}

int main() {    
    ios :: sync_with_stdio(0);
    cin >> n >> m; int L = 2 * max(n, m);
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= L; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[L] = qpow(fac[L]);
    for (int i = L; i >= 1; i--) inv[i - 1] = 1ll * inv[i] * i % mod;
    int ans = 0;
    for (int i = 1; i <= min(n, m); i++) add(ans, 1ll * C(2 * i, i) * C(n - i + m - i, n - i) % mod);
    ans = 1ll * ans * inv[2] % mod * inv[n + m] % mod * fac[n] % mod * fac[m] % mod;
    add(ans, max(n, m));
    cout << ans << endl;
    return 0;
}

原文地址：http://www.cnblogs.com/came11ia/p/16845910.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性