Codeforces Round 861 (Div. 2)

比较难的一场比赛。

C. Unlucky Numbers

题意

定义一个整数的幸运值为其数位中的最大值减去最小值。求区间 $[l,r]$ 内幸运值最小的数。

题解

比较特殊的数位dp。由于不是求数量，所以不能用前缀和来做。这时，在dp中需要同时设置上界和下界。其它区别就不大了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B=20;
ll e[B];
pair<int,ll> s={-1,-1},f[B][10][10];
void init()
{
    e[0]=1;
    for(int i=1;i<B;i++) e[i]=e[i-1]*10;
    for(int i=0;i<B;i++)
        for(int j=0;j<10;j++)
            for(int k=0;k<10;k++) f[i][j][k]=s;
}
int a[B],b[B];
pair<int,ll> dfs(int pos,bool limit1,bool limit2,bool lead0,int mx,int mn)
{
    if(!pos) return {mx-mn,0};
    auto &now=f[pos][mx][mn];
    if(!limit1&&!limit2&&!lead0&&now!=s) return now;
    int down=limit1?a[pos]:0,up=limit2?b[pos]:9,res=10;
    ll tmp;
    for(int i=down;i<=up;i++)
    {
        bool new0=lead0&&i==0;
        int mmx=new0?0:max(mx,i);
        int mmn=new0?9:min(mn,i);
        auto j=dfs(pos-1,limit1&&i==down,limit2&&i==up,new0,mmx,mmn);
        if(res>j.first)
        {
            res=j.first;
            tmp=i*e[pos-1]+j.second;
        }
    }
    if(!limit1&&!limit2&&!lead0) now={res,tmp};
    return {res,tmp};
}
ll solve()
{
    ll l,r;cin>>l>>r;
    int tmp=0;
    while(r>0)
    {
        b[++tmp]=r%10;
        r/=10;
    }
    int len=tmp;
    for(int i=1;i<=len;i++) a[i]=0;
    tmp=0;
    while(l>0)
    {
        a[++tmp]=l%10;
        l/=10;
    }
    return dfs(len,true,true,true,0,9).second;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int t;cin>>t;
    while(t--) cout<<solve()<<'\n';
    return 0;
}

D. Petya, Petya, Petr, and Palindromes

题意

给定一个长度为 $n$ 的数组 $a$。定义一个数组的回文值为将它修改为回文串的最少修改位置。给定一个奇数 $k$，求其长度为 $k$ 的所有子数组的回文值之和。

题解

对每个位置，考虑能与它在某些回文串中对应的位置，计算贡献。从反面做更加方便，所以我们先计算总的花费，然后对每个位置，计算与它对应的位置有多少相同的数。

总的花费是容易算的。一共有 $n-(k-1)$ 个区间，每个区间至多修改 $\lfloor\dfrac{k}{2}\rfloor$ 次。

然后对于每个下标，求解合法的位置。由于 $k$ 为奇数，所以对称只会出现在奇偶性相同的位置。将下标按照奇偶分类后，对于每个下标 $i$，其对应位置 $t$ 必然满足

• 我们钦定 $t$ 在 $i$ 的左边，则 $1\leq t\leq i-1$
• $t$ 和 $i$ 的距离不能超过 $k$，则 $t\geq i-(k-1)$
• 以二者中点为中心的子段端点不能超出 $[1,n]$ 的范围，即
  • $\dfrac{i+t}{2}-\lfloor\dfrac{k}{2}\rfloor\geq 1$
  • $\dfrac{i+t}{2}+\dfrac{k}{2}\leq n$

综上，得到 $\max(1,i-(k-1),2+2\times\lfloor\dfrac{k}{2}\rfloor-i)\leq t\leq \min(i-1,2n-2\times \lfloor\dfrac{k}{2}\rfloor-i)$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
vector<int> pos[maxn][2];
int cal(int i,int j,int l,int r)
{
    return upper_bound(pos[i][j].begin(),pos[i][j].end(),r)-lower_bound(pos[i][j].begin(),pos[i][j].end(),l);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;cin>>n>>k;
    if(k==1)
    {
        cout<<0<<'\n';
        return 0;
    }
    ll ans=1ll*(n-(k-1))*(k/2);
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        pos[x][i&1].push_back(i);
    }
    for(int i=1;i<=2e5;i++)
        for(int j=0;j<=1;j++)
            for(auto x:pos[i][j])
            {
                int l=max({1,x-(k-1),2+k/2*2-x});
                int r=min(x-1,2*n-k/2*2-x);
                if(l<=r) ans-=cal(i,j,l,r);
            }
    cout<<ans<<'\n';
    return 0;
}