题目链接

Luogu
Hydro OJ
SPOJ

题目描述

给定一个正整数\(n(n \le 10^{15})\)，将1到n之间的所有数按照十进制排成一排，并在相邻两个数字之间加上交错的正负号（1的前面为正号），求该表达式的值

分析

考虑对每个数进行分析，我们不难发现以下性质

1. 对于每个数，考虑一个值为这个数的第一个数字前面是正号时这个数对答案的贡献（注意上述语句中数和数字的差别），我们不难发现，这个值不超过63（90909090909090）不小于-62（19090909090909）

2. 对于每个数，考虑这个数的第一个数字前面的符号，不难发现，当这个数有偶数位时，它第一个数字前面必为负号，当这个数有奇数位时，它若为奇数，则其第一个数字前面为正号，反之为负号

性质2告诉我们：若两个数位数相同且奇偶性相同，则其第一个数字前面的符号是一样的，那若是性质1中的值还相同，则他们对答案的贡献也是一样的

那就是很显然的数位DP了，我们设\(f_{i,j,k}\)为小于等于n的，性质1中的值为j的，奇偶性为\(k(k \in \left\{0, 1\right\})\)的\(i\)位数有多少个，具体实现方法看个人喜好

代码

我用的是最丑陋的从高位到低位的暴力讨论

在i，j，k的基础上在加一维\(o(o \in \left\{0, 1,2\right\})\)，表示满足前面三个条件并且 小于/等于/大于 n的前i位的数的个数

统计答案乱搞即可

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int D = 20;
const int MX = 210;
const LL mx = 80;

LL n, f[D][MX][3][2], d[D], cnt, ans;

int get(int x) {
    return x + mx;
}
int calc(int x, int y) {
    if (x < y)
        return 0;
    else if (x == y)
        return 1;
    else
        return 2;
}

void solve() {
    ans = cnt = 0;
    memset(f, 0, sizeof(f));

    while (n)
        d[++cnt] = n % 10, n /= 10;

    reverse(d + 1, d + cnt + 1);

    for (int i = 1; i <= 9; i++)
        f[1][get(i)][calc(i, d[1])][i & 1] = 1;

    for (int i = 2; i <= cnt; i++) {
        int x = d[i];

        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k <= (mx << 1); k++) {
                int cur = k + (i & 1 ? -j : j);

                if (cur < 0 || cur > (mx << 1))
                    continue;

                //f[i][k][0 / 1 / 2][j & 1] <- f[i - 1][cur][0 / 1 / 2][0 / 1]
                f[i][k][0][j & 1] += f[i - 1][cur][0][0] + f[i - 1][cur][0][1];
                f[i][k][0][j & 1] += (f[i - 1][cur][1][0] + f[i - 1][cur][1][1]) * (j < x);

                f[i][k][1][j & 1] += (f[i - 1][cur][1][0] + f[i - 1][cur][1][1]) * (j == x);

                f[i][k][2][j & 1] += f[i - 1][cur][2][0] + f[i - 1][cur][2][1];
                f[i][k][2][j & 1] += (f[i - 1][cur][1][0] + f[i - 1][cur][1][1]) * (j > x);
            }
        }
    }

    for (int i = 1; i <= cnt; i++)
        for (LL k = 0; k <= (mx << 1); k++) {
            //cout << i << " " << k << " "; out(i, k);
            if (i & 1) {
                ans += f[i][k][0][1] * (k - mx) + f[i][k][0][0] * (mx - k);
                ans += f[i][k][1][1] * (k - mx) + f[i][k][1][0] * (mx - k);

                if (i < cnt)
                    ans += f[i][k][2][1] * (k - mx) + f[i][k][2][0] * (mx - k);
            } else {
                ans += (f[i][k][0][1] + f[i][k][0][0] + f[i][k][1][1] + f[i][k][1][0]) * (mx - k);

                if (i < cnt)
                    ans += (f[i][k][2][1] + f[i][k][2][0]) * (mx - k);
            }
        }

    return printf("%lld\n", ans), void();
}

int main() {
    scanf("%lld", &n);

    while (n) {
        solve();
        scanf("%lld", &n);
    }

    return 0;
}

吐槽

我的一份代码在洛谷的RemoteJudge上Waiting了六天，最后还是在Hydro OJ上才A掉（Orz Hydro）