「解题报告」Codeforces Round 667 (Div. 3)

最近 CF 的 Div2.3 有一点点水啊，虽然说蒟蒻还是上不了分……

比赛链接

A. Yet Another Two Integers Problem

签到傻题。

int t, a, b;
t = read(); while(t--){
    a = read(), b = read(); int k = abs(a - b), b = k / 10;
    if(b * 10 == k) printf("%d", b);
    else printf("%d", b + 1); puts("");
}

B. Minimum Product

设 $a$ 变成了 $a-c$，$b$ 变成了 $b-d$，则减少的部分是 $-cb-ad+cd$，代入 $c+d=n$ 可以推出这是一个关于 $c$ 的二次函数，且开口向下，那么容易知道 $c$ 只有两种取值 $\max(0,y-b+n)$ 或 $a-x$，代入检验即可。

代码：

#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;
int t, a, b, x, y, n;
t = read(); while(t--){
    a = read(), b = read(), x = read(), y = read(), n = read();
    int ans = INF, c, d;
    if(a + b - x - y <= n) ans = x * y;
    else{
        c = min(n, a - x), d = min(b - y, n - c);
        ans = min(ans, (a - c) * (b - d));
        c = min(n, max(0ll, y - b + n)), d = min(b - y, n - c);
        ans = min(ans, (a - c) * (b - d));
    }
    printf("%I64d", ans);
    puts("");
}}

C. Yet Another Array Restoration

傻题，模拟即可。

const int CN = 202;
int t, n, x, y, d, a[CN], ans[CN];
int mx(int a[]){
    int mx = 0;
    for(int i = 1; i <= n; i++) mx = max(mx, a[i]);
    return mx;
}
t = read(); while(t--){
    n = read(), x = read(), y = read(); int mn = INT_MAX;
    for(d = 1; d <= y; d++){
        if((y - x) % d) continue;
        int l = (y - x) / d + 1, u = x; if(l > n) continue;
        for(int i = 1; i <= l; i++) a[i] = u, u += d;
        if(l < n){
            int sum = n - l; u = x - d;
            while(u > 0 && sum) sum--, a[++l] = u, u -= d;
            u = y + d;
            while(sum) sum--, a[++l] = u, u += d;
        }
        int cur = mx(a); if(cur < y) continue;
        if(cur < mn) mn = cur, memcpy(ans, a, sizeof(a));
    }
    for(int i = 1; i <= n; i++) printf("%d ", ans[i]); puts("");
}

D. Decrease the Sum of Digits

容易发现代价是固定的，那么模拟即可。

#define int long long
int t, n, s, bit[101], p10[101], cur;
p10[0] = 1; for(int i = 1; i <= 70; i++) p10[i] = p10[i - 1] * 10;
t = read(); while(t--){
    cur = 0, n = read(), s = read();
    int lg = 0;
    while(n) bit[++lg] = n % 10, n /= 10, cur += bit[lg];
    int ans = 0;
    for(int i = 1; i <= lg && cur > s; i++){
        if(!bit[i]) continue;
        ans += (10 - bit[i]) * p10[i - 1];
        bit[i + 1]++, cur -= bit[i] - 1;
    }
    printf("%I64d", ans), puts("");
}

E. Two Platforms

离散化坐标，考虑对于每个坐标 $i$ ，求出 $[1,i]$ 和 $(i,n]$ 的答案，加起来更新答案即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

#define int long long
const int CN = 6e5 + 5;

int t, n, d, X[CN], val[CN], pre[CN], suf[CN], sum[CN];
int id(int x) {return lower_bound(val + 1, val + val[0] + 1, x) - val;}

