你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

Banknotes(思维)

2021-10-30 20:35:44

题目链接
在这里插入图片描述
有几种面值的钞票,定义F(i)=x 表示现有的钞票构成X最少需要X张
询问最小的i满足F(i)>k
显然相邻的ai之间没有恰好填充其等值的倍数时,其他钞票无法干涉,又因为求最小,直接顺着扫上去就行了。

 #include<bits/stdc++.h>
#include<stdlib.h>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define IOS ios::sync_with_stdio(false);cin.tie(0)
 using namespace std;
 ll gcd(ll a,ll b){if(a<0)a=-a;if(b<0)b=-b;return b==0?a:gcd(b,a%b);}
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll qp(ll a,ll b,ll mod){ll ans=1;if(b==0){return ans%mod;}while(b){if(b%2==1){b--;ans=ans*a%mod;}a=a*a%mod;b=b/2;}return ans%mod;}//快速幂%
ll qpn(ll a,ll b, ll p){ll ans = 1;a%=p;while(b){if(b&1){ans = (ans*a)%p;--b;}a =(a*a)%p;b >>= 1;}return ans%p;}//逆元   (分子*qp(分母,mod-2,mod))%mod;

//19.27

ll a[20];
signed main(){

    ll t;
    read(t);
    while(t--){
     ll n,k;
     read(n);
     read(k);
     ll num=0;
     ll card=0;
     for(int i=1;i<=n;i++){
        read(a[i]);
        //ll ok=qp(10)
     }
        for(int i=1; i<=n; i++)
        {
            //ll nex=
            if(i==n)
            {
                ll now=qp(10,a[i],mods);
                num=num+now*(k-card+1);
                break;
            }
            else
            {
                ll now=qp(10,a[i+1],mods);
                ll pre=qp(10,a[i],mods);
                ll le=now/pre-1;//本来
                if(card+le<=k)
                {
                    num=num+le*pre;
                    card=card+le;
                    continue;
                }
                else
                {
                    num=num+pre*(k-card+1);
                    break;
                }

            }


        }

        printf("%lld\n",num);
    }

}