Educational Codeforces Round 39 (Rated for Div. 2)

A

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        ans += std::abs(a);
    }

    std::cout << ans << "\n";
}

B

两个数满足比对方两倍大就减去对方的两倍，相差很大时可以考虑直接取模

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    ll a, b;
    std::cin >> a >> b;

    while (a != 0 && b != 0) {
        if (a >= 2 * b) {
            a %= 2 * b;
        } else if (b >= 2 * a) {
            b %= 2 * a;
        } else {
            break;
        }
    }
    std::cout << a << " " << b << "\n";
}

C

小的字符可以转换成大的字符，问是否有一个从$a$到$z$的子串，直接统计当前枚举到的字符即可

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string s;
    std::cin >> s;
    int now = 'a';
    std::string ans;
    for (auto ch : s) {
        if (now <= 'z' && ch <= now) {
            ans.push_back(now);
            now++;
        } else {
            ans.push_back(ch);
        }
    }
    std::cout << (now == 'z' + 1 ? ans : "-1") << "\n";
}

D

$m$个$01$序列，每次能消一个1，最多k次，问每个序列的最左边的1到最右边的1的和的最小值是多少

考虑对每列消x次所获得的最小值，x从1枚举到最大能消的次数，然后会发现这就是一个分组背包问题

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, k;
    std::cin >> n >> m >> k;

    std::vector<std::string> s(n);
    for (auto &i : s) {
        std::cin >> i;
    }

    ll ans = 0;
    std::vector max(n, std::vector<int>(k + 1));
    for (int t = 0; t < n; t++) {
        auto z = s[t];
        std::vector<int> del;
        del.push_back(0);
        int lst = -1;
        for (int i = 0; i < m; i++) {
            if (z[i] == '1') {
                ans++;
                if (lst != -1) {
                    auto len = i - lst;
                    ans += len - 1;
                    del.push_back(len);
                }

                lst = i;
            }
        }
        del.push_back(0);

        const int N = del.size();
        std::vector<int> sum(N + 1);
        for (int i = 0; i < N; i++) {
            sum[i + 1] = sum[i] + del[i];
        }

        auto get = [&](int l, int r) { return sum[r + 1] - sum[l]; };
        for (int i = 0; i < N; i++) {
            for (int j = N - 1; j > i; j--) {
                auto K = i + N - j - 1;
                if (K > k) {
                    break;
                }
                auto S = get(0, i) + get(j, N - 1);
                max[t][K] = std::max(max[t][K], S);
            }
            // select without lst
            if (N - 2 <= k && N - 2 > 0) {
                max[t][N - 2] = std::max(max[t][N - 2], get(0, N - 1));
            }
            // select all
            if (lst != -1 && N - 1 <= k) {
                max[t][N - 1] = std::max(max[t][N - 1], get(0, N - 1) + 1);
            }
        }
    }

    std::vector<int> dp(k + 1);
    for (int i = 0; i < n; i++) {
        for (int j = k; j > 0; j--) {
            for (int K = k; K > 0; K--) {
                if (j - K >= 0) {
                    dp[j] = std::max(dp[j], dp[j - K] + max[i][K]);
                }
            }
        }
    }
    std::cout << ans - dp[k] << "\n";
}

E

类似$数位dp$的思想，从高到低每次能取大的就取大的，限制情况是后缀必须能把前缀$cnt$不为偶数的补掉，这里是长度限制

在有限制的情况下还要使得在后缀前面全填$0$的情况下满足严格小于后面的字串

void solve() {
    std::string s;
    std::cin >> s;

    const int N = s.size();
    std::string ans;
    std::vector<int> cnt(10);
    bool lim = true;
    for (int i = 0; i < N - 1; i++) {
        int st = lim ? s[i] - '0' : 9;
        for (int j = st; j >= 0; j--) {

            auto ch = j + '0';
            cnt[j]++;
            if (ch < s[i]) {
                lim = false;
            }
            if (ch == '0') {
                ans += ch;
                break;
            }

            std::string check;
            for (int k = 0; k < 10; k++) {
                if (cnt[k] & 1) {
                    check += k + '0';
                }
            }

            int len = N - 1 - i - check.size();
            bool ok = false;
            if (len >= 0) {
                ok = !lim;

                if (!ok) {
                    for (int k = 0; k < len; k++) {
                        if (s[i + k + 1] > '0') {
                            ok = true;
                            break;
                        }
                    }
                }

                if (!ok) {
                    for (int k = 0; k < check.size(); k++) {
                        if (s[i + len + k + 1] != check[k]) {
                            ok = s[i + len + k + 1] > check[k];
                            break;
                        }
                    }
                }
            }

            if (ok) {
                ans += ch;
                break;
            }

            cnt[j]--;
        }
    }

    for (int i = 0; i < 10; i++) {
        if (cnt[i] & 1) {
            ans += i + '0';
            break;
        }
    }

    std::string check{"1"};
    while (check.size() < s.size() && check < s) {
        check.append("0");
    }
    check[check.size() - 1] = '2';
    if (check.size() == s.size() && s < check) {
        ans = std::string(s.size() - 2, '9');
    }
    std::cout << ans << "\n";
}

F

dp加线段树的思想？题解说是$kmp自动机$但是没看懂

令$dp[i][j][k]$表示$F(i)$中能匹配$s$中${\{j...k\}}$位的subsequence个数

由于：

$$F(i)=F(i-1)+F(i-2)$$

考率$F(i-1)$和$F(i-2)$合并对$F(i)$的$dp$数组的贡献，可以发现：

