Codeforces Round 1025(Div. 2)A~E题解

Dashboard - Codeforces Round 1025 (Div. 2) - Codeforces

A

首先，$n-1$ 场比赛不可能出现 $n$ 个胜场，所以必然会有 0；另外，如果中间人次出现 0，那么他两侧数字必须为 1。

void solve() {
    int n;
    cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    if (std::count(a.begin(), a.end(), 1) == n) {
        cout << "YES\n";
        return;
    }
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) {
            if (i > 0 && a[i - 1] == 0 || i + 1 < n && a[i + 1] == 0) {
                cout << "YES\n";
                return;
            }
        }
    }
    cout << "NO\n";
}

B

按照贪心的策略，唯一不确定的就是开始时刻是横切还是纵切，可以选择收益最大的，也可以两种情况均尝试一次。

void solve() {
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    int ans = INF;
    {    
        int n1 = std::min(a, n - a + 1), m1 = m;
        int cnt = 0;
        while (n1 > 1) {
            if (n1 & 1) n1++;
            n1 /= 2;
            cnt++;
        }
        while (m1 > 1) {
            if (m1 & 1) m1++;
            m1 /= 2;
            cnt++;
        }
        ans = std::min(ans, cnt);
    }    
    {   
        int n1 = n, m1 = std::min(b, m - b + 1);
        int cnt = 0;
        while (n1 > 1) {
            if (n1 & 1) n1++;
            n1 /= 2;
            cnt++;
        }
        while (m1 > 1) {
            if (m1 & 1) m1++;
            m1 /= 2;
            cnt++;
        }
        ans = std::min(ans, cnt);
    }
    cout << ans + 1 << "\n";
}

C1

限制在 7 步以内：

取一次digit操作，x 落在区间 1 $\sim$ 72，再取一次digit操作，x 落在区间 1 $\sim$ 15，执行add操作减到 1 为止，此时mul(n)，得到数字 n。

bool add(i64 y) {
    cout << "add " << y << std::endl;
    int t;
    cin >> t;
    return t == 1;
}
bool mul(i64 y) {
    cout << "mul " << y << std::endl;
    int t;
    cin >> t;
    return t == 1;
}
bool div(i64 y) {
    cout << "div " << y << std::endl;
    int t;
    cin >> t;
    return t == 1;
}
void digit() {
    cout << "digit" << std::endl;
    int t;
    cin >> t;
}
void solve() {
    int n;
    cin >> n;
    digit();
    digit();
    add(-8);
    add(-4);
    add(-2);
    add(-1);
    mul(n);
    cout << "!" << std::endl;
    int t;
    cin >> t;
}

C2

限制在4步以内：

十进制下能被9整除的数字其各数位之和能被9整除

先将 x 执行mul(9)，以保证其能被 9 整除，并且范围在 1 $\sim$ 999999999 之间，取digit操作，范围落在 1 $\sim$ 81 上，再取一次digit操作，范围落在 1 $\sim$ 16 上，此段能被 9 整除的数字只有 9，因此此时 x 即为 9，操作 add(n-9)，得到 n。

void solve() {
    int n;
    cin >> n;
    mul(9);
    digit();
    digit();
    add(n - 9);
    cout << "!" << std::endl;
    int t;
    cin >> t;
}

C3

对每个数操作的次数保证最小：
注意到，对每个数字mul(1e9-1)再digit后值都是 81，因此再add(n-81)即可，对于 $n=81$ 的情况只需要前两次操作。

void solve() {
    int n;
    cin >> n;
    mul(1e9 - 1);
    digit();
    if (n != 81) {
        add(n - 81);
    }
    cout << "!" << std::endl;
    int t;
    cin >> t;
}

D

分层图最短路的好题：

从 0 点出发，一些点可以走偶数步到达，一些点可以走奇数步到达，用 $dis[i][j],i\in{0,1,2,…,n-1},j\in{0,1}$ 来表示从 0 点出发，经过偶数0（奇数1）的路径长度，能够到达 $i$ 的最短路。

