文档章节

【数位dp】Beautiful Numbers @2018acm上海大都会赛J

o
 osc_1ee7cxmx
发布于 2018/08/06 15:27
字数 630
阅读 5
收藏 0

精选30+云产品,助力企业轻松上云!>>>

[TOC] #Beautiful Numbers ##PROBLEM ###题目描述 NIBGNAUK is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by the sum of its digits. We will not argue with this and just count the quantity of beautiful numbers from 1 to N. ###输入描述: The first line of the input is T(1≤ T ≤ 100), which stands for the number of test cases you need to solve. Each test case contains a line with a positive integer N (1 ≤ N ≤ 1012). ###输出描述: For each test case, print the case number and the quantity of beautiful numbers in [1, N]. ###输入 2 10 18 ###输出 Case 1: 10 Case 2: 12 ##MEANING t组测试用例,每组测试用例给一个整数n,询问从1到n中有多少数能被其各位数之和整除。 ##SOLUTION 对于每个整数n,找到从1到n的每个数的各位数和的最大值k。 从1到k枚举各位数之和。 对于每个各位数之和,相当于在1到n中找有多少数能整除这个和,且各位数之和等于这个和。这样就将问题分解成若干子问题。 接下来就是数位dp套板子。具体可以看代码中的注释。 ##CODE

#define IN_PC() freopen("C:\\Users\\hz\\Desktop\\in.txt","r",stdin)
#define IN_TEST() freopen("","r",stdin)
#define IN_LB() freopen("C:\\Users\\acm2018\\Desktop\\in.txt","r",stdin)
#define OUT_PC() freopen("C:\\Users\\hz\\Desktop\\out.txt","w",stdout)
#define OUT_LB() freopen("C:\\Users\\acm2018\\Desktop\\out.txt","w",stdout)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;

ll dp[15][100][100];
bool q[15][100][100];
int b[15], tot;
//pos:枚举到哪一位 sum:最高位到当前位的和 remain:当前枚举的数除以各位数和的余数
ll dfs(int pos, int sum, int remain, int meiju, bool limit) {
    if(pos == 0) return (remain == 0) ? 1ll : 0;
    if(limit && q[pos][sum][remain]) return dp[pos][sum][remain];//记忆化搜索
    ll res = 0;
    int up = limit?9:b[pos];
    for(int i = 0; i <= up; i++) {
        if(i + sum <= meiju && i + sum + 9 * (pos - 1) >= meiju)
            res += dfs(pos-1, sum+i, (remain*10+i) % meiju, meiju, limit || (i!=b[pos]));
    }
    if(limit) {
        q[pos][sum][remain] = true;
        dp[pos][sum][remain] = res;
    }
    return res;
}

ll solve(ll num) {
    int sum = 0;
    tot = 0;
    while(num) {
        sum += num % 10;
        b[++tot] = num % 10;
        num /= 10;
    }
    int ret;
    if(tot == 1)ret = b[tot];
    else ret = b[tot] - 1 + (tot - 1) * 9;
    sum = max(sum, ret);//找到各位数之和的最大值
    ll ans = 0;
    for(int i = 1; i <= sum; i++) {//枚举各位数之和,解决子问题
        memset(dp, 0, sizeof dp);
        memset(q, 0, sizeof q);
        ans += dfs(tot, 0, 0, i, false);
    }
    return ans;
}

int main() {
//    IN_PC();
    int T;
    scanf("%d", &T);
    for(int ca = 1; ca <= T; ca++) {
        ll n;
        scanf("%lld", &n);
        printf("Case %d: ", ca);
        printf("%lld\n", solve(n));
    }
    return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

如何将div放置在其容器的底部? - How can I position my div at the bottom of its container?

问题: Given the following HTML: 鉴于以下HTML: <div id="container"> <!-- Other elements here --> <div id="copyright"> Copyright Foo web designs </div> </div> I would like #cop......

富含淀粉
23分钟前
10
0
unity列表控件Horizontal/Vertical/Grid Layout Group用法介绍

1. Grid Layout Group 为Panel控件添加Grid Layout Group,子控件为四个按钮,分别为Grid,Calendar,Gear,User: 默认属性为 为方便演示,按钮的底色为控件自带image,按钮上面的图标为其子...

路过暴风
48分钟前
19
0
Distinct()与lambda? - Distinct() with lambda?

问题: Right, so I have an enumerable and wish to get distinct values from it. 是的,所以我有一个可枚举的,并希望从中获得不同的值。 Using System.Linq , there's of course an ext......

法国红酒甜
53分钟前
8
0
学习编写编译器[关闭] - Learning to write a compiler [closed]

问题: Preferred languages : C/C++, Java, and Ruby. 首选语言 :C / C ++,Java和Ruby。 I am looking for some helpful books/tutorials on how to write your own compiler simply for......

技术盛宴
今天
17
0
OSChina 周一乱弹 —— 毛巾又怎么样?!我在乎的是大姐姐温柔的怀抱!

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @薛定谔的兄弟 :分享洛神有语创建的歌单「我喜欢的音乐」: 《雨 因你而下,于你而止》- Seto 手机党少年们想听歌,请使劲儿戳(这里) @Dan...

小小编辑
今天
43
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部