$$对dp[i][j][k]贡献=\sum_{l=j}^{k-1}dp[i-1][j][l]*dp[i-2][l+1][k]$$

对于单边的贡献，需要分类讨论:

$$F(i-1)对dp[i][j][k]的贡献=\begin{cases} dp[i-1][j][k]*2^{len_{F(i-2)}}&\text{if }k=n\\ dp[i-1][j][k]&\text{if }k\neq n \end{cases}$$

这里当$k=n$时，$F(i-2)$中的字符可以随便选，总方案数如上

注意到这里组成的是严格的串而不是任选其子序列，于是后面即$F(i-2)$中的字符没有贡献

当$k\neq n$时，如果选$F(i-2)$中的字符，会导致阻断或者重复计算$F(i-2)$和$F(i-2)$合并的贡献，因此只能计算$F(i-2)$本身的贡献

同理，当考虑$F(i-2)$的贡献时，有：

$$F(i-2)对dp[i][j][k]的贡献=\begin{cases} dp[i-1][j][k]*2^{len_{F(i-1)}}&\text{if }k=1\\ dp[i-1][j][k]&\text{if }k\neq 1 \end{cases}$$

哦对了这里我用的$0-base$来做，$j,k$的范围是$\{0...n-1\}$

同时前面预处理字串长度的时候,因为模数是质数且长度作为指数计算，可以通过费马小定理提前降幂处理

constexpr int mod = 1e9 + 7;
using Z = Mint<mod>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, x;
    std::string s;
    std::cin >> n >> x >> s;

    std::vector<int> len(x + 2);
    len[0] = len[1] = 1;
    for (int i = 2; i <= x; i++) {
        len[i] = (len[i - 1] + len[i - 2]) % (mod - 1);
    }

    std::vector f(x + 2, std::vector(n, std::vector<Z>(n)));
    for (int i = 0; i < n; i++) {
        f[0][i][i] += s[i] == '0';
        f[1][i][i] += s[i] == '1';
    }

    for (int c = 2; c <= x; c++) {
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                f[c][i][j] +=
                    f[c - 1][i][j] * (j == n - 1 ? Z(2).pow(len[c - 2]) : 1);

                f[c][i][j] +=
                    f[c - 2][i][j] * (i == 0 ? Z(2).pow(len[c - 1]) : 1);
                for (int k = i; k < j; k++) {
                    f[c][i][j] += f[c - 1][i][k] * f[c - 2][k + 1][j];
                }
            }
        }
    }

    std::cout << f[x][0][n - 1] << "\n";
}

G

第一个问题，首先考虑不删除数的情况：

对于一个数组，选取其中的一个子序列，能通过改变不在序列中的数，使得整个数组严格递增，答案就是剩下的数的个数

问题就在于维护这样一个子序列，然而直觉上该子序列很难维护，但是有一个结论：

该子序列(元素记为$a_i$)，需要满足$\forall i<j, a_i-i<=a_j-j$

可以通过反证法证明，而且恰好对于剩下的数也能夹在中间（传递性保证能夹在左右两个数中间就行）

记$dp[i]$表示以第i个元素结尾时，上面所描述的子序列的最大长度

本来想用一般性的LIS模型来维护，发现很复杂

使用树状数组来更新（只从比该元素小的地方更新）

第二个问题，如果有删除数：

枚举删除位置是一种思路但是不会

选择分类讨论，

$dp[i][0]$是原$dp[i]$

$dp[i][1]$表示在前面删了一个数的$dp[i]$

因为删除之后偏移了一位，相对大小（用$a_i-i$表示）要发生1的改变，更有余地了，加入末尾的大小是$a_i-i+1$

$dp[i][0]$更新照常

$dp[i][1]$从本身的更新照常，考虑从$dp[i][0]$更新：

只能设计当前数选，上一个数不选（之前数不选的情况已经包括在$dp[i-1][1]$里或者等待从这里更新（第二种删不删上一个数都无所谓）），从上上个状态更新

struct Info {
    int x = 0;
    friend Info operator+(const Info &lhs, const Info &rhs) {
        return {std::max(lhs.x, rhs.x)};
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> a(n);
    std::vector<int> all;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        all.push_back(a[i] - i);
        all.push_back(a[i] - i + 1);
    }

    std::sort(all.begin(), all.end());
    all.erase(std::unique(all.begin(), all.end()), all.end());

    auto find = [&](int k) {
        return std::lower_bound(all.begin(), all.end(), k) - all.begin() + 1;
    };

    const int N = all.size();
    std::vector<int> pos1(n), pos2(n);
    for (int i = 0; i < n; i++) {
        pos1[i] = find(a[i] - i);
        pos2[i] = find(a[i] - i + 1);
    }

    std::vector fen(3, Fenwick<Info>(N + 1));
    std::vector dp(n, std::vector<int>(2));
    for (int i = 0; i < n; i++) {
        dp[i][0] = fen[0].sum(pos1[i]).x + 1;
        dp[i][1] = (fen[1].sum(pos1[i]) + fen[2].sum(pos2[i])).x + 1;

        fen[0].add(pos1[i], {dp[i][0]});
        fen[1].add(pos1[i], {dp[i][1]});
        if (i > 0) {
            fen[2].add(pos1[i - 1], {dp[i - 1][0]});
        }
    }

    int max = 0;
    for (int i = 0; i < n; i++) {
        max = std::max({max, dp[i][0], dp[i][1]});
    }
    std::cout << std::max(0, n - 1 - max) << "\n";
}