题解：AT_arc075_d [ARC075F] Mirrored

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

首先发现对于合法数字

n

，只关心其

i

和

n-i+1

位置上数字的差值。暴力枚举每个差值最多只能算到

n<=1e14

的合法数字。考虑可行性剪枝，注意到如果当前的差值之和

s

加上后面全部选择 9 或 -9 都不行，那么当前答案一定非法。

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

code

CPP

//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
*/

题解：AT_arc075_d [ARC075F] Mirrored

文章操作

code

相关推荐

评论

题解：AT_arc075_d [ARC075F] Mirrored