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思维大提升 文章被收录于专栏

争取每天写两题

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 18:27
天津大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
4 收藏 评论
分享

全站热榜

正在热议