signed main()
{
    freopen("_in.in", "r", stdin);
    t = read(); while(t--){
    
    n = read(), d = read(), val[0] = 0;
    for(int i = 1; i <= n; i++) X[i] = read(), val[ ++val[0] ] = X[i], val[ ++val[0] ] = X[i] + d, val[ ++val[0] ] = X[i] - d;
    for(int i = 1; i <= n; i++) read();

    sort(val + 1, val + val[0] + 1); int cnt = 1;
    for(int i = 2; i <= val[0]; i++) if(val[i] ^ val[i - 1]) val[++cnt] = val[i];
    val[0] = cnt;

    for(int i = 0; i <= val[0] + 100; i++) pre[i] = suf[i] = sum[i] = 0;
    for(int i = 1; i <= n; i++) sum[ id(X[i]) ]++;
    for(int i = 1; i <= val[0]; i++) sum[i] += sum[i - 1];

    for(int i = 1; i <= n; i++){
        int p = id(X[i]), l = id(X[i] - d), r = id(X[i] + d);
        pre[p] = sum[p] - sum[l - 1], suf[p] = sum[r] - sum[p - 1];
    }

    for(int i = 1; i <= val[0]; i++) pre[i] = max(pre[i], pre[i - 1]);
    for(int i = val[0]; i; i--) suf[i] = max(suf[i], suf[i + 1]);

    int ans = 0;
    for(int i = 1; i <= val[0]; i++) ans = max(ans, pre[i] + suf[i + 1]);

    printf("%lld", ans), puts("");
}}

F. Subsequences of Length Two

显然要 DP，设 $f[i,j,k]$ 表示考虑 $s[1:i]$ 中，$t[1]$ 出现了 $j$ 次，当前改动了 $k$ 次的方案数，就可以转移了。

具体来讲，考虑 $i\to i+1$，我们有两种选择：

1. 什么都不做，转移到 $f[i+1,c+0/1,k]$；
2. 把这一位改成 $t_1$，转移到 $f[i+1,c+1,k+1]$
3. 把这一位改成 $t_2$，转移到 $f[i+1,c,k+1]+c$

最后特殊考虑一下 $t[1]=t[2]$ 的情况即可，时间复杂度 $O(n^3)$。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

#define int long long
const int CN = 210;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

int n, d, f[CN][CN][CN], ans; char s[CN], c1, c2;

void DP1(){
    memset(f, -0x3f, sizeof(f)), f[0][0][0] = 0; int c = 0; 
    for(int i = 1; i <= n; i++){
        f[i][c + (s[i] == c1)][0] = f[i - 1][c][0];
        c += (s[i] == c1); if(s[i] == c2) f[i][c][0] += c;
    }
    for(int k = 0; k <= d; k++)
      for(int c = 0; c <= n; c++)
        for(int i = 0; i <= n; i++){
          if(s[i + 1] == c2) f[i + 1][c][k] = max(f[i + 1][c][k], f[i][c][k] + c);
          else if(s[i + 1] == c1) f[i + 1][c + 1][k] = max(f[i + 1][c + 1][k], f[i][c][k]);
          else f[i + 1][c][k] = max(f[i + 1][c][k], f[i][c][k]);
          if(s[i + 1] != c1) f[i + 1][c + 1][k + 1] = max(f[i + 1][c + 1][k + 1], f[i][c][k]);
          if(s[i + 1] != c2) f[i + 1][c][k + 1] = max(f[i + 1][c][k + 1], f[i][c][k] + c);
        }
}
void DP2(){
    memset(f, -0x3f, sizeof(f)), f[0][0][0] = 0; int c = 0; 
    for(int i = 1; i <= n; i++){
        f[i][c + (s[i] == c1)][0] = f[i - 1][c][0];
        if(s[i] == c1) c++, f[i][c][0] += c - 1;
    }
    for(int k = 0; k <= d; k++)
      for(int c = 0; c <= n; c++)
        for(int i = 0; i <= n; i++){
          if(s[i + 1] == c1) f[i + 1][c + 1][k] = max(f[i + 1][c + 1][k], f[i][c][k] + c);
          else f[i + 1][c][k] = max(f[i + 1][c][k], f[i][c][k]);
          if(s[i + 1] != c1) f[i + 1][c + 1][k + 1] = max(f[i + 1][c + 1][k + 1], f[i][c][k] + c);
        }
}

signed main(){
    freopen("_in.in", "r", stdin);

    n = read(), d = read(), cin >> (s + 1) >> c1 >> c2;
    
    if(c1 != c2) DP1(); else DP2();
    for(int x = 0; x <= n; x++) 
        for(int k = 0; k <= d; k++)
            ans = max(ans, f[n][x][k]);
    
    printf("%lld", ans);
}