Valid payments

代码很多注释///

//给你一个数x,然后要你找到两个数a,b使得b=x+a,且a,b位数不一样.要你求这样的a,b个数.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=55;
ll x,n,a[N];
ll span[N];//这一位假如进位可以到哪一位.
ll f[N];//到i的时候进位不进位可以有多少种方案数.
ll cnt[N];//记录每一位的大小.
ll possible[N];//可以进位的方案数
int main()
{
    //a+x=b,且a,b位数不能相同,肯定是a存在进位.考虑每次a进位的情况即可?
    cin>>n>>x;
    for(ll i=1;i<=n;i++)   scanf("%lld",&a[i]);
    ll copy=x;
    for(ll i=n;i>=1;i--)
    {
        cnt[i]=copy/a[i];
        copy%=a[i];
    }//记录每一位的大小
    for(ll i=n;i>=1;i--)
    {
        ll num=0;
        for(ll j=i;j<n;j++)
        {
            if(cnt[j]==(a[j+1]/a[j]-1ll)) num++;
            else                           break;
        }span[i-1]=num;
    }//记录我i这一位进位可以跃进到哪一位?
    //for(int i=1;i<=n;i++)   cout<<span[i]<<' ';puts("");
    f[n]=1;possible[n]=1;
    //for(int i=1;i<=n;i++)   cout<<cnt[i]<<' ';puts("");
    for(ll i=n-1;i>=0;i--)
    {
        if(cnt[i])//假如这一位有数字,说明可以进位.
        {
            f[i]+=possible[i+span[i]+1];
        }f[i]+=f[i+1];
        possible[i]=possible[i+span[i]+1]+f[i+1];
    }cout<<f[0]<<endl;
    return 0;
}
//527581354 0 4 0 0 0 0 0 0
AtCoder思维大提升 文章被收录于专栏

争取每天写两题

全部评论
possible{i}理解i位有个多的1的方案数更好理解(通过a分为进位和不进位.)
点赞 回复 分享
发布于 2020-11-10 00:42

相关推荐

frutiger:逆天,我家就安阳的,这hr咋能说3k的,你送外卖不比这工资高得多?还说大厂来的6k,打发叫花子的呢?这hr是怎么做到说昧良心的话的
找工作时遇到的神仙HR
点赞 评论 收藏
分享
评论
4
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务