cf刷题杂记（2）

Educational Codeforces Round 167 (Rated for Div. 2)

D. Smithing Skill (D)

很无语的一题······ 运用类似单调队列思维处理出最优的选择序列，之后发现 \(c_i\leq 10^9\) 没法预处理，二分查找又会被卡成 \(n^2\log n\)，唯独没想到在 \(a_i\) 的 \(10^6\) 范围内预处理（）不好评价。

bool cmp(xxx n, xxx m) {
    if(n.a - n.b != m.a - m.b) {
        return n.a - n.b < m.a - m.b;
    }
    return n.a < m.a;
}
int main() {
    // ...
    sort(x + 1, x + n + 1, cmp);
    x[0] = ans[0] = {INF, INF + 1};
    for(int i = 1; i <= n; i++) {
        if(x[i].a - x[i].b != x[i - 1].a - x[i - 1].b) {
            if(x[i].a < ans[cnt].a) ans[++cnt] = x[i];
        }
    }
    int cur = cnt;
    for(int i = ans[cnt].a; i < N; i++) {
        if(i >= ans[cur - 1].a) cur--;
        if(!cur) break;
        int num = (i - ans[cur].a) / (ans[cur].a - ans[cur].b) + 1;
        int x = i - num * (ans[cur].a - ans[cur].b);
        dp[i] = num * 2 + dp[x];
    }
    ll sum = 0;
    for(int i = 1; i <= m; i++) {
        scanf("%d", &c[i]);
        if(c[i] < ans[1].a) sum += dp[c[i]];
        else {
            int num = (c[i] - ans[1].a) / (ans[1].a - ans[1].b) + 1;
            int x = c[i] - num * (ans[1].a - ans[1].b);
            sum += dp[x] + num * 2;
        }
    }

E. Distance to Different (E)

不同的 \(a\) 序列可能产生相同的 \(b\) 序列，因此只需要考虑可能的合法 \(b\) 序列；\(a\) 中连续 \(x\) 个相同的数会在 \(b\) 中产生一段长度为 \(x\) 的特定序列，题目即等价于将 \(b\) 划分成至少 \(k\) 个不同的序列。对于除2以外的所有 \(x\)，其产生的序列具有特异性，但 \(x = 2\) 时，若该序列位于 \(b\) 的中部，则 \(b = 1\)，与 \(x = 1\) 情况相同，计算时应注意舍去。设 \(dp_{i, j}\) 表示将前 \(i\) 个数划分成 \(j\) 个序列的方案数，特别地，为节省空间，\(j = k\) 时表示划分出至少 \(k\) 个序列的方案数。使用前缀和优化转移，复杂度 \(O(nk)\).

    dp[0][0] = 1;
    sum[0] = 1; // 初始化
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= k; j++) {
            dp[i][min(j + 1, k)] += sum[j];
            if(i > 2 && i < n) {
                dp[i][min(j + 1, k)] += (mo - dp[i - 2][j]);
            }
            dp[i][min(j + 1, k)] %= mo;
        }
        for(int j = 1; j <= k; j++) {
            sum[j] += dp[i][j];
            sum[j] %= mo;
        }
    }