AcWing 1084. 数字游戏 II
游戏 数字 II AcWing
2023-09-27 14:28:12 时间
\(AcWing\) \(1084\). 数字游戏 $II $
一、方法1
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 32;
const int M = 100; // n<=100,所有 mod n 的结果最大是99
int mod;
int a[N];
int f[N][M];
int dfs(int pos, int sum, bool limit) {
if (pos == 0) return sum % mod == 0; //各位数字和 %n == 0就是一个答案
if (!limit && ~f[pos][sum]) return f[pos][sum];
int ans = 0, up = limit ? a[pos] : 9;
for (int i = 0; i <= up; i++)
ans += dfs(pos - 1, (sum + i) % mod, limit && i == a[pos]);
if (!limit) f[pos][sum] = ans;
return ans;
}
int calc(int x) {
//疑问:为什么本题不能将memset放在整体上呢?是因为取模造成的吗?
//答:是的,因为n是每次全新输入的,如果有兴趣,可以再加一维,维护n
memset(f, -1, sizeof f);
int al = 0;
while (x) a[++al] = x % 10, x /= 10;
//某人又命名了一种取模数,这种数字必须满足各位数字之和 mod N 为 0。
//前0位数字和为0,st = 0
return dfs(al, 0, true);
}
int main() {
//加快读入
ios::sync_with_stdio(false);
cin.tie(0);
int l, r;
while (cin >> l >> r >> mod)
printf("%d\n", calc(r) - calc(l - 1));
return 0;
}
二、方法2
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 32;
const int M = 100; // n<=100,所有 mod n 的结果最大是99
int mod;
int a[N];
int f[N][M][M];
int dfs(int pos, int sum, bool limit) {
if (pos == 0) return sum % mod == 0; //各位数字和 %n == 0就是一个答案
if (!limit && ~f[pos][sum][mod]) return f[pos][sum][mod];
int ans = 0, up = limit ? a[pos] : 9;
for (int i = 0; i <= up; i++)
ans += dfs(pos - 1, (sum + i) % mod, limit && i == a[pos]);
if (!limit) f[pos][sum][mod] = ans;
return ans;
}
int calc(int x) {
int al = 0;
while (x) a[++al] = x % 10, x /= 10;
//某人又命名了一种取模数,这种数字必须满足各位数字之和 mod N 为 0。
//前0位数字和为0,st = 0
return dfs(al, 0, true);
}
int main() {
//加快读入
ios::sync_with_stdio(false);
cin.tie(0);
//疑问:为什么本题不能将memset放在整体上呢?是因为取模造成的吗?
//答:是的,因为n是每次全新输入的,如果有兴趣,可以再加一维,维护n
memset(f, -1, sizeof f);
int l, r;
while (cin >> l >> r >> mod)
printf("%d\n", calc(r) - calc(l - 1));
return 0;
}
相关文章
- 游戏版号停发和疫情反复的这半年,UWA如何躬身入局?
- 猜数字游戏及自动解猜数字程序
- C语言中 循环语句 while for do while的使用 循环语句的嵌套使用 猜数字游戏的实现
- 《Android游戏开发详解》一1.2 数据类型
- 《游戏大师Chris Crawford谈互动叙事》一6.1 拥抱数学
- 《OpenGL ES 3.x游戏开发(下卷)》一1.8 小结
- 《游戏开发物理学(第2版)》一第1章 基本概念
- 《精通Unreal游戏引擎》一第5步 使用减法BSP继续创建地图
- 《Unity 5.x游戏开发实战》一1.11 小结
- 《HTML5完美游戏开发》——2.4 A到B游戏何以成功
- 华为OD机试 - 数字加减游戏(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 相同数字的积木游戏 1(Python)| 真题+思路+考点+代码+岗位
- 二分法(折半查找)的运用之java实现猜数字游戏
- Unity 之 OnGUI实时显示游戏FPS...
- 使用Swift和SpriteKit写一个忍者游戏
- 猜数字游戏