Codeforces Round #714 (Div. 2) Divide by Zero 2021 个人补题记录

补题链接：Here

A. Array and Peaks

题意：给定 数组大小 和 峰值点 请问是否存在这样的排序，不存在则输出-1

先序从 i = 2 开始填，依次 i += 2 ，如果这样还有不够即 则肯定不存在这种排序。

接下来就是填空位了

AC 代码：

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    int nn = n;
    for (int i = 2; i <= n; i += 2) {
        if (k == 0) break;
        a[i] = nn--, k--;
    }
    if (k) {
        cout << -1 << "\n";
        return;
    }
    int cur = 1;
    for (int i = 1; i <= n; ++i)
        if (!a[i]) a[i] = cur++;
    for (int i = 1; i <= n; ++i) cout << a[i] << " ";
    cout << "\n";
}

B. AND Sequences

这道题，仍是看了题解都没怎么理解是这样子做的

using ll     = long long;
const ll mod = 1e9 + 7;
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    int h = 0;
    for (int i = 0; i < 30; ++i) {
        h |= 1 << i;
        for (int x : a)
            if (not((x >> i) & 1)) h &= ~(1 << i);
    }
    int c  = count(a.begin(), a.end(), h);
    ll ans = (ll)c * (c - 1) % mod;
    for (int i = 1; i <= n - 2; ++i) ans = ans * i % mod;
    cout << ans << '\n';
}

C. Add One

题意很容易懂：现给一个大数 和 次操作机会，每次操作都要使 的每个位数 + 1，满十进一。如：

思路：

由于 的范围在 就别想着暴力了，尝试 DP + 预处理

预处理部分： $DP_{(i,j)}\ $ 代表第 i 次操作时位数值时 j 的变化值

%20%3D%20j%20%3C%209%5C%20%3F%5C%20dp(i%20-%201%2Cj%20%2B%201)%20%3A%20(dp(i-1%2C0)%20%2B%20dp(i%20-%201%2C1)%5C%20%5C%25%5C%20mod)%0A#card=math&code=init%3Adp%5B0%5D%5Bi%5D%20%3D%201%5C%5C%0Adp%28i%2Cj%29%20%3D%20j%20%3C%209%5C%20%3F%5C%20dp%28i%20-%201%2Cj%20%2B%201%29%20%3A%20%28dp%28i-1%2C0%29%20%2B%20dp%28i%20-%201%2C1%29%5C%20%5C%25%5C%20mod%29%0A)

int M = 2e5 + 10;
vector<vector<int>> dp(M + 1, vector<int>(10));
void init() {
    for (int i = 0; i < 10; ++i) dp[0][i] = 1;
    for (int i = 1; i <= M; ++i)
        for (int j = 0; j < 10; ++j) {
            if (j < 9) dp[i][j] = dp[i - 1][j + 1];
            else
                dp[i][j] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
        }
}

所以根据 DP 数组，可以快速得到输入值 n，m的情况下最后的位数

void solve() {
    string s;
    int m;
    cin >> s >> m;
    ll ans = 0;
    for (char c : s) ans = (ans + dp[m][c - '0']) % mod;
    cout << ans << "\n";
}

赛后看了下官方题解，发现可以把二维DP压缩为一位DP

定义为对数字 进行 次运算以后的字符串长度

• in

• if
  即对数字 进行 次运算后最终数字为

• 对于其他情况：
  长度是 次运算和 次运算的和

这里同样先预处理

最后的答案为 (s%5Bi%5D%20-%20’0’)%20%3C%2010)%3F1%3Adp%7Bm-10%2B(int)(s%5Bi%5D%20-%20’0’)%7D)#card=math&code=ans%20%3D%20%5Csum%7Bi%20%3D%201%7D%5E%7B%7Cs%7C%7D%28%28m%20%2B%20%28int%29%28s%5Bi%5D%20-%20%270%27%29%20%3C%2010%29%3F1%3Adp_%7Bm-10%2B%28int%29%28s%5Bi%5D%20-%20%270%27%29%7D%29)

• 时间复杂度为：#card=math&code=%5Cmathcal%7BO%7D%28m%2Bt%C2%B7%7Cs%7C%29)

#define int long long
const int max_n = 200005, mod = 1000000007;
int dp[max_n];
signed main() {
    for (int i = 0; i < 9; i++) dp[i] = 2;
    dp[9] = 3;
    for (int i = 10; i < max_n; i++) {
        dp[i] = (dp[i - 9] + dp[i - 10]) % mod;
    }
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int ans = 0;
        while (n > 0) {
            int x = n % 10;
            ans += ((m + x < 10) ? 1 : dp[m + x — 10]);
            ans %= mod;
            n /= 10;
        }
        cout << ans << "\n";
    }
    return 0;
}