若存在 $u\rightarrow v$，则状态转移方程：
$$
dp[v][0]=min(dp[v][0],dp[u][1]+1)\
dp[v][1]=min(dp[v][1],dp[u][0]+1)
$$
由于向下一层节点转移的过程中固定+1，因此可使用bfs进行递推。再根据能够走的所有长度，统计出能够走的最大偶数长度和最大奇数长度。

void solve() {
    int n, m, l;
    cin >> n >> m >> l;
    std::vector<int> a(l);
    for (int &x : a) {
        cin >> x;
    }
    std::vector<std::vector<int>> g(n);
    std::vector<std::vector<int>> dis(n, std::vector<int>(2, INF));
    std::vector<std::vector<bool>> vis(n, std::vector<bool>(2));
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    std::queue<PII> q;
    dis[0][0] = 0;
    vis[0][0] = true;
    q.push({0, 0});
    while (!q.empty()) {
        auto [u, p] = q.front();
        q.pop();
        int t = p ^ 1;
        for (int v : g[u]) {
            if (!vis[v][t]) {
                vis[v][t] = true;
                dis[v][t] = dis[u][p] + 1;
                q.push({v, t});
            }
        }
    }
    int cntodd = 0, minodd = INF;
    i64 sumeven = 0, sumodd = 0;
    for (int x : a) {
        if (x & 1) {
            cntodd++;
            sumodd += x;
            minodd = std::min(minodd, x);
        } else {
            sumeven += x;
        }
    }
    if (cntodd & 1) {
        i64 t1 = sumeven + sumodd - minodd, t2 = sumodd + sumeven;
        sumeven = t1;
        sumodd = t2;         
    } else {
        i64 t1 = sumeven + sumodd, t2 = cntodd == 0 ? -1 : sumodd + sumeven - minodd;
        sumeven = t1;
        sumodd = t2;
    }
    for (int i = 0; i < n; i++) {
        bool ok = false;
        for (int j = 0; j < 2; j++) {
            if (dis[i][j] != INF && (j == 0 ? sumeven : sumodd) >= dis[i][j]) {
                ok = true;
                break;
            }
        }
        cout << (ok ? '1' : '0');
    }
    cout << "\n";
    
}

E

发现如果选择 $i$ 位置，不会对 $i+1$ 及其之后的位置产生影响，因此选择从后往前dp求解。

设 $dp[i][j]$ 为对于 $i,i+1,i+2,…,n-1$ 位置，应用了 $j$ 次操作，能得到的操作序列总数。

如果 $i$ 位置初始为 0，则肯定对 $i$ 位置的操作分布在总操作序列的奇数位置上 $1,3,5,…，$，不一定连续，因为 $i$ 位置操作后变为 1，必须等到 $i+1\sim n-1$ 位置操作奇数次之后，才能重新对 $i$ 位置操作，因此两次对 $i$ 的操作在序列中的位置奇偶性相同；$i$ 初始位置为 1 时同理。

设当前总操作次数为 $j+c\le k$，其中对当前位置操作次数为 $c$ 次，对 $i+1\sim n-1$ 的操作次数为 $j$ 次，则总的操作序列长度为 $j+c$。若 $s[i]$ 初始为 0，则有 $\lceil\frac{j+c}{2}\rceil$ 个奇数位置，反之则有 $\lfloor\frac{j+c}{2}\rfloor$ 个偶数位置，可简单表示为 $(j+c+(s[i]==0))/2$，取其中 $c$ 个位置，为 $\binom{(j+c+(s[i]==0))/2}{c}$ 个选择。
$$
dp[i][j+c]\leftarrow dp[i][j+c]+dp[i+1][j]\cdot\binom{(j+c+(s[i]==0))/2}{c}
$$

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    std::vector<std::vector<mint>> dp(n, std::vector<mint>(k + 1));
    dp[n - 1][0] = 1;
    dp[n - 1][1] = s.back() == '0';
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= k; j++) {
            for (int t = 0; t + j <= k; t++) {
                dp[i][t + j] += dp[i + 1][j] * comb.binom((t + j + (s[i] == '0')) / 2, t);
            }
        }
    }
    cout << dp[0][k] << "\n";
}