BZOJ3598 [Scoi2014]方伯伯的商场之旅

			    <div class="post_brief"><p>
题目名字好长。</p>

当年在考场上只会分块打表的题。

前几天有人讲之后觉得大概可做。而且好像那个方法很优秀。

于是我难得地去写了一回不用记搜且不记上界的数位dp。感觉这个玩意写出来很短，但是思考和调试的复杂度变高了。我觉得是状态定义变得不明确的原因。也许再补一些题就好了。

考虑先让所有都合并到最低位，一个基础数位dp。（然后写丑了好久）

然后考虑如果把一个数字的集合位置从p移动到p+1，设这个数字从低位到高位是a[0]..a[n-1]，那么贡献就是∑a[0..p]-∑a[p+1..n-1]。显然当p从右往左移动的时候它是会先负后正的。如果它负的话就减，否则就不玩了。可以发现它们互相不影响。于是对于每一个p单独计算一遍贡献就行了。

然后还是没有原版跑得快。OTL。

#define PROC "shop"
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long dint;
#ifdef WIN32
#define lld “%I64d”
#else
#define lld “%lld”
#endif
#define _l (long long int)
const int maxn = 53;
const int maxm = 509;
const int mb = 253;
dint l, r;
int n, m, bs, a[maxn];
dint dpBeginning() {
static dint f[maxn], c[maxn], g[maxn], cr[maxn];
c[0] = bs;
f[0] = 0;
for (int i = 1; i < n; ++ i) {
c[i] = c[i - 1] * bs;
f[i] = f[i - 1] * bs;
for (int j = 1; j < bs; ++ j)
f[i] = f[i] + c[i - 1] * i * j;
}
cr[0] = g[0] = 0;
cr[1] = a[0] + 1;
g[1] = a[1] * cr[1];
for (int i = 2; i <= n; ++ i)  {
cr[i] = g[i] = 0;
for (int d = 0; d < a[i - 1]; ++ d) {
cr[i] += c[i - 2];
g[i] += f[i - 2] + c[i - 2] * (d * (i - 1) + a[i] * i);
}
cr[i] += cr[i - 1];
g[i] += cr[i - 1] * a[i] * i + g[i - 1];
}
return g[n];
}
dint dp(dint v) {
static dint c[maxn][maxm];
static dint cr[maxn][maxm];
m = 0;
for (n = 0; v; v /= bs)
a[n ++] = v % bs;
a[n] = 0;
m = n * bs;
dint ans(dpBeginning());
//printf(lld “\n”, ans);
for (int p = 1; p < n; ++ p) {
memset(c, 0, sizeof(c));
for (int i = 0; i < bs; ++ i)
c[0][mb - i] = 1;
for (int i = 1; i < n; ++ i)
for (int j = mb - m; j <= mb + m; ++ j)
if (c[i - 1][j])
for (int d = 0; d < bs; ++ d) {
int t((i < p) ? j - d : j + d);
c[i][t] += c[i - 1][j];
}
memset(cr, 0, sizeof(cr));
cr[0][mb - a[0]] = 1;
for (int i = 1; i <= n; ++ i) {
for (int d = 0; d < a[i - 1]; ++ d)
if (i > 1) {
for (int j = mb - m; j <= mb + m; ++ j)
if (c[i - 2][j]) {
int t((i - 1 < p) ? j - d : j + d);
t = (i < p) ? t - a[i] : t + a[i];
cr[i][t] += c[i - 2][j];
}
}
else  {
int t((i < p) ? mb - d - a[i] : mb - d + a[i]);
++ cr[i][t];
}
for (int j = mb - m; j <= mb + m; ++ j)
if (cr[i - 1][j]) {
int t((i < p) ? j - a[i] : j + a[i]);
cr[i][t] += cr[i - 1][j];
}
}
for (int i = 1; i <= m; ++ i)
ans -= cr[n][i + mb] * i;
}
return ans;
}
int main() {
#ifndef ONLINE_JUDGE
freopen(PROC “.in”, “r”, stdin);
freopen(PROC “.out”, “w”, stdout);
#endif
scanf(lld lld "%d", &amp;l, &amp;r, &amp;bs);
printf(lld "\n", dp(r) - dp(l - 1));

}

Comments