- CodeForces 55D Beautiful numbers
- HDU 4352 XHXJ's LIS
- HDU 2089 不要62
- HDU 3555 Bomb
- POJ 3252 Round Numbers
- HDU 3709 Balanced Number
- HDU 3652 B-number
- HDU 4734 F(x)
- ZOJ 3494 BCD Code
- HDU 4507 吉哥系列故事――恨7不成妻
- SPOJ BALNUM Balanced Numbers
CodeForces 55D Beautiful numbers
大意 :
给出n和m,求出n和m之间的美丽数的数量。
美丽数的定义是每个数位上的数都能整除这个数
思路:
首先需要知道的是,一个数能被每个数位整除,那么它能被所有数位的lcm整除
其次,因为1到9的lcm为2520,那么判断一个数能否被某个数位整除,可以先将这个数对2520取模
然后就可以解决这个问题了,\(dp[pos][stat][lcm]\)代表当前为pos位,已经取的数位的lcm为lcm,已经取得数对2520取模为stat
但是lcm没必要开2520,因为现在取到的数,肯定是2520的因数,所以可以将lcm离散化,2520的因数只有不到50个,这样就把一个维度从2520压缩到了50
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int num[100], cnt, prime[2550], pc;
const int mod = 2520;
LL dp[32][2550][50];
LL dfs(int pos, int limit, int lcm, int stat) {
if (pos == -1) {
return stat % lcm == 0;
}
if ((!limit)&&dp[pos][stat][prime[lcm]] != -1)
return dp[pos][stat][prime[lcm]];
int up;
if (limit)
up = num[pos];
else
up = 9;
LL res = 0;
for (int i = 0; i <= up; i++) {
int ne = lcm;
if (i) ne = (lcm * i) / __gcd(lcm, i);
res += dfs(pos - 1, limit && (i == num[pos]), ne, (stat * 10 + i) % 2520);
}
if(!limit)
dp[pos][stat][prime[lcm]] = res;
return res;
}
LL solve(LL n) {
//memset(dp, -1, sizeof dp);
cnt = 0;
while (n) {
num[cnt++] = n % 10;
n /= 10;
}
return dfs(cnt - 1, 1, 1, 0);
}
int main() {
LL n, m;
int t;
memset(dp, -1, sizeof dp);
cin >> t;
for (int i = 1; i <= mod; i++) {
if (mod % i == 0) prime[i] = pc++;
}
while (t--) {
cin >> n >> m;
cout << solve(m) - solve(n - 1) << endl;
}
return 0;
}
HDU 4352 XHXJ's LIS
大意 :
要求找出n和m之间满足:数位中最长上升子序列的长度为k的数 的个数
k<=10
思路:
此题需要记录状态,那么考虑状态压缩,即维护当前lis的状态,由于数位只可能是0到9,所以我们可以利用一个十位的二进制数,表示当前lis中出现了哪些数,然后利用类似\(O(nlog(n))\)求lis的方法去更新这个状态即可,即每次在lis里找比x大的数,然后删掉这个数,用x去替换
注意需要记录前导零,因为如果当前有前导零,且当前的数也是0,那么0就不能加入到lis里面,否则0就可以加入到lis里面
另外由于测试数据很多,但是k只有10中可能性,所以可以在记忆化的时候记录k,否则超时
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int num[32], cnt;
LL dp[32][3000][15];
int k;
int getnum(int n) {
int res = 0;
for (int i = 0; i <= 9; i++) {
if (n & (1 << i)) res++;
}
return res;
}
int update(int stat, int x) {
for (int i = x; i <= 9; i++) {
if (stat & (1 << i)) {
stat -= (1 << i);
stat += (1 << x);
return stat;
}
}
return stat + (1 << x);
}
LL dfs(int pos, int stat, int limit, int pre) {//pre记录前导0
if (pos == -1) {
return getnum(stat)==k;
}
if (!limit && dp[pos][stat][k] != -1) return dp[pos][stat][k];
int up;
if (limit)
up = num[pos];
else
up = 9;
LL res = 0;
for (int i = 0; i <= up; i++) {
if (pre == 1 && i == 0)
res += dfs(pos - 1, 0, limit && i == num[pos], 1);
else
res += dfs(pos - 1, update(stat, i), limit && i == num[pos], 0);
}
if (!limit) dp[pos][stat][k] = res;
return res;
}
LL solve(LL n) {
cnt = 0;
while (n) {
num[cnt++] = n % 10;
n /= 10;
}
return dfs(cnt - 1, 0, 1, 1);
}
int main() {
LL n, m;
int t;
cin >> t;
int cases = 0;
memset(dp, -1, sizeof dp);
while (t--) {
cases++;
cin >> n >> m >> k;
cout << "Case #" << cases << ": ";
cout << solve(m) - solve(n - 1) << endl;
}
return 0;
}
HDU 2089 不要62
大意 :
找出n到m中的吉利数,不吉利的数字为所有含有4或62的号码。
思路:
模板数位DP
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int num[20], cnt, dp[20][2];
int dfs(int pos, int stat, int limit) {
if (pos == -1) return 1;
if (!limit && dp[pos][stat] != -1) return dp[pos][stat];
int up;
if (limit)
up = num[pos];
else
up = 9;
int res = 0;
for (int i = 0; i <= up; i++) {
if (i == 4) continue;
if (stat && i == 2) continue;
res += dfs(pos - 1, i == 6, limit && i == num[pos]);
}
if (!limit) dp[pos][stat] = res;
return res;
}
int solve(int n) {
cnt = 0;
while (n) {
num[cnt++] = n % 10;
n /= 10;
}
return dfs(cnt - 1, 0, 1);
}
int main() {
int n, m;
memset(dp, -1, sizeof dp);
while (scanf("%d%d", &n, &m) && (n + m != 0)) {
printf("%d\n", solve(m) - solve(n - 1));
}
return 0;
}
HDU 3555 Bomb
大意 :
要求求出1到N中 数位里出现过49的数 的数量
思路:
dfs(pos, stat,limit,pre)代表第pos位,是否出现过49(stat),是否达到上界,前一个数是多少
注意dp数组也要相应开3维,分别记录pos,stat,pre
一开始没有开pre这一维,但是情况会被覆盖,导致全0
总结一下就是dfs除了limit以外有多少参数dp就要开多少维来记录状态,否则状态会重叠
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int num[32], cnt;
LL dp[32][2][20];
LL dfs(int pos, int stat, int limit,int pre) {
//cout << stat << endl;
if (pos == -1) return stat;
if (!limit && dp[pos][stat][pre] != -1) return dp[pos][stat][pre];
int up;
if (limit)
up = num[pos];
else
up = 9;
LL res = 0;
for (int i = 0; i <= up; i++) {
//int ne = stat | (pre == 4 && i == 9);
if(pre == 4 && i == 9)
res += dfs(pos - 1, 1, limit && i == num[pos],i);
else
res += dfs(pos - 1, stat, limit && i == num[pos],i);
}
if (!limit) dp[pos][stat][pre] = res;
return res;
}
LL solve(LL n) {
cnt = 0;
while (n) {
num[cnt++] = n % 10;
n /= 10;
}
return dfs(cnt - 1, 0, 1,0);
}
int main() {
int t;
LL n;
memset(dp, -1, sizeof dp);
cin >> t;
while (t--) {
cin >> n;
cout << solve(n) << endl;
}
return 0;
}
POJ 3252 Round Numbers
大意 :
求出n到m之间的Round数,Round数满足:二进制表示中0的个数大于等于1的个数
思路:
\(dfs(pos, num1, num0, limit,pre)\),
num1和num0来记录当前二进制中0和1的个数,pre来记录是否为前导0,只有不是前导0的情况才能把0加入num0中
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int num[70], cnt;
LL dp[70][70][70][2];
LL dfs(int pos, int num1, int num0, int limit,int pre) {
if (pos == -1) return num0 >= num1;
if (!limit && dp[pos][num1][num0][pre] != -1) return dp[pos][num1][num0][pre];
int up;
if (limit)
up = num[pos];
else
up = 1;
LL res = 0;
for (int i = 0; i <= up; i++) {
res += dfs(pos - 1, num1 + (i == 1), num0 + (pre==0&&i == 0),limit && i == num[pos],pre==1&&i==0);
}
if (!limit) dp[pos][num1][num0][pre] = res;
return res;
}
LL solve(LL n) {
cnt = 0;
while (n) {
num[cnt++] = n % 2;
n /= 2;
}
return dfs(cnt - 1, 0, 0, 1,1);
}
int main() {
LL n, m;
memset(dp, -1, sizeof dp);
cin >> n >> m;
cout << solve(m) - solve(n - 1) << endl;
return 0;
}
HDU 3709 Balanced Number
大意 :
求出n和m之间的平衡数的数量,平衡数的定义是能找到一个数位,使得左边数位的值 乘 位置差=右边数位的值 乘 位置差
思路:
对于每平衡数,有且仅有一个平衡点,那么可以枚举平衡的位置,进行dfs,dfs时还是从左到右试填,但是需要记录数位的值乘上位置差的和,最后看这个和是不是0即可,又可以考虑到,当这个和小于0时必然无解,因为越过平衡点后,越靠右这个和肯定是越小的
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int num[20], cnt;
LL dp[20][20][5000];
LL dfs(int pos, int stat, int mid, int limit) {
if (pos == -1) return stat == 0;
if (stat < 0) return 0;
if (!limit && dp[pos][mid][stat] != -1) return dp[pos][mid][stat];
int up;
if (limit)
up = num[pos];
else
up = 9;
LL res = 0;
for (int i = 0; i <= up; i++) {
res += dfs(pos - 1, stat + i * (pos - mid),mid, limit && (i == num[pos]));
}
if (!limit) dp[pos][mid][stat] = res;
return res;
}
LL solve(LL n) {
cnt = 0;
while (n) {
num[cnt++] = n % 10;
n /= 10;
}
LL res = 0;
for (int i = 0; i < cnt; i++) {
res += dfs(cnt - 1, 0, i, 1);
}
return res - (cnt - 1);
}
int main() {
int t;
LL n, m;
memset(dp, -1, sizeof dp);
cin >> t;
while (t--) {
cin >> n >> m;
cout << solve(m) - solve(n - 1) << endl;
}
return 0;
}
HDU 3652 B-number
大意 :
求出0到n之间的B-数,B-数的定义是含有13且能被13整除的数
思路:
和Beautiful numbers那道题有点像,记录当前对13取余的值,以及是否出现过13,以及前一个数是不是1即可
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int num[20], cnt;
LL dp[20][2][2][20];
LL dfs(int pos, int stat, int have, int pre,int limit) {
if (pos == -1) return have && stat %13==0;
if (!limit && dp[pos][have][pre][stat] != -1) return dp[pos][have][pre][stat];
int up;
if (limit)
up = num[pos];
else
up = 9;
LL res = 0;
for (int i = 0; i <= up; i++) {
res += dfs(pos - 1, (stat*10+i)%13,have|(pre==1&&i==3), (i==1),limit && (i == num[pos]));
}
if (!limit) dp[pos][have][pre][stat] = res;
return res;
}
LL solve(LL n) {
cnt = 0;
while (n) {
num[cnt++] = n % 10;
n /= 10;
}
return dfs(cnt-1,0,0,0,1);
}
int main() {
int t;
LL n, m;
memset(dp, -1, sizeof dp);
//cin >> t;
while (scanf("%lld",&n)!=EOF) {
cout << solve(n) << endl;
}
return 0;
}
HDU 4734 F(x)
大意 :
给出两个数n和m,求0到m之间f(x)小于f(n)的数量
f函数的定义;
\(F(x) = A_n * 2^{n-1} + A_{n-1} * 2^{n-2} + ... + A_2 * 2 + A_1 * 1\)
思路:
常规的想法是\(dp[pos][stat]\)来记录前pos位,前缀状态为stat下的数量,状态只有不到5000个,可以保存,但是由于n不同,每次都需要清空dp数组,这样会超时,那么又可以想到加一维记录n,但是这样数组大小开到了1e8,内存会爆。
可以利用做差来优化,\(dp[pos][fa-stat]\)记录还差fa-stat达到fa的状态,这样不管n怎么变都不影响dp数组,但是需要注意的是,这样stat就不能写成\((stat<<1)+i\)来转移,必须要写成\(stat+(i<<pos)\)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int num[32], cnt;
int numa;
map<int, int> mp;
LL dp[10][5000];
int getnum(LL x) {
int res = 0;
int base = 1;
while(x){
int tmp = x % 10;
res += tmp * base;
base *= 2;
x /= 10;
}
return res;
}
//int update(int stat, int x) { return stat << 1 + x; }
LL dfs(int pos, int stat, int limit,int fa) {
if (pos == -1) return stat<=fa;
if (stat > fa) return 0;
if (!limit && dp[pos][fa-stat]!= -1)
return dp[pos][fa-stat];
int up;
if (limit)
up = num[pos];
else
up = 9;
LL res = 0;
for (int i = 0; i <= up; i++) {
res += dfs(pos - 1, stat + (i<<pos), limit && (i == num[pos]), fa);
}
if (!limit) dp[pos][fa-stat] = res;
return res;
}
LL solve(LL n, LL m) {
//memset(dp, -1, sizeof dp);
cnt = 0;
int tmp = getnum(n);
while (m) {
num[cnt++] = m % 10;
m /= 10;
}
return dfs(cnt - 1, 0, 1,tmp);
}
int main() {
int t;
LL n, m;
memset(dp, -1, sizeof dp);
cin >> t;
int cases = 0;
while (t--) {
cases++;
cin >> n >> m;
cout << "Case #" << cases << ": ";
cout << solve(n, m) << endl;
}
return 0;
}
ZOJ 3494 BCD Code
大意 :
求出n到m之间的数以bcd码表示中不含被禁的字符串的数量
思路:
AC自动机+数位dp即可
HDU 4507 吉哥系列故事――恨7不成妻
大意 :
求出n到m内和7无关的数字的平方和。
如果一个整数符合下面3个条件之一,那么我们就说这个整数和7有关——
1、整数中某一位是7;
2、整数的每一位加起来的和是7的整数倍;
3、这个整数是7的整数倍;
思路:
很容易想到\(dp[pos][stat][sum]\)代表前缀为stat%7,数位的和为sum%7
但是要求平方和,上面的dp只能求个数,求不了平方和,所以可以利用类似线段树求平方和的方法,用结构体维护cnt,sum,sqrsum
转移时将\((A+B)^2\)拆开分析即可,具体看代码(注意输出时要+mod再取模):
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int num[32], cnt;
struct node {
LL cnt; //记录个数
LL sum; //记录和
LL sqrsum; //记录平方和
} dp[25][10][10];
LL pw[25];
const LL mod = 1e9 + 7;
void init() {
pw[0] = 1;
for (int i = 1; i <= 20; i++) {
pw[i] = pw[i - 1] * 10 % mod;
}
}
node dfs(int pos, int stat, int limit,
int sum) { // stat记录整体mod7 sum记录数位和mod7
if (pos == -1) {
node tmp;
tmp.cnt = 1;
tmp.sum = 0;
tmp.sqrsum = 0;
if (sum % 7 == 0) tmp.cnt = 0;
if (stat % 7 == 0) tmp.cnt = 0;
return tmp;
}
if (!limit && dp[pos][stat][sum].cnt != -1) return dp[pos][stat][sum];
int up;
if (limit)
up = num[pos];
else
up = 9;
node res;
res.cnt = res.sqrsum = res.sum = 0;
for (int i = 0; i <= up; i++) {
if (i == 7) continue;
node temp;
temp = dfs(pos - 1, (stat * 10 + i) % 7, limit && i == num[pos],
(sum + i) % 7);
res.cnt += temp.cnt;
res.cnt %= mod;
res.sum += (temp.sum + temp.cnt * (pw[pos] * i % mod) % mod) % mod;
res.sum %= mod;
res.sqrsum +=
((temp.sqrsum + 2LL * (pw[pos] * i % mod * temp.sum % mod) % mod) %
mod +
temp.cnt * pw[pos] % mod * pw[pos] % mod * i % mod * i % mod) %
mod;
res.sqrsum %= mod;
}
if (!limit) dp[pos][stat][sum] = res;
return res;
}
node solve(LL n) {
cnt = 0;
while (n) {
num[cnt++] = n % 10;
n /= 10;
}
return dfs(cnt - 1, 0, 1, 0);
}
int main() {
int t;
LL n, m;
init();
memset(dp, -1, sizeof dp);
cin >> t;
while (t--) {
cin >> n >> m;
cout << (solve(m).sqrsum - solve(n - 1).sqrsum + mod) % mod << endl;
}
return 0;
}
SPOJ BALNUM Balanced Numbers
大意 :
求出n到m之间的平衡数,平衡数的定义是数位上每个奇数都出现偶数次,每个偶数都出现奇数次
思路:
因为要同时记录10个数位的状态,可以利用三进制进行状态压缩,0代表没出现过,1代表出现过奇数次,2代表出现过偶数次,这样总状态只有\(3^{10}\)不到6e4个,完全够用
注意一下三进制状态压缩时的judge和update
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int num[25], cnt;
LL dp[25][60000];
bool judge(int stat) {
for (int i = 0; i <= 9; i++) {
if (i % 2 == 1 && stat % 3 == 1) return 0;
if (i % 2 == 0 && stat % 3 == 2) return 0;
stat /= 3;
}
return 1;
}
int update(int stat, int x) {
int temp = stat / (pow(3, x));
stat -= temp * pow(3, x);
if (temp % 3 == 0)
temp++;
else if (temp % 3 == 1)
temp++;
else
temp--;
stat += temp * pow(3, x);
return stat;
}
LL dfs(int pos, int stat, int limit) {
// cout << stat << endl;
if (pos == -1) return judge(stat);
if (!limit && dp[pos][stat] != -1) return dp[pos][stat];
int up;
if (limit)
up = num[pos];
else
up = 9;
LL res = 0;
for (int i = 0; i <= up; i++) {
if (stat == 0 && i == 0)//前导0 因为可以直接从stat的值看出来是否为前导0,所以不需要pre参数
res += dfs(pos - 1, 0, limit&&i==num[pos]);
else
res += dfs(pos - 1, update(stat, i), limit&&i==num[pos]);
}
if (!limit) dp[pos][stat] = res;
return res;
}
LL solve(LL n) {
cnt = 0;
while (n) {
num[cnt++] = n % 10;
n /= 10;
}
return dfs(cnt - 1, 0, 1);
}
int main() {
int t;
LL n, m;
memset(dp, -1, sizeof dp);
cin >> t;
while (t--) {
cin >> n >> m;
cout << solve(m) - solve(n - 1) << endl;
}
return 0;
}