题解：AT_arc075_d [ARC075F] Mirrored

cvd420 · 2025-05-03 16:33:20 · 题解

提供一个只用 DFS 和剪枝一毫秒通过的方法

首先发现对于合法数字 n，只关心其 i 和 n-i+1 位置上数字的差值。暴力枚举每个差值最多只能算到 n<=1e14 的合法数字。考虑可行性剪枝，注意到如果当前的差值之和 s 加上后面全部选择 9 或 -9 都不行，那么当前答案一定非法。

注意一下最高位不能为 0 即可。

code

//created by fqr & cyx in 2025
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define int long long
#define pb emplace_back
int ff,Ch;
template <typename T> inline void rd(T &x) {
    x=0,ff=1,Ch=getchar();
    while((Ch<'0'||Ch>'9') && Ch!='-') Ch=getchar();
    if(Ch=='-')Ch=getchar(),ff=-1;
    while(Ch>='0' && Ch<='9') {
        x=(x<<1)+(x<<3)+Ch-'0';
        Ch=getchar();
    }
    x*=ff;
}
template <typename T,typename ...Args> inline void rd(T &x,Args &...args) {
    rd(x), rd(args...);
}
using namespace std;
int n,D;
int ans;
int pw[20];
int mx[20];
void dfs(int dep,int s,int num) {
    if(dep==n/2+1) {
        if(s==D) {
//          奇数位的中间一位随便填 
//          cout<<n<<' '<<num<<'\n'; 
            if(n&1) ans+=num*10;
            else ans+=num;
        }
        return ;
    }
    if(s+mx[dep]<D || s-mx[dep]>D) return ;
    for(int i=-9; i<=9; i++) {
//     最高位不为0 
        if(dep==1) 
            dfs(dep+1,s+(pw[n-dep]-pw[dep-1])*i,num*min(9-i,10+i));
        else
            dfs(dep+1,s+(pw[n-dep]-pw[dep-1])*i,num*min(10-i,10+i));
    }

}
signed main() {
#ifdef LOCAL
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
#endif
    rd(D);
    pw[0]=1;
    for(int i=1; i<=19; i++)
        pw[i]=pw[i-1]*10;
    for(n=1; n<=18; n++) {
        mx[n+1]=0;
        for(int i=1; i<=n/2; i++)
            for(int j=i; j<=n/2; j++)
                mx[i]+=(pw[n-j]-pw[j-1])*9;
//      cout<<n<<'\n';
//      for(int i=1; i<=n/2; i++)
//          cout<<mx[i]<<' ';
//      cout<<'\n';
        dfs(1,0,1);
    }
    cout<<ans;
    return 0;
}
/*
d=900000000
ans=810000000
*/