SPOJ KPSUM - The Sum题解
2021/10/2 6:11:46
本文主要是介绍SPOJ KPSUM - The Sum题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
Luogu
Hydro OJ
SPOJ
题目描述
给定一个正整数\(n(n \le 10^{15})\),将1到n之间的所有数按照十进制排成一排,并在相邻两个数字之间加上交错的正负号(1的前面为正号),求该表达式的值
分析
考虑对每个数进行分析,我们不难发现以下性质
-
对于每个数,考虑一个值为这个数的第一个数字前面是正号时这个数对答案的贡献(注意上述语句中数和数字的差别),我们不难发现,这个值不超过63(90909090909090)不小于-62(19090909090909)
-
对于每个数,考虑这个数的第一个数字前面的符号,不难发现,当这个数有偶数位时,它第一个数字前面必为负号,当这个数有奇数位时,它若为奇数,则其第一个数字前面为正号,反之为负号
性质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)
这篇关于SPOJ KPSUM - The Sum题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24内网穿透资料入门教程
- 2024-12-24微服务资料入门指南
- 2024-12-24微信支付系统资料入门教程
- 2024-12-24微信支付资料详解:新手入门指南
- 2024-12-24Hbase资料:新手入门教程
- 2024-12-24Java部署资料
- 2024-12-24Java订单系统资料:新手入门教程
- 2024-12-24Java分布式资料入门教程
- 2024-12-24Java监控系统资料详解与入门教程
- 2024-12-24Java就业项目资料:新手入门必备教程