求调!!!
查看原帖
求调!!!
757647
zhangzhixing99楼主2025/7/2 14:55
#include <bits/stdc++.h>
using namespace std;

#define EOL '\n'

#define __LOG true
#ifdef __LOG
#define PRINTF printf
#else
#define PRINTF //
#endif

#define __IOFILE true
#ifdef __IOFILE
#define FREOPEN freopen
#else
#define FREOPEN //
#endif

const int offset = 1377;

int num[20];
bool vis[20][2 * offset + 1][2];
long long f[20][2 * offset + 1][2];

long long dfs(int now, int cnt, int piv, int sum, bool lim)
{
	if (now > cnt)
	{
		return (long long)(!sum);
	}
	if (vis[now][sum + offset][lim])
	{
		return f[now][sum + offset][lim];
	}
	vis[now][sum + offset][lim] = true;
	for (int digit = (now == 1); digit < 10 && (!lim || digit <= num[now]); ++digit)
	{
		f[now][sum + offset][lim] += dfs(now + 1, cnt, piv, sum + (piv - now) * digit, lim && digit == num[now]);
	}
	return f[now][sum + offset][lim];
}

long long calc(long long x)
{
	if (x < 10)
	{
		return x;
	}
	int cnt = 0;
	while (x)
	{
		num[++cnt] = x % 10;
		x /= 10;
	}
	reverse(num + 1, num + cnt + 1);
	int ret = 9;
	for (int i = 2; i < cnt; ++i)
	{
		for (int j = 1; j < i; ++j)
		{
			memset(vis, false, sizeof vis);
			memset(f, 0, sizeof f);
			ret += dfs(1, i, j, 0, false);
		}
	}
	for (int j = 1; j < cnt; ++j)
	{
		memset(vis, false, sizeof vis);
		memset(f, 0, sizeof f);
		ret += dfs(1, cnt, j, 0, true);
	}
	return ret;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	long long l, r;
	cin >> l >> r;
	cout << calc(r) - (l == 1? 0 : calc(l - 1)) << EOL;
	return 0;
}

大致的思路就是枚举长度 cntcnt 和支点 pivpiv,然后记搜
第一个调对的悬 11

2025/7/2 14:55
加载中...