Codeforces Round 1010 (Div. 2, Unrated)¶

比赛链接: https://codeforces.com/contest/2082

B¶

哎哎，这个看着稍微有点难受啊，因为我瞎搞也对了。

如果想要结果更大，那先用向下取整再用向上取整是更好的。结果更小先用向上取整。。

void ChatGptDeepSeek()
{
    int x, n, m;
    cin >> x >> n >> m;
    n = min(35, n), m = min(35, m);
    vector<vector<int>> dp1(n + 1, vector<int>(m + 1, 0));
    vector<vector<int>> dp2(n + 1, vector<int>(m + 1, 1e9 + 1));
    dp1[0][0] = x, dp2[0][0] = x;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++) {
            if (i) {
                dp1[i][j] = max(dp1[i][j], dp1[i - 1][j] / 2);
                dp2[i][j] = min(dp2[i][j], dp2[i - 1][j] / 2);
            }
            if (j) {
                dp1[i][j] = max(dp1[i][j], (dp1[i][j - 1] & 1) + dp1[i][j - 1] / 2);
                dp2[i][j] = min(dp2[i][j], (dp2[i][j - 1] & 1) + dp2[i][j - 1] / 2);
            }
            // cerr << dp1[i][j] << '\n';
        }
    // for (int i = 0; i <= n; i++)
    //     for (int j = 0; j <= m; j++)
    //         cerr << dp1[i][j] << " \n"[j == m];
    // cerr << '\n';
    cout << dp2[n][m] << " " << dp1[n][m] << '\n';
}

C¶

只有最高位的下一位可以进位的时候，才会多用一次操作。

using ll = long long;
constexpr int mod = 1e9 + 7;

ll ksm(ll a, ll b)
{
    ll res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
ll inv = ksm(2, mod - 2);
void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    if (n == 1) {
        cout << "0\n";
        return;
    }
    vector<ll> f(n);
    reverse(s.begin(), s.end());
    if (s[0] == '1')
        f[0] = inv;
    for (int i = 1; i < n; i++) {
        if (s[i] == '1')
            f[i] = (1 - f[i - 1]) * inv % mod + f[i - 1];
        else
            f[i] = inv * f[i - 1] % mod;
        f[i] = (f[i] + mod) % mod;
    }
    cout << (n - 1 + f[n - 2]) % mod << '\n';
}

所以其实向下取整操作，只有在前面全为1时，才会使位不变，但是这样会使除最高位全为0，这样永远不会再触发第二次了。

所以想要多一次操作，那必然就是第二位能产生进位的概率。